title: Optimal Routing in Chord
creator: Ganesan, Prasanna
creator: Manku, Gurmeet Singh
subject: Distributed Systems
description: 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. 
date: 2004
type: Conference or Workshop Item
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/640/1/2004-1.pdf
identifier: 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.
relation: http://ilpubs.stanford.edu:8090/640/