This paper examines graph-theoretic properties of existing peer-to-peer architectures and
proposes a new infrastructure based on optimal diameter de Bruijn graphs. Since
generalized de Bruijn graphs possess very short average routing distances and high
resilience to node failure, they are well suited for structured peer-to-peer networks. Using the
example of Chord, CAN, and de Bruijn, we first study routing performance, graph expansion,
and clustering properties of each graph. We then examine bisection width, path overlap, and …

This paper examines graph-theoretic properties of existing peer-to-peer networks and
proposes a new infrastructure based on optimal-diameter de Bruijn graphs. Since
generalized de Bruijn graphs exhibit very short average distances and high resilience to
node failure, they are well suited for distributed hash tables (DHTs). Using the example of
Chord, CAN, and de Bruijn, we study the routing performance, graph expansion, clustering
properties, and bisection width of each graph. Having confirmed that de Bruijn graphs offer …