draft-ietf-grow-va-00.txt   draft-ietf-grow-va-01.txt 
Network Working Group P. Francis Network Working Group P. Francis
Internet-Draft MPI-SWS Internet-Draft MPI-SWS
Intended status: Informational X. Xu Intended status: Informational X. Xu
Expires: November 24, 2009 Huawei Expires: April 28, 2010 Huawei
H. Ballani H. Ballani
Cornell U. Cornell U.
D. Jen D. Jen
UCLA UCLA
R. Raszuk R. Raszuk
Self Self
L. Zhang L. Zhang
UCLA UCLA
May 23, 2009 October 25, 2009
FIB Suppression with Virtual Aggregation FIB Suppression with Virtual Aggregation
draft-ietf-grow-va-00.txt draft-ietf-grow-va-01.txt
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 41 skipping to change at page 1, line 41
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. 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 Notice
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info). publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
skipping to change at page 4, line 25 skipping to change at page 4, line 25
for instance those that interface with other ISPs. Alternatively, for instance those that interface with other ISPs. Alternatively,
some lower-tier ISPs may simply ignore some routes, for instance some lower-tier ISPs may simply ignore some routes, for instance
/24's that fall within the aggregate of another route. /24's that fall within the aggregate of another route.
FIB Suppression is an approach to shrinking FIB size that requires no FIB Suppression is an approach to shrinking FIB size that requires no
changes to BGP, no changes to packet forwarding mechanisms in changes to BGP, no changes to packet forwarding mechanisms in
routers, and relatively minor changes to control mechanisms in routers, and relatively minor changes to control mechanisms in
routers and configuration of those mechanisms. The core idea behind routers and configuration of those mechanisms. The core idea behind
FIB suppression is to run BGP as normal, and in particular to not 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 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 FIB. This approach minimizes changes to routers, and in particular
approach minimizes changes to routers, and in particular is simpler is simpler than more general routing architectures that try to shrink
than more general routing architectures that try to shrink both RIB both RIB and FIB. With FIB suppression, there are no changes to BGP
and FIB. With FIB suppression, there are no changes to BGP per se. per se. The BGP decision process does not change. The selected AS-
The BGP decision process does not change. The selected AS-path does path does not change, and except on rare occasion the exit router
not change, and except on rare occasion the exit router does not does not change. ISPs can deploy FIB suppression autonomously and
change. ISPs can deploy FIB suppression autonomously and with no with no coordination with neighbor ASes.
coordination with neighbor ASes.
This document describes an approach to FIB suppression called This document describes an approach to FIB suppression called
"Virtual Aggregation" (VA). VA operates by organizing the IP (v4 or "Virtual Aggregation" (VA). VA operates by organizing the IP (v4 or
v6) address space into Virtual Prefixes (VP), and using tunnels to v6) address space into Virtual Prefixes (VP), and using tunnels to
aggregate the (regular) sub-prefixes within each VP. The decrease in 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 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 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 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 way that "core" routers keep the full FIB, and "edge" routers have
almost no FIB (i.e. by defining a VP of 0/0). almost no FIB (i.e. by defining a VP of 0/0).
skipping to change at page 5, line 36 skipping to change at page 5, line 35
Aggregation Point Router (APR): An Aggregation Point Router (APR) is Aggregation Point Router (APR): An Aggregation Point Router (APR) is
a router that aggregates a Virtual Prefix (VP) by installing a router that aggregates a Virtual Prefix (VP) by installing
routes (into the FIB) for all of the sub-prefixes within the VP. 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- APRs advertise the VP to other routers with BGP. For each sub-
prefix within the VP, APRs have a tunnel from themselves to the prefix within the VP, APRs have a tunnel from themselves to the
remote ASBR (Autonomous System Border Router) where packets for remote ASBR (Autonomous System Border Router) where packets for
that prefix should be delivered. that prefix should be delivered.
Install and Suppress: The terms "install" and "suppress" are used to Install and Suppress: The terms "install" and "suppress" are used to
describe whether a RIB entry has been loaded or not loaded into describe whether a RIB entry has been loaded or not loaded into
the FIB (or, equivalently, the Routing Table). In other words, the FIB. In other words, the phrase "install a route" means
the phrase "install a route" means "install a route into the FIB", "install a route into the FIB", and the phrase "suppress a route"
and the phrase "suppress a route" means "do not install a route means "do not install a route into the FIB".
into the FIB".
Legacy Router: A router that does not run VA, and has no knowledge Legacy Router: A router that does not run VA, and has no knowledge
of VA. Legacy routers, however, must be able to terminate of VA. Legacy routers, however, must be able to terminate
tunnels. (If a Legacy router cannot terminate tunnels, then any tunnels. (If a Legacy router cannot terminate tunnels, then any
routes that are reached via that router must be installed in all routes that are reached via that router must be installed in all
FIBs.) FIBs.)
non-APR Router: In discussing VPs, it is often necessary to non-APR Router: In discussing VPs, it is often necessary to
distinguish between routers that are APRs for that VP, and routers 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 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 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 taken to mean "a VA router that is an APR for the given VP", and
skipping to change at page 6, line 5 skipping to change at page 6, line 4
routes that are reached via that router must be installed in all routes that are reached via that router must be installed in all
FIBs.) FIBs.)
non-APR Router: In discussing VPs, it is often necessary to non-APR Router: In discussing VPs, it is often necessary to
distinguish between routers that are APRs for that VP, and routers 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 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 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 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 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 APR for the given VP". The term non-APR router is not used to
refer to legacy routers. refer to legacy routers.
Popular Prefix: A popular prefix is a sub-prefix that is installed 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 in a router in addition to the sub-prefixes it holds by virtue of
being a Aggregation Point Router. The popular prefix allows being a Aggregation Point Router. The popular prefix allows
packets to follow the shortest path. Note that different routers packets to follow the shortest path. Note that different routers
do not need to have the same set of popular prefixes. 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 Routing Information Base (RIB): The term RIB is used rather sloppily
in this document to refer either to the loc-RIB (as used in 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 [RFC4271]), or to the combined Adj-RIBs-In, the Loc-RIB, and the
Adj-RIBs-Out. Adj-RIBs-Out.
Sub-Prefix: A regular (physically aggregatable) prefix. These are Sub-Prefix: A regular (physically aggregatable) prefix. These are
equivalent to the prefixes that would normally comprise the DFRT equivalent to the prefixes that would normally comprise the DFRT
in the absence of VA. A VA router will contain a sub-prefix entry 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 either because the sub-prefix falls within a virtual prefix for
which the router is an APR, or because the sub-prefix is installed which the router is an APR, or because the sub-prefix is installed
as a popular prefix. Legacy routers hold the same sub-prefixes as a popular prefix. Legacy routers hold the same sub-prefixes
skipping to change at page 7, line 5 skipping to change at page 6, line 46
1.4. Temporary Sections 1.4. Temporary Sections
This section contains temporary information, and will be removed in This section contains temporary information, and will be removed in
the final version. the final version.
1.4.1. Document revisions 1.4.1. Document revisions
This document was previously published as both This document was previously published as both
draft-francis-idr-intra-va-01.txt and draft-francis-intra-va-01.txt. 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) draft-francis-intra-va-00.txt)
Added additional authors (Jen, Raszuk, Zhang), to reflect primary Added additional authors (Jen, Raszuk, Zhang), to reflect primary
contributors moving forwards. In addition, a number of minor contributors moving forwards. In addition, a number of minor
clarifications were made. 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) draft-francis-idr-intra-va-01.txt)
1. Changed file name from draft-francis-idr-intra-va to 1. Changed file name from draft-francis-idr-intra-va to
draft-francis-intra-va. draft-francis-intra-va.
2. Restructured the document to make the edge suppression mode a 2. Restructured the document to make the edge suppression mode a
specific sub-case of VA rather than a separate mode of operation. specific sub-case of VA rather than a separate mode of operation.
This includes modifying the title of the draft. This includes modifying the title of the draft.
3. Removed MPLS tunneling details so that specific tunneling 3. Removed MPLS tunneling details so that specific tunneling
approaches can be described in separate documents. 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 o Changed intended document type from STD to BCP, as per advice from
Dublin IDR meeting. Dublin IDR meeting.
o Cleaned up the MPLS language, and specified that the full-address 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). routes to remote ASBRs must be imported into OSPF (Section 3.2.3).
As per Daniel Ginsburg's email As per Daniel Ginsburg's email
http://www.ietf.org/mail-archive/web/idr/current/msg02933.html. http://www.ietf.org/mail-archive/web/idr/current/msg02933.html.
o Clarified that legacy routers must run MPLS. As per Daniel o Clarified that legacy routers must run MPLS. As per Daniel
Ginsburg's email Ginsburg's email
http://www.ietf.org/mail-archive/web/idr/current/msg02935.html. http://www.ietf.org/mail-archive/web/idr/current/msg02935.html.
skipping to change at page 10, line 9 skipping to change at page 10, line 12
every POP contains at least two APRs for every virtual prefix. By 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 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 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 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 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 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 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 every sub-prefix. Note that any router ("edge", "core", etc.) may be
an APR. 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 2.1. Mix of legacy and VA routers
It is important that an ISP be able to operate with a mix of "VA 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 routers" (routers upgraded to operate VA as described in the
document) and "legacy routers". This allows ISPs to deploy VA in an document) and "legacy routers". This allows ISPs to deploy VA in an
incremental fashion and to continue to use routers that for whatever incremental fashion and to continue to use routers that for whatever
reason cannot be upgraded. This document allows such a mix, and reason cannot be upgraded. This document allows such a mix, and
indeed places no topological restrictions on that mix. It does, indeed places no topological restrictions on that mix. It does,
however, require that legacy routers (and VA routers for that matter) however, require that legacy routers (and VA routers for that matter)
are able to forward already-tunneled packets, are able to serve as are able to forward already-tunneled packets, are able to serve as
skipping to change at page 26, line 15 skipping to change at page 26, line 21
[RFC3107] Rekhter, Y. and E. Rosen, "Carrying Label Information in [RFC3107] Rekhter, Y. and E. Rosen, "Carrying Label Information in
BGP-4", RFC 3107, May 2001. BGP-4", RFC 3107, May 2001.
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Tunnels", RFC 3209, December 2001. Tunnels", RFC 3209, December 2001.
[RFC4271] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway [RFC4271] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway
Protocol 4 (BGP-4)", RFC 4271, January 2006. 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 7.2. Informative References
[nsdi09] Ballani, H., Francis, P., Cao, T., and J. Wang, "Making [nsdi09] Ballani, H., Francis, P., Cao, T., and J. Wang, "Making
Routers Last Longer with ViAggre", ACM Usenix NSDI 2009 ht Routers Last Longer with ViAggre", ACM Usenix NSDI 2009 ht
tp://www.usenix.org/events/nsdi09/tech/full_papers/ tp://www.usenix.org/events/nsdi09/tech/full_papers/
ballani/ballani.pdf, April 2009. ballani/ballani.pdf, April 2009.
Authors' Addresses Authors' Addresses
Paul Francis Paul Francis
 End of changes. 13 change blocks. 
25 lines changed or deleted 39 lines changed or added

This html diff was produced by rfcdiff 1.37a. The latest version is available from http://tools.ietf.org/tools/rfcdiff/