Landmark Routing on Structured P2P Overlays

Structured Peer to Peer overlay networks such as Tapestry, Pastry, Chord and CAN provide scalable, wide-area lookup and routing services.  Applications built on these systems, such as decentralized file systems, backup services, network indirection systems, all rely on reliable and fast message routing to a destination node, given some unique identifier.

Due to the theoretical approach taken in these systems, however, they assume that most nodes in the system are uniform in resources such as network bandwidth and storage.  This results in messages being routed on the overlay with minimum consideration to actual network topology and differences between node resources.

In Brocade, we propose a secondary overlay to be layered on top of these systems, that exploits knowledge of underlying network characteristics. The secondary overlay builds a location layer between ``supernodes,'' nodes that are situated near network access points, such gateways to administrative domains. By associating local nodes with their nearby ``supernode,'' messages across the wide-area can take advantage of the highly connected network infrastructure between these supernodes to shortcut across distant network domains, greatly improving point-to-point routing distance and reducing network bandwidth usage.


Brocade: landmark routing on overlay networks
Ben Y. Zhao, Yitao Duan, Ling Huang, Anthony D. Joseph and John D. Kubiatowicz
First International Workshop on Peer-to-Peer Systems (IPTPS)
Cambridge, MA. March 2002.
[Abstract, PDF (91KB), ps.gz (62KB)]


Brocade: landmark routing on overlay networks
Presented at IPTPS 2002, Cambridge, MA. March 2002.
[PDF, PowerPoint Show]


Ben Y. Zhao, February 24, 2003