home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_i / draft-ietf-idr-aggregation-tutorial-00.txt < prev    next >
Text File  |  1997-07-30  |  17KB  |  399 lines
  1.  
  2.  
  3. INTERNET-DRAFT                                John W. Stewart, III / ISI
  4. <draft-ietf-idr-aggregation-tutorial-00.txt>           Enke Chen / Cisco
  5.                                                                July 1997
  6.  
  7.  
  8.                         Route Aggregation Tutorial
  9.                <draft-ietf-idr-aggregation-tutorial-00.txt>
  10.  
  11. Status of this Memo
  12.  
  13.    This document is an Internet-Draft. Internet-Drafts are working
  14.    documents of the Internet Engineering Task Force (IETF), its areas,
  15.    and its working groups. Note that other groups may also distribute
  16.    working documents as Internet-Drafts.
  17.  
  18.    Internet-Drafts are draft documents valid for a maximum of six
  19.    months.  Internet-Drafts may be updated, replaced or obsoleted by
  20.    other documents at any time. It is not appropriate to use Internet-
  21.    Drafts as reference material or to cite them other than as a "working
  22.    draft" or "work in progress."
  23.  
  24.    Please check the abstract listing contained in each Internet-Draft
  25.    directory to learn the current status of this or any other Internet-
  26.    Draft.
  27.  
  28. Abstract
  29.  
  30.    Route aggregation is critical to the long-term viability of the
  31.    Internet.  This document presents practical information that network
  32.    managers can use to both understand the concepts of aggregation as
  33.    well as put those concepts into use in order to do their part to make
  34.    the Internet stable and allow its continued growth.  The intended
  35.    audience for this document is anyone responsible for configuring a
  36.    network which has its own Autonomous System Number (ASN) and
  37.    exchanges routing information with its Internet Service Provider(s)
  38.    (ISP(s)) using the Border Gateway Protocol (BGP).  This document does
  39.    not cover multi-homing, though multi-homed sites can still benefit
  40.    from understanding this material.
  41.  
  42. 1. Introduction
  43.  
  44.    The long-term viability of the Internet depends on its ability to
  45.    support the continued growth in demand.  A large part of its ability
  46.    to grow is dependent on the successful scaling of the routing system.
  47.    Because the complexity of the Internet's routing system is a function
  48.    of the number of reachable destinations, great care must be taken
  49.    that, as the net grows, the demands on the routing system don't
  50.    outpace advances in hardware and software.
  51.  
  52.  
  53.  
  54. Stewart & Chen                                                  [Page 1]
  55.  
  56.  
  57. INTERNET-DRAFT         Route Aggregation Tutorial              July 1997
  58.  
  59.  
  60.    In the early 1990s, the paradigm for large scale Internet routing
  61.    changed from a "Classful" system to a "Classless" system.  The
  62.    Classless system applies techniques of hierarchy to achieve large
  63.    scaling.  In order for Classless routing to achieve its goal of
  64.    allowing the routing system to scale very well, networks in all areas
  65.    of the Internet must be vigilant about "route aggregation."  This
  66.    document provides educational information, both conceptual and
  67.    practical, in an effort to encourage efficient aggregation throughout
  68.    the Internet.
  69.  
  70. 2. Network Classes and the Bit-Level Detail
  71.  
  72.    As originally specified in the early 1980s, the Internet Protocol
  73.    (IP) included the idea of network "Classes."  [1]  In IP, a certain
  74.    number of bits in the 32-bit addresses refer to the network and the
  75.    remainder of the bits refer to a host on that network.  (In the mid
  76.    1980s IP was extended such that part of the host bits can refer to a
  77.    subnet and the remainder would refer to a host on that subnet.  [2])
  78.    The point of the different Classes was to have addresses with
  79.    different numbers of network/host bits.  The Class of an address
  80.    could be determined by the high-order bits.  A Class A address had
  81.    "0" as the high-order bit, and then 7 bits of network and 24 bits of
  82.    host; a Class B address had "10" as the high-order two bits, and then
  83.    14 bits of network and 16 bits of host; and a Class C address had
  84.    "110" as the high-order three bits and then 21 bits of network and 8
  85.    bits of host.  Looking at an address in "dotted quad notation" (e.g.,
  86.    166.45.3.46), Class A networks have a first number of 0-127, Class B
  87.    networks have a first number of 128-191 and Class C networks have a
  88.    first number of 192-223.  A Class A network could number 1.7 million
  89.    hosts, a Class B 65,000 and a Class C 256.  Diagramatically:
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111. Stewart & Chen                                                  [Page 2]
  112.  
  113.  
  114. INTERNET-DRAFT         Route Aggregation Tutorial              July 1997
  115.  
  116.  
  117.  
  118.           3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  119.           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
  120.    Class +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  121.      A   |0                                                              |
  122.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  123.            |<--network-->|<---------------------host-------------------->|
  124.  
  125.           3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  126.           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
  127.    Class +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  128.      B   |1 0                                                            |
  129.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  130.              |<---------network--------->|<-------------host------------>|
  131.  
  132.           3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  133.           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
  134.    Class +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  135.      C   |1 1 0                                                          |
  136.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  137.                |<----------------network---------------->|<-----host---->|
  138.  
  139.  
  140.    Although the original intent of having Classes was to allow for
  141.    flexible addressing, experience showed that the hard boundary of the
  142.    three Classes actually made the addressing less flexible.  For
  143.    example, if a site connecting to the Internet needed to address 300
  144.    hosts, then a Class C network wouldn't be adequate and a Class B
  145.    would need to be assigned.  This resulted in poor utilization of the
  146.    assigned address space and caused a faster-than-necessary rate of
  147.    consumption of the available IP address space.
  148.  
  149.    Another problem with the scalability of Internet routing under the
  150.    Classful system had to do with the address allocation policies used.
  151.    At that time, when a site connected to the Internet, it would go to a
  152.    central registry to get a unique IP network and then it would go to
  153.    an ISP to procure connectivity.  What this means is that if an ISP
  154.    had 1000 customers, each of whom had been assigned a Classful network
  155.    of some type, then that ISP would have to announce each of those 1000
  156.    networks to other providers in the Internet.  In other words, the
  157.    Internet's routing system was not taking advantage of the inherent
  158.    provider/subscriber hierarchy and instead was being "flat-routed."
  159.  
  160. 3. The Introduction of CIDR
  161.  
  162.    In the early 1990s, a number of ISPs began to have operational
  163.    problems related to the size of a full Internet routing table because
  164.    of the limited amount of memory available in commercial routers.  (A
  165.  
  166.  
  167.  
  168. Stewart & Chen                                                  [Page 3]
  169.  
  170.  
  171. INTERNET-DRAFT         Route Aggregation Tutorial              July 1997
  172.  
  173.  
  174.    "full routing table" means a routing table which does not contain a
  175.    default route and instead contains an entry for every active network
  176.    in the Internet.)  Because of these problems, Classless Inter-Domain
  177.    Routing (CIDR) was created.  [3]
  178.  
  179.    CIDR removed the idea of Classes from IP.  Instead of having networks
  180.    with an implied number of bits referring to network/host, there are
  181.    "prefixes" with an associated mask explicitly identifying which bits
  182.    refer to network/host.  For example, the prefix "38.245.76.0" with a
  183.    mask of "255.255.255.0" has 24 bits of network and 8 bits of host
  184.    (i.e., it can address the same number of hosts as a Class C network
  185.    even though the prefix is in the Class A range).  The CIDR paradigm
  186.    prefers the term "prefix" over "network" because it's more clear that
  187.    no Class is being implied.  Another way to write this example prefix
  188.    is "38.245.76.0/24", meaning that the mask contains 24 1s in the
  189.    high-order portion of the mask.
  190.  
  191.    The strength of CIDR is that the masks can be on arbitrary bit
  192.    boundaries and don't have to be on byte boundaries.  So for example,
  193.    going back to the case of the site which needs to address 300 hosts,
  194.    the site could be allocated a "/23" (i.e., a prefix which has 23 bits
  195.    for network and 9 bits for host, thus allowing 512 hosts to be
  196.    addressed with the single prefix).
  197.  
  198.    To complete the picture, in order for CIDR to actually help achieve
  199.    better scaling of Internet routing, a specific address allocation
  200.    architecture must be used.  [4]  Rather than the pre-CIDR style where
  201.    sites would go to a centralized registry to get an address which does
  202.    not take into account where that site connects to the Internet,
  203.    CIDR-style address allocation involves registries allocating address
  204.    space to ISPs who, in turn, sub-allocate it to their customers.  So
  205.    for example, a registry might allocate the prefix 204.71.0.0/16
  206.    (called a "CIDR block") to ISP1, and then ISP1 could sub-allocate
  207.    204.71.1.0/24 to SmallCustomer1, 204.71.2.0/24 to SmallCustomer2,
  208.    204.71.128.0/22 to MediumCustomer and 204.71.136.0/20 to
  209.    LargeCustomer.  The benefit, then, is that when ISP1 exchanges
  210.    routing information with other ISPs, it only needs to announce the
  211.    single prefix 204.71.0.0/16 and not each of the individual prefixes
  212.    used by its customers.  The ability to merge multiple prefixes which
  213.    have some number of leading bits in common is called "aggregation."
  214.  
  215.    In 1993, the deployment of a routing protocol which supported CIDR
  216.    (specifically BGP Version 4 [5]) had an immediate and measurably
  217.    positive effect on route scaling.  Immediately after its deployment a
  218.    full routing table went down in size in absolute numbers (this was
  219.    possible only because address allocation had already been done for
  220.    some time in the CIDR style even though the routing hadn't yet taken
  221.    advantage of it) and, more importantly, the rate of growth was
  222.  
  223.  
  224.  
  225. Stewart & Chen                                                  [Page 4]
  226.  
  227.  
  228. INTERNET-DRAFT         Route Aggregation Tutorial              July 1997
  229.  
  230.  
  231.    slowed.
  232.  
  233. 4. A Note on Renumbering
  234.  
  235.    The crux of CIDR is that the Internet's generally hierarchical
  236.    topology is being reflected in the addressing.  As a result, if a
  237.    site started out as a customer of ISP1 and is thus numbered out of
  238.    one of ISP1's CIDR blocks, but then that site terminates the
  239.    relationship with ISP1 and "rehomes" to ISP2, then the site would
  240.    need to renumber its nodes to be part of one of ISP2's CIDR blocks.
  241.    The major reason for this is to retain efficiency in the routing
  242.    system.  [6]
  243.  
  244.    Renumbering is an unfortunate necessity in the current IPv4 Internet.
  245.    This is the reason for the recent advance of renumbering technology
  246.    in IPv4 (e.g., DHCP [7]) as well as the focus of easy renumbering in
  247.    IPv6.  [8]  Sites should keep this "unfortunate necessity" in mind
  248.    when deploying equipment to make sure that their infrastructure can
  249.    be renumbered easily if that becomes necessary.
  250.  
  251. 5. Practical Aggregation
  252.  
  253.    As stated earlier, aggregation refers to the combining of multiple
  254.    contiguous prefixes into a single prefix.  For example, assume the
  255.    prefixes 209.123.10.0/24 and 209.123.11.0/24.  The binary
  256.    representation for 209.123.10.0/24 is:
  257.  
  258.  
  259.           3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  260.           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
  261.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  262.          |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|
  263.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  264.          |<---- 209 ---->|<---- 123 ---->|<----  10 ---->|<----  0  ---->|
  265.  
  266.  
  267.    And the binary representation for 209.123.9.0/24 is
  268.  
  269.  
  270.           3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  271.           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
  272.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  273.          |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|
  274.          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  275.          |<---- 209 ---->|<---- 123 ---->|<----  11 ---->|<----  0  ---->|
  276.  
  277.  
  278.    The important thing to note here is that the two networks can be
  279.  
  280.  
  281.  
  282. Stewart & Chen                                                  [Page 5]
  283.  
  284.  
  285. INTERNET-DRAFT         Route Aggregation Tutorial              July 1997
  286.  
  287.  
  288.    aggregated into the single prefix 209.123.10.0/23 because they have
  289.    the leading 23 bits in common.
  290.  
  291.    The example above is very simple.  A real example of a very large
  292.    degree of aggregation is the prefix 208.0.0.0/12, which covers the
  293.    4096 Class C networks 208.0.0.0/24 through 208.15.255.0/24.  It's
  294.    obvious from this example how profound an impact aggregation can have
  295.    on the size of a routing table and the resources required for the
  296.    associated storage and computation.
  297.  
  298.    It is important to aggregate as much as possible, even in the simple
  299.    example presented earlier, because small non-optimalities can add up
  300.    and result in a poorly aggregated global routing system.  If you
  301.    exchange routes with your provider using BGP, then it is your
  302.    responsibility to do the aggregation configuration.  (Note that
  303.    aggregation can only be done with BGP4, so if you are running an
  304.    earlier version of BGP, you should upgrade your software; most major
  305.    router manufacturers have implemented BGP4.)  Assuming that your AS
  306.    number is 5555, your provider's AS number is 2222 and the IP address
  307.    of your provider's BGP speaker is 1.2.3.4, the Cisco syntax for
  308.    configuring the aggregation would be:
  309.  
  310.  
  311.       router bgp 5555
  312.        network 209.123.10.0 mask 255.255.254.0
  313.        neighbor 1.2.3.4 remote-as 2222
  314.       ...
  315.       ip route 209.123.10.0 255.255.255.0 Ethernet0
  316.       ip route 209.123.11.0 255.255.255.0 Ethernet1
  317.       ip route 209.123.10.0 255.255.254.0 Null0 254
  318.  
  319.  
  320.    The "network" line in the BGP section tells the router to announce
  321.    that network if it has a route to it.  The third static route for
  322.    209.123.10.0/23 creates a "pull-up" route for the aggregate so that
  323.    the router actually has a route to it so that the "network" line
  324.    takes effect and the prefix is announced.  The static route for the
  325.    aggregate is only needed in order for the "network" line to take
  326.    effect; that static route will never be used for packet forwarding
  327.    because the static routes for the individual Class C networks are
  328.    more specific and therefore take precedence.  This configuration
  329.    information is required only on the router which speaks BGP with your
  330.    provider's router.
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339. Stewart & Chen                                                  [Page 6]
  340.  
  341.  
  342. INTERNET-DRAFT         Route Aggregation Tutorial              July 1997
  343.  
  344.  
  345. 6.  References
  346.  
  347.    [1] Postel, J., "Internet Protocol", RFC 791, September 1991.
  348.  
  349.    [2] Postel, J., Mogul, J.C., "Internet Standard Subnetting
  350.    Procedure", RFC 950, August 1985.
  351.  
  352.    [3] Fuller, V., Li, T., Yu, J., and K. Varadhan, "Classless Inter-
  353.    Domain Routing (CIDR): an Address Assignment and Aggregation
  354.    Strategy", RFC 1519, September 1993.
  355.  
  356.    [4] Rekhter, Y., Li, T., "An Architecture for IP Address Allocation
  357.    with CIDR", RFC 1518, September 1993.
  358.  
  359.    [5] Rekhter, Y., and Li, T., "A Border Gateway Protocol 4 (BGP-4)",
  360.    RFC1771, March 1995.
  361.  
  362.    [6] Ferguson, P., Berkowitz, H., "Network Renumbering Overview:  Why
  363.    would I want it and what is it anyway?", RFC 2071, January 1997.
  364.  
  365.    [7] Droms, R., "Dynamic Host Configuration Protocol", RFC 2131, March
  366.    1997.
  367.  
  368.    [8] Thomson, S., Narten, T., "IPv6 Stateless Address
  369.    Autoconfiguration", RFC 1971, August 1996.
  370.  
  371. 7.  Authors' Addresses
  372.  
  373.  
  374.    John W. Stewart, III
  375.    USC/ISI
  376.    4350 North Fairfax Drive
  377.    Suite 620
  378.    Arlington, VA  22203
  379.    phone: +1 703 807 0132
  380.    email: jstewart@isi.edu
  381.  
  382.    Enke Chen
  383.    Cisco Systems
  384.    170 West Tasman Drive
  385.    San Jose, CA  95134-1706
  386.    Phone: +1 408 527 4652
  387.    email: enkechen@cisco.com
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396. Stewart & Chen                                                  [Page 7]
  397.  
  398.  
  399.