TreeOpt: Self-Organizing, Evolving P2P Overlay Topologies Based On Spanning Trees

Conference: KiVS 2007 - Kommunikation in Verteilten Systemen - 15. ITG/GI-Fachtagung
02/26/2007 - 03/02/2007 at Bern, Schweiz

Proceedings: KiVS 2007

Pages: 12Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Merz, Peter; Wolf, Steffen (Department of Computer Science, University of Kaiserslautern, Germany)

We present a novel approach for self-organizing peer-to-peer overlays which enables the self-optimization of spanning tree topologies. We consider the minimum routing cost spanning tree problem which is known to be NP-hard and demonstrate that our proposed algorithm approximates a close lower bound even with minimal cooperation among the peers. This is achieved by evolving shortest path trees in which the root is allowed to move. We present results of simulations based on networks derived from Internet ping measurements. Moreover, we show that the algorithm can handle unannounced leaving as well as joining of nodes.