INTERNET-DRAFT                                         Enke Chen / Cisco
<draft-ietf-idr-aggregation-framework-01.txt> John W. Stewart, III / ISI
                                                               July 1997


              A Framework for Inter-Domain Route Aggregation
               <draft-ietf-idr-aggregation-framework-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

   This document presents a framework for inter-domain route aggregation
   and shows an example router configuration which 'implement' this
   framework.  This framework is flexible and scales well as it
   emphasizes the philosophy of aggregation by the source, both within
   routing domains as well as towards upstream providers, and it also
   strongly encourages the use of the 'no-export' BGP community to
   balance the provider-subscriber need for more granular routing
   information with the Internet's need for scalable inter-domain
   routing.















Chen & Stewart                                                  [Page 1]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


1. Introduction

   The need for route aggregation has long been recognized. Route
   aggregation is good as it reduces the size, and slows the growth, of
   the Internet routing table.  Thus, the amount of resources (e.g., CPU
   and memory) required to process routing information is reduced and
   route calculation is sped up.  Another benefit of route aggregation
   is that route flaps are limited in number, frequency and scope, which
   saves resources and makes the global Internet routing system more
   stable.

   Since CIDR (Classless Inter-Domain Routing) [2] was introduced,
   significant progress has been made on route aggregation, particularly
   in the following two areas:

   -    Formulation and implementation of IP address allocation policies
        by the top registries that conform to the CIDR principles.  [1]
        This policy work is the cornerstone which makes efficient route
        aggregation technically possible.

   -    Route aggregation by large (especially "Tier 1") providers.  To
        date, the largest reductions in the size of the routing table
        have resulted from efficient aggregation by large providers.

   However, the ability of various levels of the global routing system
   to implement efficient aggregation schemes varies widely.  As a
   result, the size and growth rate of the Internet routing table, as
   well as the associated route computation required, remain major
   issues today.  To support Internet growth, it is important to maxim-
   ize the efficiency of aggregation at all levels in the routing sys-
   tem.

   Because of the current size of the routing system and its dynamic
   nature, the first step towards this goal is to establish a clearly-
   defined framework in which scaleable inter-domain route aggregation
   can be realized.  The framework described in this document emphasizes
   the philosophy of aggregation by the source, both within routing
   domains as well as towards upstream providers.  The framework also
   strongly encourages the use of the "no-export" BGP community to bal-
   ance the provider-subscriber need for more granular routing informa-
   tion with the Internet's need for scalable inter-domain routing.  The
   advantages of this framework include the following:

   -    Route aggregation is done in a distributed fashion.  The Inter-
        net is too large and too distributed for aggregation to be per-
        formed successfully by anyone other than the party injecting the
        aggregatable routing information into the global mesh.




Chen & Stewart                                                  [Page 2]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   -    The flexibility of a routing domain to be able to inject more
        granular routing information to an adjacent domain to control
        the resulting traffic patterns, without having an impact on the
        global routing system.

   In addition to describing the philosophy, we illustrate it by
   presenting sample configurations.  IPv4 prefixes, BGP4 and ASs are
   used in examples, though the principles are applicable to inter-
   domain route aggregation in general.

   Address allocation policies and technologies to renumber entire net-
   works, while very relevant to the realization of successful and sus-
   tained inter-domain routing, are not the focus of this document.  The
   references section contains pointers to relevant documents. [8, 9,
   11, 12]



2. Route Aggregation Framework

   The framework of inter-domain route aggregation we are proposing can
   be summarized as follows:

   -    Aggregation from the originating AS

        That is, in its outbound route announcements, each AS aggregates
        the BGP routes originated by itself, by dedicated AS and by
        private-ASs.  [10]  ("Routes originated by an AS" refers to
        routes which have that AS first in the AS path attribute.  For
        example, routes statically configured and injected into BGP fall
        into this category.)

        In general no "proxy aggregation" (i.e., aggregation of a route
        by an AS other than the originating AS) shall be performed.
        This preserves the capability of a multi-homed site to control
        the granularity of routing information injected into the global
        routing system.  Successful proxy aggregation requires coordina-
        tion on a very large scale (i.e., between potentially many pro-
        viders and subscribers) and experience has shown that this is
        nearly impossible to achieve, so to date little aggregation has
        been achieved with proxy aggregation.

        An AS shall always originate via a stable mechanism (e.g.,
        static route configuration) the BGP routes for the large aggre-
        gates from which it allocates addresses to customers.  This
        ensures that it is safe for its customers to use BGP "no-
        export".




Chen & Stewart                                                  [Page 3]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   -    Using BGP community "no-export" toward upstream providers

        That is, in its route announcements toward its upstream pro-
        vider, an AS tags the BGP community "no-export" to routes it
        originates that do not need to be propagated beyond its upstream
        provider (e.g., prefixes allocated by the upstream provider).


   This framework is illustrated in Figure 1. A "Tier 1" provider does
   not use "no-export" in its announcement as it does not have an
   upstream provider.  However, it shall aggregate the routes it ori-
   ginates in its outbound announcements towards both peer providers and
   customers.  An AS with an upstream provider shall aggregate the
   routes it originates and use "no-export" toward its upstream provider
   for routes that do not need to be propagated beyond its provider's
   AS.   This recursion shall apply to all levels of the routing hierar-
   chy.




                              Tier 1
                         +-- Provider <--+
                         |               |
     o aggregates routes |               |  o announces customer routes
       it originates     |               |  o aggregates routes it originates
                         |               ^  o uses "no-export" if appropriate
                         |
                         +---> Tier 2 <--+
                             Provider    |
                         V               |
                         |               |
     o aggregates routes |               |  o announces customer routes
       it originates     |               |  o aggregates routes it originates
                         |               |  o uses "no-export" if appropriate
                         |               |
                         |               ^
                         -> Customer AS


                              Figure 1



   This framework scales well as aggregation is done at all levels of
   the routing system.  It is flexible because the originating AS con-
   trols whether routes of finer granularity are injected to, and/or
   propagated by, its upstream provider.  It facilitates multi-homing



Chen & Stewart                                                  [Page 4]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   without compromising route aggregation.

   This framework is detailed in the following sections.


3. Aggregation from the Originating AS

   It has been well recognized that address allocation and address
   renumbering are keys to containing the growth of the Internet routing
   table.  [1, 2, 8, 9, 11, 12]

   Although the strategies discussed in this document do not assume a
   perfect address allocation, it is strongly urged that an AS receive
   allocation from its upstream service providers' address block.


3.1 Intra-Domain Aggregation

   To reduce the number of routes that need to be injected into an AS,
   there are a couple of principles that shall be followed:


   -    Carry in its BGP table the large route block allocated from its
        upstream provider or an address registry (e.g., InterNIC, RIPE,
        APNIC).  This can be done by either static configuration of the
        large block or by aggregating more specific BGP routes.  The
        former is recommended as it does not depend on other routes.

   -    Allocate sub-blocks to the access routers where further alloca-
        tion is done.  That is, the address allocation shall be done
        such that only a few, less specific routes (instead of many
        more, specific ones) need to be known to the other routers
        within the AS.

        For example, a prefix of /17 can be further allocated to dif-
        ferent access routers as /20s which can then be allocated to
        customers connected to different interfaces on that router (as
        shown in Figure 2).  Then in general only the /20 needs to be
        injected into the whole AS. Exceptions need to be made for
        multi-homed static routes.











Chen & Stewart                                                  [Page 5]


INTERNET-DRAFT        Route Aggregation Framework              July 1997



                            access router
                           +------------+
                           | x.x.x.x/20 |
                           +------------+
                            |     |    |
                            |     |    |
                            /24   /22  /25


                              Figure 2



   It is noted that rehoming of customers without renumbering even
   within the same AS may lead to injection of more specific routes.
   However, in general the more-specifics do not need to be advertised
   outside of that AS. Such routes can either be tagged with the BGP
   community "no-export" or filtered out by a prefix-based filter to
   prevent them from being advertised out.


3.2 Inter-Domain Aggregation

   There are at least two types of routes that need to be advertised by
   an AS: routes originated by the AS and routes originated by its BGP
   customers.  An AS may need to advertise full routes to certain BGP
   customers, in which case the routing announcements include routes
   originated by non-customer ASs.  Clearly an AS can, and should,
   safely aggregate the routes originated by itself and by its BGP cus-
   tomers multi-homed only to it (using, e.g., the dedicated-AS and by
   the private-AS mechanism [10]) in its outbound announcement.  But it
   is far more dangerous to aggregate routes originated by customer ASs
   due to multi-homing.

   However, there are several cases in which a route originated by a BGP
   customer (other than using the dedicated AS or private AS) does not
   need to be advertised out by its upstream providers.  For example,

   -    The route is a more-specific of the upstream provider's block.
        However, the customer is either singly homed; or its connection
        to this particular upstream provider is used for backup only.

   -    The more-specifics of a larger block are announced by the custo-
        mer in order to balance traffic over the multiple links to the
        upstream provider.

   One approach to suppress such routes is to aggregate them even though



Chen & Stewart                                                  [Page 6]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   they are originated by other ASs (termed "proxy aggregation").  How-
   ever, due to the legitimate need for injecting more-specifics for
   multi-homing, proxy aggregation needs to be done with special coordi-
   nation and care.  The coordination work involved is non-trivial in a
   large environment, and as a result, little aggregation savings have
   been achieved with proxy aggregation to date.

   Instead of "proxy aggregation," our approach for dealing with these
   cases is to give control to the ASs that originate the more-specifics
   (as seen by its upstream providers) and let them tag the BGP commun-
   ity "no-export" to the appropriate routes.

   The BGP community "no-export" is a well known BGP community [6, 7].
   A route with this attribute is not propagated beyond an AS boundary.
   So, if a route is tagged with this community in its announcement to
   an upstream provider and is accepted by the upstream provider, the
   route will not be announced beyond the upstream provider's AS. This
   achieves the goal of suppressing the more-specifics in the upstream
   provider's outbound announcement.

   In this framework, the BGP community "no-export" shall be tagged to
   routes that are to be advertized to, but not propagated by, its
   upstream provider.  They may include routes allocated out of its
   upstream provider's block or the more specific routes announced to
   its upstream provider for the purpose of load balancing. This aggre-
   gation strategy can be implemented via prefix-based filtering as
   shown in the example of Section 5.

   For its own protection, a downstream AS shall announce only its own
   routes and its customer routes to its upstream providers.  Thus, the
   outbound routing announcement and aggregation policy can be expressed
   as follows:

      For routes originated by itself/dedicated-AS/private-AS:
         tag with "no-export" when appropriate, and advertise the
         large block and suppress the more-specifics

      For routes originated by customer ASs:
         advertise to upstream ASs

      For any other routes:
         do not advertise to upstream ASs

   This approach is flexible and scales well as it gives control to the
   party with the special needs, distributes the workload and avoids the
   coordination overhead required by proxy aggregation.





Chen & Stewart                                                  [Page 7]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


4. Aggregation by a Provider

   A provider shall aggregate all the routes it originates, as docu-
   mented in Section 3.  The only difference is that the provider may be
   providing full routes to certain BGP customers where no outbound
   filtering is presently in place.  Experience has shown that incon-
   sistent route announcement (e.g., aggregate at the interconnects but
   not toward certain customers) can cause serious routing problems for
   the Internet as a whole because of longest-match routing.  In certain
   cases announcing the more-specifics to customers might provide for
   more accurate IGP metrics and could be useful for better load-
   balancing.  However, the potential risk seems to outweigh the bene-
   fit, especially given the increasing complexity of connectivity that
   a customer may have.  As a result, every effort shall be made to
   ensure consistent route aggregation for all BGP peers.  This means
   deploying filters for the BGP peers which receive full routes.


   In summary, the aggregation strategy for a provider shall be:

   -    In announcing customer routes:

        For routes originated by itself/dedicated-AS/private-AS:
           tag with "no-export" when appropriate, and advertise the
           large block and suppress the more-specifics

        For routes originated by other customer ASs:
           advertise

        For any other routes:
           do not advertise

   -    In announcing full routes:

        For routes originated by itself/dedicated-AS/private-AS:
           tag with "no-export" when appropriate, and advertise the
           large block and suppress the more-specifics

        For any other routes:
           advertise


5. An Example

   Consider the example shown in Figure 3 where AS 1000 is a "Tier 1"
   provider with two large aggregates 208.128.0.0/12 and 166.55.0.0/16,
   and AS 2000 is a customer of AS 1000 with a "portable address"
   160.75.0.0/16 and an address 208.128.0.0/19 allocated from AS 1000.



Chen & Stewart                                                  [Page 8]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   Assume that 208.128.0.0/19 does not need to be propagated beyond AS
   1000.



                                +----------------+
                                |    AS 1000     |
                                | 208.128.0.0/12 |
                                | 166.55.0.0/16  |
                                +----------------+
                                        |
                                        | BGP
                                        |
                                        |
                                +----------------+
                                |     AS 2000    |
                                | 208.128.0.0/19 |
                                | 160.75.0.0/16  |
                                +----------------+

                                     Figure 3


   Then, based on the framework presented, AS 1000 would

   -    originate and advertise the BGP routes 208.128.0.0/12 and
        166.70.0.0/16, and suppress more-specifics originated by
        itself/private-ASs/dedicated-ASs

   -    advertise the routes received from the customer AS 2000

   and AS 2000 would

   -    originate BGP route 208.128.0.0/19 and 160.75.0.0/16

   -    advertise both 160.75.0.0/16 and 208.128.0.0/19 to its provider
        AS 1000 and suppress the more specifics originated by
        itself/private-AS/dedicated-AS, taggin the route 208.128.0.0/19
        with "no-export"

   -    advertise both 160.75.0.0/16 and 208.128.0.0/19 to its BGP cus-
        tomers (if any) and suppress the more-specifics originated by
        itself/private-AS/dedicated-AS, plus any other routes the custo-
        mers may desire to receive

   The sample configuration which implement these policies (in Cisco
   syntax) is given in Appendix A.




Chen & Stewart                                                  [Page 9]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


6. Acknowledgments

   The authors would like to thank Roy Alcala of MCI for a number of
   interesting hallway discussions related to this work.  The IETF's IDR
   Working Group also provided many helpful comments and suggestions.

7. References

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

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

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

   [4] Rekhter, Y., and Gross, P., "Application of the Border Gateway
   Protocol in the Internet", RFC1772, March 1995.

   [5] Rekhter, Y., "Routing in a Multi-provider Internet", RFC1787,
   April 1995.

   [6] Chandra, R., Traina, P., and Li, T., "BGP Communities Attribute",
   RFC 1997, August 1996.

   [7] Chen, E., and Bates, T., "An Application of the BGP Community
   Attribute in Multi-home Routing", RFC 1998, August 1996.

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

   [9] Berkowitz, H., "Router Renumbering Guide", RFC 2072, January
   1997.

   [10] Stewart, J., and Chen, E., "Using BGP Without Consuming a Unique
   ASN", Internet-Draft, January 1997 (expires July 1997), <draft-
   stewart-bgp-multiprotocol-00.txt>.

   [11] Carpenter, B., Crowcroft, J., Rekhter, Y., "IPv4 Address
   Behaviour Today", Internet-Draft, October 1996 (expires April 1997),
   <draft-iab-ip-ad-today-01.txt>.

   [12] Carpenter, B., Rekhter, Y., "Renumbering Needs Work", RFC 1900,
   February 1996.

   [13] Cisco systems, Cisco IOS Software Version 10.3 Router Products



Chen & Stewart                                                 [Page 10]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   Configuration Guide (Addendum), May 1995.


8.  Authors' Addresses


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

   John W. Stewart, III
   USC/ISI
   4350 North Fairfax Drive
   Suite 620
   Arlington, VA  22203
   phone: +1 703 807 0132
   email: jstewart@isi.edu































Chen & Stewart                                                 [Page 11]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


A. Appendix A:  Example Cisco Configuration

   This appendix lists the Cisco configurations for AS 2000 of the exam-
   ples presented in Section 5.   The configuration here uses the AS-
   path for outbound filtering although it can also be based on BGP com-
   munity.  Several route-maps are defined that can be used for peering
   with the upstream provider, and for peering with customers (announc-
   ing full routes or customer routes).











































Chen & Stewart                                                 [Page 12]


INTERNET-DRAFT        Route Aggregation Framework              July 1997



   !!# inject aggregates
   ip route 160.75.0.0 255.255.0.0 Null0 254
   ip route 208.128.0.0 255.255.224.0 Null0 254
   !
   router bgp 2000
   network 160.75.0.0 mask 255.255.0.0
   network 208.128.0.0 mask 255.255.224.0
   neighbor x.x.x.x remote-as 1000
   neighbor x.x.x.x route-map export-routes-to-provider out
   neighbor x.x.x.x send-community
   !
   !!# match all
   ip as-path access-list 1 permit .*
   !
   !!# List of internal AS and private ASs that are safe to aggregate
   ip as-path access-list 10 permit ^$
   ip as-path access-list 10 permit ^64999_
   ip as-path access-list 10 deny .*
   !
   !!# list of other customer ASs
   ip as-path access-list 20 permit ^3000_

   !!# List of prefixes to be tagged with "no-export"
   access-list 101 permit ip 208.128.0.0 0.0.0.0 255.255.224.0 0.0.0.0
   !!# Filter out the more specifics of large aggregates, and permit the rest
   access-list 102 permit ip 160.75.0.0 0.0.0.0 255.255.0.0 0.0.0.0
   access-list 102 deny ip 160.75.0.0 0.0.255.255 255.255.128.0 0.0.127.255
   access-list 102 permit ip 208.128.0.0 0.0.0.0 255.255.224.0 0.0.0.0
   access-list 102 deny ip 208.128.0.0 0.0.31.255 255.255.240.0 0.0.16.255
   access-list 102 permit ip any any
   !
   !!# route-map with the upstream provider
   route-map export-routes-to-provider permit 10
   match ip address 101
   set community no-export
   route-map export-routes-to-provider permit 20
   match as-path 10
   match ip address 102
   route-map export-routes-to-provider permit 30
   match as-path 20
   !
   !!# route-map with BGP customers that desire only customer routes
   route-map export-customer-routes permit 10
   match as-path 10
   match ip address 102
   route-map export-customer-routes permit 20
   match as-path 20



Chen & Stewart                                                 [Page 13]


INTERNET-DRAFT        Route Aggregation Framework              July 1997


   !
   !!# route-map with BGP customers that desire full routes
   route-map export-full-routes permit 10
   match as-path 10
   match ip address 102
   route-map export-full-routes permit 20
   match as-path 1
   !











































Chen & Stewart                                                 [Page 14]