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
On Routing in Distributed Hash Tables
Ecole Polytech. Fed. de Lausanne (EPFL), Lausanne .
Ecole Polytech. Fed. de Lausanne (EPFL), Lausanne .ORCID iD: 0000-0003-4516-7317
Ecole Polytech. Fed. de Lausanne (EPFL), Lausanne .
Ecole Polytech. Fed. de Lausanne (EPFL), Lausanne .
2007 (English)In: Peer-to-Peer Computing, 2007. P2P 2007. Seventh IEEE International Conference on, 2007, 113-122 p.Conference paper, Published paper (Refereed)
Abstract [en]

There have been many proposals for constructing routing tables for distributed hash tables (DHT). They can be classified into two groups: A) those that assume that the peers are uniformly randomly distributed in the identifier space, and B) those that allow order-preserving hash functions that lead to a skewed peer distribution in the identifier space. Good solutions for group A have been known for many years. However, DHTs in group A are limited to use randomized hashing and therefore, queries over whole identifier ranges thus do not scale. Group B can handle such queries easily. However, it is more difficult to connect the peers such that the resulting topology provides efficient routing, small routing tables, and balanced routing load. We present an elegant new solution to construct an efficient DHT for group B. Our main idea is to decouple the identifier space from the routing topology. In consequence, our DHT allows arbitrarily skewed peer distributions in the identifier space and does not require the overhead of sampling. Furthermore, the table construction is cheap and does not require active replacement of lost routing entries. To evaluate the performance of routing cost and table construction under high churn, we built an efficient simulator. Using the right data structures, we can easily process the state of over one million peers in RAM.

Place, publisher, year, edition, pages
2007. 113-122 p.
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-109816DOI: 10.1109/P2P.2007.38ISI: 000252246000014ISBN: 978-0-7695-2986-8 (print)OAI: oai:DiVA.org:kth-109816DiVA: diva2:584588
Conference
Peer-to-Peer Computing, 2007. P2P 2007. Seventh IEEE International Conference on
Note

QC 20130610

Available from: 2013-01-09 Created: 2013-01-09 Last updated: 2013-06-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Girdzijauskas, Sarunas
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 25 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