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

In: Torsten Braun and Georg Carle and Burkhard Stiller ed., KiVS 2007: Kommunikation in Verteilten Systemen -- Workshops. VDE-Verlag, P. 231--242, 2007

Authors

• Peter Merz
• Steffen Wolf

Abstract

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.

Full Text

• Publication: Merz2007TreeOpt.pdf

BibTeX

 
@InProceedings{ Merz2007TreeOpt, 
   title = { TreeOpt: Self-Organizing, Evolving P2P Overlay Topologies Based On Spanning Trees }, 
   author = { Peter Merz and Steffen Wolf },  
   editor = { Torsten Braun and Georg Carle and Burkhard Stiller }, 
   booktitle = { KiVS 2007: Kommunikation in Verteilten Systemen -- Workshops },        
   publisher = { VDE-Verlag },   
   pages = { 231--242 },   
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.