3. Hierarchical routing and its implication on address allocation

Hierarchical routing [Kleinrock 77] is a mechanism that improves the scaling properties of a routing system. It is the only proven mechanism for scaling routing to the current size of the Internet.

Hierarchical routing requires that addresses be assigned to reflect the actual network topology. Hierarchical routing works by taking the set of addresses covered by a portion of the topology, and generating a single routing advertisement (route) for the entire set. Further, hierarchical routing allows this to be done recursively: multiple advertisements (routes) can be combined into a single advertisement (route). By exercising this recursion, the amount of information necessary to provide routing can be decreased substantially.

A common example of hierarchical routing is the phone network, where country codes, area codes, exchanges, and finally subscriber lines are different levels in the hierarchy. In the phone network, a switch need not keep detailed routing information about every possible subscriber in a distant area code. Instead, the switch usually knows one routing entry for the entire area code.

Notice that the effect on scaling is dramatic. If we look at the space complexity of the different schemes, the switch that knows about every subscriber in the world needs O(n) space for n worldwide subscribers. Now consider the case of hierarchical routing. We can break n down into the number of subscribers in the local area (l), the other exchanges in the area code (e), the other area codes in the local country code (a) and other country codes (c). Using this notation, hierarchical routing has space complexity O(l + e + a + c). Notice that each of these factors is much, much less than n, and grows very slowly, if at all. This implies that a phone switch can be built today that has some hope of not running out of space when it is deployed.

The fundamental property of hierarchical routing that makes this scalability possible is the ability to form abstractions: here, the ability to group subscribers into exchanges, area codes and country codes. Further, such abstractions must provide useful information for the ability to do routing. Some abstractions, such as the group of users with green phones, are not useful when it comes time to route a call.

Since the information that the routing system really needs is the location of the address within the topology, for hierarchical routing, the useful abstraction must capture the topological location of an address within the network. In principle this could be accomplished in one of two ways. Either (a) constrain the topology (and allowed topology changes) to match address assignment. Or, (b) avoid constraints on the topology (and topology changes), but require that as the topology changes, an entity's address change as well. The process of changing an entity's address is known as "renumbering."