On de Bruijn Routing in Distributed Hash Tables: There and Back Again

• Presented at: The Fourth IEEE International Conference on Peer-to-Peer Computing, Zurich, Switzerland, August 25-27 2004
• Published in: P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing, Zurich, Switzerland
• Publication date: 2004

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) in stead 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).

Keywords: NCCR-MICS/CL4 ; NCCR-MICS

Reference

• LSIR-CONF-2000-051
• View record in Web of Science

Record created on 2005-09-15, modified on 2017-05-12