Geometric Routing, Embeddings and Hyperbolic Spaces
Speaker: Petar Maymounkov , MIT CSAIL
Date: April 12 2007
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Ronitt Rubinfeld, MIT CSAIL
Contact: Joanne Hanley, 617 253 6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/petar-abs.html
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.
See other events that are part of Algorithms and Complexity Series 2006/2007
See other events happening in April 2007
