On de Bruijn routing in distributed hash tables: There and back again
2004 (English)In: The 4th IEEE International Conference on Peer-to-Peer Computing, proceedings, 2004, 159-166 p.Conference paper (Refereed)
We show in this paper that de Bruijn networks, despite providing efficient search while using constant routing table size, as well as simplicity of the understanding and implementation of such networks, are unsuitable where key distribution will be uneven, a realistic scenario for most practical applications. In presence of arbitrarily skewed data distribution, it has only recently been shown that some traditional P2P overlay networks with non-constant (typically logarithmic) instead of constant routing table size can meet conflicting objectives of storage load balancing as well as search efficiency. So this paper while showing that de Bruijn networks fail, to meet these dual objectives, opens up a more general problem for the research community as to whether P2P systems with constant routing table can at all achieve the conflicting objectives of retaining search efficiency as well as storage load balancing, while preserving key ordering (which leads to uneven key distribution).
Place, publisher, year, edition, pages
2004. 159-166 p.
IdentifiersURN: urn:nbn:se:kth:diva-109820ISI: 000223904300019OAI: oai:DiVA.org:kth-109820DiVA: diva2:584666
4th International Conference on Peer-to-Peer Computing (P2P2004)
QC 201306102013-01-092013-01-092013-06-10Bibliographically approved