An Expresway over Chord in Peer-to-Peer Systems


Hathai Tanta-ngai

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2


We introduce an auxiliary coarse-grained routing layer (an expressway) on Chord, a DHT based structured peer to peer system. With the assumption that nodes in the system have different resource capacities such as storages and bandwidths, powerful (high connectivity and bandwidth) nodes can join the expressway to perform fast routing. First we design the logical structure of an expressway overlay. Then we explore the advantages of physical properties to superimpose the expressway on powerful nodes such as nodes nearby gateway routers.

We focus on the design and analysis of the logical structure of the expressway overlay. Expressway nodes maintain more routing entries that can forward requests with a longer per hop distance. The expressway defers the "last mile" One-grained routing to the underlying system. Instead of using periodically update, we propose event-based notifications for membership and routing entry management on the expressway. Our initial experimental results show that the average logical path length of the system when over 20% of nodes join the expressway with a forwarding power of 4 is about the same as when every node joins the expressway. The logical routing path lengths of the system improve up to (1 ¡ 2( p¡1 p )logp2) ¤ 100% for an expressway with a forwarding power of p. The system requires O(log2r) messages to update all expressway routing entries when a node joins or leaves the system, where r is the number of expressway nodes.

By exploring the advantages of node abilities in both logical and physical networks, we expect the expressway will help forwarding requests faster by reducing routing path lengths and using high bandwidth channels.

Tech Report Number: 
Report Date: 
January 18, 2005
PDF icon CS-2005-19.pdf1.05 MB