--- 1/draft-ietf-grow-va-00.txt 2009-10-25 16:12:09.000000000 +0100 +++ 2/draft-ietf-grow-va-01.txt 2009-10-25 16:12:09.000000000 +0100 @@ -1,27 +1,27 @@ Network Working Group P. Francis Internet-Draft MPI-SWS Intended status: Informational X. Xu -Expires: November 24, 2009 Huawei +Expires: April 28, 2010 Huawei H. Ballani Cornell U. D. Jen UCLA R. Raszuk Self L. Zhang UCLA - May 23, 2009 + October 25, 2009 FIB Suppression with Virtual Aggregation - draft-ietf-grow-va-00.txt + draft-ietf-grow-va-01.txt 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), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. @@ -30,21 +30,21 @@ 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. - This Internet-Draft will expire on November 24, 2009. + This Internet-Draft will expire on April 28, 2010. Copyright Notice Copyright (c) 2009 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 in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights @@ -113,28 +113,27 @@ for instance those that interface with other ISPs. Alternatively, some lower-tier ISPs may simply ignore some routes, for instance /24's that fall within the aggregate of another route. FIB Suppression is an approach to shrinking FIB size that requires no changes to BGP, no changes to packet forwarding mechanisms in routers, and relatively minor changes to control mechanisms in routers and configuration of those mechanisms. The core idea behind FIB suppression is to run BGP as normal, and in particular to not shrink the RIB, but rather to not load certain RIB entries into the - FIB, for instance by not committing them to the Routing Table. This - approach minimizes changes to routers, and in particular is simpler - than more general routing architectures that try to shrink both RIB - and FIB. With FIB suppression, there are no changes to BGP per se. - The BGP decision process does not change. The selected AS-path does - not change, and except on rare occasion the exit router does not - change. ISPs can deploy FIB suppression autonomously and with no - coordination with neighbor ASes. + FIB. This approach minimizes changes to routers, and in particular + is simpler than more general routing architectures that try to shrink + both RIB and FIB. With FIB suppression, there are no changes to BGP + per se. The BGP decision process does not change. The selected AS- + path does not change, and except on rare occasion the exit router + does not change. ISPs can deploy FIB suppression autonomously and + with no coordination with neighbor ASes. This document describes an approach to FIB suppression called "Virtual Aggregation" (VA). VA operates by organizing the IP (v4 or v6) address space into Virtual Prefixes (VP), and using tunnels to aggregate the (regular) sub-prefixes within each VP. The decrease in FIB size can be dramatic, easily 5x or 10x with only a slight path length and router load increase [nsdi09]. The VPs can be organized such that all routers in an ISP see FIB size decrease, or in such a way that "core" routers keep the full FIB, and "edge" routers have almost no FIB (i.e. by defining a VP of 0/0). @@ -173,24 +172,23 @@ Aggregation Point Router (APR): An Aggregation Point Router (APR) is a router that aggregates a Virtual Prefix (VP) by installing routes (into the FIB) for all of the sub-prefixes within the VP. APRs advertise the VP to other routers with BGP. For each sub- prefix within the VP, APRs have a tunnel from themselves to the remote ASBR (Autonomous System Border Router) where packets for that prefix should be delivered. Install and Suppress: The terms "install" and "suppress" are used to describe whether a RIB entry has been loaded or not loaded into - the FIB (or, equivalently, the Routing Table). In other words, - the phrase "install a route" means "install a route into the FIB", - and the phrase "suppress a route" means "do not install a route - into the FIB". + the FIB. In other words, the phrase "install a route" means + "install a route into the FIB", and the phrase "suppress a route" + means "do not install a route into the FIB". Legacy Router: A router that does not run VA, and has no knowledge of VA. Legacy routers, however, must be able to terminate tunnels. (If a Legacy router cannot terminate tunnels, then any routes that are reached via that router must be installed in all FIBs.) non-APR Router: In discussing VPs, it is often necessary to distinguish between routers that are APRs for that VP, and routers that are not APRs for that VP (but of course may be APRs for other VPs not under discussion). In these cases, the term "APR" is taken to mean "a VA router that is an APR for the given VP", and @@ -190,31 +188,26 @@ routes that are reached via that router must be installed in all FIBs.) non-APR Router: In discussing VPs, it is often necessary to distinguish between routers that are APRs for that VP, and routers that are not APRs for that VP (but of course may be APRs for other VPs not under discussion). In these cases, the term "APR" is taken to mean "a VA router that is an APR for the given VP", and the term "non-APR" is taken to mean "a VA router that is not an APR for the given VP". The term non-APR router is not used to refer to legacy routers. + Popular Prefix: A popular prefix is a sub-prefix that is installed in a router in addition to the sub-prefixes it holds by virtue of being a Aggregation Point Router. The popular prefix allows packets to follow the shortest path. Note that different routers do not need to have the same set of popular prefixes. - Routing Table: The term Routing Table is defined here the same way - as in Section 3.2 of [RFC4271]: "Routing information that the BGP - speaker uses to forward packets (or to construct the forwarding - table used for packet forwarding) is maintained in the Routing - Table." As such, FIB Suppression can be achieved by not - installing a route into the Routing Table Routing Information Base (RIB): The term RIB is used rather sloppily in this document to refer either to the loc-RIB (as used in [RFC4271]), or to the combined Adj-RIBs-In, the Loc-RIB, and the Adj-RIBs-Out. Sub-Prefix: A regular (physically aggregatable) prefix. These are equivalent to the prefixes that would normally comprise the DFRT in the absence of VA. A VA router will contain a sub-prefix entry either because the sub-prefix falls within a virtual prefix for which the router is an APR, or because the sub-prefix is installed as a popular prefix. Legacy routers hold the same sub-prefixes @@ -237,39 +230,48 @@ 1.4. Temporary Sections This section contains temporary information, and will be removed in the final version. 1.4.1. Document revisions This document was previously published as both draft-francis-idr-intra-va-01.txt and draft-francis-intra-va-01.txt. -1.4.1.1. Revisions from the 00 version (of +1.4.1.1. Revisions from the 00 version of draft-ietf-grow-va-00 + + Removed the notion that FIB suppression can be done by suppressing + entries from the Routing Table (as defined in Section 3.2 of + [RFC4271]), an idea that was introduced in the second version of the + draft. Suppressing from the Routing Table breaks PIM-SM, which + relies on the contents of the Routing Table to produce its forwarding + table. + +1.4.1.2. Revisions from the 00 version (of draft-francis-intra-va-00.txt) Added additional authors (Jen, Raszuk, Zhang), to reflect primary contributors moving forwards. In addition, a number of minor clarifications were made. -1.4.1.2. Revisions from the 01 version (of +1.4.1.3. Revisions from the 01 version (of draft-francis-idr-intra-va-01.txt) 1. Changed file name from draft-francis-idr-intra-va to draft-francis-intra-va. 2. Restructured the document to make the edge suppression mode a specific sub-case of VA rather than a separate mode of operation. This includes modifying the title of the draft. 3. Removed MPLS tunneling details so that specific tunneling approaches can be described in separate documents. -1.4.1.3. Revisions from 00 version +1.4.1.4. Revisions from 00 version o Changed intended document type from STD to BCP, as per advice from Dublin IDR meeting. o Cleaned up the MPLS language, and specified that the full-address routes to remote ASBRs must be imported into OSPF (Section 3.2.3). As per Daniel Ginsburg's email http://www.ietf.org/mail-archive/web/idr/current/msg02933.html. o Clarified that legacy routers must run MPLS. As per Daniel Ginsburg's email http://www.ietf.org/mail-archive/web/idr/current/msg02935.html. @@ -386,20 +388,28 @@ every POP contains at least two APRs for every virtual prefix. By having APRs in every POP, the latency imposed by routing to the APR is minimal (the extra hop is within the POP). By having more than one APR, there is a redundant APR should one fail. In practice it is often not possible to have an APR for every VP in every POP. This is because some POPs may have only one or a few routers, and therefore there may not have enough cumulative FIB space in the POP to hold every sub-prefix. Note that any router ("edge", "core", etc.) may be an APR. + It is important that both the contents of BGP RIBs, as well as the + contents of the Routing Table (as defined in Section 3.2 of + [RFC4271]) not be modified by VA (other than the introduction of + routes to VPs). This is because PIM-SM [RFC4601] relies on the + contents of the Routing Table to build its own trees and forwarding + table. Therefore, FIB suppression must take place between the + Routing Table and the actual FIB(s). + 2.1. Mix of legacy and VA routers It is important that an ISP be able to operate with a mix of "VA routers" (routers upgraded to operate VA as described in the document) and "legacy routers". This allows ISPs to deploy VA in an incremental fashion and to continue to use routers that for whatever reason cannot be upgraded. This document allows such a mix, and indeed places no topological restrictions on that mix. It does, however, require that legacy routers (and VA routers for that matter) are able to forward already-tunneled packets, are able to serve as @@ -1147,20 +1157,24 @@ [RFC3107] Rekhter, Y. and E. Rosen, "Carrying Label Information in BGP-4", RFC 3107, May 2001. [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001. [RFC4271] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 4 (BGP-4)", RFC 4271, January 2006. + [RFC4601] Fenner, B., Handley, M., Holbrook, H., and I. Kouvelas, + "Protocol Independent Multicast - Sparse Mode (PIM-SM): + Protocol Specification (Revised)", RFC 4601, August 2006. + 7.2. Informative References [nsdi09] Ballani, H., Francis, P., Cao, T., and J. Wang, "Making Routers Last Longer with ViAggre", ACM Usenix NSDI 2009 ht tp://www.usenix.org/events/nsdi09/tech/full_papers/ ballani/ballani.pdf, April 2009. Authors' Addresses Paul Francis