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

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.