GROW Working Group                                             R. Raszuk
Internet-Draft                                                   NTT MCL
Intended status: Informational                                  J. Heitz
Expires: December 7, 2012 January 6, 2013                                        Ericsson
                                                                   A. Lo
                                                                  Arista
                                                                L. Zhang
                                                                    UCLA
                                                                   X. Xu
                                                                  Huawei
                                                            June
                                                            July 5, 2012

                   Simple Virtual Aggregation (S-VA)
                    draft-ietf-grow-simple-va-09.txt
                    draft-ietf-grow-simple-va-10.txt

Abstract

   The continued growth

   All BGP routers in the Default Free Routing Table (DFRT)
   stresses Zone (DFZ) are required to carry
   all the global routing system routes in a number of ways.  One of the
   most costly stresses Default Free Routing Table (DFRT).  A technique
   is described that allows some BGP routers not to install all of those
   routes into the Forwarding Information Base (FIB) size: ISPs
   often must upgrade router hardware simply because the FIB has run out
   of space, and router vendors must design (FIB).

   Some routers that have adequate
   FIB.

   FIB suppression is in an Autonomous System (AS) announce an approach aggregate (the
   VA prefix) in addition to relieving stress on the FIB routes they already announce.  This
   enables other routers not to install the routes covered by NOT
   loading selected RIB entries the VA
   prefix into the FIB.  Simple Virtual
   Aggregation (S-VA) is a simple form of Virtual Aggregation (VA) that
   allows any and all edge routers to shrink their RIB and FIB
   requirements substantially and therefore increase their useful
   lifetime.

   S-VA does not increase FIB requirements for core routers.  S-VA is
   extremely easy to configure considerably more so than as long as those routes have the various
   tricks done today to extend same next-hop as
   the life of edge routers.  S-VA can be
   deployed autonomously by VA prefix.

   The VA prefixes that are announced within an ISP (cooperation between ISPs is AS are not
   required), and can co-exist with legacy routers in the ISP. announced to
   any other AS.

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

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

   This Internet-Draft will expire on December 7, 2012. January 6, 2013.

Copyright Notice

   Copyright (c) 2012 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . .  4 3
     1.1.  Scope of this Document  . . . . . . . . . . . . . . . . . .  5 3
     1.2.  Requirements notation . . . . . . . . . . . . . . . . . .  5 . 3
     1.3.  Terminology . . . . . . . . . . . . . . . . . . . . . . .  6 . 3
   2.  Operation of S-VA . . . . . . . . . . . . . . . . . . . . . .  6 . 4
   3.  Deployment considerations . . . . . . . . . . . . . . . . . .  8 . 6
   4.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  9 . 6
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  9 . 7
   6.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . .  9 7
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 10 7
     7.1.  Normative References  . . . . . . . . . . . . . . . . . . . 10 7
     7.2.  Informative References  . . . . . . . . . . . . . . . . . . 10 7
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 10 7

1.  Introduction

   ISPs today manage constant

   A technique called Simple Virtual Aggregation (S-VA) is described.
   It allows some routers not to have to store some routes in the
   Forwarding Information Base (FIB) while still advertising and
   receiving the full Default Free Routing Table (DFRT) growth in a number of ways.  One way, of course, BGP.

   A typical scenario is for ISPs to upgrade
   their router hardware before DFRT growth outstrips as follows.  Core routers in the size of ISP maintain
   the
   FIB.  This is too expensive for many ISPs.  They would prefer to
   extend full DFRT in the lifetime of FIB and RIB.  Edge routers whose FIBs can no longer hold the full
   DFRT.

   A common approach taken by lower-tier ISPs is to default route to
   their providers.  Routes to customers and peer ISPs are maintained,
   but everything else defaults to the provider.  This approach has
   several disadvantages.  First, packets to Internet destinations may
   take longer-than-necessary AS paths.

   This problem can be mitigated through careful configuration of
   partial defaults, but this can require substantial configuration
   overhead.  A second problem with defaulting to providers is that the
   ISP is no longer able to provide the full DFRT to its customers.
   Finally, provider defaults prevents the ISP from being able to detect
   martian packets.  As a result, the ISP transmits packets that could
   otherwise have been dropped over its expensive provider links.

   An alternative is for the ISP to maintain full routes in its core
   routers, but to filter routes from edge routers that do not require a
   full DFRT.  These edge routers can then default route to the core or
   exit routers.  This is often possible with edge routers that
   interface to customer networks.  The problem with this approach is
   that it cannot be used for all edge routers.  For instance, it cannot
   be used for routers that connect to transits.  It should also not be
   used for routers that connect to customers which wish to receive the
   full DFRT.

   This draft describes a very simple technique, called Simple Virtual
   Aggregation (S-VA), that allows any and all edge routers to have
   substantially reduced FIB requirements even while still advertising
   and receiving the full DFRT over BGP.  The basic idea is as follows.
   Core routers in the ISP maintain the full DFRT in the FIB and RIB.
   Edge routers maintain maintain the full
   DFRT in the BGP protocol RIB, Loc-RIB, but
   suppress do not install certain routes from being installed in the RIB
   and FIB tables. FIB.  Edge routers may install a default route to core routers,
   to ABRs Area Border Routers (ABR) which are installed on the Point of
   Presence (POP) (POP), to core boundary routers or to the ASBR routers.

   S-VA requires no changes to BGP and no changes to any choice of
   forwarding mechanisms in routers.  Configuration is extremely simple: Autonomous System
   Border Routers (ASBR).

   S-VA must be enabled on the an edge router which that needs to save its RIB
   and FIB space.  In the same time operator must inject into his intra-
   domain routing a new prefix further called virtual aggregate (VA-
   prefix) which will be used as the aggregate forwarding reference by
   the edge routers performing S-VA.  Everything else is automatic.
   ISPs can deploy FIB suppression autonomously and with no coordination
   with neighbor ASes.

   In configurations where BGP routes are used to resolve other routes
   or where BGP routes are redistributed to other protocols which both
   happen via RIB simple-va can rather then suppressing routes before
   they are installed in global RIB flag them as "suppress eligible".
   That will allow for seamless route resolution or redistribution while
   in the same time FIB size will continue to be limited as previously
   flagged routes will not be send from RIB to FIB. and
   FIB space.  The core routers must announce a new prefix called
   virtual aggregate (VA-prefix).

1.1.  Scope of this Document

   The scope of this document VA-prefix is limited not intended to Intra-domain S-VA operation.
   In other words, the case where a single ISP autonomously operates
   S-VA internally without any coordination with neighboring ISPs.

   Note that this document assumes that the S-VA "domain" (i.e. the unit
   of autonomy) is the be announced from one AS (that is, different ASes run S-VA
   independently and without coordination).  For the remainder into
   another, only between routers of this
   document, the terms ISP, AS, and domain are same AS.

   S-VA can be used interchangeably.

   This document applies equally to for IPv4 and IPv6 both unicast and multicast address
   families.

   S-VA may need not operate with a mix of upgraded routers and legacy routers.
   There are no topological restrictions placed on the mix of routers.
   S-VA functionality is local to the every router on which it is enabled and
   routing correctness is guaranteed.

   Note that S-VA is a greatly simplified variant of "full VA"
   [I-D.ietf-grow-va].  With full VA, all routers (core or otherwise)
   can have reduced FIBs.  However, full VA requires substantial new
   configuration and operational complexity compared to S-VA.  Full VA
   also requires the use of MPLS LSPs between all routers.  Note that
   S-VA was formerly specified in [I-D.ietf-grow-va].  It has been moved
   to this separate draft to simplify its understanding. an AS.

1.2.  Requirements notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

1.3.  Terminology

   RIB/FIB-Installing Router (FIR):  An  A router that does not suppress any routes,
      routes and advertises itself as a default route for 0/0. announces the VA-prefix.  Typically a core router, a
      POP to core boundary router or an ASBR would be configured as an
      FIR.
   RIB/FIB-Suppressing Router (FSR):  An S-VA router that installs a
      route to 0/0, the
      VA-prefix, and may suppress other routes. does not install into its FIB routes that are
      covered by and have the same next-hop as the VA-prefix.  Typically
      an edge router would be configured as an FSR.
   Install and

   Suppress:  The terms "install" and "suppress" are used  Not to
      describe whether a protocol local RIB entry has been loaded or not
      loaded into the global RIB and FIB.  In other words, the phrase
      "install a route" means "install a route into the global RIB and
      FIB", and the phrase "suppress a route" means "do not install a route from BGP that is covered by the VA-prefix
      into the global RIB and FIB". or FIB
   Legacy Router:  A router that does not run S-VA, and has no knowledge
      of S-VA.
   Global Routing Information Base (RIB):  The term global RIB is used
      to indicate  All the router's main routing information base.  That protocols in
      a router install their selected routes into the RIB.  The routes
      in the RIB
      is normally are used to populate FIB tables of the router.  It needs resolve next-hops for other routes, to be highlighted that unless FIB compression is used global RIB
      redistributed to other routing protocols and FIB tables are in sync. to be installed into
      the FIB.
   Local/Protocol Routing Information Base (loc-RIB):  The term local
      RIB is used to indicate Loc-RIB
      contains the protocol's table where product of SPF
      or routes that have been selected by the local BGP best path selection is kept before being installed in
      global RIB.  For example,
      speaker's Decision Process as in some protocol implementations BGP
      loc-RIB can be further divided into Adj-RIBs-In, the Loc-RIB, and
      the Adj-RIBs-Out. [RFC4271].
   NLRI:  Network Layer Reachability Information [RFC4271]

2.  Operation of S-VA

   There are three types of routers in S-VA, FIB-Installing routers
   (FIR), FIB-Suppressing routers (FSR), (FSR) and optionally optionally, legacy routers.
   While any router can be an FIR or an FSR (there are no topology
   constraints), FSR, the most simple simplest form of
   deployment is for AS border or
   POP border routers to be configured as FIRs, FIRs and for
   customer facing edge routers respectively in the AS or in the POP to be configured as FSRs.

   There are two basic network deployment scenarios for S-VA - with and
   without presence of

   When a default route.  In both cases simple VA
   operates in an identical way however when default route is found and
   is eligible to become FIR announces a less specific prefix by router's
   configuration VA-prefix, it sets the S-VA may use it.  That should not prevent detection
   of any other potential prefix with different next hop path attributes as the next hop
   of default route.

   In the event of FIRs originating a default BGP route to NLRI 0/0
   [RFC4271].
   follows: The ORIGIN is MUST be set to INCOMPLETE (value 2) and the BGP 2).  The
   NEXT_HOP is MUST be set to match the other BGP same as that of the routes which are also
   advertised
   intended to be covered by said FIR. the VA-prefix.  The ATOMIC_AGGREGATE and
   AGGREGATOR attributes are not SHOULD NOT be included.  The FIR MUST attach a
   NO_EXPORT Community Attribute [RFC1997] to the default route.

   FIRs should not [RFC1997].  The NLRI SHOULD be 0/0.

   A FIR SHOULD NOT FIB-suppress any routes.  They may, however, still
   use some form of local FIB compression algorithm if deemed necessary.

   FSRs

   An FSR must detect the VA prefix VA-prefix or prefixes (including 0/0) and
   install it both them in loc-RIB, all of Loc-RIB, RIB and FIB.  Following that  The FSR may MAY suppress
   any more specific routes which that carry the same next hop next-hop as the VA VA-
   prefix.  To guarantee semantical correctness FSR by default
   should also be able to detect installation of not matching next hop
   route and reinstall all the more specifics which were previously
   eligible for suppression to maintain semantical forwarding
   correctness.

   Generally, any more specific route which carries the same next hop next-hop as
   the VA-prefix is eligible for suppression.  However, provided that
   there was is at least one one less specific prefix with different next-hop
   between the VA-prefix and the suppressed prefixes then those
   suppressed prefixes must be reinstalled.

   For example, consider 3 prefixes.  VA-prefix is the least specific
   and covers prefix2. prefix2 is less specific prefix with different next hop
   between VA-prefix than prefix3 and covers
   it.  Like Russian dolls.  If they all have the prefixes which got suppressed same next-hop, then
   you can just send the biggest one with all
   previously suppressed prefixes the others inside.
   However, if the middle one, prefix2 has a different next-hop, then
   you have to take it out and send it separately.  However, you must be reinstalled.

   Similarly
   remember to take out the smallest doll, prefix3 and also send it
   separately.

   Similarly, when IBGP multipath is enabled and when multiple VA
   prefixes are detected which are multipath candidates under given
   network condition form a multipath, only those more specific prefixes are subject to
   suppression of which have
   the identical set of next hops as multipath next-hops are identical to the set of VA prefixes.

   We illustrate next-hops of the VA-
   prefix multipath are subject to suppression.

   The expected behavior on the figure below. is illustrated in Figure 1.  This figure shows
   an autonomous system with a FIR FIR1 and an FSR FSR1.  FSR1 is an
   ASBR and is connected to two remote external ASBRs, EP1 and EP2.

        +------------------------------------------+
        |      Autonomous System                   |   +----+
        |                                          |   |EP1 |
        |                                      /---+---|    |
        |   To   ----\ +----+          +----+ /    |   +----+
        | Other       \|FIR1|----------|FSR1|/     |
        |Routers      /|    |          |    |\     |
        |        ----/ +----+          +----+ \    |   +----+
        |                                      \---+---|EP2 |
        |                                          |   |    |
        |                                          |   +----+
        +------------------------------------------+
                             Figure 1

   Suppose that FSR1 has been enabled to perform S-VA.  Originally it
   receives all routes from FIR1 (doing next hop self) next-hop-self) as well as
   directly connected EBGP peers from
   EP1 and EP2.  FIR1 now will advertise a VA prefix 0/0 with next hop next-hop
   set to himself. itself.  That will trigger
   detection of such prefix on cause FSR1 and suppression to suppress all routes which
   have with the
   same next hop next-hop as VA prefix and which otherwise would be
   installed in RIB and FIB.  However it needs to be observed that the VA-prefix.  However, FSR1 will not suppress any EBGP
   routes received from his peers EP1 and EP2
   due to next hop being EP2, because their next-hops are
   different from that of the one assigned to VA-prefix.

3.  Deployment considerations

   The simplest deployment model of

   Several FIRs may announce different S-VA is its use within the POP.  In
   such model the POP to core boundary routers (usually RRs prefixes.  For example, in the data
   path) would act as FIRs and would inject VA-prefix 0/0 to all of its
   clients within the POP.  In such model of operation an observation a
   POP, each edge router can be made that such ABRs do have full routing knowledge and client
   to ABR distance is negligible as compared with client to intra-domain
   exit distance.

   Therefore under announce into the above intra POP an S-VA deployment model clients can
   be configured prefix that even in the event of lack of ABR to ABR
   advertisement symmetry there is still no need to monitor if more
   specific unsuppressed route would cover suppressed one.  Thus in this
   particular deployment model there is no need to detect and reinstall
   the previously suppressed ones.

   Another deployment consideration should be given to networks which
   may utilize route reflection.  In
   covers the event of enabling IBGP
   multipath a special care must be taken that both outbound prefixes as
   well as VA-prefixes would pass via said route reflectors to their
   clients. addresses of the customers it services.

   Several FIRs may announce the same S-VA prefix.  In order this case an FSR
   must choose to address install only one of them.  For example, two redundant
   ASBRs, both of which announce the above aspects complete DFRT may each also
   announce the following solutions could
   be considered:

   - Use of intra-POP default route as an S-VA
   - Full mesh  Small or medium side networks where prefix into the AS.

   S-VA can may be deployed
      are normally fully meshed and do not use route reflection.  It
      also needs used to pointed out that some large networks split traffic among redundant exit routers.  For
   example, referring to Figure 1, suppose EP1 and EP2 are two redundant
   ASBRs that announce the complete DFRT.  Each may also fully
      meshed today.
   - Use of add-paths  Use of add-paths new BGP encoding announce two
   S-VA prefixes into the AS: 0/1 and 128/1.  EP1 might announce 0/1
   with higher preference and EP2 might announce 128/1 with higher
   preference.  FIR1 will allow now install into is FIB 0/1 pointing to
      distribute more then one overall best path from RR EP1
   and 128/1 pointing to each client.

   - Alternate advertisement EP2.  If either one of VA-prefix   S-VA prefix does not need EP1 or EP2 were to
      be advertised in BGP.  The BGP suppression will happen as long as
      we configure fail,
   then FSR1 would switch the S-VA with next hop(s) and implementation verifies
      that such VA-prefix is installed in traffic to the RIB and FIB. other exit router with a
   single FIB installation of one S-VA prefix.

3.  Deployment considerations

   BGP routes may be used to resolve nexthops next-hops for static routes or
   other BGP routes.  Because the default route does not imply
   reachability of any destination, a router can be configured not to
   resolve nexthops next-hops using the default route.  In this case, simple-va S-VA should
   not suppress from installation into the RIB a route that may be used
   to resolve a nexthop next-hop for another route.  It may still suppress it
   from installation into the FIB

   Selected BGP routes in the RIB may be redistributed to other
   protocols.  If they no longer exist in the RIB, they will not be
   redistributed.  This is especially important when the conditional
   redistribution is taking place based on the length of the prefix,
   community value etc ..  In those cases where redistribution policy is
   in place simple-va S-VA code should refrain from suppressing prefixes from installation
   into the RIB routes matching such policy.  It may still suppress them
   from installation into the FIB.

   A router may originate a network route or an aggregate route into
   BGP.  Some addresses covered by such a route may not exist.  If this
   router were to receive a packet for an unreachable address within an
   originated route, it must not send that packet to the default VA-prefix
   route.  There are several ways to achieve this.  One is to have the
   FIR aggregate the routes instead of the FSR.  Another is to install a
   blackhole route for the nonexistent addresses on the originating
   router.  This issue is not specific to simple-va, S-VA, but applicable to the
   general use of default routes.

   Like any aggregate, an S-VA prefix may include more address space
   than the sum of the prefixes it covers.  As such, the S-VA prefix may
   provide a route for a packet for which no real destination exists.
   An FSR will forward such a packet to the FIR.

   If an S-VA prefix changes its next-hop or is removed, then many
   routes may need to be downloaded into the FIB to achieve convergence.

4.  IANA Considerations

   There are no IANA considerations.

5.  Security Considerations

   The authors are not aware of any new security considerations due to
   S-VA.

6.  Acknowledgements

   The concept for Virtual Aggregation comes from Paul Francis.  In this
   document authors only simplified some aspects of its behavior to
   allow simpler adoption by some operators.

   Authors would like to thank Clarence Filsfils, Nick Hilliard, S.
   Moonesamy and Tom Petch for their review and valuable input.

7.  References

7.1.  Normative References

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

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC4271]  Rekhter, Y., Li, T.,

   [RFC5082]  Gill, V., Heasley, J., Meyer, D., Savola, P., and S. Hares, "A Border Gateway
              Protocol 4 (BGP-4)", C.
              Pignataro, "The Generalized TTL Security Mechanism
              (GTSM)", RFC 4271, January 2006. 5082, October 2007.

7.2.  Informative References

   [I-D.ietf-grow-va]
              Francis, P., Xu, X., Ballani, H., Jen, D., Raszuk, R., and
              L. Zhang, "FIB Suppression with Virtual Aggregation",
              draft-ietf-grow-va-06 (work in progress), December 2011.

Authors' Addresses

   Robert Raszuk
   NTT MCL
   101 S Ellsworth Avenue Suite 350
   San Mateo, CA  94401
   US

   Email: robert@raszuk.net
   Jakob Heitz
   Ericsson
   300 Holger Way
   San Jose, CA  95135
   USA

   Phone:
   Email: jakob.heitz@ericsson.com

   Alton Lo
   Arista Networks
   5470 Great America Parkway
   Santa Clara, CA  95054
   USA

   Phone:
   Email: altonlo@aristanetworks.com

   Lixia Zhang
   UCLA
   3713 Boelter Hall
   Los Angeles, CA  90095
   US

   Phone:
   Email: lixia@cs.ucla.edu

   Xiaohu Xu
   Huawei Technologies
   No.3 Xinxi Rd., Shang-Di Information Industry Base, Hai-Dian District
   Beijing, Beijing  100085
   P.R.China

   Phone: +86 10 82836073
   Email: xuxh@huawei.com