routing protocols, such as OSPF [RFC2328], Intermediate System to
Intermediate System (IS-IS) [RFC1195], RIPv2 [RFC2453], and Cisco
Enhanced Interior Gateway Routing Protocol (EIGRP), and the BGP4
exterior routing protocol [RFC4271], all support this functionality,
having been developed or modified as part of the deployment of
classless inter-domain routing during the 1990s.
Older interior routing protocols, such as RIP [RFC1058], HELLO, and
Cisco Interior Gateway Routing Protocol (IGRP), and older exterior
routing protocols, such as Exterior Gateway Protocol (EGP) [RFC904],
do not support explicit carriage of prefix length/mask and thus
cannot be effectively used on the Internet other than in very limited
stub configurations. Although their use may be appropriate in simple
legacy end-site configurations, they are considered obsolete and
should NOT be used in transit networks connected to the global
Internet.
Similarly, routing and forwarding tables in layer-3 network equipment
must be organized to store both prefix and prefix length or mask.
Equipment that organizes its routing/forwarding information according
to legacy Class A/B/C network/subnet conventions cannot be expected
to work correctly on networks connected to the global Internet; use
of such equipment is not recommended. Fortunately, very little such
equipment is in use today.
5.1. Rules for Route Advertisement
1. Forwarding in the Internet is done on a longest-match basis.
This implies that destinations that are multi-homed relative to a
routing domain must always be explicitly announced into that
routing domain (i.e., they cannot be summarized). If a network
is multi-homed, all of its paths into a routing domain that is
"higher" in the hierarchy of networks must be known to the
"higher" network).
2. A router that generates an aggregate route for multiple, more-
specific routes must discard packets that match the aggregate
route, but not any of the more-specific routes. In other words,
the "next hop" for the aggregate route should be the null
destination. This is necessary to prevent forwarding loops when
some addresses covered by the aggregate are not reachable.
Note that during failures, partial routing of traffic to a site that
takes its address space from one service provider but that is
actually reachable only through another (i.e., the case of a site
that has changed service providers) may occur because such traffic
will be forwarded along the path advertised by the aggregated route.
Rule #2 will prevent packet misdelivery by causing such traffic to be
discarded by the advertiser of the aggregated route, but the output
of "traceroute" and other similar tools will suggest that a problem
exists within that network rather than in the network that is no
longer advertising the more-specific prefix. This may be confusing
to those trying to diagnose connectivity problems; see the example in
Section 6.2 for details. A solution to this perceived "problem" is
beyond the scope of this document; it lies with better education of
the user/operator community, not in routing technology.
An implementation following these rules should also be generalized,
so that an arbitrary network number and mask are accepted for all
routing destinations. The only outstanding constraint is that the
mask must be left contiguous. Note that the degenerate route to
prefix 0.0.0.0/0 is used as a default route and MUST be accepted by
all implementations. Further, to protect against accidental
advertisements of this route via the inter-domain protocol, this
route should only be advertised to another routing domain when a
router is explicitly configured to do so, never as a non-configured,
"default" option.
5.2. How the Rules Work
Rule #1 guarantees that the forwarding algorithm used is consistent
across routing protocols and implementations. Multi-homed networks
are always explicitly advertised by every service provider through
which they are routed, even if they are a specific subset of one
service provider’s aggregate (if they are not, they clearly must be
explicitly advertised). It may seem as if the "primary" service
provider could advertise the multi-homed site implicitly as part of
its aggregate, but longest-match forwarding causes this not to work.
More details are provided in [RFC4116].
Rule #2 guarantees that no routing loops form due to aggregation.
Consider a site that has been assigned 192.168.64/19 by its "parent"
provider, which has 192.168.0.0/16. The "parent" network will
advertise 192.168.0.0/16 to the "child" network. If the "child"
network were to lose internal connectivity to 192.168.65.0/24 (which
is part of its aggregate), traffic from the "parent" to the to the
"child" destined for 192.168.65.1 will follow the "child’s"
advertised route. When that traffic gets to the "child", however,
the child *must not* follow the route 192.168.0.0/16 back up to the
"parent", since that would result in a forwarding loop. Rule #2 says
that the "child" may not follow a less-specific route for a
destination that matches one of its own aggregated routes (typically,
this is implemented by installing a "discard" or "null" route for all
aggregated prefixes that one network advertises to another). Note
that handling of the "default" route (0.0.0.0/0) is a special case of
this rule; a network must not follow the default to destinations that
are part of one of its aggregated advertisements.
5.3. A Note on Prefix Filter Formats
Systems that process route announcements must be able to verify that
information that they receive is acceptable according to policy
rules. Implementations that filter route advertisements must allow
masks or prefix lengths in filter elements. Thus, filter elements
that formerly were specified as
accept 172.16.0.0
accept 172.25.120.0.0
accept 172.31.0.0
deny 10.2.0.0
accept 10.0.0.0
now look something like this:
accept 172.16.0.0/16
accept 172.25.0.0/16
accept 172.31.0.0/16
deny 10.2.0.0/16
accept 10.0.0.0/8
This is merely making explicit the network mask that was implied by
the Class A/B/C classification of network numbers. It is also useful
to enhance filtering capability to allow the match of a prefix and
all more-specific prefixes with the same bit pattern; fortunately,
this functionality has been implemented by most vendors of equipment
used on the Internet.
5.4. Responsibility for and Configuration of Aggregation
Under normal circumstances, a routing domain (or "Autonomous System")
that has been allocated or assigned a set of prefixes has sole
responsibility for aggregation of those prefixes. In the usual case,
the AS will install configuration in one or more of its routers to
generate aggregate routes based on more-specific routes known to its
internal routing system. These aggregate routes are advertised into
the global routing system by the border routers for the routing
domain. The more-specific internal routes that overlap with the
aggregate routes should not be advertised globally. In some cases,
an AS may wish to delegate aggregation responsibility to another AS
(for example, a customer may wish for its service provider to
generate aggregated routing information on its behalf); in such
cases, aggregation is performed by a router in the second AS
according to the routes that it receives from the first, combined
with configured policy information describing how those routes should
be aggregated.
Note that one provider may choose to perform aggregation on the
routes it receives from another without explicit agreement; this is
termed "proxy aggregation". This can be a useful tool for reducing
the amount of routing state that an AS must carry and propagate to
its customers and neighbors. However, proxy aggregation can also
create unintended consequences in traffic engineering. Consider what
happens if both AS 2 and 3 receive routes from AS 1 but AS 2 performs
proxy aggregation while AS 3 does not. Other ASes that receive
transit routing information from both AS 2 and AS 3 will see an
inconsistent view of the routing information originated by AS 1.
This may cause an unexpected shift of traffic toward AS 1 through AS
3 for AS 3’s customers and any others receiving transit routes from
AS 3. Because proxy aggregation can cause unanticipated consequences
for parts of the Internet that have no relationship with either the
source of the aggregated routes or the party providing aggregation,
it should be used with extreme caution.
Configuration of the routes to be combined into aggregates is an
implementation of routing policy and requires some manually
maintained information. As an addition to the information that must
be maintained for a set of routeable prefixes, aggregation
configuration is typically just a line or two defining the range of
the block of IPv4 addresses to be aggregated. A site performing its
own aggregation is doing so for address blocks that it has been
assigned; a site performing aggregation on behalf of another knows
this information because of an agreement to delegate aggregation.
Assuming that the best common practice for network administrators is
to exchange lists of prefixes to accept from each other,
configuration of aggregation information does not introduce
significant additional administrative overhead.
The generation of an aggregate route is usually specified either
statically or in response to learning an active dynamic route for a
prefix contained within the aggregate route. If such dynamic
aggregate route advertisement is done, care should be taken that
routes are not excessively added or withdrawn (known as "route
flapping"). In general, a dynamic aggregate route advertisement is
added when at least one component of the aggregate becomes reachable
and it is withdrawn only when all components become unreachable.
Properly configured, aggregated routes are more stable than non-
aggregated routes and thus improve global routing stability.
Implementation note: Aggregation of the "Class D" (multicast) address
space is beyond the scope of this document.
5.5. Route Propagation and Routing Protocol Considerations
Prior to the original deployment of CIDR, common practice was to
propagate routes learned via exterior routing protocols (i.e., EGP or
BGP) through a site’s interior routing protocol (typically, OSPF,
IS-IS, or RIP). This was done to ensure that consistent and correct
exit points were chosen for traffic to be sent to a destination
learned through those protocols. Four evolutionary effects -- the
advent of CIDR, explosive growth of global routing state, widespread
adoption of BGP4, and a requirement to propagate full path
information -- have combined to deprecate that practice. To ensure
proper path propagation and prevent inter-AS routing inconsistency
(BGP4’s loop detection/prevention mechanism requires full path
propagation), transit networks must use internal BGP (iBGP) for
carrying routes learned from other providers both within and through
their networks.
6. Example of New Address Assignments and Routing
6.1. Address Delegation
Consider the block of 524288 (2^19) addresses, beginning with
10.24.0.0 and ending with 10.31.255.255, allocated to a single
network provider, "PA". This is equivalent in size to a block of
2048 legacy "Class C" network numbers (or /24s). A classless route
to this block would be described as 10.24.0.0 with a mask of
255.248.0.0 and the prefix 10.24.0.0/13.
Assume that this service provider connects six sites in the following
order (significant because it demonstrates how temporary "holes" may
form in the service provider’s address space):
o "C1", requiring fewer than 2048 addresses (/21 or 8 x /24)
o "C2", requiring fewer than 4096 addresses (/20 or 16 x /24)
o "C3", requiring fewer than 1024 addresses (/22 or 4 x /24)
o "C4", requiring fewer than 1024 addresses (/22 or 4 x /24)
o "C5", requiring fewer than 512 addresses (/23 or 2 x /24)
o "C6", requiring fewer than 512 addresses (/23 or 2 x /24)
In all cases, the number of IPv4 addresses "required" by each site is
assumed to allow for significant growth. The service provider
delegates its address space as follows:
o C1. assign 10.24.0 through 10.24.7. This block of networks is
described by the route 10.24.0.0/21 (mask 255.255.248.0).
o C2. Assign 10.24.16 through 10.24.31. This block is described by
the route 10.24.16.0/20 (mask 255.255.240.0).
o C3. Assign 10.24.8 through 10.24.11. This block is described by
the route 10.24.8.0/22 (mask 255.255.252.0).
o C4. Assign 10.24.12 through 10.24.15. This block is described by
the route 10.24.12.0/22 (mask 255.255.252.0).
o C5. Assign 10.24.32 and 10.24.33. This block is described by the
route 10.24.32.0/23 (mask 255.255.254.0).
o C6. Assign 10.24.34 and 10.24.35. This block is described by the
route 10.24.34.0/23 (mask 255.255.254.0).
These six sites should be represented as six prefixes of varying size
within the provider’s IGP. If, for some reason, the provider uses an
obsolete IGP that doesn’t support classless routing or variable-
length subnets, then explicit routes for all /24s will have to be
carried.
To make this example more realistic, assume that C4 and C5 are multi-
homed through some other service provider, "PB". Further assume the
existence of a site, "C7", that was originally connected to "RB" but
that has moved to "PA". For this reason, it has a block of network
numbers that are assigned out PB’s block of (the next) 2048 x /24.
o C7. Assign 10.32.0 through 10.32.15. This block is described by
the route 10.32.0.0/20 (mask 255.255.240.0).
For the multi-homed sites, assume that C4 is advertised as primary
via "RA" and secondary via "RB"; and that C5 is primary via "RB" and
secondary via "RA". In addition, assume that "RA" and "RB" are both
connected to the same transit service provider, "BB".
Graphically, this topology looks something like this:
10.24.0.0 -- 10.24.7.0__ __10.32.0.0 - 10.32.15.0
C1: 10.24.0.0/21 \ / C7: 10.32.0.0/20
\ /
+----+ +----+
10.24.16.0 - 10.24.31.0_ | | | |
C2: 10.24.16.0/20 \ | | _10.24.12.0 - 10.24.15.0__ | |
\| | / C4: 10.24.12.0/20 \ | |
| |/ \| |
10.24.8.0 - 10.24.11.0___/| PA |\ | PB |
C3: 10.24.8.0/22 | | \__10.24.32.0 - 10.24.33.0___| |
| | C5: 10.24.32.0/23 | |
| | | |
10.24.34.0 - 10.24.35.0__/| | | |
C6: 10.24.34.0/23 | | | |
+----+ +----+
|| ||
routing advertisements: || ||
|| ||
10.24.12.0/22 (C4) || 10.24.12.0/22 (C4) ||
10.32.0.0/20 (C7) || 10.24.32.0/23 (C5) ||
10.24.0.0/13 (PA) || 10.32.0.0/13 (PB) ||
|| ||
VV VV
+---------- BACKBONE NETWORK BB ----------+
6.2. Routing Advertisements
To follow rule #1, PA will need to advertise the block of addresses
that it was given and C7. Since C4 is multi-homed and primary
through PA, it must also be advertised. C5 is multi-homed and
primary through PB. In principle (and in the example above), it need
not be advertised, since longest match by PB will automatically
select PB as primary and the advertisement of PA’s aggregate will be
used as a secondary. In actual practice, C5 will normally be
advertised via both providers.
Advertisements from "PA" to "BB" will be
10.24.12.0/22 primary (advertises C4)
10.32.0.0/20 primary (advertises C7)
10.24.0.0/13 primary (advertises remainder of PA)
For PB, the advertisements must also include C4 and C5, as well as
its block of addresses.
Advertisements from "PB" to "BB" will be
10.24.12.0/22 secondary (advertises C4)
10.24.32.0/23 primary (advertises C5)
10.32.0.0/13 primary (advertises remainder of RB)
To illustrate the problem diagnosis issue mentioned in Section 5.1,
consider what happens if PA loses connectivity to C7 (the site that
is assigned out of PB’s space). In a stateful protocol, PA will
announce to BB that 10.32.0.0/20 has become unreachable. Now, when
BB flushes this information out of its routing table, any future
traffic sent through it for this destination will be forwarded to PB
(where it will be dropped according to Rule #2) by virtue of PB’s
less-specific match, 10.32.0.0/13. Although this does not cause an
operational problem (C7 is unreachable in any case), it does create
some extra traffic across "BB" (and may also prove confusing to
someone trying to debug the outage with "traceroute"). A mechanism
to cache such unreachable state might be nice, but it is beyond the
scope of this document.
7. Domain Name Service Considerations
One aspect of Internet services that was notably affected by the move
to CIDR was the mechanism used for address-to-name translation: the
IN-ADDR.ARPA zone of the domain system. Because this zone is
delegated on octet boundaries only, the move to an address assignment
plan that uses bitmask-oriented addressing caused some increase in
work for those who maintain parts of the IN-ADDR.ARPA zone.
A description of techniques to populate the IN-ADDR.ARPA zone when
and used address that blocks that do not align to octet boundaries is
described in [RFC2317].
8. Transition to a Long-Term Solution
CIDR was designed to be a short-term solution to the problems of
routing state and address depletion on the IPv4 Internet. It does
not change the fundamental Internet routing or addressing
architectures. It is not expected to affect any plans for transition
to a more long-term solution except, perhaps, by delaying the urgency
of developing such a solution.
9. Analysis of CIDR’s Effect on Global Routing State
When CIDR was first proposed in the early 1990s, the original authors
made some observations about the growth rate of global routing state
and offered projections on how CIDR deployment would, hopefully,
reduce what appeared to be exponential growth to a more sustainable
rate. Since that deployment, an ongoing effort, called "The CIDR
Report" [CRPT], has attempted to quantify and track that growth rate.
What follows is a brief summary of the CIDR report as of March 2005,
with an attempt to explain the various patterns and changes of growth
rate that have occurred since measurements of the size of global
routing state began in 1988.
When the graph of "Active BGP Table Entries" [CBGP] is examined,
there appear to be several different growth trends with distinct
inflection points reflecting changes in policy and practice. The
trends and events that are believed to have caused them were as
follows:
1. Exponential growth at the far left of the graph. This represents
the period of early expansion and commercialization of the former
research network, from the late 1980s through approximately 1994.
The major driver for this growth was a lack of aggregation
capability for transit providers, and the widespread use of
legacy Class C allocations for end sites. Each time a new site
was connected to the global Internet, one or more new routing
entries were generated.
2. Acceleration of the exponential trend in late 1993 and early 1994
as CIDR "supernet" blocks were first assigned by the NIC and
routed as separate legacy class-C networks by service provider.
3. A sharp drop in 1994 as BGP4 deployment by providers allowed
aggregation of the "supernet" blocks. Note that the periods of
largest declines in the number of routing table entries typically
correspond to the weeks following each meeting of the IETF CIDR
Deployment Working Group.
4. Roughly linear growth from mid-1994 to early 1999 as CIDR-based
address assignments were made and aggregated routes added
throughout the network.
5. A new period of exponential growth again from early 1999 until
2001 as the "high-tech bubble" fueled both rapid expansion of the
Internet, as well as a large increase in more-specific route
advertisements for multi-homing and traffic engineering.
6. Flattening of growth through 2001 caused by a combination of the
"dot-com bust", which caused many organizations to cease
operations, and the "CIDR police" [CPOL] work aimed at improving
aggregation efficiency.
7. Roughly linear growth through 2002 and 2003. This most likely
represents a resumption of the "normal" growth rate observed
before the "bubble", as well as an end to the "CIDR Police"
effort.
8. A more recent trend of exponential growth beginning in 2004. The
best explanation would seem to be an improvement of the global
economy driving increased expansion of the Internet and the
continued absence of the "CIDR Police" effort, which previously
served as an educational tool for new providers to improve
aggregation efficiency. There have also been some cases where
service providers have deliberately de-aggregated prefixes in an
attempt to mitigate security problems caused by conflicting route
advertisements (see Section 12). Although this behavior may
solve the short-term problems seen by such providers, it is
fundamentally non-scalable and quite detrimental to the community
as a whole. In addition, there appear to be many providers
advertising both their allocated prefixes and all the /24