BGP Prefix Independent Convergence

Status of This Memo

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

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

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

This Internet-Draft will expire on 19 August 2026.¶

Copyright Notice

Copyright (c) 2026 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 (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

BGP speakers exchange reachability information about prefixes [RFC4271]. For labeled address families, an edge router assigns local labels to prefixes and associates the local label with each advertised prefix using technologies such as L3VPN [RFC4364], 6PE [RFC4798], and Softwire [RFC5565] using BGP label unicast (BGP-LU) technique [RFC8277]. A BGP speaker then applies the path selection steps to choose the best route. In modern networks, it is not uncommon to have a prefix reachable via multiple edge routers. Multiple techniques have been described to allow for BGP to advertise more than one path for a given prefix [I-D.ietf-idr-best-external][RFC7911][RFC6774], whether in the form of equal cost multipath or primary-backup. Another common and widely deployed scenario is L3VPN with multi-homed VPN sites with unique Route Distinguisher.¶

This document describes a hierarchical and shared forwarding chain organization that allows traffic to be restored to a pre-calculated alternative equal cost path or backup path in a time period that does not depend on the number of BGP prefixes. The technique relies on internal router behavior that is completely transparent to the operator and can be incrementally deployed and enabled with zero operator intervention. In other words, once it is implemented and deployed on a router, nothing is required from the operator to make it work. It is noteworthy to mention that this document describes a Forwarding Information Base (FIB) architecture that can be implemented in both hardware and/or software, although we refer to hardware implementation in most of the cases because of the additional complexity and performance requirements associated with hardware implementations.¶

It should be noted that although BGP is used for routes calculation in this document, the underlying principles of hierarchical forwarding, recursive resolution are not BGP specific. These mechanisms apply equally to routes computed by other routing protocols as well. The benefits of BGP-PIC are tied to the forwarding plane design rather than to the BGP protocol.¶

2. Overview

The idea of BGP-PIC is based on the following two pillars to make convergence independent of the number of prefixes:¶

• A shared hierarchical forwarding chain: Multiple prefixes reference common next-hop and path objects arranged in a hierarchy, so that changes to a single shared object affect all dependent prefixes simultaneously.¶

• A forwarding plane with multiple levels of indirection: The forwarding plane supports recursive resolution and pointer-based forwarding entries, allowing failover by updating a small number of shared objects rather than per-prefix state.¶

A forwarding plane with shared, hierarchical forwarding chains with maximal object reuse can reroute a large number of destinations by modifying only a small set of shared objects. This enables convergence in a time frame that does not depend on the number of affected destinations. For example, if an IGP prefix used to resolve a recursive next-hop changes, there is no need to update the potentially large number of BGP NLRIs that reference that next-hop.¶

 +--------------------------------+
 |                                |
 |                               ePE2 (IGP-IP1 192.0.2.1, Loopback)
 |                                |  \
 |                                |   \
 |                                |    \
iPE                               |    CE....VRF "Blue", ASN 65000
 |                                |    /   (VPN-IP1 198.51.100.0/24)
 |                                |   /    (VPN-IP2 203.0.113.0/24)
 |   LDP/Segment-Routing Core     |  /
 |                               ePE1 (IGP-IP2 192.0.2.2, Loopback)
 |                                |
 +--------------------------------+
Figure 1: VPN prefix reachable via multiple PEs

       65000: 198.51.100.0/24
            via ePE1 (192.0.2.1), VPN Label: VPN-L11
            via ePE2 (192.0.2.2), VPN Label: VPN-L21

       65000: 203.0.113.0/24
            via ePE1 (192.0.2.1), VPN Label: VPN-L12
            via ePE2 (192.0.2.2), VPN Label: VPN-L22

IP Leaf:  pathlist:       IP Leaf:       pathlist:
--------  +-----------+   --------
          |           |                 +-------------+
          |BGP-NH1------->IGP-IP1 ----->|             |
VPN-IP1-->|           |       |         | IGP-NH1,I1----->adjacency1
  |       |BGP-NH2------->... |         |             |
  |       |           |       |         | IGP-NH2,I2----->adjacency2
  |       +-----------+       |         |             |
  |                           |         +-------------+
  |                           |
  v                           v
OutLabel-List:             OutLabel-List:
+--------+                 +--------+
|VPN-L11 |                 |IGP-L11 |
|VPN-L21 |                 |IGP-L12 |
+--------+                 +--------+

      65000: 2001:DB8:1::/48
          via ePE1 (65000: 2001:DB8:192::1), VPN Label: VPN6-L11
          via ePE2 (65000: 2001:DB8:192::2), VPN Label: VPN6-L21

      65000: 2001:DB8:2:/48
          via ePE1 (65000: 2001:DB8:192::1), VPN Label: VPN6-L12
          via ePE2 (65000: 2001:DB8:192::2), VPN Label: VPN6-L22

      65000: 2001:DB8:192::1/128
          via Core, Label:    IGP6-L11
          via Core, Label:    IGP6-L12

      65000: 2001:DB8:192::2/128
          via Core, Label:    IGP6-L21
          via Core, Label:    IGP6-L22

3. Constructing the Shared Hierarchical Forwarding Chain

This section describes how the forwarding chain is constructed using a hierarchical shared model, as introduced in Section 2. Section 3.1 details the construction steps, and Section 3.2 provides an illustrative example.¶

                 BGP OutLabel-List
                     +---------+
  VPN-L11            |Unlabeled|
(Label-leaf)---+---->+---------+
               |     | VPN-L21 |
               v     | (swap)  |
               |     +---------+
               |
               |
               |
               |
               |                    BGP pathlist
               |                   +--------------+
               |                   |              |
               |                   |    CE-NH   ------->(to the CE)
               |                   | path-index=0 |
  VPN-IP1 -----+------------------>+--------------+
(IP leaf)                          |   VPN-NH2    |
     |                             |   (backup) ------->IGP Leaf
     |                             | path-index=1 |   (Towards ePE2)
     |                             +--------------+
     |
     |           BGP OutLabel-List
     |              +---------+
     |              |Unlabeled|
     +------------->+---------+
                    | VPN-L21 |
                    | (push)  |
                    +---------+

4. Forwarding Behavior

This section explains how the forwarding plane uses the hierarchical shared forwarding chain to forward a packet.¶

When a packet arrives at a router, assume it matches a leaf. If not, the packet is handled according to the local policy (such as silently dropping the packet), which is beyond the scope of this document. A labeled packet matches a label leaf while an IP packet matches an IP leaf. The forwarding engines walks the forwarding chain starting from the leaf until the walk terminates on an adjacency. Thus when a packet arrives, the chain is walked as follows:¶

1. Lookup the leaf based on the destination address or the label at the top of the packet.¶

2. Retrieve the parent pathlist of the leaf.¶

3. Pick an outgoing path "Pi" from the list of resolved pic- paths in the pathlist. The method by which the outgoing path is picked is beyond the scope of this document (e.g. flow- preserving hash exploiting entropy within the MPLS stack and IP header). Let the "path-index" of the outgoing path "Pi" be "j". Remember that, as described in the definition of the term pathlist in Section 1.1, the path-index of a path may not always be identical the position of the path in the pathlist.¶

4. If the prefix is labeled, use the "path-index" "j" to retrieve the label "Lj" stored position j in the OutLabel-List and 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 mentioned in Section 1.1 the value of the "path-index" stored in the pic- path may not necessarily be the same value of the location of the path in the pathlist.¶

5. If the chosen path "Pi" is recursive, move to its parent prefix and go to step 2.¶

6. If the chosen path is non-recursive move to its parent adjacency.¶

7. Encapsulate the packet in the layer string specified by the adjacency and send the packet out.¶

Let's apply the above forwarding steps to the forwarding chain depicted in Figure 2 in Section 2. Suppose a packet arrives at ingress PE iPE from an external neighbor. Assume the packet matches the VPN prefix VPN-IP1. While walking the forwarding chain, the forwarding engine applies a hashing algorithm to choose the path and the hashing at the BGP level chooses the first path in the BGP pathlist while the hashing at the IGP level yields the second path in the IGP pathlist. In that case, the packet will be sent out of interface I2 with the label stack "IGP-L12,VPN-L11".¶

5. Handling Platforms with Limited Levels of Hierarchy

This section describes the construction of the forwarding chain if a platform does not support the number of recursion levels required to resolve the NLRIs. There are two main design objectives.¶

• Being able to reduce the number of hierarchical levels from any arbitrary value to a smaller arbitrary value that can be supported by the forwarding engine.¶

• Minimal modifications to the forwarding algorithm due to such reduction.¶

  Appendix B provides details on how to handle limited hardware¶

  capabilities.

6. Forwarding Chain Adjustment at a Failure

The hierarchical and shared structure of the forwarding chain explained in the previous section allows modifying a small number of forwarding chain objects to re-route traffic to a pre-calculated equal-cost or backup path without the need to modify the possibly very large number of BGP prefixes. This section goes over various core and edge failure scenarios to illustrate how the FIB manager can utilize the forwarding chain structure to achieve BGP prefix independent convergence.¶

7. Operational Properties

8. Security Considerations

The behavior described in this document is internal functionality to a router that result in significant improvement to convergence time as well as reduction in CPU and memory used by FIB while not showing change in basic routing and forwarding functionality. As such no additional security risk is introduced by using the mechanisms described in this document.¶

9. IANA Considerations

This document has no IANA actions.¶

Appendix A. Acknowledgments

Special thanks to Neeraj Malhotra and Yuri Tsier for the valuable help¶

Special thanks to Bruno Decraene, Theresa Enghardt, Ines Robles, Luc Andre Burdet, and Alvaro Retana for the valuable comments¶

This document was prepared using 2-Word-v2.0.template.dot.¶

Appendix B. Handling Platforms with Limited Levels of Hierarchy

This section provides additional details on how to handle platforms with limited number of hierarchical levels.¶

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 an OutLabel-list <L1, L2,..., Ln>. Suppose the path Pi is a recursive path that resolves via a prefix represented by the leaf "R2". The leaf "R2" itself is pointing to a pathlist consisting of the paths <Q1, Q2,..., Qm>.¶

If the platform supports the number of hierarchy levels of the forwarding chain, then a packet that uses the path "Pi" will be forwarded according to the steps in Section 4.¶

Suppose the platform cannot support the number of hierarchy levels in the forwarding chain. FIB manager needs to reduce the number of hierarchy levels when programming the forwarding chain in the FIB. The idea of reducing the number of hierarchy levels is to "flatten" two chain levels into a single level. The "flattening" steps are as follows¶

1. FIB manager walks to the parent of "Pi", which is the leaf "R2".¶

2. FIB manager extracts the parent pathlist of the leaf "R2", which is <Q1, Q2,..., Qm>.¶

3. FIB manager also extracts the OutLabel-list of R2 associated with the leaf "R2". Remember that the OutLabel-list of R2 is <L1, L2,..., Lm>.¶

4. FIB manager replaces the path "Pi", with the list of pic- paths <Q1, Q2,..., Qm>.¶

5. Hence the path list <P1, P2,..., Pn> now becomes "<P1,
   P2,...,Pi-1, Q1, Q2,..., Qm, Pi+1, Pn>.

1. The path-index stored inside the locations "Q1", "Q2", ..., "Qm" must all be "i" because the index "i" refers to the label "Li" associated with leaf "R1".¶

2. FIB manager attaches an OutLabel-list with the new pathlist as follows: <Unlabeled,..., Unlabeled, L1, L2,..., Lm, Unlabeled, ..., Unlabeled>. The size of the label list associated with the flattened pathlist equals the size of the pathlist. Thus there is a 1-1 mapping between every path in the "flattened" pathlist and the OutLabel-list associated with it.¶

It is noteworthy to mention that the labels in the OutLabel-list associated with the "flattened" pathlist may be stored in the same memory location as the path itself to avoid additional memory access.¶

The same steps can be applied to all paths in the pathlist <P1, P2,..., Pn> so that all paths are "flattened" thereby reducing the number of hierarchical levels by one. Note that that "flattening" a pathlist pulls in all paths of the parent pic- paths, a desired feature to utilize all paths at all levels. A platform that has a limit on the number of paths in a pathlist for any given leaf may choose to reduce the number paths using methods that are beyond the scope of this document.¶

The steps can be recursively applied to other paths at the same levels or other levels to recursively reduce the number of hierarchical levels to an arbitrary value so as to accommodate the capability of the forwarding engine.¶

Because a flattened pathlist may have an associated OutLabel-list the forwarding behavior has to be slightly modified. The modification is done by adding the following step right after step 4 in Section 4.¶

1. If there is an OutLabel-list associated with the pathlist, then if the path "Pi" is chosen by the hashing algorithm, retrieve the label at location "i" in that OutLabel-list and apply the label action of that label on the packet.¶

The steps in this Section to are applied to an example in the next Section.¶

Appendix C. Example: Flattening a forwarding chain.

This example uses a case of inter-AS option C [RFC4364] where there are 3 levels of hierarchy. Figure 4 illustrates the sample topology. The Autonomous System Border Routers (ASBRs) on the ingress domain (Domain 1) use BGP to advertise the core routers (ASBRs and ePEs) of the egress domain (Domain 2) to the iPE. The end result is that the ingress PE (iPE) has 2 levels of recursion for the VPN prefixes VPN- IP1 and VPN-IP2.¶

    Domain 1                 Domain 2
+-------------+          +-------------+
|             |          |             |
| LDP/SR Core |          | LDP/SR core |
|             |          |             |
|     (192.0.2.4)        |             |
|         ASBR11-------ASBR21........ePE1(192.0.2.1)
|             | \      / |   .      .  |\
|             |  \    /  |    .    .   | \
|             |   \  /   |     .  .    |  \
|             |    \/    |      ..     |   \VPN-IP1(198.51.100.0/24)
|             |    /\    |      . .    |   /VRF "Blue" ASN: 65000
|             |   /  \   |     .   .   |  /
|             |  /    \  |    .     .  | /
|             | /      \ |   .       . |/
iPE        ASBR12-------ASBR22........ePE2 (192.0.2.2)
|     (192.0.2.5)        |             |\
|             |          |             | \
|             |          |             |  \
|             |          |             |   \VRF "Blue" ASN: 65000
|             |          |             |   /VPN-IP2(203.0.113.0/24)
|             |          |             |  /
|             |          |             | /
|             |          |             |/
|         ASBR13-------ASBR23........ePE3(192.0.2.3)
|     (192.0.2.6)        |             |
|             |          |             |
|             |          |             |
+-------------+          +-------------+
 <===========  <=========  <============
Advertise ePEx  Advertise   Redistribute
Using IBGP-LU   ePEx Using  ePEx routes
                 EBGP-LU      into BGP

The following assumptions about connectivity are made:¶

• In "Domain 2", both ASBR21 and ASBR22 can reach both ePE1 and ePE2 using the same metric.¶

• In "Domain 2", only ASBR23 can reach ePE3.¶

• In "Domain 1", iPE (the ingress PE) can reach ASBR11, ASBR12, and ASBR13 via IGP using the same metric.¶

The following assumptions are made about the labels:¶

• The VPN labels advertised by ePE1 and ePE2 for prefix VPN-IP1 are VPN-L11 and VPN-L21, respectively.¶

• The VPN labels advertised by ePE2 and ePE3 for prefix VPN-IP2 are VPN-L22 and VPN-L32, respectively.¶

• The labels advertised by ASBR11 to iPE using BGP-LU for the egress PEs ePE1 and ePE2 are LASBR111(ePE1) and LASBR112(ePE2), respectively.¶

• The labels advertised by ASBR12 to iPE using BGP-LU for the egress PEs ePE1 and ePE2 are LASBR121(ePE1) and LASBR122(ePE2), respectively.¶

• The label advertised by ASBR13 to iPE using BGP-LU for the egress PE ePE3 is LASBR13(ePE3).¶

• The IGP labels advertised by the next hops directly connected to iPE towards ASBR11, ASBR12, and ASBR13 in the core of domain 1 are IGP-L11, IGP-L12, and IGP-L13, respectively.¶

• Both the routers ASBR21 and ASBR22 of Domain 2 advertise the same label LASBR21 and LASBR22 for the egress PEs ePE1 and ePE2, respectively, to the routers ASBR11 and ASBR22 of Domain 1.¶

• The router ASBR23 of Domain 2 advertises the label LASBR23 for the egress PE ePE3 to the router ASBR13 of Domain 1.¶

Based on these connectivity assumptions and the topology in Figure 4, the routing table on iPE is¶

       65000: 198.51.100.0/24
            via ePE1 (192.0.2.1), VPN Label: VPN-L11
            via ePE2 (192.0.2.2), VPN Label: VPN-L21
       65000: 203.0.113.0/24
            via ePE2 (192.0.2.2), VPN Label: VPN-L22
            via ePE3 (192.0.2.3), VPN Label: VPN-L32

• 192.0.2.1/32 (ePE1)

  via ASBR11, Label: LASBR111(ePE1) via ASBR12, Label: LASBR121(ePE1)¶

  192.0.2.2/32 (ePE2)

  via ASBR11, Label: LASBR112(ePE2) via ASBR12, Label: LASBR122(ePE2)¶

  192.0.2.3/32 (ePE3)

  Via ASBR13, Label: LASBR13(ePE3)¶

       192.0.2.4/32 (ASBR11)
            via Core, Label:    IGP-L11
       192.0.2.5/32 (ASBR12)
            via Core, Label:    IGP-L12
       192.0.2.6/32 (ASBR13)
            via Core, Label:    IGP-L13

The diagram in Figure 5 illustrates the forwarding chain in iPE assuming that the forwarding hardware in iPE supports 3 levels of hierarchy. The leaves corresponding to the ASBRs on domain 1 (ASBR11, ASBR12, and ASBR13) are at the bottom of the hierarchy. There are few important points:¶

• Because the hardware supports the required depth of hierarchy, the sizes of a pathlist equal the size of the label list associated with the leaves using this pathlist.¶

• The path-index inside the pathlist entry indicates the label that will be picked from the OutLabel-List associated with the child leaf if that path is chosen by the forwarding engine hashing function.¶

OutLabel-List                                      OutLabel-List
  For VPN-IP1                                         For VPN-IP2
+------------+    +--------+           +-------+   +------------+
|  VPN-L11   |<---| VPN-IP1|           |VPN-IP2|-->|  VPN-L22   |
+------------+    +---+----+           +---+---+   +------------+
|  VPN-L21   |        |                    |       |  VPN-L32   |
+------------+        |                    |       +------------+
                      |                    |
                      V                    V
                 +---+---+            +---+---+
                 | 0 | 1 |            | 0 | 1 |
                 +-|-+-\-+            +-/-+-\-+
                   |    \              /     \
                   |     \            /       \
                   |      \          /         \
                   |       \        /           \
                   v        \      /             \
              +-----+       +-----+             +-----+
         +----+ ePE1|       |ePE2 +-----+       | ePE3+-----+
         |    +--+--+       +-----+     |       +--+--+     |
         v       |            /         v          |        v
+--------------+ |           /   +--------------+  | +-------------+
|LASBR111(ePE1)| |          /    |LASBR112(ePE2)|  | |LASBR13(ePE3)|
+--------------+ |         /     +--------------+  | +-------------+
|LASBR121(ePE1)| |        /      |LASBR122(ePE2)|  | OutLabel-List
+--------------+ |       /       +--------------+  |    For ePE3
OutLabel-List    |      /        OutLabel-List     |
    For ePE1     |     /           For ePE2        |
                 |    /                            |
                 |   /                             |
                 |  /                              |
                 v v                               v
             +---+---+  Shared pathlist          +---+  pathlist
             | 0 | 1 | For ePE1 and ePE2         | 0 |  For ePE3
             +-|-+-\-+                           +-|-+
               |    \                              |
               |     \                             |
               |      \                            |
               |       \                           |
               v        v                          v
            +------+    +------+               +------+
        +---+ASBR11|    |ASBR12+--+            |ASBR13+---+
        |   +------+    +------+  |            +------+   |
        v                         v                       v
   +-------+                  +-------+              +-------+
   |IGP-L11|                  |IGP-L12|              |IGP-L13|
   +-------+                  +-------+              +-------+

Now suppose the hardware on iPE (the ingress PE) supports 2 levels of hierarchy only. In that case, the 3-levels forwarding chain in Figure 5 needs to be "flattened" into 2 levels only.¶

OutLabel-List                                  OutLabel-List
  For VPN-IP1                                    For VPN-IP2
+------------+    +-------+      +-------+     +------------+
|  VPN-L11   |<---|VPN-IP1|      | VPN-IP2|--->|  VPN-L22   |
+------------+    +---+---+      +---+---+     +------------+
|  VPN-L21   |        |              |         |  VPN-L32   |
+------------+        |              |         +------------+
                      |              |
                      |              |
                      |              |
       Flattened      |              |  Flattened
       pathlist       V              V   pathlist
                 +===+===+        +===+===+===+     +==============+
        +--------+ 0 | 1 |        | 0 | 0 | 1 +---->|LASBR112(ePE2)|
        |        +=|=+=\=+        +=/=+=/=+=\=+     +==============+
        v          |    \          /   /     \      |LASBR122(ePE2)|
 +==============+  |     \  +-----+   /       \     +==============+
 |LASBR111(ePE1)|  |      \/         /         \    |LASBR13(ePE3) |
 +==============+  |      /\        /           \   +==============+
 |LASBR121(ePE1)|  |     /  \      /             \
 +==============+  |    /    \    /               \
                   |   /      \  /                 \
                   |  /       +  +                  \
                   |  +       |  |                   \
                   |  |       |  |                    \
                   v  v       v  v                     v
                 +------+    +------+              +------+
            +----|ASBR11|    |ASBR12+---+          |ASBR13+---+
            |    +------+    +------+   |          +------+   |
            v                           v                     v
        +-------+                  +-------+              +-------+
        |IGP-L11|                  |IGP-L12|              |IGP-L13|
        +-------+                  +-------+              +-------+

Figure 6 represents one way to "flatten" a 3 levels hierarchy into two levels. There are a few important points:¶

• As mentioned in Appendix B, a flattened pathlist may have label lists associated with them. The size of the label list associated with a flattened pathlist equals the size of the pathlist. Hence it is possible that an implementation includes these label lists in the flattened pathlist itself.¶

• Again as mentioned in Appendix B, the size of a flattened pathlist may not be equal to the size of the OutLabel-lists of leaves using the flattened pathlist. So the indices inside a flattened pathlist still indicate the label index in the OutLabel-Lists of the leaves using that pathlist. Because the size of the flattened pathlist may be different from the size of the OutLabel-lists of the leaves, the indices may be repeated.¶

• Let's take a look at the flattened pathlist used by the prefix "VPN-IP2". The pathlist associated with the prefix "VPN-IP2" has three entries.¶

  • The first and second entry have index "0". This is because both entries correspond to ePE2. Thus when hashing performed by the forwarding engine results in using the first or the second entry in the pathlist, the forwarding engine will pick the correct VPN label "VPN-L22", which is the label advertised by ePE2 for the prefix "VPN-IP2".¶

  • The third entry has the index "1". This is because the third entry corresponds to ePE3. Thus when the hashing is performed by the forwarding engine results in using the third entry in the flattened pathlist, the forwarding engine will pick the correct VPN label "VPN-L32", which is the label advertised by "ePE3" for the prefix "VPN-IP2".¶

Now let's try and apply the forwarding steps in Section 4 together with the additional step in Section Appendix B to the flattened forwarding chain illustrated in Figure 6.¶

• Suppose a packet arrives at "iPE" and matches the VPN prefix "VPN-IP2".¶

• The forwarding engine walks to the parent of the "VPN-IP2", which is the flattened pathlist and applies a hashing algorithm to pick a path.¶

• Suppose the hashing by the forwarding engine picks the second path in the flattened pathlist associated with the leaf "VPN-IP2".¶

• Because the second path has the index "0", the label "VPN-L22" is pushed on the packet.¶

• Next the forwarding engine picks the second label from the OutLabel-List associated with the flattened pathlist resulting in "LASBR122(ePE2)" being the next pushed label.¶

• The forwarding engine now moves to the parent of the flattened pathlist corresponding to the second path. The parent is the IGP label leaf corresponding to "ASBR12".¶

• So the packet is forwarded towards the ASBR "ASBR12" and the IGP label at the top will be "IGP-L12".¶

Based on the above steps, a packet arriving at iPE and destined to the prefix VPN-L22 reaches its destination as follows:¶

o  iPE sends the packet along the shortest path towards ASBR12
   with the following label stack starting from the top: {L12,
   LASBR122(ePE2), VPN-L22}.

o  The penultimate hop of ASBR12 pops the top label "L12". Hence the
   packet arrives at ASBR12 with the remaining label stack
   {LASBR122(ePE2), VPN-L22} where "LASBR12(ePE2)" is the top label.

o  ASBR12 swaps "LASBR122(ePE2)" with the label "LASBR22(ePE2)",
   which is the label advertised by ASBR22 for the ePE2 (the egress
   PE).

o  ASBR22 receives the packet with "LASBR22(ePE2)" at the top.

o  Hence ASBR22 swaps "LASBR22(ePE2)" with the IGP label for ePE2
   advertised by the next-hop towards ePE2 in domain 2, and sends
   the packet along the shortest path towards ePE2.

o  The penultimate hop of ePE2 pops the top label. Hence ePE2
   receives the packet with the top label VPN-L22 at the top

o  ePE2 pops "VPN-L22" and sends the packet as a pure IP packet
   towards the destination VPN-IP2.

Appendix D. Perspective

The following table puts the BGP-PIC benefits in perspective assuming¶

• 1M impacted BGP prefixes¶

• IGP convergence ~ 500 msec¶

• local protection ~ 50msec¶

• FIB Update per BGP destination ~ 100usec conservative,¶

  ~ 10usec optimistic¶

• BGP best route recalculation per BGP destination¶

  ~ 10usec optimistic,¶

  ~ 100usec optimistic¶

  Without PIC With PIC¶

  Local IGP Failure

  10 to 100sec 50msec¶

  Local BGP Failure

  100 to 200sec 50msec¶

  Remote IGP Failure

  10 to 100sec 500msec¶

  Local BGP Failure

  100 to 200sec 500msec¶

Upon local IGP next-hop failure or remote IGP next-hop failure, the existing primary BGP next-hop is intact and usable hence the resiliency only depends on the ability of the FIB mechanism to reflect the new path to the BGP next-hop to the depending BGP destinations. Without BGP-PIC, a conservative back-of-the-envelope estimation for this FIB update is 100usec per BGP destination. An optimistic estimation is 10usec per entry.¶

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 recomputed and new updates need to be sent to peers. This depends on BGP processing time that will be shared between best-path computation, RIB update and peer update. A conservative back-of-the- envelope estimation for this is 200usec per BGP destination. An optimistic estimation is 100usec per entry.¶

Authors' Addresses