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: PDFPersö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.