Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sub-Second Lookups on a Large-Scale Kademlia-Based Overlay
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Telecommunication Systems Laboratory, TSLab.
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Telecommunication Systems Laboratory, TSLab.
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Telecommunication Systems Laboratory, TSLab.
2011 (English)In: 11th IEEE International Conference on Peer-to-Peer Computing 2011 (P2P’11), IEEE , 2011, 82-91 p.Conference paper, Published paper (Refereed)
Abstract [en]

Previous studies of large-scale (multimillion node) Kademlia-based DHTs have shown poor performance, measured in seconds, in contrast to the far more optimistic results from theoretical analysis, simulations and testbeds. In this paper, we unexpectedly find that in the Mainline BitTorrent DHT (MDHT), probably the largest DHT overlay on the Internet, many lookups already yield results in less than a second, albeit not consistently. With the backwards-compatible modifications we present, we show that not only can we reduce median latencies to between 100 and 200 ms, but also consistently achieve sub-second lookups. These results suggest that it is possible to deploy latency-sensitive applications on top of large-scale DHT overlays on the Internet, contrary to what some might have concluded based on previous results reported in the literature.

Place, publisher, year, edition, pages
IEEE , 2011. 82-91 p.
Series
IEEE International Conference on Peer-to-Peer Computing, ISSN 2161-3567
Keyword [en]
dht, kademlia, performance, large-scale
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-38313DOI: 10.1109/P2P.2011.6038665ISI: 000298838500010Scopus ID: 2-s2.0-80055024024ISBN: 978-1-4577-0149-8 (print)OAI: oai:DiVA.org:kth-38313DiVA: diva2:436670
Conference
11th IEEE International Conference on Peer-to-Peer Computing 2011 (P2P’11)
Funder
EU, FP7, Seventh Framework Programme, No. 216217
Note
QC 20110825Available from: 2011-10-13 Created: 2011-08-24 Last updated: 2013-12-03Bibliographically approved
In thesis
1. Kademlia on the Open Internet: How to Achieve Sub-Second Lookups in a Multimillion-Node DHT Overlay
Open this publication in new window or tab >>Kademlia on the Open Internet: How to Achieve Sub-Second Lookups in a Multimillion-Node DHT Overlay
2011 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2011. x, 31 p.
Series
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 11:10
Keyword
dht, p2p, distributed systems, kademlia
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-46469 (URN)978-91-7501-153-0 (ISBN)
Presentation
2011-12-09, C2, Isafjordsgatan 22, Kista, 10:00 (English)
Opponent
Supervisors
Note
QC 20111118Available from: 2011-11-18 Created: 2011-11-03 Last updated: 2011-11-18Bibliographically approved
2. Distributed Peer Discovery in Large-Scale P2P Streaming Systems: Addressing Practical Problems of P2P Deployments on the Open Internet
Open this publication in new window or tab >>Distributed Peer Discovery in Large-Scale P2P Streaming Systems: Addressing Practical Problems of P2P Deployments on the Open Internet
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Peer-to-peer (P2P) techniques allow users with limited resources to distribute content to a potentially large audience by turning passive clients into peers. Peers can self-organize to distribute content to each other, increasing the scalability of the system and decreasing the publisher’s costs, compared to a publisher distributing the data himself using a content delivery network (CDN) or his own servers.

Peer discovery is the mechanism that peers use to find each other. Peer discovery is a critical component of any P2P-based system, because P2P networks are dynamic by nature. That is, peers constantly join and leave the network and each individual peer is assumed to be unreliable. This thesis addresses practical issues in distributed peer discovery mech- anisms in the context of three different large-scale P2P streaming systems: a (1) BitTorrent-based streaming system, (2) Spotify, and (3) our own mobile P2P streaming system based on the upcoming Peer-to-peer Streaming Protocol (PPSP) Internet standard.

We dramatically improve peer discovery performance in BitTorrent’s Mainline DHT, the largest distributed hash table (DHT) overlay on the open Internet. Our implementation’s median lookup latency is an order of magnitude lower than the best performing measurement reported in the literature and does not exhibit a long tail of high-latency lookups, which is critical for P2P streaming applications.

We have achieved these results by studying how connectivity artifacts on the underlying network —probably caused by network address translation (NAT) gateways— affect the DHT overlay. Our measurements of more than three million nodes reveal that connectivity artifacts are widespread and can severely degrade DHT performance.

This thesis also addresses the practical issues of integrating mobile devices into P2P streaming systems. In particular, we enable P2P on Spotify’s Android app, study how distributed peer discovery affects energy consumption, and implement and evaluate backwards-compatible modifications which dramatically reduce energy consumption on 3G.

Then, we build the first complete system that not only is capable of streaming content to mobile devices but also allows them to publish content directly into the P2P system, even when they are behind a NAT gateway, with minimal impact on their battery and data usage.

While our preferred approach is implementing backwards-compatible modifications, we also propose and analyze backwards-incompatible ones. The former allow us to evaluate them in the existing large-scale systems and allow developers to deploy our modifications into the actual system. The latter free us to propose deeper changes. In particular, we propose (1) a DHT-based peer discovery mechanism that improves scalability and introduces localityawareness, and (2) modifications on Spotify’s gossip-like peer discovery to better accommodate mobile devices

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. x, 43 p.
Series
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 13:19
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-134608 (URN)978-91-7501-917-8 (ISBN)
Public defence
2013-12-11, Aula, Forum, KTH-ICT, Isafjordsgatan 39, Kista, 13:00 (English)
Opponent
Supervisors
Note

QC 20131203

Available from: 2013-12-03 Created: 2013-11-25 Last updated: 2013-12-04Bibliographically approved

Open Access in DiVA

fulltext(369 kB)523 downloads
File information
File name FULLTEXT01.pdfFile size 369 kBChecksum SHA-512
b02f4b4331e10e8b7278c58e69f05076f70929086b8821c2693bc895f339d6e533e99e7cf97563f14304c226ef06d8241b3937f82879adc865434f2b25c6a0d9
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jimenez, RaúlOsmani, FlutraKnutsson, Björn
By organisation
Telecommunication Systems Laboratory, TSLab
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 523 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 144 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf