Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience
Authors:
- J. CasasJCJ. Casas
- Xiaoming WangXWXiaoming Wang
- 7 November 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 13 (5) , 1107-1120
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.Keywords
This publication has 39 references indexed in Scilit:
- The impact of DHT routing geometry on resilience and proximity2003
- Novel architectures for P2P applications2003
- On connectivity of consecutive-d digraphsDiscrete Mathematics, 2002
- A scalable content-addressable networkACM SIGCOMM Computer Communication Review, 2001
- Building low-diameter P2P networks2001
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- Bisecting de Bruijn and Kautz graphsDiscrete Applied Mathematics, 1998
- Accessing nearby copies of replicated objects in a distributed environment1997
- A better upper bound on the bisection width of de Bruijn networks1997
- Lightwave networks based on de Bruijn graphsIEEE/ACM Transactions on Networking, 1994