HybridNN: Supporting Network Location Service on Generalized Delay Metrics

Details HybridNN: Supporting Network Location Service on Generalized Delay Metrics HybridNN: Supporting Network Location Service on Generalized Delay Metrics

2011-08-09

arxiv.org/abs/1108.1928v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

Distributed Nearest Neighbor Search (DNNS) locates service nodes that have shortest interactive delay towards requesting hosts. DNNS 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 work assumes the delay to be symmetric, which does not generalize to applications that are sensitive to one-way delays, such as the multimedia video delivery from the servers to the hosts. We propose a relaxed inframetric model for the network delay space that does not assume the triangle inequality and delay symmetry to hold. We prove that the DNNS requests can be completed efficiently if the delay space exhibits modest inframetric dimensions, which we can observe empirically. Finally, we propose a DNNS method named HybridNN (\textit{Hybrid} \textit{N}earest \textit{N}eighbor search) based on the inframetric model for fast and accurate DNNS. For DNNS requests, HybridNN chooses closest neighbors accurately via the inframetric modelling, and scalably by combining delay predictions with direct probes to a pruned set of neighbors. Simulation results show that HybridNN locates nearly optimally the nearest neighbor. Experiments on PlanetLab show that HybridNN can provide accurate nearest neighbors that are close to optimal with modest query overhead and maintenance traffic.

Affiliated with

Also associated with

No associations

Rating

HybridNN: Supporting Network Location Service on Generalized Delay Metrics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with HybridNN: Supporting Network Location Service on Generalized Delay Metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and HybridNN: Supporting Network Location Service on Generalized Delay Metrics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-70289