draft-ietf-rtgwg-bgp-pic-10.txt   draft-ietf-rtgwg-bgp-pic-11.txt 
Network Working Group A. Bashandy, Ed. Network Working Group A. Bashandy, Ed.
Internet Draft Arrcus Internet Draft Individual Contributor
Intended status: Informational C. Filsfils Intended status: Informational C. Filsfils
Expires: April 2020 Cisco Systems Expires: August 2020 Cisco Systems
P. Mohapatra P. Mohapatra
Sproute Networks Sproute Networks
October 2, 2019 February 10, 2020
BGP Prefix Independent Convergence BGP Prefix Independent Convergence
draft-ietf-rtgwg-bgp-pic-10.txt draft-ietf-rtgwg-bgp-pic-11.txt
Abstract Abstract
In the network comprising thousands of iBGP peers exchanging millions In the network comprising thousands of iBGP peers exchanging millions
of routes, many routes are reachable via more than one next-hop. of routes, many routes are reachable via more than one next-hop.
Given the large scaling targets, it is desirable to restore traffic Given the large scaling targets, it is desirable to restore traffic
after failure in a time period that does not depend on the number of after failure in a time period that does not depend on the number of
BGP prefixes. In this document we proposed an architecture by which BGP prefixes. In this document we proposed an architecture by which
traffic can be re-routed to ECMP or pre-calculated backup paths in a traffic can be re-routed to ECMP or pre-calculated backup paths in a
timeframe that does not depend on the number of BGP prefixes. The timeframe that does not depend on the number of BGP prefixes. The
skipping to change at page 1, line 36 skipping to change at page 1, line 36
deployment, complete automation, and zero management and provisioning deployment, complete automation, and zero management and provisioning
effort. It is noteworthy to mention that the benefits of BGP-PIC are effort. It is noteworthy to mention that the benefits of BGP-PIC are
hinged on the existence of more than one path whether as ECMP or hinged on the existence of more than one path whether as ECMP or
primary-backup. primary-backup.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s)
controlling the copyright in such materials, this document may not
be modified outside the IETF Standards Process, and derivative
works of it may not be created outside the IETF Standards Process,
except to format it for publication as an RFC or to translate it
into languages other than English.
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.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as "work in as reference material or to cite them other than as "work in
progress." progress."
skipping to change at page 2, line 18 skipping to change at page 2, line 4
Drafts. Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as "work in as reference material or to cite them other than as "work in
progress." 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 April 2, 2019. This Internet-Draft will expire on August 10, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2020 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 Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with carefully, as they describe your rights and restrictions with
respect to this document. Code Components extracted from this respect to this document. Code Components extracted from this
document must include Simplified BSD License text as described in document must include Simplified BSD License text as described in
Section 4.e of the Trust Legal Provisions and are provided without Section 4.e of the Trust Legal Provisions and are provided without
warranty as described in the Simplified BSD License. warranty as described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction...................................................3 1. Introduction...................................................3
1.1. Terminology...............................................4 1.1. Terminology...............................................3
2. Overview.......................................................5 2. Overview.......................................................5
2.1. Dependency................................................6 2.1. Dependency................................................6
2.1.1. Hierarchical Hardware FIB............................6 2.1.1. Hierarchical Hardware FIB............................6
2.1.2. Availability of more than one primary or secondary BGP 2.1.2. Availability of more than one BGP next-hops..........6
next-hops...................................................7
2.2. BGP-PIC Illustration......................................7 2.2. BGP-PIC Illustration......................................7
3. Constructing the Shared Hierarchical Forwarding Chain..........9 3. Constructing the Shared Hierarchical Forwarding Chain..........9
3.1. Constructing the BGP-PIC forwarding Chain.................9 3.1. Constructing the BGP-PIC forwarding Chain.................9
3.2. Example: Primary-Backup Path Scenario....................10 3.2. Example: Primary-Backup Path Scenario....................10
4. Forwarding Behavior...........................................11 4. Forwarding Behavior...........................................11
5. Handling Platforms with Limited Levels of Hierarchy...........12 5. Handling Platforms with Limited Levels of Hierarchy...........12
5.1. Flattening the Forwarding Chain..........................12 5.1. Flattening the Forwarding Chain..........................12
5.2. Example: Flattening a forwarding chain...................14 5.2. Example: Flattening a forwarding chain...................14
6. Forwarding Chain Adjustment at a Failure......................21 6. Forwarding Chain Adjustment at a Failure......................21
6.1. BGP-PIC core.............................................22 6.1. BGP-PIC core.............................................22
skipping to change at page 4, line 16 skipping to change at page 3, line 51
organization that allows traffic to be restored to pre-calculated organization that allows traffic to be restored to pre-calculated
alternative equal cost primary path or backup path in a time alternative equal cost primary path or backup path in a time
period that does not depend on the number of BGP prefixes. The period that does not depend on the number of BGP prefixes. The
technique relies on internal router behavior that is completely technique relies on internal router behavior that is completely
transparent to the operator and can be incrementally deployed and transparent to the operator and can be incrementally deployed and
enabled with zero operator intervention. enabled with zero operator intervention.
1.1. Terminology 1.1. Terminology
This section defines the terms used in this document. For ease of This section defines the terms used in this document. For ease of
use, we will use terms similar to those used by L3VPN [7] use, we will use terms similar to those used by L3VPN [7].
o BGP prefix: A prefix P/m (of any AFI/SAFI) that a BGP speaker o BGP prefix: A prefix P/m (of any AFI/SAFI) that a BGP speaker
has a path for. has a path for.
o IGP prefix: A prefix P/m (of any AFI/SAFI) that is learnt via o IGP prefix: A prefix P/m (of any AFI/SAFI) that is learnt via
an Interior Gateway Protocol, such as OSPF and ISIS, has a path an Interior Gateway Protocol, such as OSPF and ISIS, has a path
for. The prefix may be learnt directly through the IGP or for. The prefix may be learnt directly through the IGP or
redistributed from other protocol(s) redistributed from other protocol(s)
o CE: An external router through which an egress PE can reach a o CE: An external router through which an egress PE can reach a
prefix P/m. prefix P/m.
o Egress PE, "ePE": A BGP speaker that learns about a prefix
through an eBGP peer and chooses that eBGP as the next-hop for
that prefix.
o Ingress PE, "iPE": A BGP speaker that learns about a prefix o Ingress PE, "iPE": A BGP speaker that learns about a prefix
through a IBGP peer and chooses an egress PE as the next-hop for through a iBGP peer and chooses an egress PE as the next-hop for
the prefix. the prefix.
o Path: The next-hop in a sequence of nodes starting from the o Path: The next-hop in a sequence of nodes starting from the
current node and ending with the destination node or network current node and ending with the destination node or network
identified by the prefix. The nodes may not be directly identified by the prefix. The nodes may not be directly
connected. connected.
o Recursive path: A path consisting only of the IP address of the o Recursive path: A path consisting only of the IP address of the
next-hop without the outgoing interface. Subsequent lookups are next-hop without the outgoing interface. Subsequent lookups are
necessary to determine the outgoing interface and a directly necessary to determine the outgoing interface and a directly
skipping to change at page 6, line 4 skipping to change at page 5, line 41
a child of object Y, then Y cannot be deleted unless object X a child of object Y, then Y cannot be deleted unless object X
is no longer a dependent/child of object Y is no longer a dependent/child of object Y
o Route: A prefix with one or more paths associated with it. o Route: A prefix with one or more paths associated with it.
Hence the minimum set of objects needed to construct a route is Hence the minimum set of objects needed to construct a route is
a leaf and a pathlist. a leaf and a pathlist.
2. Overview 2. Overview
The idea of BGP-PIC is based on two pillars The idea of BGP-PIC is based on two pillars
o A shared hierarchical forwarding Chain: It is not uncommon to see
o A shared hierarchical forwarding chain: It is not uncommon to see
multiple destinations are reachable via the same list of next- multiple destinations are reachable via the same list of next-
hops. Instead of having a separate list of next-hops for each hops. Instead of having a separate list of next-hops for each
destination, all destinations sharing the same list of next-hops destination, all destinations sharing the same list of next-hops
can point to a single copy of this list thereby allowing fast can point to a single copy of this list thereby allowing fast
convergence by making changes to a single shared list of next- convergence by making changes to a single shared list of next-
hops rather than possibly a large number of destinations. Because hops rather than possibly a large number of destinations. Because
paths in a pathlist may be recursive, a hierarchy is formed paths in a pathlist may be recursive, a hierarchy is formed
between pathlist and the resolving prefix whereby the pathlist between pathlist and the resolving prefix whereby the pathlist
depends on the resolving prefix. depends on the resolving prefix.
skipping to change at page 6, line 35 skipping to change at page 6, line 25
chains with maximal sharing of forwarding objects allows rerouting a chains with maximal sharing of forwarding objects allows rerouting a
large number of destinations by modifying a small number of objects large number of destinations by modifying a small number of objects
thereby achieving convergence in a time frame that does not depend thereby achieving convergence in a time frame that does not depend
on the number of destinations. For example, if the IGP prefix that on the number of destinations. For example, if the IGP prefix that
resolves a recursive next-hop is updated there is no need to update resolves a recursive next-hop is updated there is no need to update
the possibly large number of BGP NLRIs that use this recursive next- the possibly large number of BGP NLRIs that use this recursive next-
hop. hop.
2.1. Dependency 2.1. Dependency
This section describes the required functionality in the forwarding This section describes the required functionalities in the
and control planes to support BGP-PIC described in this document forwarding and control planes to support BGP-PIC described in this
document.
2.1.1. Hierarchical Hardware FIB 2.1.1. Hierarchical Hardware FIB
BGP PIC requires a hierarchical hardware FIB support: for each BGP BGP-PIC requires a hierarchical hardware FIB support: for each BGP
forwarded packet, a BGP leaf is looked up, then a BGP Pathlist is forwarded packet, a BGP leaf is looked up, then a BGP Pathlist is
consulted, then an IGP Pathlist, then an Adjacency. consulted, then an IGP Pathlist, then an Adjacency.
An alternative method consists in "flattening" the dependencies when An alternative method consists in "flattening" the dependencies when
programming the BGP destinations into HW FIB resulting in programming the BGP destinations into HW FIB resulting in
potentially eliminating both the BGP Path-List and IGP Path-List potentially eliminating both the BGP Path-List and IGP Path-List
consultation. Such an approach decreases the number of memory consultation. Such an approach decreases the number of memory
lookup's per forwarding operation at the expense of HW FIB memory lookup's per forwarding operation at the expense of HW FIB memory
increase (flattening means less sharing hence duplication), loss of increase (flattening means less sharing hence duplication), loss of
ECMP properties (flattening means less pathlist entropy) and loss of ECMP properties (flattening means less pathlist entropy) and loss of
BGP PIC properties. BGP-PIC properties.
2.1.2. Availability of more than one primary or secondary BGP next-hops 2.1.2. Availability of more than one BGP next-hops
When the primary BGP next-hop fails, BGP PIC depends on the When the primary BGP next-hop fails, BGP-PIC depends on the
availability of a pre-computed and pre-installed secondary BGP next- availability of one or more pre-computed and pre-installed secondary
hop in the BGP Pathlist. BGP next-hop(s) in the BGP Pathlist.
The existence of a secondary next-hop is clear for the following The existence of a secondary next-hop is clear for the following
reason: a service caring for network availability will require two reason: a service caring for network availability will require two
disjoint network connections hence two BGP next-hops. disjoint network connections hence two BGP next-hops.
The BGP distribution of the secondary next-hop is available thanks The BGP distribution of secondary next-hops is available thanks to
to the following BGP mechanisms: Add-Path [10], BGP Best-External the following BGP mechanisms: Add-Path [10], BGP Best-External [5],
[5], diverse path [11], and the frequent use in VPN deployments of diverse path [11], and the frequent use in VPN deployments of
different VPN RD's per PE. It is noteworthy to mention that the different VPN RD's per PE. It is noteworthy to mention that the
availability of another BGP path does not mean that all failure availability of another BGP path does not mean that all failure
scenarios can be covered by simply forwarding traffic to the scenarios can be covered by simply forwarding traffic to the
available secondary path. The discussion of how to cover various available secondary path. The discussion of how to cover various
failure scenarios is beyond the scope of this document failure scenarios is beyond the scope of this document.
2.2. BGP-PIC Illustration 2.2. BGP-PIC Illustration
To illustrate the two pillars above as well as the platform To illustrate the two pillars above as well as the platform
dependency, we will use an example of a simple multihomed L3VPN [7] dependency, we will use an example of a simple multihomed L3VPN [7]
prefix in a BGP-free core running LDP [4] or segment routing over prefix in a BGP-free core running LDP [4] or segment routing over
MPLS forwarding plane [13]. MPLS forwarding plane [13].
+--------------------------------+ +--------------------------------+
| | | |
skipping to change at page 7, line 52 skipping to change at page 7, line 42
| | | |
+--------------------------------+ +--------------------------------+
Figure 1 VPN prefix reachable via multiple PEs Figure 1 VPN prefix reachable via multiple PEs
Referring to Figure 1, suppose the iPE (the ingress PE) receives Referring to Figure 1, suppose the iPE (the ingress PE) receives
NLRIs for the VPN prefixes VPN-IP1 and VPN-IP2 from two egress PEs, NLRIs for the VPN prefixes VPN-IP1 and VPN-IP2 from two egress PEs,
ePE1 and ePE2 with next-hop BGP-NH1 and BGP-NH2, respectively. ePE1 and ePE2 with next-hop BGP-NH1 and BGP-NH2, respectively.
Assume that ePE1 advertise the VPN labels VPN-L11 and VPN-L12 while Assume that ePE1 advertise the VPN labels VPN-L11 and VPN-L12 while
ePE2 advertise the VPN labels VPN-L21 and VPN-L22 for VPN-IP1 and ePE2 advertise the VPN labels VPN-L21 and VPN-L22 for VPN-IP1 and
VPN-IP2, respectively. Suppose that BGP-NH1 and BGP-NH2 are resolved VPN-IP2, respectively. Suppose that BGP-NH1 and BGP-NH2 are resolved
via the IGP prefixes IGP-IP1 and IGP-P2, where each happen to have 2 via the IGP prefixes IGP-IP1 and IGP-IP2, where each happen to have
ECMP paths with IGP-NH1 and IGP-NH2 reachable via the interfaces I1 2 ECMP paths with IGP-NH1 and IGP-NH2 reachable via the interfaces
and I2, respectively. Suppose that local labels (whether LDP [4] or I1 and I2, respectively. Suppose that local labels (whether LDP [4]
segment routing [13]) on the downstream LSRs for IGP-IP1 are IGP-L11 or segment routing [13]) on the downstream LSRs for IGP-IP1 are IGP-
and IGP-L12 while for IGP-P2 are IGP-L21 and IGP-L22. As such, the L11 and IGP-L12 while for IGP-IP2 are IGP-L21 and IGP-L22. As such,
routing table at iPE is as follows: the routing table at iPE is as follows:
65000: 198.51.100.0/24 65000: 198.51.100.0/24
via ePE1 (192.0.2.1), VPN Label: VPN-L11 via ePE1 (192.0.2.1), VPN Label: VPN-L11
via ePE2 (192.0.2.2), VPN Label: VPN-L21 via ePE2 (192.0.2.2), VPN Label: VPN-L21
65000: 203.0.113.0/24 65000: 203.0.113.0/24
via ePE1 (192.0.2.1), VPN Label: VPN-L12 via ePE1 (192.0.2.1), VPN Label: VPN-L12
via ePE2 (192.0.2.2), VPN Label: VPN-L22 via ePE2 (192.0.2.2), VPN Label: VPN-L22
192.0.2.1/32 192.0.2.1/32
skipping to change at page 9, line 26 skipping to change at page 9, line 23
always exist platforms with limited capabilities and hence imposing always exist platforms with limited capabilities and hence imposing
a limit on the depth of the forwarding chain. Section 5 describes a limit on the depth of the forwarding chain. Section 5 describes
how to gracefully trade off convergence speed with the number of how to gracefully trade off convergence speed with the number of
hierarchical levels to support platforms with different hierarchical levels to support platforms with different
capabilities. capabilities.
3. Constructing the Shared Hierarchical Forwarding Chain 3. Constructing the Shared Hierarchical Forwarding Chain
Constructing the forwarding chain is an application of the two Constructing the forwarding chain is an application of the two
pillars described in Section 2. This section describes how to pillars described in Section 2. This section describes how to
construct the forwarding chain in hierarchical shared manner construct the forwarding chain in hierarchical shared manner.
3.1. Constructing the BGP-PIC forwarding Chain 3.1. Constructing the BGP-PIC forwarding Chain
The whole process starts when BGP downloads a prefix to FIB. The The whole process starts when BGP downloads a prefix to FIB. The
prefix contains one or more outgoing paths. For certain labeled prefix contains one or more outgoing paths. For certain labeled
prefixes, such as VPN [7] prefixes, each path may be associated with prefixes, such as VPN [7] prefixes, each path may be associated with
an outgoing label and the prefix itself may be assigned a local an outgoing label and the prefix itself may be assigned a local
label. The list of outgoing paths defines a pathlist. If such label. The list of outgoing paths defines a pathlist. If such
pathlist does not already exist, then FIB creates a new pathlist, pathlist does not already exist, then FIB creates a new pathlist,
otherwise the existing pathlist is used. The BGP prefix is added as otherwise the existing pathlist is used. The BGP prefix is added as
skipping to change at page 11, line 17 skipping to change at page 11, line 17
This section explains how the forwarding plane uses the hierarchical This section explains how the forwarding plane uses the hierarchical
shared forwarding chain to forward a packet. shared forwarding chain to forward a packet.
When a packet arrives at a router, it matches a leaf. A labeled When a packet arrives at a router, it matches a leaf. A labeled
packet matches a label leaf while an IP packet matches an IP prefix packet matches a label leaf while an IP packet matches an IP prefix
leaf. The forwarding engines walks the forwarding chain starting leaf. The forwarding engines walks the forwarding chain starting
from the leaf until the walk terminates on an adjacency. Thus when a from the leaf until the walk terminates on an adjacency. Thus when a
packet arrives, the chain is walked as follows: packet arrives, the chain is walked as follows:
1. Lookup the leaf based on the destination address or the label at 1. Lookup the leaf based on the destination address or the label at
the top of the packet the top of the packet.
2. Retrieve the parent pathlist of the leaf 2. Retrieve the parent pathlist of the leaf.
3. Pick the outgoing path "Pi" from the list of resolved paths in 3. Pick the outgoing path "Pi" from the list of resolved paths in
the pathlist. The method by which the outgoing path is picked is the pathlist. The method by which the outgoing path is picked is
beyond the scope of this document (e.g. flow-preserving hash beyond the scope of this document (e.g. flow-preserving hash
exploiting entropy within the MPLS stack and IP header). Let the exploiting entropy within the MPLS stack and IP header). Let the
"path-index" of the outgoing path "Pi" be "j". "path-index" of the outgoing path "Pi" be "j".
4. If the prefix is labeled, use the "path-index" "j" to retrieve 4. If the prefix is labeled, use the "path-index" "j" to retrieve
the jth label "Lj" stored the jth entry in the OutLabel-List and the jth label "Lj" stored the jth entry in the OutLabel-List and
apply the label action of the label on the packet (e.g. for VPN apply the label action of the label on the packet (e.g. for VPN
label on the ingress PE, the label action is "push"). As label on the ingress PE, the label action is "push"). As
mentioned in Section 1.1 the value of the "path-index" stored mentioned in Section 1.1 the value of the "path-index" stored
in path may not necessarily be the same value of the location of in path may not necessarily be the same value of the location of
the path in the pathlist. the path in the pathlist.
5. Move to the parent of the chosen path "Pi" 5. Move to the parent of the chosen path "Pi".
6. If the chosen path "Pi" is recursive, move to its parent prefix 6. If the chosen path "Pi" is recursive, move to its parent prefix
and go to step 2 and go to step 2.
7. If the chosen path is non-recursive move to its parent adjacency. 7. If the chosen path is non-recursive move to its parent adjacency.
Otherwise go to the next step. Otherwise go to the next step.
8. Encapsulate the packet in the layer string specified by the 8. Encapsulate the packet in the layer string specified by the
adjacency and send the packet out. adjacency and send the packet out.
Let's apply the above forwarding steps to the forwarding chain Let's apply the above forwarding steps to the forwarding chain
depicted in Figure 2 in Section 2. Suppose a packet arrives at depicted in Figure 2 in Section 2. Suppose a packet arrives at
ingress PE iPE from an external neighbor. Assume the packet matches ingress PE iPE from an external neighbor. Assume the packet matches
the VPN prefix VPN-IP1. While walking the forwarding chain, the the VPN prefix VPN-IP1. While walking the forwarding chain, the
forwarding engine applies a hashing algorithm to choose the path and forwarding engine applies a hashing algorithm to choose the path and
the hashing at the BGP level yields path 0 while the hashing at the the hashing at the BGP level yields path 0 while the hashing at the
IGP level yields path 1. In that case, the packet will be sent out IGP level yields path 1. In that case, the packet will be sent out
of interface I2 with the label stack "IGP-L12,VPN-L11". of interface I2 with the label stack "IGP-L12,VPN-L11".
5. Handling Platforms with Limited Levels of Hierarchy 5. Handling Platforms with Limited Levels of Hierarchy
This section describes the construction of the forwarding chain if a This section describes the construction of the forwarding chain if a
platform does not support the number of recursion levels required to platform does not support the number of recursion levels required to
resolve the NLRIs. There are two main design objectives resolve the NLRIs. There are two main design objectives.
o Being able to reduce the number of hierarchical levels from any o Being able to reduce the number of hierarchical levels from any
arbitrary value to a smaller arbitrary value that can be arbitrary value to a smaller arbitrary value that can be
supported by the forwarding engine supported by the forwarding engine.
o Minimal modifications to the forwarding algorithm due to such o Minimal modifications to the forwarding algorithm due to such
reduction. reduction.
5.1. Flattening the Forwarding Chain 5.1. Flattening the Forwarding Chain
Let's consider a pathlist associated with the leaf "R1" consisting Let's consider a pathlist associated with the leaf "R1" consisting
of the list of paths <P1, P2,..., Pn>. Assume that the leaf "R1" has of the list of paths <P1, P2,..., Pn>. Assume that the leaf "R1" has
an Outlabel-list <L1, L2,..., Ln>. Suppose the path Pi is a an Outlabel-list <L1, L2,..., Ln>. Suppose the path Pi is a
recursive path that resolves via a prefix represented by the leaf recursive path that resolves via a prefix represented by the leaf
"R2". The leaf "R2" itself is pointing to a pathlist consisting of "R2". The leaf "R2" itself is pointing to a pathlist consisting of
the paths <Q1, Q2,..., Qm> the paths <Q1, Q2,..., Qm>.
If the platform supports the number of hierarchy levels of the If the platform supports the number of hierarchy levels of the
forwarding chain, then a packet that uses the path "Pi" will be forwarding chain, then a packet that uses the path "Pi" will be
forwarded as follows: forwarded as follows:
1. The forwarding engine is now at leaf "R1" 1. The forwarding engine is now at leaf "R1".
2. So it moves to its parent pathlist, which contains the list <P1, 2. So it moves to its parent pathlist, which contains the list <P1,
P2,..., Pn>. P2,..., Pn>.
3. The forwarding engine applies a hashing algorithm and picks the 3. The forwarding engine applies a hashing algorithm and picks the
path "Pi". So now the forwarding engine is at the path "Pi" path "Pi". So now the forwarding engine is at the path "Pi".
4. The forwarding engine retrieves the label "Li" from the outlabel- 4. The forwarding engine retrieves the label "Li" from the outlabel-
list attached to the leaf "R1" and applies the label action list attached to the leaf "R1" and applies the label action.
5. The path "Pi" uses the leaf "R2" 5. The path "Pi" uses the leaf "R2".
6. The forwarding engine walks forward to the leaf "R2" for 6. The forwarding engine walks forward to the leaf "R2" for
resolution resolution.
7. The forwarding plane performs a hash to pick a path among the 7. The forwarding plane performs a hash to pick a path among the
pathlist of the leaf "R2", which is <Q1, Q2,..., Qm> pathlist of the leaf "R2", which is <Q1, Q2,..., Qm>.
8. Suppose the forwarding engine picks the path "Qj" 8. Suppose the forwarding engine picks the path "Qj".
9. Now the forwarding engine continues the walk to the parent of 9. Now the forwarding engine continues the walk to the parent of
"Qj" "Qj".
Suppose the platform cannot support the number of hierarchy levels Suppose the platform cannot support the number of hierarchy levels
in the forwarding chain. FIB needs to reduce the number of hierarchy in the forwarding chain. FIB needs to reduce the number of hierarchy
levels. The idea of reducing the number of hierarchy levels is to levels. The idea of reducing the number of hierarchy levels is to
"flatten" two chain levels into a single level. The "flattening" "flatten" two chain levels into a single level. The "flattening"
steps are as follows steps are as follows
1. FIB wants to reduce the number of levels used by "Pi" by 1 1. FIB wants to reduce the number of levels used by "Pi" by 1.
2. FIB walks to the parent of "Pi", which is the leaf "R2" 2. FIB walks to the parent of "Pi", which is the leaf "R2".
3. FIB extracts the parent pathlist of the leaf "R2", which is <Q1, 3. FIB extracts the parent pathlist of the leaf "R2", which is <Q1,
Q2,..., Qm> Q2,..., Qm>.
4. FIB also extracts the OutLabel-list(R2) associated with the leaf 4. FIB also extracts the OutLabel-list(R2) associated with the leaf
"R2". Remember that OutLabel-list(R2) = <L1, L2,..., Lm> "R2". Remember that OutLabel-list(R2) = <L1, L2,..., Lm>.
5. FIB replaces the path "Pi", with the list of paths <Q1, Q2,..., 5. FIB replaces the path "Pi", with the list of paths <Q1, Q2,...,
Qm> Qm>.
6. Hence the path list <P1, P2,..., Pn> now becomes "<P1, P2,...,Pi- 6. Hence the path list <P1, P2,..., Pn> now becomes "<P1, P2,...,Pi-
1, Q1, Q2,..., Qm, Pi+1, Pn> 1, Q1, Q2,..., Qm, Pi+1, Pn>.
7. The path index stored inside the locations "Q1", "Q2", ..., "Qm" 7. The path index stored inside the locations "Q1", "Q2", ..., "Qm"
must all be "i" because the index "i" refers to the label "Li" must all be "i" because the index "i" refers to the label "Li"
associated with leaf "R1" associated with leaf "R1".
8. FIB attaches an OutLabel-list with the new pathlist as follows: 8. FIB attaches an OutLabel-list with the new pathlist as follows:
<Unlabeled,..., Unlabeled, L1, L2,..., Lm, Unlabeled, ..., <Unlabeled,..., Unlabeled, L1, L2,..., Lm, Unlabeled, ...,
Unlabeled>. The size of the label list associated with the Unlabeled>. The size of the label list associated with the
flattened pathlist equals the size of the pathlist. Hence there flattened pathlist equals the size of the pathlist. Hence there
is a 1-1 mapping between every path in the "flattened" pathlist is a 1-1 mapping between every path in the "flattened" pathlist
and the OutLabel-list associated with it. and the OutLabel-list associated with it.
It is noteworthy to mention that the labels in the outlabel-list It is noteworthy to mention that the labels in the outlabel-list
associated with the "flattened" pathlist may be stored in the same associated with the "flattened" pathlist may be stored in the same
skipping to change at page 14, line 15 skipping to change at page 14, line 15
capability of the forwarding engine. capability of the forwarding engine.
Because a flattened pathlist may have an associated OutLabel-list Because a flattened pathlist may have an associated OutLabel-list
the forwarding behavior has to be slightly modified. The the forwarding behavior has to be slightly modified. The
modification is done by adding the following step right after step 4 modification is done by adding the following step right after step 4
in Section 4. in Section 4.
5. If there is an OutLabel-list associated with the pathlist, then 5. If there is an OutLabel-list associated with the pathlist, then
if the path "Pi" is chosen by the hashing algorithm, retrieve the if the path "Pi" is chosen by the hashing algorithm, retrieve the
label at location "i" in that OutLabel-list and apply the label label at location "i" in that OutLabel-list and apply the label
action of that label on the packet action of that label on the packet.
In the next subsection, we apply the steps in this subsection to a In the next subsection, we apply the steps in this subsection to a
sample scenario. sample scenario.
5.2. Example: Flattening a forwarding chain 5.2. Example: Flattening a forwarding chain.
This example uses a case of inter-AS option C [7] where there are 3 This example uses a case of inter-AS option C [7] where there are 3
levels of hierarchy. Figure 4 illustrates the sample topology. To levels of hierarchy. Figure 4 illustrates the sample topology. To
force 3 levels of hierarchy, the ASBRs on the ingress domain (domain force 3 levels of hierarchy, the ASBRs on the ingress domain (domain
1) advertise the core routers of the egress domain (domain 2) to the 1) advertise the core routers of the egress domain (domain 2) to the
ingress PE (iPE) via BGP-LU [3] instead of redistributing them into ingress PE (iPE) via BGP-LU [3] instead of redistributing them into
the IGP of domain 1. The end result is that the ingress PE (iPE) has the IGP of domain 1. The end result is that the ingress PE (iPE) has
2 levels of recursion for the VPN prefix VPN-IP1 and VPN2-IP2. 2 levels of recursion for the VPN prefix VPN-IP1 and VPN2-IP2.
Domain 1 Domain 2 Domain 1 Domain 2
skipping to change at page 15, line 44 skipping to change at page 15, line 44
<=========== <========= <============ <=========== <========= <============
Advertise ePEx Advertise Redistribute Advertise ePEx Advertise Redistribute
Using iBGP-LU ePEx Using IGP into Using iBGP-LU ePEx Using IGP into
eBGP-LU BGP eBGP-LU BGP
Figure 4 : Sample 3-level hierarchy topology Figure 4 : Sample 3-level hierarchy topology
We will make the following assumptions about connectivity We will make the following assumptions about connectivity
o In "domain 2", both ASBR21 and ASBR22 can reach both ePE1 and o In "domain 2", both ASBR21 and ASBR22 can reach both ePE1 and
ePE2 using the same distance ePE2 using the same distance.
o In "domain 2", only ASBR23 can reach ePE3 o In "domain 2", only ASBR23 can reach ePE3.
o In "domain 1", iPE (the ingress PE) can reach ASBR11, ASBR12, and o In "domain 1", iPE (the ingress PE) can reach ASBR11, ASBR12, and
ASBR13 via IGP using the same distance. ASBR13 via IGP using the same distance.
We will make the following assumptions about the labels We will make the following assumptions about the labels
o The VPN labels advertised by ePE1 and ePE2 for prefix VPN-IP1 are o The VPN labels advertised by ePE1 and ePE2 for prefix VPN-IP1 are
VPN-L11 and VPN-L21, respectively VPN-L11 and VPN-L21, respectively.
o The VPN labels advertised by ePE2 and ePE3 for prefix VPN-IP2 are o The VPN labels advertised by ePE2 and ePE3 for prefix VPN-IP2 are
VPN-L22 and VPN-L32, respectively VPN-L22 and VPN-L32, respectively.
o The labels advertised by ASBR11 to iPE using BGP-LU [3] for the o The labels advertised by ASBR11 to iPE using BGP-LU [3] for the
egress PEs ePE1 and ePE2 are LASBR111(ePE1) and LASBR112(ePE2), egress PEs ePE1 and ePE2 are LASBR111(ePE1) and LASBR112(ePE2),
respectively. respectively.
o The labels advertised by ASBR12 to iPE using BGP-LU [3] for the o The labels advertised by ASBR12 to iPE using BGP-LU [3] for the
egress PEs ePE1 and ePE2 are LASBR121(ePE1) and LASBR122(ePE2), egress PEs ePE1 and ePE2 are LASBR121(ePE1) and LASBR122(ePE2),
respectively respectively.
o The label advertised by ASBR13 to iPE using BGP-LU [3] for the o The label advertised by ASBR13 to iPE using BGP-LU [3] for the
egress PE ePE3 is LASBR13(ePE3) egress PE ePE3 is LASBR13(ePE3).
o The IGP labels advertised by the next hops directly connected to o The IGP labels advertised by the next hops directly connected to
iPE towards ASBR11, ASBR12, and ASBR13 in the core of domain 1 iPE towards ASBR11, ASBR12, and ASBR13 in the core of domain 1
are IGP-L11, IGP-L12, and IGP-L13, respectively. are IGP-L11, IGP-L12, and IGP-L13, respectively.
o Both the routers ASBR21 and ASBR22 of Domain 2 advertise the same o Both the routers ASBR21 and ASBR22 of Domain 2 advertise the same
label LASBR21 and LASBR22 to the egress PEs ePE1 and ePE2, label LASBR21 and LASBR22 to the egress PEs ePE1 and ePE2,
respectively, to the routers ASBR11 and ASBR22 of Domain 1 respectively, to the routers ASBR11 and ASBR22 of Domain 1.
o The router ASBR23 of Domain 2 advertises the label LASBR23 for o The router ASBR23 of Domain 2 advertises the label LASBR23 for
the egress PE ePE3 to the router ASBR13 of Domain 1 the egress PE ePE3 to the router ASBR13 of Domain 1.
Based on these connectivity assumptions and the topology in Figure Based on these connectivity assumptions and the topology in Figure
4, the routing table on iPE is 4, the routing table on iPE is
65000: 198.51.100.0/24 65000: 198.51.100.0/24
via ePE1 (192.0.2.1), VPN Label: VPN-L11 via ePE1 (192.0.2.1), VPN Label: VPN-L11
via ePE2 (192.0.2.2), VPN Label: VPN-L21 via ePE2 (192.0.2.2), VPN Label: VPN-L21
65000: 203.0.113.0/24 65000: 203.0.113.0/24
via ePE1 (192.0.2.2), VPN Label: VPN-L22 via ePE1 (192.0.2.2), VPN Label: VPN-L22
via ePE2 (192.0.2.3), VPN Label: VPN-L32 via ePE2 (192.0.2.3), VPN Label: VPN-L32
skipping to change at page 17, line 35 skipping to change at page 17, line 35
via Core, Label: IGP-L13 via Core, Label: IGP-L13
The diagram in Figure 5 illustrates the forwarding chain in iPE The diagram in Figure 5 illustrates the forwarding chain in iPE
assuming that the forwarding hardware in iPE supports 3 levels of assuming that the forwarding hardware in iPE supports 3 levels of
hierarchy. The leaves corresponding to the ABSRs on domain 1 hierarchy. The leaves corresponding to the ABSRs on domain 1
(ASBR11, ASBR12, and ASBR13) are at the bottom of the hierarchy. (ASBR11, ASBR12, and ASBR13) are at the bottom of the hierarchy.
There are few important points: There are few important points:
o Because the hardware supports the required depth of hierarchy, o Because the hardware supports the required depth of hierarchy,
the sizes of a pathlist equal the size of the label list the sizes of a pathlist equal the size of the label list
associated with the leaves using this pathlist associated with the leaves using this pathlist.
o The index inside the pathlist entry indicates the label that will o The index inside the pathlist entry indicates the label that will
be picked from the Outlabel-List associated with the child leaf be picked from the Outlabel-List associated with the child leaf
if that path is chosen by the forwarding engine hashing function. if that path is chosen by the forwarding engine hashing function.
Outlabel-List Outlabel-List Outlabel-List Outlabel-List
For VPN-IP1 For VPN-IP2 For VPN-IP1 For VPN-IP2
+------------+ +--------+ +-------+ +------------+ +------------+ +--------+ +-------+ +------------+
| VPN-L11 |<---| VPN-IP1| |VPN-IP2|-->| VPN-L22 | | VPN-L11 |<---| VPN-IP1| |VPN-IP2|-->| VPN-L22 |
+------------+ +---+----+ +---+---+ +------------+ +------------+ +---+----+ +---+---+ +------------+
skipping to change at page 20, line 9 skipping to change at page 20, line 9
Figure 6 : Flattening 3 levels to 2 levels of Hierarchy on iPE Figure 6 : Flattening 3 levels to 2 levels of Hierarchy on iPE
Figure 6 represents one way to "flatten" a 3 levels hierarchy into Figure 6 represents one way to "flatten" a 3 levels hierarchy into
two levels. There are few important points: two levels. There are few important points:
o As mentioned in Section 5.1 a flattened pathlist may have label o As mentioned in Section 5.1 a flattened pathlist may have label
lists associated with them. The size of the label list associated lists associated with them. The size of the label list associated
with a flattened pathlist equals the size of the pathlist. Hence with a flattened pathlist equals the size of the pathlist. Hence
it is possible that an implementation includes these label lists it is possible that an implementation includes these label lists
in the flattened pathlist itself in the flattened pathlist itself.
o Again as mentioned in Section 5.1, the size of a flattened o Again as mentioned in Section 5.1, the size of a flattened
pathlist may not be equal to the size of the OutLabel-lists of pathlist may not be equal to the size of the OutLabel-lists of
leaves using the flattened pathlist. So the indices inside a leaves using the flattened pathlist. So the indices inside a
flattened pathlist still indicate the label index in the flattened pathlist still indicate the label index in the
Outlabel-Lists of the leaves using that pathlist. Because the Outlabel-Lists of the leaves using that pathlist. Because the
size of the flattened pathlist may be different from the size of size of the flattened pathlist may be different from the size of
the OutLabel-lists of the leaves, the indices may be repeated. the OutLabel-lists of the leaves, the indices may be repeated.
o Let's take a look at the flattened pathlist used by the prefix o Let's take a look at the flattened pathlist used by the prefix
"VPN-IP2", The pathlist associated with the prefix "VPN-IP2" has "VPN-IP2", The pathlist associated with the prefix "VPN-IP2" has
three entries. three entries.
o The first and second entry have index "0". This is because o The first and second entry have index "0". This is because
both entries correspond to ePE2. Hence when hashing performed both entries correspond to ePE2. Hence when hashing performed
by the forwarding engine results in using first or the second by the forwarding engine results in using first or the second
entry in the pathlist, the forwarding engine will pick the entry in the pathlist, the forwarding engine will pick the
correct VPN label "VPN-L22", which is the label advertised by correct VPN label "VPN-L22", which is the label advertised by
ePE2 for the prefix "VPN-IP2" ePE2 for the prefix "VPN-IP2".
o The third entry has the index "1". This is because the third o The third entry has the index "1". This is because the third
entry corresponds to ePE3. Hence when the hashing is performed entry corresponds to ePE3. Hence when the hashing is performed
by the forwarding engine results in using the third entry in by the forwarding engine results in using the third entry in
the flattened pathlist, the forwarding engine will pick the the flattened pathlist, the forwarding engine will pick the
correct VPN label "VPN-L32", which is the label advertised by correct VPN label "VPN-L32", which is the label advertised by
"ePE3" for the prefix "VPN-IP2" "ePE3" for the prefix "VPN-IP2".
Now let's try and apply the forwarding steps in Section 4 together Now let's try and apply the forwarding steps in Section 4 together
with the additional step in Section 5.1 to the flattened forwarding with the additional step in Section 5.1 to the flattened forwarding
chain illustrated in Figure 6. chain illustrated in Figure 6.
o Suppose a packet arrives at "iPE" and matches the VPN prefix o Suppose a packet arrives at "iPE" and matches the VPN prefix
"VPN-IP2" "VPN-IP2".
o The forwarding engine walks to the parent of the "VPN-IP2", which o The forwarding engine walks to the parent of the "VPN-IP2", which
is the flattened pathlist and applies a hashing algorithm to pick is the flattened pathlist and applies a hashing algorithm to pick
a path a path.
o Suppose the hashing by the forwarding engine picks the second o Suppose the hashing by the forwarding engine picks the second
path in the flattened pathlist associated with the leaf "VPN- path in the flattened pathlist associated with the leaf "VPN-
IP2". IP2".
o Because the second path has the index "0", the label "VPN-L22" is o Because the second path has the index "0", the label "VPN-L22" is
pushed on the packet pushed on the packet.
o Next the forwarding engine picks the second label from the o Next the forwarding engine picks the second label from the
Outlabel-Array associated with the flattened pathlist. Hence the Outlabel-Array associated with the flattened pathlist. Hence the
next label that is pushed is "LASBR122(ePE2)" next label that is pushed is "LASBR122(ePE2)".
o The forwarding engine now moves to the parent of the flattened o The forwarding engine now moves to the parent of the flattened
pathlist corresponding to the second path. The parent is the IGP pathlist corresponding to the second path. The parent is the IGP
label leaf corresponding to "ASBR12" label leaf corresponding to "ASBR12".
o So the packet is forwarded towards the ASBR "ASBR12" and the IGP o So the packet is forwarded towards the ASBR "ASBR12" and the IGP
label at the top will be "L12" label at the top will be "L12".
Based on the above steps, a packet arriving at iPE and destined to Based on the above steps, a packet arriving at iPE and destined to
the prefix VPN-L22 reaches its destination as follows the prefix VPN-L22 reaches its destination as follows:
o iPE sends the packet along the shortest path towards ASBR12 with o iPE sends the packet along the shortest path towards ASBR12 with
the following label stack starting from the top: {L12, the following label stack starting from the top: {L12,
LASBR122(ePE2), VPN-L22}. LASBR122(ePE2), VPN-L22}.
o The penultimate hop of ASBR12 pops the top label "L12". Hence the o The penultimate hop of ASBR12 pops the top label "L12". Hence the
packet arrives at ASBR12 with the label stack {LASBR122(ePE2), packet arrives at ASBR12 with the label stack {LASBR122(ePE2),
VPN-L22} where "LASBR12(ePE2)" is the top label. VPN-L22} where "LASBR12(ePE2)" is the top label.
o ASBR12 swaps "LASBR122(ePE2)" with the label "LASBR22(ePE2)", o ASBR12 swaps "LASBR122(ePE2)" with the label "LASBR22(ePE2)",
skipping to change at page 23, line 51 skipping to change at page 23, line 51
attribute to its iBGP peers. attribute to its iBGP peers.
In the first case, the rest of iBGP peers will remain unaware of the In the first case, the rest of iBGP peers will remain unaware of the
link failure and will continue to forward traffic to the edge node link failure and will continue to forward traffic to the edge node
until the edge node attached to the failed link withdraws the BGP until the edge node attached to the failed link withdraws the BGP
prefixes. If the destination prefixes are multi-homed to another prefixes. If the destination prefixes are multi-homed to another
iBGP peer, say ePE2, then FIB manager on the edge router detecting iBGP peer, say ePE2, then FIB manager on the edge router detecting
the link failure applies the following steps: the link failure applies the following steps:
o FIB manager backwalks to the BGP pathlists marks the path through o FIB manager backwalks to the BGP pathlists marks the path through
the failed link to the external peer as unresolved the failed link to the external peer as unresolved.
o Hence traffic will be forwarded used the backup path towards ePE2 o Hence traffic will be forwarded used the backup path towards
ePE2.
o For labeled traffic o For labeled traffic
o The Outlabel-List attached to the BGP leaf already contains o The Outlabel-List attached to the BGP leaf already contains
an entry corresponding to the backup path. an entry corresponding to the backup path.
o The label entry in OutLabel-List corresponding to the o The label entry in OutLabel-List corresponding to the
internal path to backup egress PE has swap action to the internal path to backup egress PE has swap action to the
label advertised by backup egress PE label advertised by backup egress PE.
o For an arriving label packet (e.g. VPN), the top label is o For an arriving label packet (e.g. VPN), the top label is
swapped with the label advertised by backup egress PE and the swapped with the label advertised by backup egress PE and the
packet is sent towards that backup egress PE packet is sent towards that backup egress PE.
o For unlabeled traffic, packets are simply redirected towards o For unlabeled traffic, packets are simply redirected towards
backup egress PE. backup egress PE.
In the second case where the edge router uses the IP address of the In the second case where the edge router uses the IP address of the
failed link as the BGP next-hop, the edge router will still perform failed link as the BGP next-hop, the edge router will still perform
the previous steps. But, unlike the case of next-hop self, IGP on the previous steps. But, unlike the case of next-hop self, IGP on
failed edge node informs the rest of the iBGP peers that IP address failed edge node informs the rest of the iBGP peers that IP address
of the failed link is no longer reachable. Hence the FIB manager on of the failed link is no longer reachable. Hence the FIB manager on
iBGP peers will delete the IGP leaf corresponding to the IP prefix iBGP peers will delete the IGP leaf corresponding to the IP prefix
skipping to change at page 26, line 47 skipping to change at page 26, line 47
the number of BGP destinations impacted by the failure. Sub-50msec the number of BGP destinations impacted by the failure. Sub-50msec
is thus possible even if millions of BGP routes are impacted. is thus possible even if millions of BGP routes are impacted.
When the failure is remote (a remote IGP failure not impacting the When the failure is remote (a remote IGP failure not impacting the
BGP next-hop or a remote BGP next-hop failure), an alternate path is BGP next-hop or a remote BGP next-hop failure), an alternate path is
activated upon IGP convergence. All the impacted BGP destinations activated upon IGP convergence. All the impacted BGP destinations
benefit from a working alternate path as soon as the IGP convergence benefit from a working alternate path as soon as the IGP convergence
occurs for their impacted BGP next-hop even if millions of BGP occurs for their impacted BGP next-hop even if millions of BGP
routes are impacted. routes are impacted.
Appendix A puts the BGP PIC benefits in perspective by providing Appendix A puts the BGP-PIC benefits in perspective by providing
some results using actual numbers. some results using actual numbers.
7.3. Automated 7.3. Automated
The BGP PIC solution does not require any operator involvement. The The BGP-PIC solution does not require any operator involvement. The
process is entirely automated as part of the FIB implementation. process is entirely automated as part of the FIB implementation.
The salient points enabling this automation are: The salient points enabling this automation are:
o Extension of the BGP Best Path to compute more than one primary o Extension of the BGP Best Path to compute more than one primary
([10]and [11]) or backup BGP next-hop ([5] and [12]). ([10]and [11]) or backup BGP next-hop ([5] and [12]).
o Sharing of BGP Path-list across BGP destinations with same o Sharing of BGP Path-list across BGP destinations with same
primary and backup BGP next-hop primary and backup BGP next-hop.
o Hierarchical indirection and dependency between BGP pathlist and o Hierarchical indirection and dependency between BGP pathlist and
IGP pathlist IGP pathlist.
7.4. Incremental Deployment 7.4. Incremental Deployment
As soon as one router supports BGP PIC solution, it benefits from As soon as one router supports BGP-PIC solution, it benefits from
all its benefits without any requirement for other routers to all its benefits without any requirement for other routers to
support BGP PIC. support BGP-PIC.
8. Security Considerations 8. Security Considerations
The behavior described in this document is internal functionality The behavior described in this document is internal functionality
to a router that result in significant improvement to convergence to a router that result in significant improvement to convergence
time as well as reduction in CPU and memory used by FIB while not time as well as reduction in CPU and memory used by FIB while not
showing change in basic routing and forwarding functionality. As showing change in basic routing and forwarding functionality. As
such no additional security risk is introduced by using the such no additional security risk is introduced by using the
mechanisms proposed in this document. mechanisms proposed in this document.
skipping to change at page 28, line 53 skipping to change at page 28, line 53
[11] R. Raszuk, R. Fernando, K. Patel, D. McPherson, K. Kumaki, [11] R. Raszuk, R. Fernando, K. Patel, D. McPherson, K. Kumaki,
"Distribution of diverse BGP paths", RFC 6774, November 2012 "Distribution of diverse BGP paths", RFC 6774, November 2012
[12] P. Mohapatra, R. Fernando, C. Filsfils, and R. Raszuk, "Fast [12] P. Mohapatra, R. Fernando, C. Filsfils, and R. Raszuk, "Fast
Connectivity Restoration Using BGP Add-path", draft-pmohapat- Connectivity Restoration Using BGP Add-path", draft-pmohapat-
idr-fast-conn-restore-03, Jan 2013 idr-fast-conn-restore-03, Jan 2013
[13] A. Bashandy, C. Filsfils, S. Previdi, B. Decraene, S. [13] A. Bashandy, C. Filsfils, S. Previdi, B. Decraene, S.
Litkowski, M. Horneffer, R. Shakir, "Segment Routing with MPLS Litkowski, M. Horneffer, R. Shakir, "Segment Routing with MPLS
data plane", draft-ietf-spring-segment-routing-mpls-12 (work data plane", RFC 8660, December 2019
in progress), February 2018
[14] A. Bashandy, C. Filsfils, B. Decraene, P. Francois, " Topology [14] S. Litkowski, A. Bashandy, C. Filsfils, B. Decraene, P.
Independent Fast Reroute using Segment Routing", draft- Francois, D. Voyer, F. Clad, P. Camarillo" Topology
bashandy-rtgwg-segment-routing-ti-lfa-02 (work in progress), Independent Fast Reroute using Segment Routing", draft-ietf-
August 2018 rtgwg-segment-routing-ti-lfa-02 (work in progress), January
2020
[15] M. Shand and S. Bryant, "IP Fast Reroute Framework", RFC 5714, [15] M. Shand and S. Bryant, "IP Fast Reroute Framework", RFC 5714,
January 2010 January 2010
[16] S. Bryant, C. Filsfils, S. Previdi, M. Shand, N So, " Remote [16] S. Bryant, C. Filsfils, S. Previdi, M. Shand, N So, " Remote
Loop-Free Alternate (LFA) Fast Reroute (FRR)", RFC 7490 April Loop-Free Alternate (LFA) Fast Reroute (FRR)", RFC 7490 April
2015 2015
[17] A. Atlas, C. Bowers, G. Enyedi, " An Architecture for IP/LDP [17] A. Atlas, C. Bowers, G. Enyedi, " An Architecture for IP/LDP
Fast-Reroute Using Maximally Redundant Trees", RFC 7812, June Fast-Reroute Using Maximally Redundant Trees", RFC 7812, June
skipping to change at page 29, line 33 skipping to change at page 29, line 34
Special thanks to Neeraj Malhotra, Yuri Tsier for the valuable Special thanks to Neeraj Malhotra, Yuri Tsier for the valuable
help help
Special thanks to Bruno Decraene for the valuable comments Special thanks to Bruno Decraene for the valuable comments
This document was prepared using 2-Word-v2.0.template.dot. This document was prepared using 2-Word-v2.0.template.dot.
Authors' Addresses Authors' Addresses
Ahmed Bashandy Ahmed Bashandy
Arrcus Individual Contributor
Email: abashandy.ietf@gmail.com Email: abashandy.ietf@gmail.com
Clarence Filsfils Clarence Filsfils
Cisco Systems Cisco Systems
Brussels, Belgium Brussels, Belgium
Email: cfilsfil@cisco.com Email: cfilsfil@cisco.com
Prodosh Mohapatra Prodosh Mohapatra
Sproute Networks Sproute Networks
Email: mpradosh@yahoo.com Email: mpradosh@yahoo.com
Appendix A. Perspective Appendix A. Perspective
The following table puts the BGP PIC benefits in perspective The following table puts the BGP-PIC benefits in perspective
assuming assuming
o 1M impacted BGP prefixes o 1M impacted BGP prefixes
o IGP convergence ~ 500 msec o IGP convergence ~ 500 msec
o local protection ~ 50msec o local protection ~ 50msec
o FIB Update per BGP destination ~ 100usec conservative, o FIB Update per BGP destination ~ 100usec conservative,
skipping to change at page 30, line 38 skipping to change at page 30, line 38
Local BGP Failure 100 to 200sec 50msec Local BGP Failure 100 to 200sec 50msec
Remote IGP Failure 10 to 100sec 500msec Remote IGP Failure 10 to 100sec 500msec
Local BGP Failure 100 to 200sec 500msec Local BGP Failure 100 to 200sec 500msec
Upon local IGP next-hop failure or remote IGP next-hop failure, the Upon local IGP next-hop failure or remote IGP next-hop failure, the
existing primary BGP next-hop is intact and usable hence the existing primary BGP next-hop is intact and usable hence the
resiliency only depends on the ability of the FIB mechanism to resiliency only depends on the ability of the FIB mechanism to
reflect the new path to the BGP next-hop to the depending BGP reflect the new path to the BGP next-hop to the depending BGP
destinations. Without BGP PIC, a conservative back-of-the-envelope destinations. Without BGP-PIC, a conservative back-of-the-envelope
estimation for this FIB update is 100usec per BGP destination. An estimation for this FIB update is 100usec per BGP destination. An
optimistic estimation is 10usec per entry. optimistic estimation is 10usec per entry.
Upon local BGP next-hop failure or remote BGP next-hop failure, Upon local BGP next-hop failure or remote BGP next-hop failure,
without the BGP PIC mechanism, a new BGP Best-Path needs to be without the BGP-PIC mechanism, a new BGP Best-Path needs to be
recomputed and new updates need to be sent to peers. This depends on recomputed and new updates need to be sent to peers. This depends on
BGP processing time that will be shared between best-path BGP processing time that will be shared between best-path
computation, RIB update and peer update. A conservative back-of-the- computation, RIB update and peer update. A conservative back-of-the-
envelope estimation for this is 200usec per BGP destination. An envelope estimation for this is 200usec per BGP destination. An
optimistic estimation is 100usec per entry. optimistic estimation is 100usec per entry.
 End of changes. 82 change blocks. 
107 lines changed or deleted 100 lines changed or added

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