| Available via | http://dbpubs.stanford.edu/pub/2004-1 |
|
Submitted on |
6th of October 2003 |
|
Author |
Ganesan, Prasanna; Manku, Gurmeet Singh |
|
Title |
Optimal Routing in Chord |
|
Date of publication |
2004 |
|
Published in |
ACM SIAM Symposium on Distributed Algorithms(SODA) 2004 |
|
Citation |
Ganesan, Prasanna; Manku, Gurmeet Singh. Optimal Routing in Chord, ACM SIAM Symposium on Distributed Algorithms(SODA) 2004 |
|
Number of pages |
10 |
|
Language |
English |
|
Project |
Peers |
|
Type |
Conference or Journal Paper |
|
Subject group |
Distributed Systems |
|
Abstract |
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. |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |