Papillon: Greedy Routing in Rings

Details Papillon: Greedy Routing in Rings Papillon: Greedy Routing in Rings

2005-07-14

arxiv.org/abs/cs/0507034v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

We study {\sc greedy} routing over $n$ nodes placed in a ring, with the \emph{distance} 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 $n$ nodes in which {\sc greedy} routing takes $O(\log n / \log d)$ hops in the worst-case, with $d$ out-going links per node. Our result has the first asymptotically optimal greedy routing complexity. Previous constructions required $O(\frac{\log^2 n}{d})$ hops.

Affiliated with

Also associated with

No associations

Rating

Papillon: Greedy Routing in Rings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Papillon: Greedy Routing in Rings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Papillon: Greedy Routing in Rings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-575007