HybridNN: An accurate and scalable network location service based on the inframetric model

作     者：Fu, Yongquan Wang, Yijie Biersack, Ernst 

作者机构：Natl Univ Def Technol Coll Comp Sci Natl Key Lab Parallel & Distributed Proc Changsha 410073 Hunan Peoples R China EURECOM Sophia Antipolis France 

出 版 物：《FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE》 (Future Gener Comput Syst)

年 卷 期：2013年第29卷第6期

页      面：1485-1504页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Grand Fundamental Research 973 Program of China [2011CB302601] National High Technology Research and Development 863 Program of China [2013AA010206] National Natural Science Foundation of China Natural Science Foundation for Distinguished Young Scholars of Hunan Province [S2010J5050] Specialized Research Fund for the Doctoral Program of Higher Education European Commission 

主　　题：Distributed nearest server location Peer-to-Peer Inframetric Growth dimension 

摘      要：Locating servers that have shortest interactive delay towards an Internet host provides an important service for large-scale latency sensitive networked applications, such as VoIP, online network games, or interactive network services on the cloud. Existing algorithms assume that the delay space is a metric space, which implies that the delay between two nodes is symmetric and the triangle inequality holds. In practice, the delay space is not metric, which lowers the accuracy of metric-based algorithms. We develop a new scheme whose theoretical foundation is based on the inframetric model, which has weaker assumptions than the metric model. We prove that the location requests can be completed efficiently if the delay space exhibits modest inframetric dimensions, which we can confirm empirically. Finally, we propose HybridNN (Hybrid Nearest Service Node Location) that finds the closest service node accurately thanks to the inframetric model and scalably by combining delay predictions with direct probes to a pruned set of neighbors. Simulation results show that HybridNN locates in nearly all cases the true nearest service nodes. Experiments on PlanetLab show that with modest query overhead and maintenance traffic HybridNN can provide accurate nearest service nodes that are close to optimal. (C) 2012 Elsevier B.V. All rights reserved.