RFC 2008 (rfc2008) - Page 3 of 13
Implications of Various Address Allocation Policies for Internet Routing
Alternative Format: Original Text Document
RFC 2008 October 1996
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."
Rekhter & Li Best Current Practice