Graph-theoretic analysis of structured peer-to-peer systems Conference Paper uri icon


  • 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 several other properties that affect routing and resilience of peer-to-peer networks. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture ODRI - Optimal Diameter Routing Infrastructure.

name of conference

  • the 2003 conference

published proceedings

  • Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications - SIGCOMM '03

author list (cited authors)

  • Loguinov, D., Kumar, A., Rai, V., & Ganesh, S.

citation count

  • 143

complete list of authors

  • Loguinov, Dmitri||Kumar, Anuj||Rai, Vivek||Ganesh, Sai

editor list (cited editors)

  • Feldmann, A., Zitterbart, M., Crowcroft, J., & Wetherall, D.

publication date

  • January 2003