Decius wrote:

It seems odd that there would be some sort of magic routing fairy dust that would make a problem like this go away. There must be some sort of tradeoff ...

Yes, of course. Two things:

1) From the paper I referenced before:

Compact routing schemes comprise a set of algorithms that aim to make a good tradeoff between stretch versus the amount of storage required at each vertex for routing tables. Stretch refers to the (usually worst-case) multiplicative factor increase of path length between a pair of vertices under a particular routing scheme versus the length of the shortest existing path between the same pair. The most efficient stretch-3 routing scheme for generic (arbitrary) graphs currently known is due to Thorup-Zwick [3], which we will simply refer to as “the TZ scheme.” It is known to be optimal, up to a logarithmic factor, for per-node memory utilization.

This tradeoff has been known since at least 1977; see

L. Kleinrock and F. Karnoun. Hierarchical routing for large networks; performance evaluation and optimization. Computer Networks, 1:155-174, 1977.

That paper is apparently not online.

From a JHU paper:

The compact routing problem considers a tradeoff of stretch for [routing table, and packet header] space, in the setting where each node locally stores its own routing tables. The stretch of a compact routing algorithm is defined as the maximum stretch over the routes for all pairs of nodes in the network. Clearly if each node stores the O(log n)-bit name of the next node along the shortest path to node TI, for all v E G, this complete routing table gives all shortest path distances. The resulting routing scheme uses O(n log n) space at every node, and has optimal stretch one. This paper answers the question: what is the minimum achievable stretch of any compact routing scheme with sublinear space at each node?

2) The best known schemes are static. Work is progressing on schemes for dynamic networks. See Compact Routing With Name Independence: (shorter version here)

This paper is concerned with compact routing schemes for arbitrary undirected networks in the name-independent model first introduced by Awerbuch, Bar-Noy, Linial and Peleg. A compact routing scheme that uses local routing tables of size ~O(n*exp(1/2)), O(log^2 n)-sized packet headers, and stretch bounded by 5 is obtained, where n is the number of nodes in the network. Alternative schemes reduce the packet header size ... at the cost of either increasing the stretch ... or increasing the table size ...

... In this paper, we have developed low-stretch schemes that decouple node names from network topology. An important next step is to study this problem on fully dynamic networks, where routing tables must be updated online as nodes and edges arrive and depart from the network.

This paper, Toward Compact Interdomain Routing, provides a good introduction and status report.

The most vital open problem, the dynamic routing problem, is to construct truly dynamic schemes.

Unfortunately, this problem is fundamentally hard, as illustrated by the notable but pessimistic result which says that even with unbounded RT sizes, there is no generic dynamic stretch-s routing scheme that guarantees less than W(n/s) routing messages. Simply put, there is no generic routing scheme that scales sublinearly in the number of control packets per topology change. As in the static case we hope that narrowing the problem from the class of all graphs to the class of Internet-like graphs will yield more auspicious scaling.

RE: Looming Issues in Internet Architecture