2nd International ICST Conference on Scalable Information Systems

Research Article

Polar: an efficient finding nearest neighbor algorithm for overlay network

Download65 downloads
  • @INPROCEEDINGS{10.4108/infoscale.2007.953,
        author={Tan  Chen and Xiangzhi Sheng and Baosong Shan},
        title={Polar: an efficient finding nearest neighbor algorithm for overlay network},
        proceedings={2nd International ICST Conference on Scalable Information Systems},
        proceedings_a={INFOSCALE},
        year={2010},
        month={5},
        keywords={overlay network  nearest neighbor  network coordinate},
        doi={10.4108/infoscale.2007.953}
    }
    
  • Tan Chen
    Xiangzhi Sheng
    Baosong Shan
    Year: 2010
    Polar: an efficient finding nearest neighbor algorithm for overlay network
    INFOSCALE
    ICST
    DOI: 10.4108/infoscale.2007.953
Tan Chen1,*, Xiangzhi Sheng1,*, Baosong Shan1,*
  • 1: State Key Laboratory of Software Development Environment, School of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing, China.
*Contact email: chentan@nlsde.buaa.edu.cn, xzsheng@nlsde.buaa.edu.cn, shanbs@nlsde.buaa.edu.cn

Abstract

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.