Peer-to-peer overlay networks offer a novel platform for a variety of scalable and decentralized distributed applications. Systems known as Distributed Hash Tables provide efficient and fault-tolerant routing, object location and load balancing within a self-organizing overlay network. The alternative solution we propose is an overlay location and routing infrastructure that efficiently uses minimal local information to achieve global routing. The main novelty of our approach consists in fitting the overlay network in a hyper-toroidal space and building it with "locality awareness". Thanks to this specific network construction phase, forwarding decisions always take into account "locality preservation'' in an implicit manner, leading to significant improvements in end-to-end delays and path lengths.
With this overlay network it is possible to obtain global routing by adding minimal information to each single host and by making only local forwarding decisions. Our analysis shows how the average path length coming from the overlay routing is close to the optimal average path length of the underlaying network: on average, they only differ by a factor of 2. Furthermore, "locality preservation"' has a significant impact on the end-to-end latency of the routing process as well.
Such a system can be viewed as novel in the field of peer-to-peer data location and addressing, allowing the development of new applications in a real "low-latency"' environment.
By: Roberto Rinaldi and Marcel Waldvogel
Published in: RZ3433 in 2002
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .