We study greedy routing over @math nodes placed in a ring, with the between two nodes defined to be the clockwise or the absolute distance between them along the ring. Such graphs arise in the context of modeling social networks and in routing networks for peer-to-peer systems. We construct the first network over @math nodes in which greedy routing takes @math hops in the worst-case, with @math out-going links per node. Our result has the first asymptotically optimal greedy routing complexity. Previous constructions required @math hops.
For routing on a circle, the best-known constructions have @math and @math . Examples include: Chord @cite_15 with distance-function @math , a variant of Chord with bidirectional links'' @cite_4 and distance-function @math , and the hypercube with distance function @math . In this paper, we improve upon all of these constructions by showing how to route in @math hops in the worst case with @math links per node.
@cite_15 @cite_4
2118428193 2070219632
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key data pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis and simulations show that Chord is scalable: Communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes. We propose optimal routing algorithms for Chord [1], a popular topology for routing in peer-to-peer networks. Chord is an undirected graph on 2b nodes arranged in a circle, with edges connecting pairs of nodes that are 2k positions apart for any k ≥ 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.