3. Background
Some background information is provided in this section that is
helpful in understanding the issues involved in IP address
allocation. A brief discussion of IP routing is provided.
IP partitions the routing problem into three parts:
- routing exchanges between end systems and routers (ARP),
- routing exchanges between routers in the same routing domain
(interior routing), and,
- routing among routing domains (exterior routing).
4. IP Addresses and Routing
For the purposes of this paper, an IP prefix is an IP address and
some indication of the leftmost contiguous significant bits within
this address. Throughout this paper IP address prefixes will be
expressed as tuples, such that a bitwise logical
AND operation on the IP-address and IP-mask components of a tuple
yields the sequence of leftmost contiguous significant bits that form
the IP address prefix. For example a tuple with the value <193.1.0.0
255.255.0.0> denotes an IP address prefix with 16 leftmost contiguous
significant bits.
When determining an administrative policy for IP address assignment,
it is important to understand the technical consequences. The
objective behind the use of hierarchical routing is to achieve some
level of routing data abstraction, or summarization, to reduce the
cpu, memory, and transmission bandwidth consumed in support of
routing.
Rekhter & Li [Page 3]
RFC 1518 CIDR Address Allocation Architecture September 1993
While the notion of routing data abstraction may be applied to
various types of routing information, this paper focuses on one
particular type, namely reachability information. Reachability
information describes the set of reachable destinations. Abstraction
of reachability information dictates that IP addresses be assigned
according to topological routing structures. However, administrative
assignment falls along organizational or political boundaries. These
may not be congruent to topological boundaries and therefore the
requirements of the two may collide. It is necessary to find a
balance between these two needs.
Routing data abstraction occurs at the boundary between
hierarchically arranged topological routing structures. An element
lower in the hierarchy reports summary routing information to its
parent(s).
At routing domain boundaries, IP address information is exchanged
(statically or dynamically) with other routing domains. If IP
addresses within a routing domain are all drawn from non-contiguous
IP address spaces (allowing no abstraction), then the boundary
information consists of an enumerated list of all the IP addresses.
Alternatively, should the routing domain draw IP addresses for all
the hosts within the domain from a single IP address prefix, boundary
routing information can be summarized into the single IP address
prefix. This permits substantial data reduction and allows better
scaling (as compared to the uncoordinated addressing discussed in the
previous paragraph).
If routing domains are interconnected in a more-or-less random (i.e.,
non-hierarchical) scheme, it is quite likely that no further
abstraction of routing data can occur. Since routing domains would
have no defined hierarchical relationship, administrators would not
be able to assign IP addresses within the domains out of some common
prefix for the purpose of data abstraction. The result would be flat
inter-domain routing; all routing domains would need explicit
knowledge of all other routing domains that they route to. This can
work well in small and medium sized internets. However, this does
not scale to very large internets. For example, we expect growth in
the future to an Internet which has tens or hundreds of thousands of
routing domains in North America alone. This requires a greater
degree of the reachability information abstraction beyond that which
can be achieved at the "routing domain" level.
In the Internet, however, it should be possible to significantly
constrain the volume and the complexity of routing information by
taking advantage of the existing hierarchical interconnectivity, as
discussed in Section 5. Thus, there is the opportunity for a group of
Rekhter & Li [Page 4]
RFC 1518 CIDR Address Allocation Architecture September 1993
routing domains each to be assigned an address prefix from a shorter
prefix assigned to another routing domain whose function is to
interconnect the group of routing domains. Each member of the group
of routing domains now has its (somewhat longer) prefix, from which
it assigns its addresses.
The most straightforward case of this occurs when there is a set of
routing domains which are all attached to a single service provider
domain (e.g., regional network), and which use that provider for all
external (inter-domain) traffic. A small prefix may be given to the
provider, which then gives slightly longer prefixes (based on the
provider's prefix) to each of the routing domains that it
interconnects. This allows the provider, when informing other routing
domains of the addresses that it can reach, to abbreviate the
reachability information for a large number of routing domains as a
single prefix. This approach therefore can allow a great deal of
hierarchical abbreviation of routing information, and thereby can
greatly improve the scalability of inter-domain routing.
Clearly, this approach is recursive and can be carried through
several iterations. Routing domains at any "level" in the hierarchy
may use their prefix as the basis for subsequent suballocations,
assuming that the IP addresses remain within the overall length and
structure constraints.
At this point, we observe that the number of nodes at each lower
level of a hierarchy tends to grow exponentially. Thus the greatest
gains in the reachability information abstraction (for the benefit of
all higher levels of the hierarchy) occur when the reachability
information aggregation occurs near the leaves of the hierarchy; the
gains drop significantly at each higher level. Therefore, the law of
diminishing returns suggests that at some point data abstraction
ceases to produce significant benefits. Determination of the point at
which data abstraction ceases to be of benefit requires a careful
consideration of the number of routing domains that are expected to
occur at each level of the hierarchy (over a given period of time),
compared to the number of routing domains and address prefixes that
can conveniently and efficiently be handled via dynamic inter-domain
routing protocols.