NDLI: Incrementally improving lookup latency in distributed hash table systems

Content Provider	ACM Digital Library
Author	Goel, Ashish Govindan, Ramesh Zhang, Hui
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.
Starting Page	114
Ending Page	125
Page Count	12
File Format	PDF
ISSN	01635999
DOI	10.1145/885651.781042
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	31
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dht Latency stretch Random sampling Peer-to-peer
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Incrementally improving lookup latency in distributed hash table systems

Improving lookup latency in distributed hash table systems using random sampling

Improving lookup latency in distributed hash table systems using random sampling

Incrementally Improving Lookup Latency in Distributed Hash Table Systems (2003)

Incrementally Improving Lookup Latency in Distributed Hash Table Systems (2003)

OpenDHT:a public DHT service and its uses

Long term study of peer behavior in the KAD DHT

Low traffic overlay networks with large routing tables

Lookup Performance Deficiencies in the KAD Network

Incrementally improving lookup latency in distributed hash table systems

Similar Documents

Incrementally improving lookup latency in distributed hash table systems

Improving lookup latency in distributed hash table systems using random sampling

Improving lookup latency in distributed hash table systems using random sampling

Incrementally Improving Lookup Latency in Distributed Hash Table Systems (2003)

Incrementally Improving Lookup Latency in Distributed Hash Table Systems (2003)

OpenDHT:a public DHT service and its uses

Long term study of peer behavior in the KAD DHT

Low traffic overlay networks with large routing tables

Lookup Performance Deficiencies in the KAD Network

Incrementally improving lookup latency in distributed hash table systems