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

Konferenz: KiVS 2007 - Kommunikation in Verteilten Systemen - 15. ITG/GI-Fachtagung
26.02.2007 - 02.03.2007 in Bern, Schweiz

Tagungsband: KiVS 2007

Seiten: 12Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

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.