idnits 2.17.1 draft-ietf-rtgwg-bgp-pic-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. == The document seems to contain a disclaimer for pre-RFC5378 work, but was first submitted on or after 10 November 2008. The disclaimer is usually necessary only for documents that revise or obsolete older RFCs, and that take significant amounts of text from those RFCs. If you can contact all authors of the source material and they are willing to grant the BCP78 rights to the IETF Trust, you can and should remove the disclaimer. Otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 20, 2016) is 2867 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 3107 (ref. '4') (Obsoleted by RFC 8277) == Outdated reference: A later version (-15) exists of draft-ietf-idr-add-paths-12 == Outdated reference: A later version (-22) exists of draft-ietf-spring-segment-routing-mpls-02 Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group A. Bashandy, Ed. 2 Internet Draft C. Filsfils 3 Intended status: Informational Cisco Systems 4 Expires: December 2016 P. Mohapatra 5 Sproute Networks 6 June 20, 2016 7 BGP Prefix Independent Convergence 8 draft-ietf-rtgwg-bgp-pic-01.txt 10 Abstract 12 In the network comprising thousands of iBGP peers exchanging millions 13 of routes, many routes are reachable via more than one next-hop. 14 Given the large scaling targets, it is desirable to restore traffic 15 after failure in a time period that does not depend on the number of 16 BGP prefixes. In this document we proposed an architecture by which 17 traffic can be re-routed to ECMP or pre-calculated backup paths in a 18 timeframe that does not depend on the number of BGP prefixes. The 19 objective is achieved through organizing the forwarding data 20 structures in a hierarchical manner and sharing forwarding elements 21 among the maximum possible number of routes. The proposed technique 22 achieves prefix independent convergence while ensuring incremental 23 deployment, complete automation, and zero management and provisioning 24 effort. It is noteworthy to mention that the benefits of BGP-PIC are 25 hinged on the existence of more than one path whether as ECMP or 26 primary-backup. 28 Status of this Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 This document may contain material from IETF Documents or IETF 34 Contributions published or made publicly available before November 35 10, 2008. The person(s) controlling the copyright in some of this 36 material may not have granted the IETF Trust the right to allow 37 modifications of such material outside the IETF Standards Process. 38 Without obtaining an adequate license from the person(s) 39 controlling the copyright in such materials, this document may not 40 be modified outside the IETF Standards Process, and derivative 41 works of it may not be created outside the IETF Standards Process, 42 except to format it for publication as an RFC or to translate it 43 into languages other than English. 45 Internet-Drafts are working documents of the Internet Engineering 46 Task Force (IETF), its areas, and its working groups. Note that 47 other groups may also distribute working documents as Internet- 48 Drafts. 50 Internet-Drafts are draft documents valid for a maximum of six 51 months and may be updated, replaced, or obsoleted by other 52 documents at any time. It is inappropriate to use Internet-Drafts 53 as reference material or to cite them other than as "work in 54 progress." 56 The list of current Internet-Drafts can be accessed at 57 http://www.ietf.org/ietf/1id-abstracts.txt 59 The list of Internet-Draft Shadow Directories can be accessed at 60 http://www.ietf.org/shadow.html 62 This Internet-Draft will expire on December 20, 2016. 64 Copyright Notice 66 Copyright (c) 2016 IETF Trust and the persons identified as the 67 document authors. All rights reserved. 69 This document is subject to BCP 78 and the IETF Trust's Legal 70 Provisions Relating to IETF Documents 71 (http://trustee.ietf.org/license-info) in effect on the date of 72 publication of this document. Please review these documents 73 carefully, as they describe your rights and restrictions with 74 respect to this document. Code Components extracted from this 75 document must include Simplified BSD License text as described in 76 Section 4.e of the Trust Legal Provisions and are provided without 77 warranty as described in the Simplified BSD License. 79 Table of Contents 81 1. Introduction...................................................3 82 1.1. Conventions used in this document.........................4 83 1.2. Terminology...............................................4 84 2. Overview.......................................................5 85 3. Constructing the Shared Hierarchical Forwarding Chain..........7 86 3.1. Example 1: Primary-Backup Path Scenario...................8 87 3.2. Example 2: Platforms with Limited Levels of Hierarchy.....9 88 4. Forwarding Behavior...........................................13 89 5. Forwarding Chain Adjustment at a Failure......................15 90 5.1. BGP-PIC core.............................................16 91 5.2. BGP-PIC edge.............................................17 92 5.2.1. Adjusting forwarding Chain in egress node failure...17 93 5.2.2. Adjusting Forwarding Chain on PE-CE link Failure....17 94 5.3. Handling Failures for Flattended Forwarding Chains.......18 95 6. Properties....................................................19 96 6.1. Coverage.................................................19 97 6.1.1. A remote failure on the path to a BGP next-hop......19 98 6.1.2. A local failure on the path to a BGP next-hop.......19 99 6.1.3. A remote iBGP next-hop fails........................20 100 6.1.4. A local eBGP next-hop fails.........................20 101 6.2. Performance..............................................20 102 6.2.1. Perspective.........................................20 103 6.3. Automated................................................21 104 6.4. Incremental Deployment...................................22 105 7. Dependency....................................................22 106 7.1. Hierarchical Hardware FIB................................22 107 7.2. Availability of more than one primary or secondary BGP next- 108 hops..........................................................22 109 7.3. Pre-Computation of a secondary BGP next-hop..............23 110 8. Security Considerations.......................................23 111 9. IANA Considerations...........................................23 112 10. Conclusions..................................................23 113 11. Acknowledgments..............................................25 114 12. References...................................................23 115 12.1. Normative References....................................23 116 12.2. Informative References..................................24 118 1. Introduction 120 As a path vector protocol, BGP is inherently slow due to the 121 serial nature of reachability propagation. BGP speakers exchange 122 reachability information about prefixes[2][3] and, for labeled 123 address families, namely AFI/SAFI 1/4, 2/4, 1/128, and 2/128, an 124 edge router assigns local labels to prefixes and associates the 125 local label with each advertised prefix such as L3VPN [8], 6PE 126 [9], and Softwire [7] using BGP label unicast technique[4]. A BGP 127 speaker then applies the path selection steps to choose the best 128 path. In modern networks, it is not uncommon to have a prefix 129 reachable via multiple edge routers. In addition to proprietary 130 techniques, multiple techniques have been proposed to allow for 131 BGP to advertise more than one path for a given prefix 132 [6][11][12], whether in the form of equal cost multipath or 133 primary-backup. Another more common and widely deployed scenario 134 is L3VPN with multi-homed VPN sites with unique Route 135 Distinguisher. 137 This document proposes a hierarchical and shared forwarding chain 138 organization that allows traffic to be restored to pre-calculated 139 alternative equal cost primary path or backup path in a time 140 period that does not depend on the number of BGP prefixes. The 141 technique relies on internal router behavior that is completely 142 transparent to the operator and can be incrementally deployed and 143 enabled with zero operator intervention. 145 1.1. Conventions used in this document 147 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL 148 NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" 149 in this document are to be interpreted as described in RFC-2119 150 [1]. 152 In this document, these words will appear with that interpretation 153 only when in ALL CAPS. Lower case uses of these words are not to 154 be interpreted as carrying RFC-2119 significance. 156 1.2. Terminology 158 This section defines the terms used in this document. For ease of 159 use, we will use terms similar to those used by L3VPN [8] 161 o BGP prefix: It is a prefix P/m (of any AFI/SAFI) that a BGP 162 speaker has a path for. 164 o IGP prefix: It is a prefix P/m (of any AFI/SAFI) that is learnt 165 via an Interior Gateway Protocol, such as OSPF and ISIS, has a 166 path for. The prefix may be learnt directly through the IGP or 167 redistributed from other protocol(s) 169 o CE: It is an external router through which an egress PE can 170 reach a prefix P/m. 172 o Ingress PE, "iPE": t is a BGP speaker that learns about a prefix 173 through a IBGP peer and chooses an egress PE as the next-hop for 174 the prefix.. 176 o Path: It is the next-hop in a sequence of unique connected 177 nodes starting from the current node and ending with the 178 destination node or network identified by the prefix. 180 o Recursive path: It is a path consisting only of the IP address 181 of the next-hop without the outgoing interface. Subsequent 182 lookups are needed to determine the outgoing interface. 184 o Non-recursive path: It is a path consisting of the IP address 185 of the next-hop and one outgoing interface 187 o Primary path: It is a recursive or non-recursive path that can 188 be used all the time. A prefix can have more than one primary 189 path 191 o Backup path: It is a recursive or non-recursive path that can 192 be used only after some or all primary paths become unreachable 194 o Leaf: A leaf is container data structure for a prefix or local 195 label. Alternatively, it is the data structure that contains 196 prefix specific information. 198 o IP leaf: Is the leaf corresponding to an IPv4 or IPv6 prefix 200 o Label leaf. It is the leaf corresponding to a locally allocated 201 label such as the VPN label on an egress PE [8]. 203 o Pathlist: It is an array of paths used by one or more prefix to 204 forward traffic to destination(s) covered by a IP prefix. Each 205 path in the pathlist carries its "path-index" that identifies 206 its position in the array of paths. A pathlist may contain a 207 mix of primary and backup paths 209 o OutLabel-List: Each labeled prefix is associated with an 210 OutLabel-List. The OutLabel-List is an array of one or more 211 outgoing labels and/or label actions where each label or label 212 action has 1-to-1 correspondence to a path in the pathlist. 213 Label actions are: push the label, pop the label, or swap the 214 incoming label with the label in the Outlabel-Array entry. The 215 prefix may be an IGP or BGP prefix 217 o Adjacency: It is the layer 2 encapsulation leading to the layer 218 3 directly connected next-hop 220 o Dependency: An object X is said to be a dependent or Child of 221 object Y if Object Y cannot be deleted unless object X is no 222 longer a dependent/child of object Y 224 o Route: It is a prefix with one or more paths associated with 225 it. Hence the minimum set of objects needed to construct a 226 route is a leaf and a pathlist. 228 2. Overview 230 The idea of BGP-PIC is based on two pillars 232 o A shared hierarchal Forwarding Chain 234 o A forwarding plane that supports multiple levels of indirection 236 To illustrate the two pillars above, we will use an example of a 237 simple multihomed L3VPN [8] prefix in a BGP-free core running LDP 238 [5] or segment routing over MPLS forwarding plane [14]. 240 +--------------------------------+ 241 | | 242 | ePE2 243 | | \ 244 | | \ 245 | | \ 246 iPE | CE.......VRF "Blue" 247 | | / (VPN-IP1) 248 | | / (VPN-IP2) 249 | LDP/Segment-Routing Core | / 250 | ePE1 251 | | 252 +--------------------------------+ 253 Figure 1 VPN prefix reachable via multiple PEs 255 Referring to Figure 1, suppose the iPE (the ingress PE) receives 256 NLRIs for the VPN prefixes VPN-IP1 and VPN-IP2 from two egress PEs, 257 ePE1 and ePE2 with next-hop BGP-NH1 and BGP-NH2, respectively. 258 Assume that ePE1 advertise the VPN labels VPN-L11 and VPN-L12 while 259 ePE2 advertise the VPN labels VPN-L21 and VPN-L22 for VPN-IP1 and 260 VPN-IP2, respectively. Suppose that BGP-NH1 and BGP-NH2 are resolved 261 via the IGP prefixes IGP-IP1 and IGP-P2, where each happen to have 2 262 ECMP paths with IGP-NH1 and IGP-NH2 reachable via the interfaces I1 263 and I2, respectively. Suppose that local labels (whether LDP[5] or 264 segment routing [14]) on the downstream LSRs for IGP-IP1 are IGP-L11 265 and IGP-L12 while for IGP-P2 are IGP-L21 and IGP-L22. 267 Based on the information about NLRIs and the resolving IGP prefixes, 268 a hierarchical forwarding chain can be constructed as shown in 269 Figure 2. 271 IP Leaf: Pathlist: IP Leaf: Pathlist: 272 -------- +-------+ -------- +----------+ 273 VPN-IP1-->|BGP-NH1|-->IGP-IP1(BGP NH1)--->|IGP NH1,I1|--->Adjacency1 274 | |BGP-NH2|-->.... | |IGP NH2,I2|--->Adjacency2 275 | +-------+ | +----------+ 276 | | 277 | | 278 v v 279 OutLabel-List: OutLabel-List: 280 +----------------------+ +----------------------+ 281 |VPN-L11 (VPN-IP1, NH1)| |IGP-L11 (IGP-IP1, NH1)| 282 |VPN-L12 (VPN-IP1, NH2)| |IGP-L12 (IGP-IP1, NH2)| 283 +----------------------+ +----------------------+ 285 Figure 2 Shared Hierarchical Forwarding Chain at iPE 287 The forwarding chain depicted in Figure 2 illustrates the first 288 pillar, which is sharing and hierarchy. We can see that the BGP 289 pathlist consisting of BGP-NH1 and BGP-NH2 is shared by all NLRIs 290 reachable via ePE1 and ePE2. As such, it is possible to make changes 291 to the pathlist without having to make changes to the NLRIs. For 292 example, if BGP-NH2 becomes unreacreachable, there is no need to 293 modify any of the possibly large number of NLRIs. Instead only the 294 shared pathlist needs to be modified. Likewise, due to the 295 hierarchical structure of the forwarding chain, it is possible to 296 make modifications to the IGP routes without having to make any 297 changes to the BGP NLRIs. For example, if the interface "I2" goes 298 down, only the shared IGP pathlist needs to be updated, but none of 299 the IGP prefixes sharing the IGP pathlist nor the BGP NLRIs using 300 the IGP prefixes for resolution need to be modified. 302 Figure 2 can also be used to illustrate the second BGP-PIC pillar. 303 Having a deep forwarding chain such as the one illustrated in Figure 304 2 requires a forwarding plane that is capable of accessing multiple 305 levels of indirection in order to calculate the outgoing 306 interface(s) and next-hops(s). While a deeper forwarding chain 307 minimizes the re-convergence time on topology change, there will 308 always exist platforms with limited capabilities and hence imposing 309 a limit on the depth of the forwarding chain. The example in Section 310 3.2 illustrates how to gracefully trade off convergence speed with 311 the number of hierarchical levels to support platforms with 312 different capabilities. 314 3. Constructing the Shared Hierarchical Forwarding Chain 316 Constructing the forwarding chain is an application of the two 317 pillars described in Section 2. 319 The whole process starts when BGP downloads a prefix to FIB. The 320 prefix contains one or more outgoing paths. For certain labeled 321 prefixes, such as VPN [8] prefixes, each path may be associated with 322 an outgoing label and the prefix itself may be assigned a local 323 label. The list of outgoing paths defines a pathlist. If such 324 pathlist does not already exist, then FIB creates a new pathlist, 325 otherwise the existing pathlist is used. The BGP prefix is added as 326 a dependent of the pathlist. 328 The previous step constructs the upper part of the hierarchical 329 forwarding chain. The forwarding chain is completed by resolving the 330 paths of the pathlist. A BGP path usually consists of a next-hop. 331 The next-hop is resolved by finding a matching IGP prefix. 333 The end result is a hierarchical shared forwarding chain where the 334 BGP pathlist is shared by all BGP prefixes that use the same list of 335 paths and the IGP prefix is shared by all pathlists that have a path 336 resolving via that IGP prefix. It is noteworthy to mention that the 337 forwarding chain is constructed without any operator intervention at 338 all. 340 The remainder of this section illustrates two examples. The first 341 example illustrates the applicability of BGP-PIC in a primary-backup 342 path deployment. The second example illustrates how BGP-PIC can be 343 applied in cases where the forwarding plane supports limited number 344 of indirections. 346 3.1. Example 1: Primary-Backup Path Scenario 348 Consider the egress PE ePE1 in the case of the multi-homed VPN 349 prefixes in the BGP-free core depicted in Figure 1. Suppose ePE1 350 determines that the primary path is the external path but the backup 351 path is the iBGP path to the other PE ePE2 with next-hop BGP-NH2. 352 ePE2 constructs the forwarding chain depicted in Figure 3. We are 353 only showing a single VPN prefix for simplicity. But all prefixes 354 that are multihomed to ePE1 and ePE2 share the BGP pathlist. 356 BGP OutLabel Array 357 VPN-L11 +---------+ 358 (Label-leaf)---+---->|Unlabeled| 359 | +---------+ 360 | | VPN-L21 | 361 | | (swap) | 362 | +---------+ 363 | ^ 364 | | BGP Pathlist 365 | | +------------+ Connected route 366 | | | CE-NH |------>(to the CE) 367 | | |path-index=0| 368 | | +------------+ 369 V | | VPN-NH2 | 370 VPN-IP1 -----------------+------>| (backup) |------>IGP Leaf 371 (IP prefix leaf) |path-index=1| (Towards ePE2) 372 +------------+ 374 Figure 3 : VPN Prefix Forwarding Chain with eiBGP paths on egress PE 376 The example depicted in Figure 3 differs from the example in Figure 377 2 in two main aspects. First, as long as the primary path towards 378 the CE (external path) is useable, it will be the only path used for 379 forwarding while the OutLabel-List contains both the unlabeled label 380 (primary path) and the VPN label (backup path) advertised by the 381 backup path ePE2. The second aspect is presence of the label leaf 382 corresponding to the VPN prefix. This label leaf is used to match 383 VPN traffic arriving from the core. Note that the label leaf shares 384 the OutLabel-List and the pathlist with the IP prefix. 386 3.2. Example 2: Platforms with Limited Levels of Hierarchy 388 This example uses a case of inter-AS option C [8] where there are 3 389 levels of hierarchy. Figure 4 illustrates the sample topology. To 390 force 3 levels of hierarchy, the ASBRs on the ingress domain (domain 391 1) advertise the core routers of the egress domain (domain 2) to the 392 ingress PE (iPE) via BGP-LU [4] instead of redistributing them into 393 the IGP of domain 1. The end result is that the ingress PE (iPE) has 394 2 levels of recursion for the VPN prefix VPN-IP1 and VPN2-P2. 396 Domain 1 Domain 2 397 +----------------+ +-------------+ 398 | | | | 399 | LDP/SR Core | | LDP/SR core | 400 | | | | 401 | ASBR11------ASBR21.......ePE1\ 402 | | \ / | . . | \ 403 | | \ / | . . | \ 404 | | \/ | .. | \VPN-IP1 405 | | /\ | . . | / 406 | | / \ | . . | / 407 | | / \ | . . | / 408 iPE ASBR12------ASBR22.......ePE2 409 | | | | \ 410 | | | | \ 411 | | | | \ 412 | | | | /VPN-IP2 413 | | | | / 414 | | | | / 415 | ASBR13------ASBR23.......ePE3/ 416 | | | | 417 | | | | 418 +----------------+ +-------------+ 419 <============== <========= <============ 420 Advertise PE2x Advertise Redistribute 421 Using iBGP-LU PE2x Using IGP into 422 eBGP-LU BGP 424 Figure 4 Sample 3-level hierarchy topology 426 We will make the following assumptions about connectivity 428 o In "domain 2", both ASBR21 and ASBR22 can reach both ePE1 and 429 ePE2 using the same distance 431 o In "domain 2", only ASBR23 can reach ePE3 432 o In "domain 1", iPE (the ingress PE) can reach ASBR11, ASBR12, and 433 ASBR13 via IGP using the same distance. 435 We will make the following assumptions about the labels 437 o The VPN labels advertised by ePE1 and ePE2 for prefix VPN-IP1 are 438 VPN-L11 and VPN-L21, respectively 440 o The VPN labels advertised by ePE2 and ePE3 for prefix VPN-IP2 are 441 VPN-L22 and VPN-L32, respectively 443 o The labels advertised by ASBR11 to iPE using BGP-LU [4] for the 444 egress PEs ePE1 and ePE2 are LASBR11(ePE1) and LASBR11(ePE2), 445 respectively. 447 o The labels advertised by ASBR12 to iPE using BGP-LU [4] for the 448 egress PEs ePE1 and ePE2 are LASBR12(ePE1) and LASBR12(ePE2), 449 respectively 451 o The label advertised by ASBR11 to iPE using BGP-LU [4] for the 452 egress PE ePE3 is LASBR13(ePE3) 454 o The IGP labels advertised by the next hops directly connected to 455 iPE towards ASBR11, ASBR12, and ASBR13 in the core of domain 1 456 are IGP-L11, IGP-L12, and IGP-L13, respectively. 458 The diagram in Figure 5 illustrates the forwarding chain in iPE 459 assuming that the forwarding hardware in iPE supports 3 levels of 460 hierarchy. The leaves corresponding to the ABSRs on domain 1 461 (ASBR11, ASBR12, and ASBR13) are at the bottom of the hierarchy. 462 There are few important points: 464 o Because the hardware supports the required depth of hierarchy, 465 the sizes of a pathlist equal the size of the label list 466 associated with the leaves using this pathlist 468 o The index inside the pathlist entry indicates the label that will 469 be picked from the Outlabel-List if that path is chosen by the 470 forwarding engine hashing function. 472 Outlabel-List Outlabel-List 473 For VPN-IP1 For VPN-IP2 474 +------------+ +--------+ +-------+ +------------+ 475 | VPN-L11 |<---| VPN-IP1| |VPN-IP2|-->| VPN-L22 | 476 +------------+ +---+----+ +---+---+ +------------+ 477 | VPN-L21 | | | | VPN-L32 | 478 +------------+ | | +------------+ 479 | | 480 V V 481 +---+---+ +---+---+ 482 | 0 | 1 | | 0 | 1 | 483 +-|-+-\-+ +-/-+-\-+ 484 | \ / \ 485 | \ / \ 486 | \ / \ 487 | \ / \ 488 v \ / \ 489 +-----+ +-----+ +-----+ 490 +----+ ePE1| |ePE2 +-----+ | ePE3+-----+ 491 | +--+--+ +-----+ | +--+--+ | 492 v | / v | v 493 +-------------+ | / +-------------+ | +-------------+ 494 |LASBR11(ePE1)| | / |LASBR11(ePE2)| | |LASBR13(ePE3)| 495 +-------------+ | / +-------------+ | +-------------+ 496 |LASBR12(ePE1)| | / |LASBR12(ePE2)| | Outlabel-List 497 +-------------+ | / +-------------+ | For ePE3 498 Outlabel-List | / Outlabel-List | 499 For ePE1 | / For ePE2 | 500 | / | 501 | / | 502 | / | 503 v / v 504 +---+---+ Shared Pathlist +---+ Pathlist 505 | 0 | 1 | For ePE1 and ePE2 | 0 | For ePE3 506 +-|-+-\-+ +-|-+ 507 | \ | 508 | \ | 509 | \ | 510 | \ | 511 v \ v 512 +------+ +------+ +------+ 513 +---+ASBR11| |ASBR12+--+ |ASBR13+---+ 514 | +------+ +------+ | +------+ | 515 v v v 516 +-------+ +-------+ +-------+ 517 |IGP-L11| |IGP-L12| |IGP-L13| 518 +-------+ +-------+ +-------+ 520 Figure 5 : Forwarding Chain for hardware supporting 3 Levels 522 Now suppose the hardware on iPE (the ingress PE) supports 2 levels 523 of hierarchy only. In that case, the 3-levels forwarding chain in 524 Figure 5 needs to be "flattended" into 2 levels only. 526 Outlabel-List Outlabel-List 527 For VPN-IP1 For VPN-IP2 528 +------------+ +-------+ +-------+ +------------+ 529 | VPN-L11 |<---|VPN-IP1| | VPN-IP2|--->| VPN-L22 | 530 +------------+ +---+---+ +---+---+ +------------+ 531 | VPN-L21 | | | | VPN-L32 | 532 +------------+ | | +------------+ 533 | | 534 | | 535 | | 536 Flattened | | Flattened 537 pathlist V V pathlist 538 +===+===+ +===+===+===+ +=============+ 539 +--------+ 0 | 1 | | 0 | 0 | 1 +---->|LASBR11(ePE2)| 540 | +=|=+=\=+ +=/=+=/=+=\=+ +=============+ 541 v | \ / / \ |LASBR12(ePE2)| 542 +=============+ | \ +-----+ / \ +=============+ 543 |LASBR11(ePE1)| | \/ / \ |LASBR13(ePE3)| 544 +=============+ | /\ / \ +=============+ 545 |LASBR12(ePE1)| | / \ / \ 546 +=============+ | / \ / \ 547 | / \ / \ 548 | / + + \ 549 | + | | \ 550 | | | | \ 551 v v v v \ 552 +------+ +------+ +------+ 553 +----|ASBR11| |ASBR12+---+ |ASBR13+---+ 554 | +------+ +------+ | +------+ | 555 v v v 556 +-------+ +-------+ +-------+ 557 |IGP-L11| |IGP-L12| |IGP-L13| 558 +-------+ +-------+ +-------+ 560 Figure 6 : Flattening 3 levels to 2 levels of Hierarchy on iPE 562 Figure 6 represents one way to "flatten" a 3 levels hierarchy into 563 two levels. There are few important points: 565 o The flattened pathlists have label lists associated with them. 566 The size of the label list associated with the flattened pathlist 567 equals the size of the pathlist. Hence it is possible that an 568 implementation includes these label lists in the flattened 569 pathlist itself 571 o Because of "flattening", the size of a flattened pathlist may not 572 be equal to the size of the label lists of leaves using the 573 flattened pathlist. 575 o The indices inside a flattened pathlist still indicate the label 576 index in the Outlabel-Lists of the leaves using that pathlist. 577 Because the size of the flattened pathlist may be different from 578 the size of the label lists of the leaves, the indices may be 579 repeated 581 o Let's take a look at the flattened pathlist used by the prefix 582 "VPN-IP2", The pathlist associated with the prefix "VPN-IP2" has 583 three entries. 585 o The first and second entry have index "0". This is because 586 both entries correspond to ePE2. Hence when hashing performed 587 by the forwarding engine results in using first or the second 588 entry in the pathlist, the forwarding engine will pick the 589 correct VPN label "VPN-L22", which is the label advertised by 590 ePE2 for the prefix "VPN-IP2" 592 o The third entry has the index "1". This is because the third 593 entry corresponds to ePE3. Hence when the hashing is performed 594 by the forwarding engine results in using the third entry in 595 the flattened pathlist, the forwarding engine will pick the 596 correct VPN label "VPN-L32", which is the label advertised by 597 "ePE3" for the prefix "VPN-IP2" 599 4. Forwarding Behavior 601 This section explains how the forwarding plane uses the hierarchical 602 shared forwarding chain to forward a packet. 604 When a packet arrives at a router, it matches a leaf. A labeled 605 packet matches a label leaf while an IP packet matches an IP prefix 606 leaf. The forwarding engines walks the forwarding chain starting 607 from the leaf until the walk terminates on an adjacency. Thus when a 608 packet arrives, the chain is walked as follows: 610 1. Lookup the leaf based on the destination address or the label at 611 the top of the packet 613 2. Retrieve the parent pathlist of the leaf 614 3. Pick the outgoing path from the list of resolved paths in the 615 pathlist. The method by which the outgoing path is picked is 616 beyond the scope of this document (i.e. flow-preserving hash 617 exploiting entropy within the MPLS stack and IP header). Let the 618 "path-index" of the outgoing path be "i". 620 4. If the prefix is labeled, use the "path-index" "i" to retrieve 621 the ith label "Li" stored the ith entry in the OutLabel-List and 622 apply the label action of the label on the packet (e.g. for VPN 623 label on the ingress PE, the label action is "push"). 625 5. Move to the parent of the chosen path "i" 627 6. If the chosen path "i" is recursive, move to its parent prefix 628 and go to step 2 630 7. If the chosen path "i" is non-recursive move to its parent 631 adjacency 633 8. Encapsulate the packet in the L2 string specified by the 634 adjacency and send the packet out. 636 Let's apply the above forwarding steps to the forwarding chain 637 depicted in Figure 2 in Section 2. Suppose a packet arrives at 638 ingress PE iPE from an external neighbor. Assume the packet matches 639 the VPN prefix VPN-IP1. While walking the forwarding chain, the 640 forwarding engine applies a hashing algorithm to choose the path and 641 the hashing at the BGP level yields path 0 while the hashing at the 642 IGP level yields path 1. In that case, the packet will be sent out 643 of interface I2 with the label stack "IGP-L12,VPN-L11". 645 Now let's try and apply the above steps to the flattened forwarding 646 chain illustrated in Figure 6. 648 o Suppose a packet arrives at "iPE" and matches the VPN prefix 649 "VPN-IP2" 651 o The forwarding engine walks to the parent of the "VPN_P2", which 652 is the flattened pathlist and applies a hashing algorithm to pick 653 a path 655 o Suppose the hashing by the forwarding engine picks the second 656 entry in the flattened pathlist associated with the leaf "VPN- 657 IP2". 659 o Because the second entry has the index "0", the label "VPN-L22" 660 is pushed on the packet 662 o At the same time, the forwarding engine picks the second label 663 from the Outlabel-Array associated with the flattened pathlist. 664 Hence the next label that is pushed is "LASBR12(ePE2)" 666 o The forwarding engine now moves to the parent of the flattened 667 pathlist corresponding to the second entry. The parent is the IGP 668 label leaf corresponding to "ASBR12" 670 o So the packet is forwarded towards the ASBR "ASBR12" and the IGP 671 label at the top will be "L12" 673 Based on the above steps, a packet arriving at iPE and destined to 674 the prefix VPN-L22 reaches its destination as follows 676 o iPE sends the packet along the shortest path towards ASBR12 with 677 the following label stack starting from the top: {L12, 678 LASBR12(ePE2), VPN-L22}. 680 o The penultimate hop of ASBR12 pops the top label "L12". Hence the 681 packet arrives at ASBR12 with the label stack {LASBR12(ePE2), 682 VPN-L22} where "LASBR12(ePE2)" is the top label. 684 o ASBR12 swaps "LASBR12(ePE2)" with the label "LASBR22(ePE2)", 685 which is the label advertised by ASBR22 for the ePE2 (the egress 686 PE). 688 o ASBR22 receives the packet with "LASBR22(ePE2)" at the top. 690 o Hence ASBR22 swaps "LASBR22(ePE2)" with the IGP label for ePE2 691 advertised by the next-hop towards ePE2 in domain 2, and sends 692 the packet along the shortest path towards ePE2. 694 o The penultimate hop of ePE2 pops the top label. Hence ePE2 695 receives the packet with the top label VPN-L22 at the top 697 o ePE2 pops "VPN-L22" and sends the packet as a pure IP packet 698 towards the destination VPN-IP2. 700 5. Forwarding Chain Adjustment at a Failure 702 The hierarchical and shared structure of the forwarding chain 703 explained in Section 2 allows modifying a small number of 704 forwarding chain objects to re-route traffic to a pre-calculated 705 equal-cost or backup path without the need to modify the possibly 706 very large number of BGP prefixes. In this section, we go over 707 various core and edge failure scenarios to illustrate how FIB 708 manager can utilize the forwarding chain structure to achieve BGP 709 prefix independent convergence. 711 5.1. BGP-PIC core 713 This section describes the adjustments to the forwarding chain when 714 a core link or node fails but the BGP next-hop remains reachable. 716 There are two case: remote link failure and attached link failure. 717 Node failures are treated as link failures. 719 When a remote link or node fails, IGP on the ingress PE receives 720 advertisement indicating a topology change so IGP re-converges to 721 either find a new next-hop and/or outgoing interface or remove the 722 path completely from the IGP prefix used to resolve BGP next-hops. 723 IGP and/or LDP download the modified IGP leaves with modified 724 outgoing labels for labeled core. 726 When a local link fails, FIB manager detects the failure almost 727 immediately. The FIB manager marks the impacted path(s) as unusable 728 so that only useable paths are used to forward packets. Hence only 729 IGP pathlists with paths using the failed local link need to be 730 modified. All other pathlists are not impacted. Note that in this 731 particular case there is actually no need even to backwalk to IGP 732 leaves to adjust the OutLabel-Lists because FIB can rely on the 733 path-index stored in the useable paths in the pathlist to pick the 734 right label. 736 It is noteworthy to mention that because FIB manager modifies the 737 forwarding chain starting from the IGP leaves only, BGP pathlists 738 and leaves are not modified. Hence traffic restoration occurs within 739 the time frame of IGP convergence, and, for local link failure, 740 assuming a backup path has been precomputed, within the timeframe of 741 local detection (e.g. 50ms). Examples of solutions that pre- 742 computing backup paths are IP FRR [16] remote LFA [17], Ti-LFA [15] 743 and MRT [18] or eBGP path having a backup path [10]. 745 Let's apply the procedure to the forwarding chain depicted in Figure 746 2. Suppose a remote link failure occurs and impacts the first ECMP 747 IGP path to the remote BGP next-hop. Upon IGP convergence, the IGP 748 pathlist used by the BGP next-hop is updated to reflect the new 749 topology (one path instead of two). As soon as the IGP convergence 750 is effective for the BGP next-hop entry, the new forwarding state is 751 immediately available to all dependent BGP prefixes. The same 752 behavior would occur if the failure was local such as an interface 753 going down. As soon as the IGP convergence is complete for the BGP 754 next-hop IGP route, all its BGP depending routes benefit from the 755 new path. In fact, upon local failure, if LFA protection is enabled 756 for the IGP route to the BGP next-hop and a backup path was pre- 757 computed and installed in the pathlist, upon the local interface 758 failure, the LFA backup path is immediately activated (sub-50msec) 759 and thus protection benefits all the depending BGP traffic through 760 the hierarchical forwarding dependency between the routes. 762 5.2. BGP-PIC edge 764 This section describes the adjustments to the forwarding chains as a 765 result of edge node or edge link failure. 767 5.2.1. Adjusting forwarding Chain in egress node failure 769 When an edge node fails, IGP on neighboring core nodes send route 770 updates indicating that the edge node is no longer reachable. IGP 771 running on the iBGP peers instructs FIB to remove the IP and label 772 leaves corresponding to the failed edge node from FIB. So FIB 773 manager performs the following steps: 775 o FIB manager deletes the IGP leaf corresponding to the failed edge 776 node 778 o FIB manager backwalks to all dependent BGP pathlists and marks 779 that path using the deleted IGP leaf as unresolved 781 o Note that there is no need to modify BGP leaves because each path 782 in the pathlist carries its path index and hence the correct 783 outgoing label will be picked. Consider for example the 784 forwarding chain depicted in Figure 2. If the 1st BGP path 785 becomes unresolved, then the forwarding engine will only use the 786 second path for forwarding. Yet the pathindex of that single 787 resolved path will still be 1 and hence the label VPN-L12 will be 788 pushed. 790 5.2.2. Adjusting Forwarding Chain on PE-CE link Failure 792 Suppose the link between an edge router and its external peer fails. 793 There are two scenarios (1) the edge node attached to the failed 794 link performs next-hop self and (2) the edge node attached to the 795 failure advertises the IP address of the failed link as the next-hop 796 attribute to its iBGP peers. 798 In the first case, the rest of iBGP peers will remain unaware of the 799 link failure and will continue to forward traffic to the edge node 800 until the edge node attached to the failed link withdraws the BGP 801 prefixes. If the destination prefixes are multi-homed to another 802 iBGP peer, say ePE2, then FIB manager on the edge router detecting 803 the link failure applies the following steps: 805 o FIB manager backwalks to the BGP pathlists marks the path through 806 the failed link to the external peer as unresolved 808 o Hence traffic will be forwarded used the backup path towards ePE2 809 o For labeled traffic 811 o The Outlabel-List attached to the BGP leaf already contains 812 an entry corresponding to the backup path. 814 o The label entry in OutLabel-List corresponding to the 815 internal path to backup egress PE has swap action to the 816 label advertised by backup egress PE 818 o For an arriving label packet (e.g. VPN), the top label is 819 swapped with the label advertised by backup egress PE and the 820 packet is sent towards that backup egress PE 822 o For unlabeled traffic, packets are simply redirected towards 823 backup egress PE. 825 In the second case where the edge router uses the IP address of the 826 failed link as the BGP next-hop, the edge router will still perform 827 the previous steps. But, unlike the case of next-hop self, IGP on 828 failed edge node informs the rest of the iBGP peers that IP address 829 of the failed link is no longer reachable. Hence the FIB manager on 830 iBGP peers will delete the IGP leaf corresponding to the IP prefix 831 of the failed link. The behavior of the iBGP peers will be identical 832 to the case of edge node failure outlined in Section 5.2.1. 834 It is noteworthy to mention that because the edge link failure is 835 local to the edge router, sub-50 msec convergence can be achieved as 836 described in [10]. 838 Let's try to apply the case of next-hop self to the forwarding chain 839 depicted in Figure 3. After failure of the link between ePE1 and CE, 840 the forwarding engine will route traffic arriving from the core 841 towards VPN-NH2 with path-index=1. A packet arriving from the core 842 will contain the label VPN-L11 at top. The label VPN-L11 is swapped 843 with the label VPN-L21 and the packet is forwarded towards ePE2. 845 5.3. Handling Failures for Flattended Forwarding Chains 847 As explained in the Example in Section 3.2 if the number of 848 hierarchy levels of a platform cannot support the native number of 849 hierarchy levels of a recursive forwarding chain, the instantiated 850 forwarding chain is constructed by flattening two or more levels. 851 Hence a 3 levels chain in Figure 5 is flattened into the 2 levels 852 chain in Figure 6. 854 While reducing the benefits of BGP-PIC, flattening one hierarchy 855 into a shallower hierarchy does not always result in a complete loss 856 of the benefits of the BGP-PIC. To illustrate this fact suppose 857 ASBR12 is no longer reachable in domain 1. If the platform supports 858 the full hierarchy depth, the forwarding chain is the one depicted 859 in Figure 5 and hence the FIB manager needs to backwalk one level to 860 the pathlist shared by "ePE1" and "ePE2" and adjust it. If the 861 platform supports 2 levels of hierarchy, then a useable forwarding 862 chain is the one depicted in Figure 6. In that case, if ASBR12 is no 863 longer reachable, the FIB manager has to backwalk to the two 864 flattened pathlists and update both of them. 866 The main observation is that the loss of convergence speed due to 867 the loss of hierarchy depth depends on the structure of the 868 forwarding chain itself. To illustrate this fact, let's take two 869 extremes. Suppose the forwarding objects in level i+1 depend on the 870 forwarding objects in level i. If every object on level i+1 depends 871 on a separate object in level i, then flattening level i into level 872 i+1 will not result in loss of convergence speed. Now let's take the 873 other extreme. Suppose "n" objects in level i+1 depend on 1 object 874 in level i. Now suppose FIB flattens level i into level i+1. If a 875 topology change results in modifying the single object in level i, 876 then FIB has to backwalk and modify "n" objects in the flattened 877 level, thereby losing all the benefit of BGP-PIC. Experience shows 878 that flattening forwarding chains usually results in moderate loss 879 of BGP-PIC benefits. Further analysis is needed to corroborate and 880 quantify this statement. 882 6. Properties 884 6.1. Coverage 886 All the possible failures, except CE node failure, are covered, 887 whether they impact a local or remote IGP path or a local or remote 888 BGP next-hop as described in Section 5. This section provides 889 details for each failure and now the hierarchical and shared FIB 890 structure proposed in this document allows recovery that does not 891 depend on number of BGP prefixes. 893 6.1.1. A remote failure on the path to a BGP next-hop 895 Upon IGP convergence, the IGP leaf for the BGP next-hop is updated 896 upon IGP convergence and all the BGP depending routes leverage the 897 new IGP forwarding state immediately. 899 This BGP resiliency property only depends on IGP convergence and is 900 independent of the number of BGP prefixes impacted. 902 6.1.2. A local failure on the path to a BGP next-hop 904 Upon LFA protection, the IGP leaf for the BGP next-hop is updated to 905 use the precomputed LFA backup path and all the BGP depending routes 906 leverage this LFA protection. 908 This BGP resiliency property only depends on LFA protection and is 909 independent of the number of BGP prefixes impacted. 911 6.1.3. A remote iBGP next-hop fails 913 Upon IGP convergence, the IGP leaf for the BGP next-hop is deleted 914 and all the depending BGP Path-Lists are updated to either use the 915 remaining ECMP BGP best-paths or if none remains available to 916 activate precomputed backups. 918 This BGP resiliency property only depends on IGP convergence and is 919 independent of the number of BGP prefixes impacted. 921 6.1.4. A local eBGP next-hop fails 923 Upon local link failure detection, the adjacency to the BGP next-hop 924 is deleted and all the depending BGP pathlists are updated to either 925 use the remaining ECMP BGP best-paths or if none remains available 926 to activate precomputed backups. 928 This BGP resiliency property only depends on local link failure 929 detection and is independent of the number of BGP prefixes impacted. 931 6.2. Performance 933 When the failure is local (a local IGP next-hop failure or a local 934 eBGP next-hop failure), a pre-computed and pre-installed backup is 935 activated by a local-protection mechanism that does not depend on 936 the number of BGP destinations impacted by the failure. Sub-50msec 937 is thus possible even if millions of BGP routes are impacted. 939 When the failure is remote (a remote IGP failure not impacting the 940 BGP next-hop or a remote BGP next-hop failure), an alternate path is 941 activated upon IGP convergence. All the impacted BGP destinations 942 benefit from a working alternate path as soon as the IGP convergence 943 occurs for their impacted BGP next-hop even if millions of BGP 944 routes are impacted. 946 6.2.1. Perspective 948 The following table puts the BGP PIC benefits in perspective 949 assuming 951 o 1M impacted BGP prefixes 953 o IGP convergence ~ 500 msec 955 o local protection ~ 50msec 957 o FIB Update per BGP destination ~ 100usec conservative, 958 ~ 10usec optimistic 960 o BGP Convergence per BGP destination ~ 200usec conservative, 962 ~ 100usec optimistic 964 Without PIC With PIC 966 Local IGP Failure 10 to 100sec 50msec 968 Local BGP Failure 100 to 200sec 50msec 970 Remote IGP Failure 10 to 100sec 500msec 972 Local BGP Failure 100 to 200sec 500msec 974 Upon local IGP next-hop failure or remote IGP next-hop failure, the 975 existing primary BGP next-hop is intact and usable hence the 976 resiliency only depends on the ability of the FIB mechanism to 977 reflect the new path to the BGP next-hop to the depending BGP 978 destinations. Without BGP PIC, a conservative back-of-the-envelope 979 estimation for this FIB update is 100usec per BGP destination. An 980 optimistic estimation is 10usec per entry. 982 Upon local BGP next-hop failure or remote BGP next-hop failure, 983 without the BGP PIC mechanism, a new BGP Best-Path needs to be 984 recomputed and new updates need to be sent to peers. This depends on 985 BGP processing time that will be shared between best-path 986 computation, RIB update and peer update. A conservative back-of-the- 987 envelope estimation for this is 200usec per BGP destination. An 988 optimistic estimation is 100usec per entry. 990 6.3. Automated 992 The BGP PIC solution does not require any operator involvement. The 993 process is entirely automated as part of the FIB implementation. 995 The salient points enabling this automation are: 997 o Extension of the BGP Best Path to compute more than one primary 998 ([11]and [12]) or backup BGP next-hop ([6] and [13]). 1000 o Sharing of BGP Path-list across BGP destinations with same 1001 primary and backup BGP next-hop 1003 o Hierarchical indirection and dependency between BGP pathlist and 1004 IGP pathlist 1006 6.4. Incremental Deployment 1008 As soon as one router supports BGP PIC solution, it benefits from 1009 all its benefits without any requirement for other routers to 1010 support BGP PIC. 1012 7. Dependency 1014 This section describes the required functionality in the forwarding 1015 and control planes to support BGP-PIC described in this document 1017 7.1. Hierarchical Hardware FIB 1019 BGP PIC requires a hierarchical hardware FIB support: for each BGP 1020 forwarded packet, a BGP leaf is looked up, then a BGP Pathlist is 1021 consulted, then an IGP Pathlist, then an Adjacency. 1023 An alternative method consists in "flattening" the dependencies when 1024 programming the BGP destinations into HW FIB resulting in 1025 potentially eliminating both the BGP Path-List and IGP Path-List 1026 consultation. Such an approach decreases the number of memory 1027 lookup's per forwarding operation at the expense of HW FIB memory 1028 increase (flattening means less sharing hence duplication), loss of 1029 ECMP properties (flattening means less pathlist entropy) and loss of 1030 BGP PIC properties. 1032 7.2. Availability of more than one primary or secondary BGP next- 1033 hops 1035 When the primary BGP next-hop fails, BGP PIC depends on the 1036 availability of a pre-computed and pre-installed secondary BGP next- 1037 hop in the BGP Pathlist. 1039 The existence of a secondary next-hop is clear for the following 1040 reason: a service caring for network availability will require two 1041 disjoint network connections hence two BGP next-hops. 1043 The BGP distribution of the secondary next-hop is available thanks 1044 to the following BGP mechanisms: Add-Path [11], BGP Best-External 1045 [6], diverse path [12], and the frequent use in VPN deployments of 1046 different VPN RD's per PE. It is noteworthy to mention that the 1047 availability of another BGP path does not mean that all failure 1048 scenarios can be covered by simply forwarding traffic to the 1049 available secondary path. The discussion of how to cover various 1050 failure scenarios is beyond the scope of this document 1051 7.3. Pre-Computation of a secondary BGP next-hop 1053 [13] describes how a secondary BGP next-hop can be precomputed on a 1054 per BGP destination basis. 1056 8. Security Considerations 1058 The behavior described in this document is internal functionality 1059 to a router that result in significant improvement to convergence 1060 time as well as reduction in CPU and memory used by FIB while not 1061 showing change in basic routing and forwarding functionality. As 1062 such no additional security risk is introduced by using the 1063 mechanisms proposed in this document. 1065 9. IANA Considerations 1067 No requirements for IANA 1069 10. Conclusions 1071 This document proposes a hierarchical and shared forwarding chain 1072 structure that allows achieving BGP prefix independent 1073 convergence, and in the case of locally detected failures, sub-50 1074 msec convergence. A router can construct the forwarding chains in 1075 a completely transparent manner with zero operator intervention 1076 thereby supporting smooth and incremental deployment. 1078 11. References 1080 11.1. Normative References 1082 [1] Bradner, S., "Key words for use in RFCs to Indicate 1083 Requirement Levels", BCP 14, RFC 2119, March 1997. 1085 [2] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 1086 4 (BGP-4), RFC 4271, January 2006 1088 [3] Bates, T., Chandra, R., Katz, D., and Rekhter Y., 1089 "Multiprotocol Extensions for BGP", RFC 4760, January 2007 1091 [4] Y. Rekhter and E. Rosen, " Carrying Label Information in BGP- 1092 4", RFC 3107, May 2001 1094 [5] Andersson, L., Minei, I., and B. Thomas, "LDP Specification", 1095 RFC 5036, October 2007 1097 11.2. Informative References 1099 [6] Marques,P., Fernando, R., Chen, E, Mohapatra, P., Gredler, H., 1100 "Advertisement of the best external route in BGP", draft-ietf- 1101 idr-best-external-05.txt, January 2012. 1103 [7] Wu, J., Cui, Y., Metz, C., and E. Rosen, "Softwire Mesh 1104 Framework", RFC 5565, June 2009. 1106 [8] Rosen, E. and Y. Rekhter, "BGP/MPLS IP Virtual Private 1107 Networks (VPNs)", RFC 4364, February 2006. 1109 [9] De Clercq, J. , Ooms, D., Prevost, S., Le Faucheur, F., 1110 "Connecting IPv6 Islands over IPv4 MPLS Using IPv6 Provider 1111 Edge Routers (6PE)", RFC 4798, February 2007 1113 [10] O. Bonaventure, C. Filsfils, and P. Francois. "Achieving sub- 1114 50 milliseconds recovery upon bgp peering link failures, " 1115 IEEE/ACM Transactions on Networking, 15(5):1123-1135, 2007 1117 [11] D. Walton, A. Retana, E. Chen, J. Scudder, "Advertisement of 1118 Multiple Paths in BGP", draft-ietf-idr-add-paths-12.txt, 1119 November 2015 1121 [12] R. Raszuk, R. Fernando, K. Patel, D. McPherson, K. Kumaki, 1122 "Distribution of diverse BGP paths", RFC 6774, November 2012 1124 [13] P. Mohapatra, R. Fernando, C. Filsfils, and R. Raszuk, "Fast 1125 Connectivity Restoration Using BGP Add-path", draft-pmohapat- 1126 idr-fast-conn-restore-03, Jan 2013 1128 [14] C. Filsfils, S. Previdi, A. Bashandy, B. Decraene, S. 1129 Litkowski, M. Horneffer, R. Shakir, J. Tansura, E. Crabbe 1130 "Segment Routing with MPLS data plane", draft-ietf-spring- 1131 segment-routing-mpls-02 (work in progress), October 2015 1133 [15] C. Filsfils, S. Previdi, A. Bashandy, B. Decraene, " Topology 1134 Independent Fast Reroute using Segment Routing", draft- 1135 francois-spring-segment-routing-ti-lfa-02 (work in progress), 1136 August 2015 1138 [16] M. Shand and S. Bryant, "IP Fast Reroute Framework", RFC 5714, 1139 January 2010 1141 [17] S. Bryant, C. Filsfils, S. Previdi, M. Shand, N So, " Remote 1142 Loop-Free Alternate (LFA) Fast Reroute (FRR)", RFC 7490 April 1143 2015 1145 [18] A. Atlas, C. Bowers, G. Enyedi, " An Architecture for IP/LDP 1146 Fast-Reroute Using Maximally Redundant Trees", draft-ietf- 1147 rtgwg-mrt-frr-architecture-10 (work in progress), February 1148 2016 1150 12. Acknowledgments 1152 Special thanks to Neeraj Malhotra, Yuri Tsier for the valuable 1153 help 1155 Special thanks to Bruno Decraene for the valuable comments 1157 This document was prepared using 2-Word-v2.0.template.dot. 1159 Authors' Addresses 1161 Ahmed Bashandy 1162 Cisco Systems 1163 170 West Tasman Dr, San Jose, CA 95134, USA 1164 Email: bashandy@cisco.com 1166 Clarence Filsfils 1167 Cisco Systems 1168 Brussels, Belgium 1169 Email: cfilsfil@cisco.com 1171 Prodosh Mohapatra 1172 Sproute Networks 1173 Email: mpradosh@yahoo.com