Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience Academic Article

abstract

• 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 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 optimal diameter routing infrastructure. 2005 IEEE.

authors

• Loguinov, Dmitri

published proceedings

• IEEE-ACM TRANSACTIONS ON NETWORKING

altmetric score

• 3

author list (cited authors)

• Loguinov, D., Casas, J., & Wang, X. M.

citation count

• 86

complete list of authors

• Loguinov, D||Casas, J||Wang, XM

publication date

• October 2005

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE ACM Transactions on Networking  Journal

keywords

• De Bruijn Graphs
• Diameter-degree Tradeoff
• Peer-to-peer Networks

Digital Object Identifier (DOI)

• 10.1109/TNET.2005.857072

start page

• 1107

end page

• 1120

volume

• 13

issue

• 5

URL

• http://dx.doi.org/10.1109/tnet.2005.857072

user-defined tag

• 9 Industry, Innovation and Infrastructure