Full text  Click to download. 
Citation  In Proc. of ACM/SIAM Symposium on Discrete Algorithms, 2004, pp 169178

Authors  Prasanna Ganesan
G. S. Manku 
We propose optimal routing algorithms for Chord [1], a popular topology for routing in peertopeer networks. Chord is an undirected graph on 2^b nodes arranged in a circle, with edges connecting pairs of nodes that are 2^b positions apart for any k\ge 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 nonnegative integers d' and d" such that the total number of 1bits 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.