Incrementally improving lookup latency in distributed hash table systems
- 10 June 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 31 (1) , 114-125
- https://doi.org/10.1145/885651.781042
Abstract
Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly different from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems.In this paper, we discuss a random sampling technique that incrementally improves lookup latency in DHT systems. Our sampling can be implemented using information gleaned from lookups traversing the overlay network. For this reason, we call our approach lookup-parasitic random sampling (LPRS). LPRS is fast, incurs little network overhead, and requires relatively few modifications to existing DHT systems.For idealized versions of DHT systems like Chord, Tapestry and Pastry, we analytically prove that LPRS can result in lookup latencies proportional to the average unicast latency of the network, provided the underlying physical topology has a power-law latency expansion. We then validate this analysis by implementing LPRS in the Chord simulator. Our simulations reveal that LPRS-Chord exhibits a qualitatively better latency scaling behavior relative to unmodified Chord.Finally, we provide evidence which suggests that the Internet router-level topology resembles power-law latency expansion. This finding implies that LPRS has significant practical applicability as a general latency reduction technique for many DHT systems. This finding is also of independent interest since it might inform the design of latency-sensitive topology models for the Internet.Keywords
This publication has 18 references indexed in Scilit:
- Heuristics for Internet map discoveryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- SOSPublished by Association for Computing Machinery (ACM) ,2002
- SquirrelPublished by Association for Computing Machinery (ACM) ,2002
- Finding nearest neighbors in growth-restricted metricsPublished by Association for Computing Machinery (ACM) ,2002
- Wide-area cooperative storage with CFSPublished by Association for Computing Machinery (ACM) ,2001
- An investigation of geographic mapping techniques for internet hostsPublished by Association for Computing Machinery (ACM) ,2001
- OceanStorePublished by Association for Computing Machinery (ACM) ,2000
- A random graph model for massive graphsPublished by Association for Computing Machinery (ACM) ,2000
- On power-law relationships of the Internet topologyPublished by Association for Computing Machinery (ACM) ,1999
- Web caching and Zipf-like distributions: evidence and implicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999