Polar: an efficient finding nearest neighbor algorithm for overlay network

Obviously, network proximity is an essential characteristic for overlay network construction. By selecting the nearest neighbor for the target node, large-scale distributed applications can decrease the communication cost and improve the performance significantly. Nevertheless, existing mechanisms for exploiting network proximity information are either inaccurate or low efficiency. In this paper, we present a novel and practical algorithm to find the nearest neighbor in overlay network, called Polar. Performing direct measurement based on the result of distance prediction using network coordinate, Polar achieves accuracy as while as it has low overhead. Meanwhile, our proposal does not rely on the static landmark so it has strong scalability and high robustness. Polar is a generic architecture that can be used for a variety of overlay network with different requirement.