On Routing in a Two-Tier Overlay Network based on de Bruijn Digraphs
Key: DMH+06-1
Author: Vasilios Darlagiannis, Andreas Mauthe, Oliver Heckmann, Nicolas Liebau, Ralf Steinmetz
Date: April 2006
Kind: In proceedings
Book title: Proceedings of 2006 IEEE/IFIP Network Operations and Management Symposium
Abstract: The intrinsic properties of the employed graphs in designing Peer-to-Peer overlay networks are crucial for the performance of the deployed Peer-to-Peer systems. Several structured topologies have been proposed based on meshes, enhanced rings, redundant tree structures, etc. Among them, de Bruijn graphs are promising alternatives since they provide some crucial asymptotically optimal characteristics. <p> In this paper, we discuss the necessary algorithms and protocol messages to develop efficiently the employed routing procedure of Omicron, which is a hybrid overlay network based on de Bruijn graphs enriched with clustering and role specialization mechanisms. Enhancements of the original de Bruijn structure are advised to cope with the intrinsic issue of uneven distribution of the routing workload. The developed system is evaluated and compared with Chord, which is used as the reference point. The superiority of de Bruijn based overlay networks with respect to scalability is quantitatively demonstrated using simulation experiments. Further, the ability of the two systems to exploit the underlying network is investigated. <p/>

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.