On Compact Routing for the Internet

Dmitri Krioukov, k c claffy, Kevin Fall, and Arthur Brady
Appears in: 
CCR July 2007

The Internet’s routing system is facing stresses due to its poor fundamental scaling properties. Compact routing is a research field that studies fundamental limits of routing scalability and designs algorithms that try to meet these limits. In particular, compact routing research shows that shortest-path routing, forming a core of traditional routing algorithms, cannot guarantee routing table (RT) sizes that on all network topologies grow slower than linearly as functions of the network size. However, there are plenty of compact routing schemes that relax the shortest-path requirement and allow for improved, sublinear RT size scaling that is mathematically provable for all static network topologies. In particular, there exist compact routing schemes designed for grids, trees, and Internet-like topologies that offer RT sizes that scale logarithmically with the network size. In this paper, we demonstrate that in view of recent results in compact routing research, such logarithmic scaling on Internet-like topologies is fundamentally impossible in the presence of topology dynamics or topology-independent (flat) addressing. We use analytic arguments to show that the number of routing control messages per topology change cannot scale better than linearly on Internet-like topologies. We also employ simulations to confirm that logarithmic RT size scaling gets broken by topology-independent addressing, a cornerstone of popular locator-identifier split proposals aiming at improving routing scaling in the presence of network topology dynamics or host mobility. These pessimistic findings lead us to the conclusion that a fundamental re-examination of assumptions behind routing models and abstractions is needed in order to find a routing architecture that would be able to scale “indefinitely.”

Public Review By: 
Dina Katabi

Currently network operators are very sensitive to the growth rate of the Internet routing table. Compact routing provides a hopeful direction for solving that problem. However, as the theorists continue to look at improving the bounds on various flavors of the problem, it is important to ask the question of how all this theory applies to the Internet.
This paper is largely a survey paper of past theoretical results in this area. But the reviewers felt that it was appropriate for CCR because it does more than just surveying the past results. It provides a numerical comparison of the various techniques, discusses how they apply to the Internet, and extends a few of the results for the specific case of the Internet.
The paper basically concludes that currently proposed compact routing schemes may prove useful in reducing the routing table size; they however cannot reduce the rate of growth of update traffic to less than linear.
The reviewers were concerned that all of the cited work on compact routing considers only the case of shortest-path routing, which is used on the Internet only for routing within an ISP. Scaling becomes a problem, however, only when considering the case of inter-domain routing (routing between ISP’s), and this fundamentally relies on the use of various non-shortest-path routing polices in order to meet economic incentives. While this does not mean that compact routing will not prove to be a useful technique, it does call into question how much the techniques and bounds in the paper apply to the problem of interdomain Internet routing.
All in all however, the reviewers felt this paper addresses an important timely problem, and provides a valuable discussion of a research direction that may eventually provide a solution to this problem.