Ganesan, Prasanna and Manku, Gurmeet Singh (2004) Optimal Routing in Chord. In: ACM SIAM Symposium on Distributed Algorithms (SODA 2004), January 11-13, 2004, New Orleans, LA.
We propose optimal routing algorithms for Chord, a popular topology for routing in peer-to-peer networks. Chord is an undirected graph on $2^b$ nodes arranged in a circle, with edges connecting pairs of nodes that are $2^k$ positions apart for any $k \geq 0$. The standard Chord routing algorithm uses edges in only one direction. Our algorithms exploit the bidirectionality of edges for optimality. At the heart of the new protocols lie algorithms for writing a positive integer $d$ as the difference of two non-negative integers $d'$ and $d''$ such that the total number of 1-bits in the binary representation of $d'$ and $d''$ is minimized. Given that Chord is a variant of the hypercube, the optimal routes possess a surprising combinatorial structure.
|Item Type:||Conference or Workshop Item (Paper)|
|Subjects:||Computer Science > Distributed Systems|
|Related URLs:||Project Homepage||http://infolab.stanford.edu/peers/|
|Deposited By:||Import Account|
|Deposited On:||05 Oct 2003 17:00|
|Last Modified:||23 Dec 2008 08:54|
Repository Staff Only: item control page