Kolloq. Prof. Dr. Biersack, topic: HybridNN -- An accurate and scalable network location service based on the inframetric model

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

Abstract: 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 N earest Service N ode 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. This is joint work with Y. Fu and Y. Wang from National University of Defense Technology, Hunan province, 410073, China Bio: Ernst Biersack studied computer science at the Technische Universität München and at the University of North Carolina at Chapel Hill. He received the Dipl. Infom. (M.S.) and Dr. rer. nat. (Ph.D.) degrees in computer science from the Technische Universität München, and the Habilitation à Diriger des Recherches from the University of Nice, France. From March 1989 to February 1992, he was a Member of Technical Staff with the Computer Communications Research District of Bell Commu- nications Research, Morristown, US. Since March 1992, he has been a Professor in telecommunications at Eurecom, Sophia Antipolis, France. His current research is on peer-to peer systems and network tomography.