"Distance Oracles and Compact Routing: Old Stories, New Characters"

Given a network (modeled as undirected, weighted graph), how quickly can we compute shortest paths? How much memory do we need to store the shortest path information? Is it possible to reduce the computation by using extra memory?  How does the problem change if one only desires "approximately" shortest paths? How does one route along these paths?

We start by reviewing a decade old result that formalized these problems in the name of "distance oracles".  We then provide the first characterization of the three-way trade-off between query time, memory requirements and approximation on path length. In particular, we present the first non-trivial data structure that returns  distances of approximation less than 2 in query time that is sublinear  in the size of the network.

In addition, we show how to use our data structures for routing in large networks with guaranteed low latency and scalability. For a large-scale map of the Internet, the schemes compute exact shortest paths for more than 99% of the source-destination pairs while reducing the number of forwarding table entries from O(n) to roughly O(n^0.5), where n is the number of nodes in the network.