Routing and Data Location in Overlay Peer-to-Peer Networks

Abstract

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.

Documents

• PDF (91 pages, 956 kBytes)
• PowerPoint Slides of the final presentation (410 kBytes)
• IBM Research Report
• A compact excerpt was published in HotNets-I.
• Related documents (CiteSeer/ResearchIndex)
• Part of the P2P project

BibTeX entry

@TechReport{rinaldi02routing-techreport,
  Author =       {Roberto Rinaldi and Marcel Waldvogel},
  Title =        {Routing and Data Location in Overlay Peer-to-Peer Networks},
  Institution =  {IBM},
  Type =         {Research Report},
  Number =       {RZ--3433},
  Year =         2002,
  Month =        jul
}

@MastersThesis{rinaldi02overlay,
  Author =       {Roberto Rinaldi},
  Title =        {Routing and Data Location in Overlay Peer-to-Peer Networks},
  School =       {Institut Eur\'ecom and Universit\`a degli Studi di Milano},
  Year =         2002,
  Type =         {Diploma thesis},
  Month =        jun
}