Geometric Routing, Embeddings and Hyperbolic Spaces

Petar Maymounkov (MIT CSAIL)

Compact routing addresses the existence and construction of distributed routing schemes (for arbitrary graphs) such that nodes are able to make local routing decisions to deliver messages efficiently. The main trade-off in routing is the one between average routing table size and stretch. Current literature has essentially closed the gap between upper and lower bounds.

Modern large-scale distributed systems require two new properties of routing schemes. First, a parallel iterative and quickly-converging algorithm for finding routing schemes is required, so that routing schemes can be used with dynamically changing graphs. Second, routing table sizes must be proportional to vertex degrees to reflect economic incentives.

We argue that existing (relatively coarse) lower-bounds do not contradict these requirements. We point out that current techniques are altogether inapplicable, which motivates the notion of geometric routing. We introduce one particular incarnation of geometric routing, called greedy embeddings. We give new upper and lower bounds in this setting. Our lower bounds work for large classes of geodesic metric spaces (in particular hyperbolic spaces) due to novel topology-based arguments.

Host: Ronitt Rubinfeld

(The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)