Distributed hash tables (DHTs) have gained much attention from the research community in the last years. Formal analysis and evaluations on simulators and small-scale deployments have shown good scalability and performance. In stark contrast, performance measurements in large-scale DHT overlays on the Internet have yielded disappointing results, with lookup latencies measured in seconds. Others have attempted to improve lookup performance with very limited success, their lowest median lookup latency at over one second and a long tail of high-latency lookups. In this thesis, the goal is to to enable large-scale DHT-based latency-sensitive applications on the Internet. In particular, we improve lookup latency in Mainline DHT, the largest DHT overlay on the open Internet, to identify and address practical issues on an existing system. Our approach is implementing and measuring backward-compatible modifications to facilitate their incremental adoption into Mainline DHT (and possibly other Kademlia-based overlays). Thus, enabling our research to have impact on a real-world system. Our results close the performance gap between small- and large-scale DHT overlays. With a median lookup latency below 200 ms and a 99\superscript{th} percentile of just above 500 ms, our median lookup latency is one order of magnitude lower than the best performing measurement reported in the literature. Moreover, our results do not show a long tail of high-latency lookups, unlike previous reports. We have achieved these results by studying how connectivity artifacts on the underlying network ---probably caused by firewalls and NAT devices on the Internet--- affect the DHT overlay. Our measurements of the connectivity of more than 3 million nodes reveal that connectivity artifacts are widespread and can severely degrade lookup performance. Scalability and locality-awareness have also been explored in this thesis, where different mechanisms have been proposed. Some of the mechanisms are planned to be integrated into Mainline DHT in future work. / QC 20111118
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-46469 |
| Date | January 2011 |
| Creators | Jimenez, Raúl |
| Publisher | KTH, Telekommunikationssystem, TSLab, Stockholm : KTH Royal Institute of Technology |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Licentiate thesis, comprehensive summary, info:eu-repo/semantics/masterThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Trita-ICT-ECS AVH, 1653-6363 ; 11:10 |
Page generated in 0.0018 seconds