idnits 2.17.1 draft-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 == Line 140 has weird spacing: '... be inter...' == Line 571 has weird spacing: '...al peer as un...' == 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 (March 29, 2013) is 4044 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: 'TBD' on line 633 == Outdated reference: A later version (-05) exists of draft-ietf-idr-best-external-04 == Outdated reference: A later version (-15) exists of draft-ietf-idr-add-paths-07 == Outdated reference: A later version (-03) exists of draft-pmohapat-idr-fast-conn-restore-02 Summary: 0 errors (**), 0 flaws (~~), 7 warnings (==), 2 comments (--). 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: September 2013 P. Mohapatra 5 Cumulus Networks 6 March 29, 2013 7 BGP Prefix Independent Convergence 8 draft-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 path. Given 14 the large scaling targets, it is desirable to restore traffic after 15 failure in a time period that does not depend on the number of BGP 16 prefixes. In this document we proposed a technique by which traffic 17 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 chains in a 20 hierarchical manner and sharing forwarding elements among the maximum 21 possible number of routes. The proposed technique achieves prefix 22 independent convergence while ensuring incremental deployment, 23 complete transparency and automation, and zero management and 24 provisioning effort 26 Status of this Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 This document may contain material from IETF Documents or IETF 32 Contributions published or made publicly available before November 33 10, 2008. The person(s) controlling the copyright in some of this 34 material may not have granted the IETF Trust the right to allow 35 modifications of such material outside the IETF Standards Process. 36 Without obtaining an adequate license from the person(s) 37 controlling the copyright in such materials, this document may not 38 be modified outside the IETF Standards Process, and derivative 39 works of it may not be created outside the IETF Standards Process, 40 except to format it for publication as an RFC or to translate it 41 into languages other than English. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF), its areas, and its working groups. Note that 45 other groups may also distribute working documents as Internet- 46 Drafts. 48 Internet-Drafts are draft documents valid for a maximum of six 49 months and may be updated, replaced, or obsoleted by other 50 documents at any time. It is inappropriate to use Internet-Drafts 51 as reference material or to cite them other than as "work in 52 progress." 54 The list of current Internet-Drafts can be accessed at 55 http://www.ietf.org/ietf/1id-abstracts.txt 57 The list of Internet-Draft Shadow Directories can be accessed at 58 http://www.ietf.org/shadow.html 60 This Internet-Draft will expire on September 29, 2013. 62 Copyright Notice 64 Copyright (c) 2013 IETF Trust and the persons identified as the 65 document authors. All rights reserved. 67 This document is subject to BCP 78 and the IETF Trust's Legal 68 Provisions Relating to IETF Documents 69 (http://trustee.ietf.org/license-info) in effect on the date of 70 publication of this document. Please review these documents 71 carefully, as they describe your rights and restrictions with 72 respect to this document. Code Components extracted from this 73 document must include Simplified BSD License text as described in 74 Section 4.e of the Trust Legal Provisions and are provided without 75 warranty as described in the Simplified BSD License. 77 Table of Contents 79 1. Introduction...................................................3 80 1.1. Conventions used in this document.........................3 81 1.2. Terminology...............................................3 82 2. Constructing the Shared Hierarchical Forwarding Chain..........5 83 2.1. Databases.................................................5 84 2.2. Constructing the forwarding chain from a downloaded route.5 85 2.3. Examples..................................................6 86 2.3.1. Example 1: Forwarding Chain for iBGP ECMP............7 87 2.3.2. Example 2: Primary Backup Paths......................9 88 3. Forwarding Behavior............................................9 89 4. Forwarding Chain Adjustment at a Failure......................10 90 4.1. BGP-PIC core.............................................11 91 4.2. BGP-PIC edge.............................................12 92 4.2.1. Adjusting forwarding Chain in egress node failure...12 93 4.2.2. Adjusting Forwarding Chain on PE-CE link Failure....12 94 4.2.3. Loop Avoidance using Special Label (backup/repair 95 label).....................................................13 96 5. Properties....................................................14 97 6. Dependency....................................................17 98 7. Security Considerations.......................................17 99 8. IANA Considerations...........................................18 100 9. Conclusions...................................................18 101 10. References...................................................18 102 10.1. Normative References....................................18 103 10.2. Informative References..................................18 104 11. Acknowledgments..............................................19 106 1. Introduction 108 As a path vector protocol, BGP is inherently slow due to the 109 serial nature of reachability propagation. BGP speakers exchange 110 reachability information about prefixes[2][3] and, for labeled 111 address families, namely AFI/SAFI 1/4, 2/4, 1/128, and 2/128, an 112 edge router assigns local labels to prefixes and associates the 113 local label with each advertised prefix such as L3VPN [6], 6PE 114 [7], and Softwire [5]. A BGP speaker then applies the path 115 selection steps to choose the best path. In modern networks, it is 116 not uncommon to have a prefix reachable via multiple edge routers. 117 In addition to proprietary techniques, multiple techniques have 118 been proposed to allow for more than one path for a given prefix 119 [4][9][10], whether in the form of equal cost multipath or 120 primary-backup. Another more common and widely deployed scenario 121 is L3VPN with multi-homed VPN sites. 123 This document proposes a hierarchical and shared forwarding chain 124 organization that allows traffic to be restored to pre-calculated 125 alternative equal cost primary path or backup path in a time 126 period that does not depend on the number of BGP prefixes. The 127 technique relies on internal router behavior that is completely 128 transparent to the operator and can be incrementally deployed and 129 enabled with zero operator intervention. 131 1.1. Conventions used in this document 133 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL 134 NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" 135 in this document are to be interpreted as described in RFC-2119 136 [1]. 138 In this document, these words will appear with that interpretation 139 only when in ALL CAPS. Lower case uses of these words are not to 140 be interpreted as carrying RFC-2119 significance. 142 1.2. Terminology 144 This section defines the terms used in this document. For ease of 145 use, we will use terms similar to those used by L3VPN [6] 146 o BGP prefix: It is a prefix P/m (of any AFI/SAFI) that a BGP 147 speaker has a path for. 149 o IGP prefix: It is a prefix P/m (of any AFI/SAFI) that is learnt 150 via an Interior Gateway Protocol, such as OSPF and ISIS, has a 151 path for. The prefix may be learnt directly through the IGP 152 redistributed from other protocol(s) 154 o CE: It is an external router through which an egress PE can 155 reach a prefix P/m. 157 o Ingress PE, "iPE": It is a BGP speaker that learns about a 158 prefix through another IBGP peer and chooses that IBGP peer as 159 the next-hop for the prefix. 161 o Path: It is the next-hop in a sequence of unique connected 162 nodes starting from the current node and ending with the 163 destination node or network identified by the prefix. 165 o Recursive path: It is a path consisting only of the IP address 166 of the next-hop without the outgoing interface. Subsequent 167 lookups are needed to determine the outgoing interface. 169 o Non-recursive path: It is a path consisting of the IP address 170 of the next-hop and one outgoing interface 172 o Primary path: It is a recursive or non-recursive path that can 173 be used all the time. A prefix can have more than one primary 174 path 176 o Backup path: It is a recursive or non-recursive path that can 177 be used only after some or all primary paths become unreachable 179 o Leaf: A leaf is container data structure for a prefix or local 180 label. Alternatively, it is the data structure that contains 181 prefix specific information. 183 o IP leaf: Is the leaf corresponding to an IPv4 or IPv6 prefix 185 o Label leaf. It is the leaf corresponding to a locally allocated 186 label such as the VPN label on an egress PE [6]. 188 o Pathlist: It is an array of paths used by one or more prefix to 189 forward traffic to destination(s) covered by a IP prefix. Each 190 path in the pathlist carries its "path-index" that identifies 191 its position in the array of paths. A pathlist may contain a 192 mix of primary and backup paths 194 o OutLabel-Array: Each labeled prefix is associated with an 195 OutLabel-Array. The OutLabel-Array is a list of one or more 196 outgoing labels and/or label actions where each label or label 197 action has 1-to-1 correspondence to a path in the pathlist. The 198 number of entries in the OutLabel-array is identical to the 199 number of paths in the pathlist and the ith outlabel entry is 200 associated with the path whose path-index is "i". Label actions 201 are: push the label, pop the label, or swap the incoming label 202 with the outlabel. The prefix may be an IGP or BGP prefix 204 o Adjacency: It is the layer 2 encapsulation leading to the layer 205 3 directly connected next-hop 207 o Dependency: An object X is said to be a dependent or Child of 208 object Y if Object Y cannot be deleted unless object X is no 209 longer a dependent/child of object Y 211 o Route: It is a prefix with one or more paths associated with 212 it. Hence the minimum set of objects needed to construct a 213 route is a leaf and a pathlist. 215 2. Constructing the Shared Hierarchical Forwarding Chain 217 2.1. Databases 219 The Forwarding Information Base (FIB) on a router maintains 3 basic 220 databases 222 o Pathlist-DB: A pathlist is uniquely identified by the list of 223 paths. The Pathlist DB contains the set of all shared pathlists 225 o Leaf-DB: A leaf is uniquely identified by the prefix or the label 227 o Adjacency-DB: An adjacency is uniquely identified by the outgoing 228 layer 3 interface and the IP address of the next-hop directly 229 connected to the layer 3 interface. Adjacency DB contains the 230 list of all adjacencies 232 2.2. Constructing the forwarding chain from a downloaded route 234 1. A prefix with a list of paths is downloaded to FIB from BGP. For 235 labeled prefixes, an OutLabel-Array and possibly a local label 236 (e.g. for a VPN [6] prefix on an egress PE) are also downloaded 238 2. If the prefix does not exist, construct a new IP leaf from the 239 downloaded prefix. If a local label is allocated, construct a 240 label leaf from the local label 242 3. Construct an OutLabel-Array and attach the Outlabel array to the 243 IP and label leaf 245 4. The list of paths attached to the route is looked up in the 246 pathlist-DB 248 5. If a pathlist PL is found 250 a. Retrieve the pathlist 252 6. Else 254 a. Construct a new pathlist 256 b. Insert the new pathlist in the pathlist-DB 258 c. Resolve the paths of the pathlist as follows 260 d. Recursive path: 262 i. Lookup the next-hop in the leaf-DB 264 ii. If a leaf with at least one reachable path is found, add 265 the path to the dependency list of the leaf 267 iii. Otherwise the path remains unresolved and cannot be used 268 for forwarding 270 e. Non-recursive path 272 i. Lookup the next-hop and outgoing interface in the 273 adjacency-DB 275 ii. If an adjacency is found, add the path to the dependency 276 list of adjacency 278 iii. Otherwise, create a new adjacency and add the path to 279 its dependency list 281 7. Attach the leaf(s) as (a) dependent(s) of the pathlist 283 As a result of the above steps, a forwarding chain starting with a 284 leaf and ending with one or more adjacency is constructed. It is 285 noteworthy to mention that the forwarding chain is constructed 286 without any operator intervention at all. 288 2.3. Examples 290 This section outlines two examples that we will use for illustration 291 for the rest of the document. The examples use a standard multihomed 292 VPN [6] prefix in a BGP-free core running LDP. The topology is 293 depicted in Figure 1. 295 +-----------------------------------+ 296 | | 297 | LDP Core | 298 | | 299 | ePE2 300 | |\ 301 | | \ 302 | | \ 303 | | \ 304 iPE | CE.......VRF "Blue" 305 | | / (VPN-P1) 306 | | / (VPN-P2) 307 | | / 308 | |/ 309 | ePE1 310 | | 311 | | 312 | | 313 +-----------------------------------+ 314 Figure 1 VPN prefix reachable via multiple PEs 316 The first example is an illustration of ECMP while the second 317 example is an illustration of primary-backup paths 319 2.3.1. Example 1: Forwarding Chain for iBGP ECMP 321 Consider the case of the ingress PE (iPE) in the multi-homed VPN 322 prefixes depicted in Figure 1. Suppose the iPE receives route 323 advertisements for the VPN prefixes VPN-P1 and VPN-P2 from two 324 egress PEs, ePE1 and ePE2 with next-hop BGP-NH1 and BGP-NH2, 325 respectively. Assume that ePE1 advertise the VPN labels VPN-L11 and 326 VPN-L12 while ePE2 advertise the VPN labels VPN-L21 and VPN-L22 for 327 VPN-P1 and VPN-P2, respectively. Suppose that BGP-NH1 and BGP-NH2 328 are resolved via the IGP prefixes IGP-P1 and IGP-P2, which also 329 happen to have 2 ECMP paths with IGP-NH1 and IGP-NH2 reachable via 330 the interfaces I1 and I2. Suppose that LDP on the downstream LSRs 331 for IGP-P1 and IGP-P2 are assign the LDP labels LDP-L1 and LDP-L2 to 332 the prefixes IGP-P1 and IGP-P2. The forwarding chain on the ingress 333 PE "iPE" for the VPN prefixes is depicted in Figure 2. 335 BGP OutLabel Array 336 +---------+ 337 | VPN-L11 | 338 +--->+---------+ 339 | | VPN-L21 | 340 | +---------+ IGP OutLabel Array 341 | +---------+ 342 | | LDP-L11 | 343 | +-->+---------+ 344 | | | LDP-L21 | 345 VPN-P1------+ | +---------+ 346 | | 347 | | 348 | IGP-P1-----+ 349 | ^ | 350 | | | 351 V | V IGP Pathlist 352 +--------+ | +-------------+ 353 |BGP-NH1 |---------------+ | IGP-NH1, I1 |------>adj1 354 BGP +--------+ +-------------+ 355 Pathlist |BGP-NH2 |----+ | IGP-NH2, I2 |------>adj2 356 +--------+ | +-------------+ 357 ^ | ^ 358 | | | 359 | | | 360 | IGP-P2----------------+ 361 | | 362 | | 363 VPN-P2------+ | +---------+ 364 | | | LDP-L12 | 365 | +--->+---------+ 366 | | LDP-L22 | 367 | +---------+ 368 | +---------+ IGP OutLabel Array 369 | | VPN-L12 | 370 +--->+---------+ 371 | VPN-L22 | 372 +---------+ 373 BGP OutLabel Array 375 Figure 2 Forwarding Chain for VPN Prefixes with iBGP ECMP 377 The structure depicted in Figure 2 illustrates the two important 378 properties discussed in this memo: sharing and hierarchy. We can 379 see that the both the BGP and IGP pathlists are shared among 380 multiple BGP and IGP prefixes, respectively. At the same time, the 381 forwarding chain objects depend on each other in a child-parent 382 relation instead of being collapsed into a single level. 384 2.3.2. Example 2: Primary Backup Paths 386 Consider the egress PE ePE1 in the case of the multi-homed VPN 387 prefixes in the BGP-free LDP core depicted in Figure 1. Suppose ePE1 388 determines that the primary path is the external path but the backup 389 path is the iBGP path to the other PE ePE2 with next-hop BGP-NH2. 390 ePE2 constructs the forwarding chain depicted in Figure 1. We are 391 only showing a single VPN prefix for simplicity. But all prefixes 392 that are multihomed to ePE1 and ePE2 share the BGP pathlist 394 BGP OutLabel Array 395 VPL-L11 +---------+ 396 (Label-leaf)---+---->|Unlabeled| 397 | +---------+ 398 | | VPN-L21 | 399 | | (swap) | 400 | +---------+ 401 | ^ 402 | | BGP Pathlist 403 | | +------------+ Connected route 404 | | | CE-NH |------>(to the CE) 405 | | |path-index=0| 406 | | +------------+ 407 V | | VPN-NH2 | 408 VPN-P1 ------------------+------>| (backup) |------>IGP Leaf 409 (IP prefix leaf) |path-index=1| (Towards ePE2) 410 +-----+------+ 412 Figure 3 VPN Prefix Forwarding Chain with eiBGP paths on egress PE 414 The example depicted in Figure 3 differs from the example in Figure 415 2 in two main aspects. First as long as the primary path towards the 416 CE (external path) is useable, it will be the only path used for 417 forwarding while the OutLabel-Array contains both the unlabeled 418 label (primary path) and the VPN label (backup path) advertised by 419 the backup path ePE2. The second aspect is presence of the label 420 leaf corresponding to the VPN prefix. This label leaf is used to 421 match VPN traffic arriving from the core. Note that the label leaf 422 shares the OutLabel-Array and the pathlist with the IP prefix. 424 3. Forwarding Behavior 426 When a packet arrives, it matches a leaf. A labeled packet matches a 427 label leaf while an IP packet matches an IP prefix leaf. The 428 forwarding engines walks the forwarding chain starting from the leaf 429 until the walk terminates on an adjacency. Thus when a packet 430 arrives, the chain is walked as follows: 432 1. Lookup the leaf based on the destination address or the label at 433 the top of the packet 435 2. Retrieve the parent pathlist of the leaf 437 3. Pick the outgoing path from the list of resolved paths in the 438 pathlist. The method by which the outgoing path is picked is 439 beyond the scope of this document (i.e. flow-preserving hash 440 exploiting entropy within the MPLS stack and IP header). Let the 441 "path-index" of the outgoing path be "i". 443 4. If the prefix is labeled, use the "path-index" "i" to retrieve 444 the ith label "Li" stored the ith entry in the OutLabel-Array and 445 apply the label action of the label on the packet (e.g. for VPN 446 label on the ingress PE, the label action is "push"). 448 5. Move to the parent of the chosen path "i" 450 6. If the chosen path "i" is recursive, move to its parent prefix 451 and go to step 2 453 7. If the chosen path "i" is non-recursive move to its parent 454 adjacency 456 8. Encapsulate the packet in the L2 string specified by the 457 adjacency and send the packet out. 459 Let's applying the above forwarding steps to the example described 460 in Figure 1 Section 2.3.1. Suppose a packet arrives at ingress PE 461 iPE from an external neighbor. Assume the packet matches the VPN 462 prefix VPN-P1. While walking the forwarding chain, the forwarding 463 engine applies hashing algorithm to choose the path and the hashing 464 at the BGP level yields path 0 while the hashing at the IGP level 465 yields path 1. In that case, the packet will be sent out of 466 interface I1 with the label stack "LDP-L12,VPN-L21". 468 4. Forwarding Chain Adjustment at a Failure 470 The hierarchical and shared structure of the forwarding chain 471 explained in Section 2 allows modifying a small number of 472 forwarding chain objects to re-route traffic to a pre-calculated 473 equal-cost or backup path without the need to modify the possibly 474 very large number of BGP prefixes. In this section, we go over 475 various core and edge failure scenarios to illustrate how FIB 476 manager can utilize the forwarding chain structure to achieve prefix 477 independent convergence. 479 4.1. BGP-PIC core 481 This section describes the adjustments to the forwarding chain when 482 a core link or node fails but the BGP next-hop remains reachable. 484 There are two case: remote link failure and attached link failure. 485 Node failures are treated as link failures. 487 When a remote link or node fails, IGP receives advertisement 488 indicating a topology change so IGP re-converges to either find a 489 new next-hop and outgoing interface or remove the path completely 490 from the IGP prefix used to resolve BGP next-hops. IGP and LDP 491 download the modified IGP leaves with modified outgoing labels for 492 labeled core. FIB manager modifies the existing IGP leaf by 493 executing the steps outlined in Section 2.2. 495 When a local link fails, FIB manager detects the failure almost 496 immediately. The FIB manager marks the impacted path(s) as unuseable 497 so that only useable paths are used to forward packets. Note that in 498 this particular case there is actually no need even to backwalk to 499 IGP leaves to adjust the OutLabel-Arrays because FIB can rely on the 500 path-index stored in the useable paths in the loadinfo to pick the 501 right label. 503 It is noteworthy to mention that because FIB manager modifies the 504 forwarding chain starting from the IGP leaves only, BGP pathlists 505 and leaves are not modified. Hence traffic restoration occurs within 506 the time frame of IGP convergence, and, for local link failure, 507 within the timeframe of local detection. Thus it is possible to 508 achieve sub-50 msec convergence as described in [8] for local link 509 failure 511 Let's apply the procedure to the forwarding chain depicted in Figure 512 2 Section 2.3.1. Suppose a remote link failure occurs and impacts 513 the first ECMP IGP path to the remote BGP nhop. Upon IGP 514 convergence, the IGP pathlist of the BGP nhop is updated to reflect 515 the new topology (one path instead of two). As soon as the IGP 516 convergence is effective for the BGP nhop entry, the new forwarding 517 state is immediately available to all dependent BGP prefixes. The 518 same behavior would occur if the failure was local such as an 519 interface going down. As soon as the IGP convergence is complete for 520 the BGP nhop IGP route, all its BGP depending routes benefit from 521 the new path. In fact, upon local failure, if LFA protection is 522 enabled for the IGP route to the BGP nhop and a backup path was pre- 523 computed and installed in the pathlist, upon the local interface 524 failure, the LFA backup path is immediately activated (sub-50msec) 525 and thus protection benefits all the depending BGP traffic through 526 the hierarchical forwarding dependency between the routes. 528 4.2. BGP-PIC edge 530 This section describes the adjustments to the forwarding chains as a 531 result of edge node or edge link failure 533 4.2.1. Adjusting forwarding Chain in egress node failure 535 When an edge node fails, IGP on neighboring core nodes send route 536 updates indicating that the edge node is no longer reachable. IGP 537 running on the iBGP peers instructs FIB to remove the IP and label 538 leaves corresponding to the failed edge node from FIB. So FIB 539 manager performs the following steps: 541 o FIB manager deletes the IGP leaf corresponding to the failed edge 542 node 544 o FIB manager backwalks to all dependent BGP pathlists and marks 545 that path using the deleted IGP leaf as unresolved 547 o Note that there is no need to modify BGP leaves because each path 548 in the pathlist carries its path index and hence the correct 549 outgoing label will be picked. So for example the forwarding 550 chain depicted in Figure 2, if the 1st path becomes unresolved, 551 then the forwarding engine will only use the second path path for 552 forwarding. Yet the pathindex of that single resolved path will 553 still be 1 and hence the label VPN-L21 or VPN-L22 will be pushed 555 4.2.2. Adjusting Forwarding Chain on PE-CE link Failure 557 Suppose the link between an edge router and its external peer fails. 558 There are two scenarios (1) the edge node attached to the failed 559 link performs next-hop self and (2) the edge node attached to the 560 failure advertises the IP address of the failed link as the next-hop 561 attribute to its iBGP peers. 563 In the first case, the rest of iBGP peers will remain unaware of the 564 link failure and will continue to forward traffic to the edge node 565 until the edge node attached to the failed link withdraws the BGP 566 prefixes. If the destination prefixes are multi-homed to another 567 iBGP peer, say ePE2, then FIB manager on the edge router detecting 568 the link failure performs the following tasks 570 o FIB manager backwalks to the BGP pathlists marks the path through 571 the failed link to the external peer as unresolved 573 o Hence traffic will be forwarded used the backup path towards ePE2 575 o For labeled traffic 576 o The Outlabel-Array attached to the BGP leaves already 577 contains an entry corresponding to the path towards ePE2. 579 o The label entry in OutLabel-Arrays corresponding to the 580 internal path to ePE2 has swap action and the label 581 advertised by ePE2 583 o For an arriving label packet (e.g. VPN), the top label is 584 swapped with the label advertised by ePE2 586 o For unlabeled traffic, packets are simply redirected towards ePE2 588 In the second case where the edge router uses the IP address of the 589 failed link as the BGP next-hop, the edge router will still perform 590 the previous steps. But, unlike the case of next-hop self, IGP on 591 failed edge node informs the rest of the iBGP peers that IP address 592 of the failed link is no longer reachable. Hence the FIB manager on 593 iBGP peers will delete the IGP leaf corresponding to the IP prefix 594 of the failed link. The behavior of the iBGP peers will be identical 595 to the case of edge node failure outlined in Section 4.2.1. 597 It is noteworthy to mention that because the edge link failure is 598 local to the edge router, sub-50 msec convergence can be achieved as 599 described in [8]. 601 Let's try to apply the case of next-hop self to the forwarding chain 602 depicted in Figure 3. After failure of the link between ePE1 and CE, 603 the forwarding engine will route traffic arriving from the core 604 towards VPN-NH2 with path-index=1. A packet arriving from the core 605 will contain the label VPN-L11 at top. The label VPN-L11 is swaped 606 with the label VPN-L21 and the packet is forwarded towards ePE2 608 4.2.3. Loop Avoidance using Special Label (backup/repair label) 610 The adjustment of the forwarding chain for edge link failure as 611 specified in Section 4.2.2 can lead to loops in the following 612 scenarios: 614 o Unlabeled traffic when the iBGP and eBGP paths are treated as 615 ECMP 617 o Unlabeled traffic if there is an AS-wide single best path such as 618 the case where the MED or LOCAL_PREF [2] is used to determine the 619 best path 621 o Labeled and unlabeled traffic if the edge link failure was due to 622 an external peer failure and the external peer is common to both 623 edge nodes. This scenario results in edge link failure on both 624 iBGP peers and may result in a mutual loop. 626 This section proposes advertising a special label as a path 627 attribute to avoid the possibility of looping. When an edge router 628 has an external path, whether this path is the BGP best path [2] or 629 not [4][10][9], the edge router associates a non-transitive path 630 attribute containing a backup/repair label. The semantics of the 631 backup/repair label is as follows: A packet arriving with the 632 backup/repair label at the top MUST either be sent outside the AS 633 dropped. Details for backup/repair label can be found in [TBD] 635 5. Properties 637 5.1 Coverage 639 All the possible failures are covered, whether they impact a local 640 or remote IGP path or a local or remote BGP nhop as described in 641 Section 4. This section provides details for each failure and now 642 the hierarchical and shared FIB structure proposed in this document 643 allows recovery that does not depend on number of BGP prefixes 645 5.1.1 A remote failure on the path to a BGP nhop 647 Upon IGP convergence, the IGP leaf for the BGP nhop is updated upon 648 IGP convergence and all the BGP depending routes leverage the new 649 IGP forwarding state immediately. 651 This BGP resiliency property only depends on IGP convergence and is 652 independent of the number of BGP prefixes impacted. 654 5.1.2 A local failure on the path to a BGP nhop 656 Upon LFA protection, the IGP leaf for the BGP nhop is updated to use 657 the precomputed LFA backup path and all the BGP depending routes 658 leverage this LFA protection. 660 This BGP resiliency property only depends on LFA protection and is 661 independent of the number of BGP prefixes impacted. 663 5.1.3 A remote iBGP nhop fails 665 Upon IGP convergence, the IGP leaf for the BGP nhop is deleted and 666 all the depending BGP Path-Lists are updated to either use the 667 remaining ECMP BGP best-paths or if none remains available to 668 activate precomputed backups. 670 This BGP resiliency property only depends on IGP convergence and is 671 independent of the number of BGP prefixes impacted. 673 5.1.4 A local eBGP nhop fails 675 Upon local link failure detection, the adjacency to the BGP nhop is 676 deleted and all the depending BGP Path-Lists are updated to either 677 use the remaining ECMP BGP best-paths or if none remains available 678 to activate precomputed backups. 680 This BGP resiliency property only depends on local link failure 681 detection and is independent of the number of BGP prefixes impacted. 683 5.2 Performance 685 When the failure is local (a local IGP nhop failure or a local eBGP 686 nhop failure), a pre-computed and pre-installed backup is activated 687 by a local-protection mechanism that does not depend on the number 688 of BGP destinations impacted by the failure. Sub-50msec is thus 689 possible even if millions of BGP routes are impacted. 691 When the failure is remote (a remote IGP failure not impacting the 692 BGP nhop or a remote BGP nhop failure), an alternate path is 693 activated upon IGP convergence. All the impacted BGP destinations 694 benefit from a working alternate path as soon as the IGP convergence 695 occurs for their impacted BGP nhop even if millions of BGP routes 696 are impacted. 698 5.2.1 Perspective 700 The following table puts the BGP PIC benefits in perspective 701 assuming 703 o 1M impacted BGP prefixes 705 o IGP convergence ~ 500 msec 707 o local protection ~ 50msec 709 o FIB Update per BGP destination ~ 100usec conservative, 711 ~ 10usec optimistic 713 o BGP Convergence per BGP destination ~ 200usec conservative, 715 ~ 100usec optimistic 717 Without PIC With PIC 719 Local IGP Failure 10 to 100sec 50msec 721 Local BGP Failure 100 to 200sec 50msec 723 Remote IGP Failure 10 to 100sec 500msec 725 Local BGP Failure 100 to 200sec 500msec 727 Upon local IGP nhop failure or remote IGP nhop failure, the existing 728 primary BGP nhop is intact and usable hence the resiliency only 729 depends on the ability of the FIB mechanism to reflect the new path 730 to the BGP nhop to the depending BGP destinations. Without BGP PIC, 731 a conservative back-of-the-enveloppe estimation for this FIB update 732 is 100usec per BGP destination. An optimistic estimation is 10usec 733 per entry. 735 Upon local BGP nhop failure or remote BGP nhop failure, without the 736 BGP PIC mechanism, a new BGP Best-Path needs to be recomputed and 737 new updates need to be sent to peers. This depends on BGP processing 738 time that will be shared between best-path computation, RIB update 739 and peer update. A conservative back-of-the-envelope estimation for 740 this is 200usec per BGP destination. An optimistic estimation is 741 100usec per entry. 743 5.3 Automated 745 The BGP PIC solution does not require any operator involvement. The 746 process is entirely automated as part of the FIB implementation. 748 The salient points enabling this automation are: 750 o Extension of the BGP Best Path to compute a backup BGP nhop [11] 752 o Sharing of BGP Path-list across BGP destinations with same 753 primary and backup BGP nhop 755 o Hierarchical indirection and dependency between BGP Path-List and 756 IGP-Path-List 758 5.4 Incremental Deployment 760 As soon as one router supports BGP PIC solution, it benefits from 761 all its benefits without any requirement for other routers to 762 support BGP PIC. 764 6. Dependency 766 This section describes the required functionality in the forwarding 767 and control planes to support BGP-PIC described in this document 769 6.1 Hierarchical Hardware FIB 771 BGP PIC requires a hierarchical hardware FIB support: for each BGP 772 forwarded packet, a BGP leaf is looked up, then a BGP Path-List is 773 consulted, then an IGP Path-List then an Adjacency. 775 An alternative method consists in "flattening" the dependencies when 776 programming the BGP destinations into HW FIB resulting in 777 potentially eliminating both the BGP Path-List and IGP Path-List 778 consultation. Such an approach decreases the number of memory 779 lookup's per forwarding operation at the expense of HW FIB memory 780 increase (flattening means less sharing hence duplication), loss of 781 ECMP properties (flattening means less path-list entropy) and loss 782 of BGP PIC properties. 784 6.2 Availability of a secondary BGP next-hop 786 When the primary BGP nhop fails, BGP PIC depends on the availability 787 of a pre-computed and pre-installed secondary BGP nhop in the BGP 788 Path-List. 790 The existence of a secondary next-hop is clear for the following 791 reason: a service caring for network availability will require two 792 disjoint network connections hence two BGP nhops. 794 The BGP distribution of the secondary next-hop is simple thanks to 795 the following BGP mechanisms: Add-Path [9], BGP Best-External [4], 796 diverse path [10], and the frequent use in VPN deployments of 797 different VPN RD's per PE. 799 6.3 Pre-Computation of a secondary BGP nhop 801 [11] describes how a secondary BGP nhop can be precomputed on a per 802 BGP destination basis. 804 7. Security Considerations 806 No additional security risk is introduced by using the mechanisms 807 proposed in this document 809 8. IANA Considerations 811 No requirements for IANA 813 9. Conclusions 815 This document proposes a hierarchical and shared forwarding chain 816 structure that allows achieving prefix independent convergence, 817 and in the case of locally detected failures, sub-50 msec 818 convergence. A router can construct this forwarding chains in a 819 completely transparent manner with zero operator intervention. It 820 supports incremental deployment. 822 10. References 824 10.1. Normative References 826 [1] Bradner, S., "Key words for use in RFCs to Indicate 827 Requirement Levels", BCP 14, RFC 2119, March 1997. 829 [2] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 830 4 (BGP-4), RFC 4271, January 2006 832 [3] Bates, T., Chandra, R., Katz, D., and Rekhter Y., 833 "Multiprotocol Extensions for BGP", RFC 4760, January 2007 835 10.2. Informative References 837 [4] Marques,P., Fernando, R., Chen, E, Mohapatra, P., Gredler, H., 838 "Advertisement of the best external route in BGP", draft-ietf- 839 idr-best-external-04.txt, April 2011. 841 [5] Wu, J., Cui, Y., Metz, C., and E. Rosen, "Softwire Mesh 842 Framework", RFC 5565, June 2009. 844 [6] Rosen, E. and Y. Rekhter, "BGP/MPLS IP Virtual Private 845 Networks (VPNs)", RFC 4364, February 2006. 847 [7] De Clercq, J. , Ooms, D., Prevost, S., Le Faucheur, F., 848 "Connecting IPv6 Islands over IPv4 MPLS Using IPv6 Provider 849 Edge Routers (6PE)", RFC 4798, February 2007 851 [8] O. Bonaventure, C. Filsfils, and P. Francois. "Achieving sub- 852 50 milliseconds recovery upon bgp peering link failures, " 853 IEEE/ACM Transactions on Networking, 15(5):1123-1135, 2007 855 [9] D. Walton, E. Chen, A. Retana, J. Scudder, "Advertisement of 856 Multiple Paths in BGP", draft-ietf-idr-add-paths-07.txt, June 857 2012 859 [10] R. Raszuk, R. Fernando, K. Patel, D. McPherson, K. Kumaki, 860 "Distribution of diverse BGP paths", draft-ietf-grow-diverse- 861 bgp-path-dist-08.txt, July 2012 863 [11] P. Mohapatra, R. Fernando, C. Filsfils, and R. Raszuk, "Fast 864 Connectivity Restoration Using BGP Add-path", draft-pmohapat- 865 idr-fast-conn-restore-02, October 2011 867 11. Acknowledgments 869 Special thanks to Neeraj Malhotra and Yuri Tsier for the valuable 870 help 872 This document was prepared using 2-Word-v2.0.template.dot. 874 Authors' Addresses 876 Ahmed Bashandy 877 Cisco Systems 878 170 West Tasman Dr, San Jose, CA 95134 879 Email: bashandy@cisco.com 881 Clarence Filsfils 882 Cisco Systems 883 Brussels, Belgium 884 Email: cfilsfil@cisco.com 886 Prodosh Mohapatra 887 Cumulus Networks 888 Email: pmohapat@cumulusnetworks.com