RFC 2008 (rfc2008) - Page 3 of 13

Implications of Various Address Allocation Policies for Internet Routing

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