[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

INTERNET-DRAFT                            John W. Stewart, III / Juniper
<draft-ietf-idr-aggregation-tutorial-01.txt>           Enke Chen / Cisco
                                                              March 1998


                        Route Aggregation Tutorial
               <draft-ietf-idr-aggregation-tutorial-01.txt>

Status of this Memo

   This document is an Internet-Draft. Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups. Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months.  Internet-Drafts may be updated, replaced or obsoleted by
   other documents at any time. It is not appropriate to use Internet-
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress."

   Please check the abstract listing contained in each Internet-Draft
   directory to learn the current status of this or any other Internet-
   Draft.

Abstract

   Route aggregation is critical to the long-term viability of the
   Internet.  This document presents practical information that network
   managers can use to both understand the concepts of aggregation as
   well as put those concepts into use in order to do their part to make
   the Internet stable and allow its continued growth.  The intended
   audience for this document is anyone responsible for configuring a
   network which has its own Autonomous System Number (ASN) and
   exchanges routing information with its Internet Service Provider(s)
   (ISP(s)) using the Border Gateway Protocol (BGP).  This document does
   not cover multi-homing, though multi-homed sites can still benefit
   from understanding this material.

1. Introduction

   The long-term viability of the Internet depends on its ability to
   support the continued growth in demand.  A large part of its ability
   to grow is dependent on the successful scaling of the routing system.
   Because the complexity of the Internet's routing system is a function
   of the number of reachable destinations, great care must be taken
   that, as the network grows, the demands on the routing system don't
   outpace advances in hardware and software.



Stewart & Chen                                                  [Page 1]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


   In the early 1990s, the paradigm for large scale Internet routing
   changed from a "Classful" system to a "Classless" system.  The
   Classless system applies techniques of hierarchy to achieve large
   scaling.  In order for Classless routing to achieve its goal of
   allowing the routing system to scale very well, networks in all areas
   of the Internet must be vigilant about "route aggregation."  This
   document provides educational information, both conceptual and
   practical, in an effort to encourage efficient aggregation throughout
   the Internet.

   This document assumes only a very casual understanding of Internet
   addresses.  Once readers clearly understand this document, they may
   wish to read "A Framework for Inter-Domain Route Aggregation" [9] to
   understand the big picture of large-scale aggregation in the
   Internet.

2. Network Classes and the Bit-Level Detail

   As originally specified in the early 1980s, the Internet Protocol
   (IP) included the idea of network "Classes."  [1]  In IP, a certain
   number of bits in the 32-bit addresses refer to the network and the
   remainder of the bits refer to a host on that network.  (In the mid
   1980s IP was extended such that part of the host bits can refer to a
   subnet and the remainder would refer to a host on that subnet.  [2])
   The point of the different Classes was to have addresses with
   different numbers of network/host bits.  The Class of an address
   could be determined by the high-order bits.  A Class A address had
   "0" as the high-order bit, and then 7 bits of network and 24 bits of
   host; a Class B address had "10" as the high-order two bits, and then
   14 bits of network and 16 bits of host; and a Class C address had
   "110" as the high-order three bits and then 21 bits of network and 8
   bits of host.  Looking at an address in "dotted quad notation" (e.g.,
   166.45.3.46), Class A networks have a first number of 0-127, Class B
   networks have a first number of 128-191 and Class C networks have a
   first number of 192-223.  A Class A network could number 1.7 million
   hosts, a Class B 65,000 and a Class C 256.  Diagramatically:















Stewart & Chen                                                  [Page 2]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


       3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
       2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1
Class +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  A   |0                                                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |<--network-->|<---------------------host-------------------->|

       3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
       2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1
Class +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  B   |1 0                                                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |<---------network--------->|<-------------host------------>|

       3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
       2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1
Class +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  C   |1 1 0                                                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |<----------------network---------------->|<-----host---->|


Although the original intent of having Classes was to allow for flexible
addressing, experience showed that the hard boundary of the three
Classes actually made the addressing less flexible.  For example, if a
site connecting to the Internet needed to address 300 hosts, then a
Class C network wouldn't be adequate and a Class B would need to be
assigned.  This resulted in poor utilization of the assigned address
space and caused a faster-than-necessary rate of consumption of the
available IP address space.

Another problem with the scalability of Internet routing under the
Classful system had to do with the address allocation policies used.  At
that time, when a site connected to the Internet, it would go to a cen-
tral registry to get a unique IP network and then it would go to an ISP
to procure connectivity.  What this means is that if an ISP had 1000
customers, each of whom had been assigned a Classful network of some
type, then that ISP would have to announce each of those 1000 networks
to other providers in the Internet.  In other words, the Internet's
routing system was not taking advantage of the inherent provider/sub-
scriber hierarchy and instead was being "flat-routed."

3. The Introduction of CIDR

In the early 1990s, a number of ISPs began to have operational problems
related to the size of a full Internet routing table because of the lim-
ited amount of memory available in commercial routers.  (A "full routing
table" means a routing table which does not contain a default route and



Stewart & Chen                                                  [Page 3]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


instead contains an entry for every active network in the Internet.)
Because of these problems, Classless Inter-Domain Routing (CIDR) was
created.  [3]

CIDR removed the idea of Classes from IP.  Instead of having networks
with an implied number of bits referring to network/host, there are
"prefixes" with an associated mask explicitly identifying which bits
refer to network/host.  For example, the prefix "38.245.76.0" with a
mask of "255.255.255.0" has 24 bits of network and 8 bits of host (i.e.,
it can address the same number of hosts as a Class C network even though
the prefix is in the Class A range).  The CIDR paradigm prefers the term
"prefix" over "network" because it's more clear that no Class is being
implied.  Another way to write this example prefix is "38.245.76.0/24",
meaning that the mask contains 24 1s in the high-order portion of the
mask.

The strength of CIDR is that the masks can be on arbitrary bit bound-
aries and don't have to be on byte boundaries.  So for example, going
back to the case of the site which needs to address 300 hosts, the site
could be allocated a "/23" (i.e., a prefix which has 23 bits for network
and 9 bits for host, thus allowing 512 hosts to be addressed with the
single prefix).

To complete the picture, in order for CIDR to actually help achieve bet-
ter scaling of Internet routing, a specific address allocation architec-
ture must be used.  [4]  Rather than the pre-CIDR style where sites
would go to a centralized registry to get an address which does not take
into account where that site connects to the Internet, CIDR-style
address allocation involves registries allocating address space to ISPs
who, in turn, sub-allocate it to their customers.  So for example, a
registry might allocate the prefix 204.71.0.0/16 (called a "CIDR block")
to ISP1, and then ISP1 could sub-allocate 204.71.1.0/24 to SmallCus-
tomer1, 204.71.2.0/24 to SmallCustomer2, 204.71.128.0/22 to MediumCus-
tomer and 204.71.136.0/20 to LargeCustomer.  The benefit, then, is that
when ISP1 exchanges routing information with other ISPs, it only needs
to announce the single prefix 204.71.0.0/16 and not each of the individ-
ual prefixes used by its customers.  The ability to merge multiple pre-
fixes which have some number of leading bits in common is called "aggre-
gation."

In 1993, the deployment of a routing protocol which supported CIDR
(specifically BGP Version 4 [5]) had an immediate and measurably posi-
tive effect on route scaling.  Immediately after its deployment a full
routing table went down in size in absolute numbers (this was possible
only because address allocation had already been done for some time in
the CIDR style even though the routing hadn't yet taken advantage of it)
and, more importantly, the rate of growth was slowed.




Stewart & Chen                                                  [Page 4]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


4. A Note on Renumbering

The crux of CIDR is that the Internet's generally hierarchical topology
is being reflected in the addressing.  As a result, if a site started
out as a customer of ISP1 and is thus numbered out of one of ISP1's CIDR
blocks, but then that site terminates the relationship with ISP1 and
"rehomes" to ISP2, then the site would need to renumber its nodes to be
part of one of ISP2's CIDR blocks.  The major reason for this is to
retain efficiency in the routing system.  [6]

Renumbering is an unfortunate necessity in the current IPv4 Internet.
This is the reason for the recent advance of renumbering technology in
IPv4 (e.g., DHCP [7]) as well as the focus of easy renumbering in IPv6.
[8]  Sites should keep this "unfortunate necessity" in mind when deploy-
ing equipment to make sure that their infrastructure can be renumbered
easily if that becomes necessary.

5. Practical Aggregation

As stated earlier, aggregation refers to the combining of multiple con-
tiguous prefixes into a single prefix.  For example, assume the prefixes
209.123.10.0/24 and 209.123.11.0/24.  The binary representation for
209.123.10.0/24 is:


       3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
       2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |<---- 209 ---->|<---- 123 ---->|<----  10 ---->|<----  0  ---->|


And the binary representation for 209.123.9.0/24 is


       3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
       2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |<---- 209 ---->|<---- 123 ---->|<----  11 ---->|<----  0  ---->|


The important thing to note here is that the two networks can be aggre-
gated into the single prefix 209.123.10.0/23 because they have the lead-
ing 23 bits in common.




Stewart & Chen                                                  [Page 5]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


The example above is very simple.  A real example of a very large degree
of aggregation is the prefix 208.0.0.0/12, which covers the 4096 24-bit
prefixes 208.0.0.0/24 through 208.15.255.0/24.  It's obvious from this
example how profound an impact aggregation can have on the size of a
routing table and the resources required for the associated storage and
computation.

It is important to aggregate as much as possible, even in the simple
example presented earlier, because small non-optimalities can add up and
result in a poorly aggregated global routing system.  If you exchange
routes with your provider using BGP, then it is your responsibility to
do the aggregation configuration.  (Note that aggregation can only be
done with BGP4, so if you are running an earlier version of BGP, you
should upgrade your software; most major router manufacturers have
implemented BGP4.)  Assuming that your AS number is 5555, your
provider's AS number is 2222 and the IP address of your provider's BGP
speaker is 1.2.3.4, the Cisco syntax for configuring the aggregation
would be:


   interface Ethernet0
    ...
    ip address 209.123.10.1 255.255.255.0
   ...
   interface Ethernet1
    ...
    ip address 209.123.11.1 255.255.255.0
   ...
   router bgp 5555
    network 209.123.10.0 mask 255.255.254.0
    neighbor 1.2.3.4 remote-as 2222
   ...
   ip route 209.123.10.0 255.255.254.0 Null0 254


The "network" line in the BGP section tells the router to announce that
network if it has a route to it.  The "ip route" statement for
209.123.10.0/23 is a static route that creates a "pull-up" route for the
aggregate; this gives the router a route to the prefix so that the "net-
work" line takes effect and the prefix is announced.  The static route
for the aggregate is only needed in order for the "network" line to take
effect; that static route will never be used for packet forwarding
because the static routes for the individual /24 prefixes are more spe-
cific and therefore take precedence.  This configuration information is
required only on the router which speaks BGP with your provider's
router.

In this example, it is assumed that the router which speaks BGP to the



Stewart & Chen                                                  [Page 6]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


provider has local interfaces numbered out of the address space being
aggregated.  This is assumed for simplicity of the example; the "net-
work" line and pull-up route would be used the same ways to do the
aggregation even if the routing for the address space were done stati-
cally, based on an IGP, etc.














































Stewart & Chen                                                  [Page 7]


INTERNET-DRAFT         Route Aggregation Tutorial              July 1997


6.  References

[1] Postel, J., "Internet Protocol", RFC 791, September 1991.

[2] Postel, J., Mogul, J.C., "Internet Standard Subnetting Procedure",
RFC 950, August 1985.

[3] Fuller, V., Li, T., Yu, J., and K. Varadhan, "Classless Inter-
Domain Routing (CIDR): an Address Assignment and Aggregation Strategy",
RFC 1519, September 1993.

[4] Rekhter, Y., Li, T., "An Architecture for IP Address Allocation with
CIDR", RFC 1518, September 1993.

[5] Rekhter, Y., and Li, T., "A Border Gateway Protocol 4 (BGP-4)",
RFC1771, March 1995.

[6] Ferguson, P., Berkowitz, H., "Network Renumbering Overview: Why
would I want it and what is it anyway?", RFC 2071, January 1997.

[7] Droms, R., "Dynamic Host Configuration Protocol", RFC 2131, March
1997.

[8] Thomson, S., Narten, T., "IPv6 Stateless Address Autoconfiguration",
RFC 1971, August 1996.

[9] Chen, E., Stewart III, John W., "A Framework for Inter-Domain Route
Aggregation", draft-ietf-idr-aggregation-framework-01.txt, July 1997.
TBD -- RFC NUMBER

7.  Authors' Addresses


John W. Stewart, III
Juniper Networks, Inc.
385 Ravendale Drive
Mountain View, CA  94043
phone: +1 650 526 8000
email: jstewart@juniper.net

Enke Chen
Cisco Systems
170 West Tasman Drive
San Jose, CA  95134-1706
Phone: +1 408 527 4652
email: enkechen@cisco.com





Stewart & Chen                                                  [Page 8]


Html markup produced by rfcmarkup 1.121, available from https://tools.ietf.org/tools/rfcmarkup/