idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-architecture-05.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 : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([RFC5286]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (January 19, 2015) is 3375 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'R' is mentioned on line 418, but not defined == Missing Reference: 'F' is mentioned on line 1421, but not defined == Missing Reference: 'C' is mentioned on line 418, but not defined == Missing Reference: 'I' is mentioned on line 416, but not defined == Missing Reference: 'G' is mentioned on line 1421, but not defined == Missing Reference: 'J' is mentioned on line 420, but not defined == Missing Reference: 'RFC 5331' is mentioned on line 580, but not defined == Missing Reference: 'A' is mentioned on line 1165, but not defined == Missing Reference: 'ABR1' is mentioned on line 1175, but not defined == Missing Reference: 'H' is mentioned on line 1421, but not defined == Missing Reference: 'E' is mentioned on line 1421, but not defined == Unused Reference: 'RFC2328' is defined on line 1732, but no explicit reference was found in the text -- No information found for draft-rtgwg-mrt-frr-algorithm - is the name correct? -- Possible downref: Normative reference to a draft: ref. 'I-D.ietf-rtgwg-mrt-frr-algorithm' ** Downref: Normative reference to an Informational RFC: RFC 5714 == Outdated reference: A later version (-03) exists of draft-atlas-mpls-ldp-mrt-01 == Outdated reference: A later version (-03) exists of draft-atlas-ospf-mrt-02 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-remote-lfa-10 == Outdated reference: A later version (-02) exists of draft-li-isis-mrt-01 == Outdated reference: A later version (-05) exists of draft-psarkar-rtgwg-rlfa-node-protection-04 -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) Summary: 2 errors (**), 0 flaws (~~), 19 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group A. Atlas, Ed. 3 Internet-Draft R. Kebler 4 Intended status: Standards Track C. Bowers 5 Expires: July 23, 2015 Juniper Networks 6 G. Enyedi 7 A. Csaszar 8 J. Tantsura 9 Ericsson 10 R. White 11 VCE 12 January 19, 2015 14 An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees 15 draft-ietf-rtgwg-mrt-frr-architecture-05 17 Abstract 19 With increasing deployment of Loop-Free Alternates (LFA) [RFC5286], 20 it is clear that a complete solution for IP and LDP Fast-Reroute is 21 required. This specification provides that solution. IP/LDP Fast- 22 Reroute with Maximally Redundant Trees (MRT-FRR) is a technology that 23 gives link-protection and node-protection with 100% coverage in any 24 network topology that is still connected after the failure. 26 MRT removes all need to engineer for coverage. MRT is also extremely 27 computationally efficient. For any router in the network, the MRT 28 computation is less than the LFA computation for a node with three or 29 more neighbors. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on July 23, 2015. 48 Copyright Notice 50 Copyright (c) 2015 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1. Importance of 100% Coverage . . . . . . . . . . . . . . . 5 67 1.2. Partial Deployment and Backwards Compatibility . . . . . 6 68 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 6 69 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 70 4. Maximally Redundant Trees (MRT) . . . . . . . . . . . . . . . 8 71 5. Maximally Redundant Trees (MRT) and Fast-Reroute . . . . . . 10 72 6. Unicast Forwarding with MRT Fast-Reroute . . . . . . . . . . 11 73 6.1. MRT Forwarding Mechanisms . . . . . . . . . . . . . . . . 11 74 6.1.1. MRT LDP labels . . . . . . . . . . . . . . . . . . . 11 75 6.1.1.1. Topology-scoped FEC encoded using a single label 76 (Option 1A) . . . . . . . . . . . . . . . . . . . 12 77 6.1.1.2. Topology and FEC encoded using a two label stack 78 (Option 1B) . . . . . . . . . . . . . . . . . . . 12 79 6.1.1.3. Compatibility of Option 1A and 1B . . . . . . . . 13 80 6.1.1.4. Mandatory support for MRT LDP Label option 1A . . 13 81 6.1.2. MRT IP tunnels (Options 2A and 2B) . . . . . . . . . 13 82 6.2. Forwarding LDP Unicast Traffic over MRT Paths . . . . . . 14 83 6.2.1. Forwarding LDP traffic using MRT LDP Labels (Option 84 1A) . . . . . . . . . . . . . . . . . . . . . . . . . 14 85 6.2.2. Forwarding LDP traffic using MRT LDP Labels (Option 86 1B) . . . . . . . . . . . . . . . . . . . . . . . . . 15 87 6.2.3. Other considerations for forwarding LDP traffic using 88 MRT LDP Labels . . . . . . . . . . . . . . . . . . . 15 89 6.3. Forwarding IP Unicast Traffic over MRT Paths . . . . . . 15 90 6.3.1. Tunneling IP traffic using MRT LDP Labels . . . . . . 16 91 6.3.1.1. Tunneling IP traffic using MRT LDP Labels (Option 92 1A) . . . . . . . . . . . . . . . . . . . . . . . 16 93 6.3.1.2. Tunneling IP traffic using MRT LDP Labels (Option 94 1B) . . . . . . . . . . . . . . . . . . . . . . . 16 95 6.3.2. Tunneling IP traffic using MRT IP Tunnels . . . . . . 17 96 6.3.3. Required support . . . . . . . . . . . . . . . . . . 17 97 7. MRT Island Formation . . . . . . . . . . . . . . . . . . . . 17 98 7.1. IGP Area or Level . . . . . . . . . . . . . . . . . . . . 17 99 7.2. Support for a specific MRT profile . . . . . . . . . . . 18 100 7.3. Excluding additional routers and interfaces from the MRT 101 Island . . . . . . . . . . . . . . . . . . . . . . . . . 18 102 7.3.1. Existing IGP exclusion mechanisms . . . . . . . . . . 18 103 7.3.2. MRT-specific exclusion mechanism . . . . . . . . . . 19 104 7.4. Connectivity . . . . . . . . . . . . . . . . . . . . . . 19 105 7.5. Example algorithm . . . . . . . . . . . . . . . . . . . . 19 106 8. MRT Profile . . . . . . . . . . . . . . . . . . . . . . . . . 19 107 8.1. MRT Profile Options . . . . . . . . . . . . . . . . . . . 19 108 8.2. Router-specific MRT paramaters . . . . . . . . . . . . . 20 109 8.3. Default MRT profile . . . . . . . . . . . . . . . . . . . 21 110 9. LDP signaling extensions and considerations . . . . . . . . . 22 111 10. Inter-area Forwarding Behavior . . . . . . . . . . . . . . . 22 112 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A . . 23 113 10.1.1. Motivation for Creating the Rainbow-FEC . . . . . . 23 114 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) . . 24 115 10.3. ABR Forwarding Behavior with LDP Label option 1B . . . . 24 116 11. Prefixes Multiply Attached to the MRT Island . . . . . . . . 26 117 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint 118 Selection . . . . . . . . . . . . . . . . . . . . . . . 28 119 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 29 120 11.2.1. Computing if an Island Neighbor (IN) is loop-free . 31 121 11.3. MRT Alternates for Destinations Outside the MRT Island . 32 122 12. Network Convergence and Preparing for the Next Failure . . . 33 123 12.1. Micro-forwarding loop prevention and MRTs . . . . . . . 33 124 12.2. MRT Recalculation . . . . . . . . . . . . . . . . . . . 33 125 13. Implementation Status . . . . . . . . . . . . . . . . . . . . 34 126 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 36 127 15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36 128 16. Security Considerations . . . . . . . . . . . . . . . . . . . 36 129 17. References . . . . . . . . . . . . . . . . . . . . . . . . . 36 130 17.1. Normative References . . . . . . . . . . . . . . . . . . 36 131 17.2. Informative References . . . . . . . . . . . . . . . . . 37 132 Appendix A. General Issues with Area Abstraction . . . . . . . . 39 133 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40 135 1. Introduction 137 This document gives a complete solution for IP/LDP fast-reroute 138 [RFC5714]. MRT-FRR creates two alternate trees separate from the 139 primary next-hop forwarding used during stable operation. These two 140 trees are maximally diverse from each other, providing link and node 141 protection for 100% of paths and failures as long as the failure does 142 not cut the network into multiple pieces. This document defines the 143 architecture for IP/LDP fast-reroute with MRT. The associated 144 protocol extensions are defined in [I-D.atlas-ospf-mrt] and 145 [I-D.atlas-mpls-ldp-mrt]. The exact MRT algorithm is defined in 146 [I-D.ietf-rtgwg-mrt-frr-algorithm]. 148 IP/LDP Fast-Reroute with MRT (MRT-FRR) uses two maximally diverse 149 forwarding topologies to provide alternates. A primary next-hop 150 should be on only one of the diverse forwarding topologies; thus, the 151 other can be used to provide an alternate. Once traffic has been 152 moved to one of MRTs, it is not subject to further repair actions. 153 Thus, the traffic will not loop even if a worse failure (e.g. node) 154 occurs when protection was only available for a simpler failure (e.g. 155 link). 157 In addition to supporting IP and LDP unicast fast-reroute, the 158 diverse forwarding topologies and guarantee of 100% coverage permit 159 fast-reroute technology to be applied to multicast traffic as 160 described in [I-D.atlas-rtgwg-mrt-mc-arch]. 162 Other existing or proposed solutions are partial solutions or have 163 significant issues, as described below. 165 Summary Comparison of IP/LDP FRR Methods 167 +---------+-------------+-------------+-----------------------------+ 168 | Method | Coverage | Alternate | Computation (in SPFs) | 169 | | | Looping? | | 170 +---------+-------------+-------------+-----------------------------+ 171 | MRT-FRR | 100% | None | less than 3 | 172 | | Link/Node | | | 173 | | | | | 174 | LFA | Partial | Possible | per neighbor | 175 | | Link/Node | | | 176 | | | | | 177 | Remote | Partial | Possible | per neighbor (link) or | 178 | LFA | Link/Node | | neighbor's neighbor (node) | 179 | | | | | 180 | Not-Via | 100% | None | per link and node | 181 | | Link/Node | | | 182 +---------+-------------+-------------+-----------------------------+ 184 Table 1 186 Loop-Free Alternates (LFA): LFAs [RFC5286] provide limited 187 topology-dependent coverage for link and node protection. 188 Restrictions on choice of alternates can be relaxed to improve 189 coverage, but this can cause forwarding loops if a worse failure 190 is experienced than protected against. Augmenting a network to 191 provide better coverage is NP-hard [LFARevisited]. [RFC6571] 192 discusses the applicability of LFA to different topologies with a 193 focus on common PoP architectures. 195 Remote LFA: Remote LFAs [I-D.ietf-rtgwg-remote-lfa] improve 196 coverage over LFAs for link protection but still cannot guarantee 197 complete coverage. The trade-off of looping traffic to improve 198 coverage is still made. Remote LFAs can provide node-protection 199 [I-D.psarkar-rtgwg-rlfa-node-protection] but not guaranteed 200 coverage and the computation required is quite high (an SPF for 201 each PQ-node evaluated). [I-D.bryant-ipfrr-tunnels] describes 202 additional mechanisms to further improve coverage, at the cost of 203 added complexity. 205 Not-Via: Not-Via [I-D.ietf-rtgwg-ipfrr-notvia-addresses] is the 206 only other solution that provides 100% coverage for link and node 207 failures and does not have potential looping. However, the 208 computation is very high (an SPF per failure point) and academic 209 implementations [LightweightNotVia] have found the address 210 management complexity to be high. 212 1.1. Importance of 100% Coverage 214 Fast-reroute is based upon the single failure assumption - that the 215 time between single failures is long enough for a network to 216 reconverge and start forwarding on the new shortest paths. That does 217 not imply that the network will only experience one failure or 218 change. 220 It is straightforward to analyze a particular network topology for 221 coverage. However, a real network does not always have the same 222 topology. For instance, maintenance events will take links or nodes 223 out of use. Simply costing out a link can have a significant effect 224 on what LFAs are available. Similarly, after a single failure has 225 happened, the topology is changed and its associated coverage. 226 Finally, many networks have new routers or links added and removed; 227 each of those changes can have an effect on the coverage for 228 topology-sensitive methods such as LFA and Remote LFA. If fast- 229 reroute is important for the network services provided, then a method 230 that guarantees 100% coverage is important to accomodate natural 231 network topology changes. 233 Asymmetric link costs are also a common aspect of networks. There 234 are at least three common causes for them. First, any broadcast 235 interface is represented by a pseudo-node and has asymmetric link 236 costs to and from that pseudo-node. Second, when routers come up or 237 a link with LDP comes up, it is recommended in [RFC5443] and 238 [RFC3137] that the link metric be raised to the maximum cost; this 239 may not be symmetric and for [RFC3137] is not expected to be. Third, 240 techniques such as IGP metric tuning for traffic-engineering can 241 result in asymmetric link costs. A fast-reroute solution needs to 242 handle network topologies with asymmetric link costs. 244 When a network needs to use a micro-loop prevention mechanism 245 [RFC5715] such as Ordered FIB[I-D.ietf-rtgwg-ordered-fib] or Farside 246 Tunneling[RFC5715], then the whole IGP area needs to have alternates 247 available so that the micro-loop prevention mechanism, which requires 248 slower network convergence, can take the necessary time without 249 adversely impacting traffic. Without complete coverage, traffic to 250 the unprotected destinations will be dropped for significantly longer 251 than with current convergence - where routers individually converge 252 as fast as possible. 254 1.2. Partial Deployment and Backwards Compatibility 256 MRT-FRR supports partial deployment. As with many new features, the 257 protocols (OSPF, LDP, ISIS) indicate their capability to support MRT. 258 Inside the MRT-capable connected group of routers (referred to as an 259 MRT Island), the MRTs are computed. Alternates to destinations 260 outside the MRT Island are computed and depend upon the existence of 261 a loop-free neighbor of the MRT Island for that destination. 263 2. Requirements Language 265 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 266 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 267 document are to be interpreted as described in [RFC2119] 269 3. Terminology 271 network graph: A graph that reflects the network topology where all 272 links connect exactly two nodes and broadcast links have been 273 transformed into the standard pseudo-node representation. 275 Redundant Trees (RT): A pair of trees where the path from any node 276 X to the root R along the first tree is node-disjoint with the 277 path from the same node X to the root along the second tree. 278 These can be computed in 2-connected graphs. 280 Maximally Redundant Trees (MRT): A pair of trees where the path 281 from any node X to the root R along the first tree and the path 282 from the same node X to the root along the second tree share the 283 minimum number of nodes and the minimum number of links. Each 284 such shared node is a cut-vertex. Any shared links are cut-links. 285 Any RT is an MRT but many MRTs are not RTs. 287 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 288 used to described the associated forwarding topology and MT-ID. 289 Specifically, MRT-Red is the decreasing MRT where links in the 290 GADAG are taken in the direction from a higher topologically 291 ordered node to a lower one. 293 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 294 used to described the associated forwarding topology and MT-ID. 295 Specifically, MRT-Blue is the increasing MRT where links in the 296 GADAG are taken in the direction from a lower topologically 297 ordered node to a higher one. 299 Rainbow MRT: It is useful to have an MT-ID that refers to the 300 multiple MRT topologies and to the default topology. This is 301 referred to as the Rainbow MRT MT-ID and is used by LDP to reduce 302 signaling and permit the same label to always be advertised to all 303 peers for the same (MT-ID, Prefix). 305 MRT Island: The set of routers that support a particular MRT 306 profile and the links connecting them that support MRT. 308 Island Border Router (IBR): A router in the MRT Island that is 309 connected to a router not in the MRT Island and both routers are 310 in a common area or level. 312 Island Neighbor (IN): A router that is not in the MRT Island but is 313 adjacent to an IBR and in the same area/level as the IBR. 315 cut-link: A link whose removal partitions the network. A cut-link 316 by definition must be connected between two cut-vertices. If 317 there are multiple parallel links, then they are referred to as 318 cut-links in this document if removing the set of parallel links 319 would partition the network graph. 321 cut-vertex: A vertex whose removal partitions the network graph. 323 2-connected: A graph that has no cut-vertices. This is a graph 324 that requires two nodes to be removed before the network is 325 partitioned. 327 2-connected cluster: A maximal set of nodes that are 2-connected. 329 2-edge-connected: A network graph where at least two links must be 330 removed to partition the network. 332 block: Either a 2-connected cluster, a cut-edge, or an isolated 333 vertex. 335 DAG: Directed Acyclic Graph - a graph where all links are directed 336 and there are no cycles in it. 338 ADAG: Almost Directed Acyclic Graph - a graph that, if all links 339 incoming to the root were removed, would be a DAG. 341 GADAG: Generalized ADAG - a graph that is the combination of the 342 ADAGs of all blocks. 344 named proxy-node: A proxy-node can represent a destination prefix 345 that can be attached to the MRT Island via at least two routers. 346 It is named if there is a way that traffic can be encapsulated to 347 reach specifically that proxy node; this could be because there is 348 an LDP FEC for the associated prefix or because MRT-Red and MRT- 349 Blue IP addresses are advertised in an undefined fashion for that 350 proxy-node. 352 4. Maximally Redundant Trees (MRT) 354 A pair of Maximally Redundant Trees is a pair of directed spanning 355 trees that provides maximally disjoint paths towards their common 356 root. Only links or nodes whose failure would partition the network 357 (i.e. cut-links and cut-vertices) are shared between the trees. The 358 algorithm to compute MRTs is given in 359 [I-D.ietf-rtgwg-mrt-frr-algorithm]. This algorithm can be computed 360 in O(e + n log n); it is less than three SPFs. Modeling results 361 comparing the alternate path lengths obtained with MRT to other 362 approaches are described in [I-D.ietf-rtgwg-mrt-frr-algorithm]. This 363 document describes how the MRTs can be used and not how to compute 364 them. 366 MRT provides destination-based trees for each destination. Each 367 router stores its normal primary next-hop(s) as well as MRT-Blue 368 next-hop(s) and MRT-Red next-hop(s) toward each destination. The 369 alternate will be selected between the MRT-Blue and MRT-Red. 371 The most important thing to understand about MRTs is that for each 372 pair of destination-routed MRTs, there is a path from every node X to 373 the destination D on the Blue MRT that is as disjoint as possible 374 from the path on the Red MRT. 376 For example, in Figure 1, there is a network graph that is 377 2-connected in (a) and associated MRTs in (b) and (c). One can 378 consider the paths from B to R; on the Blue MRT, the paths are 379 B->F->D->E->R or B->C->D->E->R. On the Red MRT, the path is B->A->R. 380 These are clearly link and node-disjoint. These MRTs are redundant 381 trees because the paths are disjoint. 383 [E]---[D]---| [E]<--[D]<--| [E]-->[D]---| 384 | | | | ^ | | | 385 | | | V | | V V 386 [R] [F] [C] [R] [F] [C] [R] [F] [C] 387 | | | ^ ^ ^ | | 388 | | | | | | V | 389 [A]---[B]---| [A]-->[B]---| [A]<--[B]<--| 391 (a) (b) (c) 392 a 2-connected graph Blue MRT towards R Red MRT towards R 394 Figure 1: A 2-connected Network 396 By contrast, in Figure 2, the network in (a) is not 2-connected. If 397 F, G or the link F<->G failed, then the network would be partitioned. 398 It is clearly impossible to have two link-disjoint or node-disjoint 399 paths from G, I or J to R. The MRTs given in (b) and (c) offer paths 400 that are as disjoint as possible. For instance, the paths from B to 401 R are the same as in Figure 1 and the path from G to R on the Blue 402 MRT is G->F->D->E->R and on the Red MRT is G->F->B->A->R. 404 [E]---[D]---| 405 | | | |----[I] 406 | | | | | 407 [R]---[C] [F]---[G] | 408 | | | | | 409 | | | |----[J] 410 [A]---[B]---| 412 (a) 413 a non-2-connected graph 415 [E]<--[D]<--| [E]-->[D] 416 | ^ | [I] | |----[I] 417 V | | | V V ^ 418 [R] [C] [F]<--[G] | [R]<--[C] [F]<--[G] | 419 ^ ^ ^ V ^ | | 420 | | |----[J] | | [J] 421 [A]-->[B]---| [A]<--[B]<--| 423 (b) (c) 424 Blue MRT towards R Red MRT towards R 426 Figure 2: A non-2-connected network 428 5. Maximally Redundant Trees (MRT) and Fast-Reroute 430 In normal IGP routing, each router has its shortest-path-tree to all 431 destinations. From the perspective of a particular destination, D, 432 this looks like a reverse SPT (rSPT). To use maximally redundant 433 trees, in addition, each destination D has two MRTs associated with 434 it; by convention these will be called the MRT-Blue and MRT-Red. 435 MRT-FRR is realized by using multi-topology forwarding. There is a 436 MRT-Blue forwarding topology and a MRT-Red forwarding topology. 438 Any IP/LDP fast-reroute technique beyond LFA requires an additional 439 dataplane procedure, such as an additional forwarding mechanism. The 440 well-known options are multi-topology forwarding (used by MRT-FRR), 441 tunneling (e.g. [I-D.ietf-rtgwg-ipfrr-notvia-addresses] or 442 [I-D.ietf-rtgwg-remote-lfa]), and per-interface forwarding (e.g. 443 Loop-Free Failure Insensitive Routing in [EnyediThesis]). 445 When there is a link or node failure affecting, but not partitioning, 446 the network, each node will still have at least one path via one of 447 the MRTs to reach the destination D. For example, in Figure 2, C 448 would normally forward traffic to R across the C<->R link. If that 449 C<->R link fails, then C could use the Blue MRT path C->D->E->R. 451 As is always the case with fast-reroute technologies, forwarding does 452 not change until a local failure is detected. Packets are forwarded 453 along the shortest path. The appropriate alternate to use is pre- 454 computed. [I-D.ietf-rtgwg-mrt-frr-algorithm] describes exactly how 455 to determine whether the MRT-Blue next-hops or the MRT-Red next-hops 456 should be the MRT alternate next-hops for a particular primary next- 457 hop to a particular destination. 459 MRT alternates are always available to use. It is a local decision 460 whether to use an MRT alternate, a Loop-Free Alternate or some other 461 type of alternate. 463 As described in [RFC5286], when a worse failure than is anticipated 464 happens, using LFAs that are not downstream neighbors can cause 465 micro-looping. Section 1.1 of [RFC5286] gives an example of link- 466 protecting alternates causing a loop on node failure. Even if a 467 worse failure than anticipated happens, the use of MRT alternates 468 will not cause looping. Therefore, while node-protecting LFAs may be 469 preferred, the certainty that no alternate-induced looping will occur 470 is an advantage of using MRT alternates when the available node- 471 protecting LFA is not a downstream path. 473 6. Unicast Forwarding with MRT Fast-Reroute 475 As mentioned before, MRT FRR needs multi-topology forwarding. 476 Unfortunately, neither IP nor LDP provides extra bits for a packet to 477 indicate its topology. Once the MRTs are computed, the two sets of 478 MRTs can be used as two additional forwarding topologies. The same 479 considerations apply for forwarding along the MRTs as for handling 480 multiple topologies. 482 There are three possible types of routers involved in forwarding a 483 packet along an MRT path. At the MRT ingress router, the packet 484 leaves the shortest path to the destination and follows an MRT path 485 to the destination. In a FRR application, the MRT ingress router is 486 the PLR. An MRT transit router takes a packet that arrives already 487 associated with the particular MRT, and forwards it on that same MRT. 488 In some situations (to be discussed later), the packet will need to 489 leave the MRT path and return to the shortest path. This takes place 490 at the MRT egress router. The MRT ingress and egress functionality 491 may depend on the underlying type of packet being forwarded (LDP or 492 IP). The MRT transit functionality is independent of the type of 493 packet being forwarded. We first consider several MRT transit 494 forwarding mechanisms. Then we look at how these forwarding 495 mechanisms can be applied to carrying LDP and IP traffic. 497 6.1. MRT Forwarding Mechanisms 499 The following options for MRT forwarding mechanisms are considered. 501 1. MRT LDP Labels 503 A. Topology-scoped FEC encoded using a single label 505 B. Topology and FEC encoded using a two label stack 507 2. MRT IP Tunnels 509 A. MRT IPv4 Tunnels 511 B. MRT IPv6 Tunnels 513 6.1.1. MRT LDP labels 515 We consider two options for the MRT forwarding mechanisms using MRT 516 LDP labels. 518 6.1.1.1. Topology-scoped FEC encoded using a single label (Option 1A) 520 [I-D.ietf-mpls-ldp-multi-topology] provides a mechanism to distribute 521 FEC-Label bindings scoped to a given topology (represented by MT-ID). 522 To use multi-topology LDP to create MRT forwarding topologies, we 523 associate two MT-IDs with the MRT-Red and MRT-Blue forwarding 524 topologies, in addition to the default shortest path forwarding 525 topology with MT-ID=0. 527 With this forwarding mechanism, a single label is distributed for 528 each topology-scoped FEC. For a given FEC in the default topology 529 (call it default-FEC-A), two additional topology-scoped FECs would be 530 created, corresponding to the Red and Blue MRT forwarding topologies 531 (call them red-FEC-A and blue-FEC-A). A router supporting this MRT 532 transit forwarding mechanism advertises a different FEC-label binding 533 for each of the three topology-scoped FECs. When a packet is 534 received with a label corresponding to red-FEC-A (for example), an 535 MRT transit router will determine the next-hop for the MRT-Red 536 forwarding topology for that FEC, swap the incoming label with the 537 outgoing label corresponding to red-FEC-A learned from the MRT-Red 538 next-hop router, and forward the packet. 540 This forwarding mechanism has the useful property that the FEC 541 associated with the packet is maintained in the labels at each hop 542 along the MRT. We will take advantage of this property when 543 specifying how to carry LDP traffic on MRT paths using multi-topology 544 LDP labels. 546 This approach is very simple for hardware to support. However, it 547 reduces the label space for other uses, and it increases the memory 548 needed to store the labels and the communication required by LDP to 549 distribute FEC-label bindings. 551 This forwarding option uses the LDP signaling extensions described in 552 [I-D.ietf-mpls-ldp-multi-topology]. The MRT-specific LDP extensions 553 required to support this option are described in 554 [I-D.atlas-mpls-ldp-mrt]. 556 6.1.1.2. Topology and FEC encoded using a two label stack (Option 1B) 558 With this forwarding mechanism, a two label stack is used to encode 559 the topology and the FEC of the packet. The top label (topology-id 560 label) identifies the MRT forwarding topology, while the second label 561 (FEC label) identifies the FEC. The top label would be a new FEC 562 type with two values corresponding to MRT Red and Blue topologies. 564 When an MRT transit router receives a packet with a topology-id 565 label, the router pops the top label and uses that it to guide the 566 next-hop selection in combination with the next label in the stack 567 (the FEC label). The router then swaps the FEC label, using the FEC- 568 label bindings learned through normal LDP mechanisms. The router 569 then pushes the topology-id label for the next-hop. 571 As with Option 1A, this forwarding mechanism also has the useful 572 property that the FEC associated with the packet is maintained in the 573 labels at each hop along the MRT. 575 This forwarding mechanism has minimal usage of additional labels, 576 memory and LDP communication. It does increase the size of packets 577 and the complexity of the required label operations and look-ups. 579 This forwarding option is consistent with context-specific label 580 spaces, as described in [RFC 5331]. However, the precise LDP 581 behavior required to support this option for MRT has not been 582 specified. 584 6.1.1.3. Compatibility of Option 1A and 1B 586 In principle, MRT transit forwarding mechanisms 1A and 1B can coexist 587 in the same network, with a packet being forwarding along a single 588 MRT path using the single label of option 1A for some hops and the 589 two label stack of option 1B for other hops. 591 6.1.1.4. Mandatory support for MRT LDP Label option 1A 593 If a router supports a profile that includes the MRT LDP Label option 594 for MRT transit forwarding mechanism, then it MUST support option 1A, 595 which encodes topology-scoped FECs using a single label. 597 6.1.2. MRT IP tunnels (Options 2A and 2B) 599 IP tunneling can also be used as an MRT transit forwarding mechanism. 600 Each router supporting this MRT transit forwarding mechanism 601 announces two additional loopback addresses and their associated MRT 602 color. Those addresses are used as destination addresses for MRT- 603 blue and MRT-red IP tunnels respectively. The special loopback 604 addresses allow the transit nodes to identify the traffic as being 605 forwarded along either the MRT-blue or MRT-red topology to reach the 606 tunnel destination. Announcements of these two additional loopback 607 addresses per router with their MRT color requires IGP extensions, 608 which have not been defined. 610 Either IPv4 (option 2A) or IPv6 (option 2B) can be used as the 611 tunneling mechanism. 613 Note that the two forwarding mechanisms using LDP Label options do 614 not require additional loopbacks per router, as is required by the IP 615 tunneling mechanism. This is because LDP labels are used on a hop- 616 by-hop basis to identify MRT-blue and MRT-red forwarding topologies. 618 6.2. Forwarding LDP Unicast Traffic over MRT Paths 620 In the previous section, we examined several options for providing 621 MRT transit forwarding functionality, which is independent of the 622 type of traffic being carried. We now look at the MRT ingress 623 functionality, which will depend on the type of traffic being carried 624 (IP or LDP). We start by considering LDP traffic. 626 We also simplify the initial discussion by assuming that the network 627 consists of a single IGP area, and that all routers in the network 628 participate in MRT. Other deployment scenarios that require MRT 629 egress functionality are considered later in this document. 631 In principle, it is possible to carry LDP traffic in MRT IP tunnels. 632 However, for LDP traffic, it is very desirable to avoid tunneling. 633 Tunneling LDP traffic to a remote node requires knowledge of remote 634 FEC-label bindings so that the LDP traffic can continue to be 635 forwarded properly when it leaves the tunnel. This requires targeted 636 LDP sessions which can add management complexity. The two MRT LDP 637 Label forwarding mechanisms have the useful property that the FEC 638 associated with the packet is maintained in the labels at each hop 639 along the MRT, as long as an MRT to the originator of the FEC is 640 used. The MRT IP tunneling mechanism does not have this useful 641 property. Therefore, this document only considers the two MRT LDP 642 Label forwarding mechanisms for protecting LDP traffic with MRT fast- 643 reroute. 645 6.2.1. Forwarding LDP traffic using MRT LDP Labels (Option 1A) 647 The MRT LDP Label option 1A forwarding mechanism uses topology-scoped 648 FECs encoded using a single label as described in section 649 Section 6.1.1.1. When a PLR receives an LDP packet that needs to be 650 forwarded on the Red MRT (for example), it does a label swap 651 operation, replacing the usual LDP label for the FEC with the Red MRT 652 label for that FEC received from the next-hop router in the Red MRT 653 computed by the PLR. When the next-hop router in the Red MRT 654 receives the packet with the Red MRT label for the FEC, the MRT 655 transit forwarding functionality continues as described in 656 Section 6.1.1.1. In this way the original FEC associated with the 657 packet is maintained at each hop along the MRT. 659 6.2.2. Forwarding LDP traffic using MRT LDP Labels (Option 1B) 661 The MRT LDP Label option 1B forwarding mechanism encodes the topology 662 and the FEC using a two label stack as described in Section 6.1.1.2. 663 When a PLR receives an LDP packet that needs to be forwarded on the 664 Red MRT, it first does a normal LDP label swap operation, replacing 665 the incoming normal LDP label associated with a given FEC with the 666 outgoing normal LDP label for that FEC learned from the next-hop on 667 the Red MRT. In addition, the PLR pushes the topology-identification 668 label associated with the Red MRT, and forward the packet to the 669 appropriate next-hop on the Red MRT. When the next-hop router in the 670 Red MRT receives the packet with the Red MRT label for the FEC, the 671 MRT transit forwarding functionality continues as described in 672 Section 6.1.1.2. As with option 1A, the original FEC associated with 673 the packet is maintained at each hop along the MRT. 675 6.2.3. Other considerations for forwarding LDP traffic using MRT LDP 676 Labels 678 Note that forwarding LDP traffic using MRT LDP Labels requires that 679 an MRT to the originator of the FEC be used. For example, one might 680 find it desirable to have the PLR use an MRT to reach the primary 681 next-next-hop for the FEC, and then continue forwarding the LDP 682 packet along the shortest path tree from the primary next-next-hop. 683 However, this would require tunneling to the primary next-next-hop 684 and a targeted LDP session for the PLR to learn the FEC-label binding 685 for primary next-next-hop to correctly forward the packet. 687 For greatest hardware compatibility, routers implementing MRT fast- 688 reroute of LDP traffic MUST support Option 1A of encoding the MT-ID 689 in the labels (See Section 9). 691 6.3. Forwarding IP Unicast Traffic over MRT Paths 693 For IP traffic, there is no currently practical alternative except 694 tunneling to gain the bits needed to indicate the MRT-Blue or MRT-Red 695 forwarding topology. The choice of tunnel egress MAY be flexible 696 since any router closer to the destination than the next-hop can 697 work. This architecture assumes that the original destination in the 698 area is selected (see Section 11 for handling of multi-homed 699 prefixes); another possible choice is the next-next-hop towards the 700 destination. As discussed in the previous section, for LDP traffic, 701 using the MRT to the original destination simplifies MRT-FRR by 702 avoiding the need for targeted LDP sessions to the next-next-hop. 703 For IP, that consideration doesn't apply. However, consistency with 704 LDP is RECOMMENDED. 706 Some situations require tunneling IP traffic along an MRT to a tunnel 707 endpoint that is not the destination of the IP traffic. These 708 situations will be discussed in detail later. We note here that an 709 IP packet with a destination in a different IGP area/level from the 710 PLR should be tunneled on the MRT to the ABR/LBR on the shortest path 711 to the destination. For a destination outside of the PLR's MRT 712 Island, the packet should be tunneled on the MRT to a non-proxy-node 713 immediately before the named proxy-node on that particular color MRT. 715 6.3.1. Tunneling IP traffic using MRT LDP Labels 717 An IP packet can be tunneled along an MRT path by pushing the 718 appropriate MRT LDP label(s). Tunneling using LDP labels, as opposed 719 to IP headers, has the the advantage that more installed routers can 720 do line-rate encapsulation and decapsulation using LDP than using IP. 721 Also, no additional IP addresses would need to be allocated or 722 signaled. 724 6.3.1.1. Tunneling IP traffic using MRT LDP Labels (Option 1A) 726 The MRT LDP Label option 1A forwarding mechanism uses topology-scoped 727 FECs encoded using a single label as described in section 728 Section 6.1.1.1. When a PLR receives an IP packet that needs to be 729 forwarded on the Red MRT to a particular tunnel endpoint, it does a 730 label push operation. The label pushed is the Red MRT label for a 731 FEC originated by the tunnel endpoint, learned from the next-hop on 732 the Red MRT. 734 6.3.1.2. Tunneling IP traffic using MRT LDP Labels (Option 1B) 736 The MRT LDP Label option 1B forwarding mechanism encodes the topology 737 and the FEC using a two label stack as described in Section 6.1.1.2. 738 When a PLR receives an IP packet that needs to be forwarded on the 739 Red MRT to a particular tunnel endpoint, the PLR pushes two labels on 740 the IP packet. The first (inner) label is the normal LDP label 741 learned from the next-hop on the Red MRT, associated with a FEC 742 originated by the tunnel endpoint. The second (outer) label is the 743 topology-identification label associated with the Red MRT. 745 For completeness, we note here a potential optimization. In order to 746 tunnel an IP packet over an MRT to the destination of the IP packet 747 (as opposed to an arbitrary tunnel endpoint), then we could just push 748 a topology-identification label directly onto the packet. An MRT 749 transit router would need to pop the topology-id label, do an IP 750 route lookup in the context of that topology-id , and push the 751 topology-id label. 753 6.3.2. Tunneling IP traffic using MRT IP Tunnels 755 In order to tunnel over the MRT to a particular tunnel endpoint, the 756 PLR encapsulates the original IP packet with an additional IP header 757 using the MRT-Blue or MRT-Red loopack address of the tunnel endpoint. 759 6.3.3. Required support 761 For greatest hardware compatibility and ease in removing the MRT- 762 topology marking at area/level boundaries, routers that support MPLS 763 and implement IP MRT fast-reroute MUST support tunneling of IP 764 traffic using MRT LDP Labels Option 1A (topology-scoped FEC encoded 765 using a single label). 767 7. MRT Island Formation 769 The purpose of communicating support for MRT in the IGP is to 770 indicate that the MRT-Blue and MRT-Red forwarding topologies are 771 created for transit traffic. The MRT architecture allows for 772 different, potentially incompatible options. In order to create 773 constistent MRT forwarding topologies, the routers participating in a 774 particular MRT Island need to use the same set of options. These 775 options are grouped into MRT profiles. In addition, the routers in 776 an MRT Island all need to use the same set of nodes and links within 777 the Island when computing the MRT forwarding topologies. This 778 section describes the information used by a router to determine the 779 nodes and links to include in a particular MRT Island. Some of this 780 information is shared among routers using the newly-defined IGP 781 signaling extensions for MRT described in [I-D.atlas-ospf-mrt] and 782 [I-D.li-isis-mrt]. Other information already exists in the IGPs and 783 can be used by MRT in Island formation, subject to the interpretation 784 defined here. 786 Deployment scenarios using multi-topology OSPF or IS-IS, or running 787 both ISIS and OSPF on the same routers is out of scope for this 788 specification. As with LFA, it is expected that OSPF Virtual Links 789 will not be supported. 791 7.1. IGP Area or Level 793 All links in an MRT Island MUST be bidirectional and belong to the 794 same IGP area or level. For ISIS, a link belonging to both level 1 795 and level 2 would qualify to be in multiple MRT Islands. A given ABR 796 or LBR can belong to multiple MRT Islands, corresponding to the areas 797 or levels in which it participates. Inter-area forwarding behavior 798 is discussed in Section 10. 800 7.2. Support for a specific MRT profile 802 All routers in an MRT Island MUST support the same MRT profile. A 803 router advertises support for a given MRT profile using the IGP 804 extensions defined in [I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt] 805 using an 8-bit Profile ID value. A given router can support multiple 806 MRT profiles and participate in multiple MRT Islands. The options 807 that make up an MRT profile, as well as the default MRT profile, are 808 defined in Section 8. 810 7.3. Excluding additional routers and interfaces from the MRT Island 812 MRT takes into account existing IGP mechanisms for discouraging 813 traffic from using particular links and routers, and it introduces an 814 MRT-specific exclusion mechanism for links. 816 7.3.1. Existing IGP exclusion mechanisms 818 Mechanisms for discouraging traffic from using particular links 819 already exist in ISIS and OSPF. In ISIS, an interface configured 820 with a metric of 2^24-2 (0xFFFFFE) will only be used as a last 821 resort. (An interface configured with a metric of 2^24-1 (0xFFFFFF) 822 will not be advertised into the topology.) In OSPF, an interface 823 configured with a metric of 2^16-1 (0xFFFF) will only be used as a 824 last resort. These metrics can be configured manually to enforce 825 administrative policy, or they can be set in an automated manner as 826 with LDP IGP synchronization [RFC5443]. 828 Mechanisms also exist in ISIS and OSPF to prevent transit traffic 829 from using a particular router. In ISIS, the overload bit is used 830 for this purpose. In OSPF, [RFC3137] specifies setting all outgoing 831 interface metrics to 0xFFFF to accomplish this. 833 The following rules for MRT Island formation ensure that MRT FRR 834 protection traffic does not use a link or router that is discouraged 835 from carrying traffic by existing IGP mechanisms. 837 1. A bidirectional link MUST be excluded from an MRT Island if 838 either the forward or reverse cost on the link is 0xFFFFFE (for 839 ISIS) or 0xFFFF for OSPF. 841 2. A router MUST be excluded from an MRT Island if it is advertised 842 with the overload bit set (for ISIS), or it is advertised with 843 metric values of 0xFFFF on all of its outgoing interfaces (for 844 OSPF). 846 7.3.2. MRT-specific exclusion mechanism 848 This architecture also defines a means of excluding an otherwise 849 usable link from MRT Islands. [I-D.atlas-ospf-mrt] and 850 [I-D.li-isis-mrt] define the IGP extensions for OSPF and ISIS used to 851 advertise that a link is MRT-Ineligible. A link with either 852 interface advertised as MRT-Ineligible MUST be excluded from an MRT 853 Island. Note that an interface advertised as MRT-Ineligigle by a 854 router is ineligible with respect to all profiles advertised by that 855 router. 857 7.4. Connectivity 859 All of the routers in an MRT Island MUST be connected by 860 bidirectional links with other routers in the MRT Island. 861 Disconnected MRT Islands will operate independently of one another. 863 7.5. Example algorithm 865 An algorithm that allows a computing router to identify the routers 866 and links in the local MRT Island satisfying the above rules is given 867 in section 5.1 of [I-D.ietf-rtgwg-mrt-frr-algorithm]. 869 8. MRT Profile 871 An MRT Profile is a set of values and options related to MRT 872 behavior. The complete set of options is designated by the 873 corresponding 8-bit Profile ID value. 875 8.1. MRT Profile Options 877 Below is a description of the values and options that define an MRT 878 Profile. 880 MRT Algorithm: This identifies the particular MRT algorithm used by 881 the router for this profile. Algorithm transitions can be managed 882 by advertising multiple MRT profiles. 884 MRT-Red MT-ID: This specifies the MT-ID to be associated with the 885 MRT-Red forwarding topology. It is needed for use in LDP 886 signaling. All routers in the MRT Island MUST agree on a value. 888 MRT-Blue MT-ID: This specifies the MT-ID to be associated with the 889 MRT-Blue forwarding topology. It is needed for use in LDP 890 signaling. All routers in the MRT Island MUST agree on a value. 892 GADAG Root Selection Policy: This specifes the manner in which the 893 GADAG root is selected. All routers in the MRT island need to use 894 the same GADAG root in the calculations used construct the MRTs. 895 A valid GADAG Root Selection Policy MUST be such that each router 896 in the MRT island chooses the same GADAG root based on information 897 available to all routers in the MRT island. GADAG Root Selection 898 Priority values, advertised in the IGP as router-specific MRT 899 parameters, MAY be used in a GADAG Root Selection Policy. 901 MRT Forwarding Mechanism: This specifies which forwarding mechanism 902 the router uses to carry transit traffic along MRT paths. A 903 router which supports a specific MRT forwarding mechanism must 904 program appropriate next-hops into the forwarding plane. The 905 current options are MRT LDP Labels, IPv4 Tunneling, IPv6 906 Tunneling, and None. If the MRT LDP Labels option is supported, 907 then option 1A and the appropriate signaling extensions MUST be 908 supported. If IPv4 is supported, then both MRT-Red and MRT-Blue 909 IPv4 Loopback Addresses SHOULD be specified. If IPv6 is 910 supported, both MRT-Red and MRT-Blue IPv6 Loopback Addresses 911 SHOULD be specified. The None option in may be useful for 912 multicast global protection. 914 Recalculation: As part of what process and timing should the new 915 MRTs be computed on a modified topology? Section 12.2 describes 916 the minimum behavior required to support fast-reroute. 918 Area/Level Border Behavior: Should inter-area traffic on the MRT- 919 Blue or MRT-Red be put back onto the shortest path tree? Should 920 it be swapped from MRT-Blue or MRT-Red in one area/level to MRT- 921 Red or MRT-Blue in the next area/level to avoid the potential 922 failure of an ABR? (See [I-D.atlas-rtgwg-mrt-mc-arch] for use- 923 case details. 925 Other Profile-Specific Behavior: Depending upon the use-case for 926 the profile, there may be additional profile-specific behavior. 928 If a router advertises support for multiple MRT profiles, then it 929 MUST create the transit forwarding topologies for each of those, 930 unless the profile specifies the None option for MRT Forwarding 931 Mechanism. A router MUST NOT advertise multiple MRT profiles that 932 overlap in their MRT-Red MT-ID or MRT-Blue MT-ID. 934 8.2. Router-specific MRT paramaters 936 For some profiles, additional router-specific MRT parameters may need 937 to be distributed via the IGP. While the set of options indicated by 938 the MRT Profile ID must be identical for all routers in an MRT 939 Island, these router-specific MRT parameters may differ between 940 routers in the same MRT island. Several such parameters are 941 described below. 943 GADAG Root Selection Priority: A GADAG Root Selection Policy MAY 944 rely on the GADAG Root Selection Priority values advertised by 945 each router in the MRT island. A GADAG Root Selection Policy may 946 use the GADAG Root Selection Priority to allow network operators 947 to configure a parameter to ensure that the GADAG root is selected 948 from a particular subset of routers. An example of this use of 949 the GADAG Root Selection Priority value by the GADAG Root 950 Selection Policy is given in the Default MRT profile below. 952 MRT-Red Loopback Address: This provides the router's loopback 953 address to reach the router via the MRT-Red forwarding topology. 954 It can be specified for either IPv4 and IPv6. 956 MRT-Blue Loopback Address: This provides the router's loopback 957 address to reach the router via the MRT-Blue forwarding topology. 958 It can be specified for either IPv4 and IPv6. 960 The extensions to OSPF and ISIS for advertising a router's GADAG Root 961 Selection Priority value are defined in [I-D.atlas-ospf-mrt] and 962 [I-D.li-isis-mrt]. IGP extensions for the advertising a router's 963 MRT-Red and MRT-Blue Loopback Addresses have not been defined. 965 8.3. Default MRT profile 967 The following set of options defines the default MRT Profile. The 968 default MRT profile is indicated by the MRT Profile ID value of 0. 970 MRT Algorithm: MRT Lowpoint algorithm defined in 971 [I-D.ietf-rtgwg-mrt-frr-algorithm]. 973 MRT-Red MT-ID: TBA-MRT-ARCH-1, final value assigned by IANA 974 allocated from the LDP MT-ID space (prototype experiments have 975 used 3997) 977 MRT-Blue MT-ID: TBA-MRT-ARCH-2, final value assigned by IANA 978 allocated from the LDP MT-ID space (prototype experiments have 979 used 3998) 981 GADAG Root Selection Policy: Among the routers in the MRT Island 982 and with the highest priority advertised, an implementation MUST 983 pick the router with the highest Router ID to be the GADAG root. 985 Forwarding Mechanisms: MRT LDP Labels 987 Recalculation: Recalculation of MRTs SHOULD occur as described in 988 Section 12.2. This allows the MRT forwarding topologies to 989 support IP/LDP fast-reroute traffic. 991 Area/Level Border Behavior: As described in Section 10, ABRs/LBRs 992 SHOULD ensure that traffic leaving the area also exits the MRT-Red 993 or MRT-Blue forwarding topology. 995 9. LDP signaling extensions and considerations 997 The protocol extensions for LDP are defined in 998 [I-D.atlas-mpls-ldp-mrt]. A router must indicate that it has the 999 ability to support MRT; having this explicit allows the use of MRT- 1000 specific processing, such as special handling of FECs sent with the 1001 Rainbow MRT MT-ID. 1003 A FEC sent with the Rainbow MRT MT-ID indicates that the FEC applies 1004 to all the MRT-Blue and MRT-Red MT-IDs in supported MRT profiles. 1005 The FEC-label bindings for the default shortest-path based MT-ID 0 1006 MUST still be sent (even though it could be inferred from the Rainbow 1007 FEC-label bindings) to ensure continuous operation of normal LDP 1008 forwarding. The Rainbow MRT MT-ID is defined to provide an easy way 1009 to handle the special signaling that is needed at ABRs or LBRs. It 1010 avoids the problem of needing to signal different MPLS labels for the 1011 same FEC. Because the Rainbow MRT MT-ID is used only by ABRs/LBRs or 1012 an LDP egress router, it is not MRT profile specific. 1014 [I-D.atlas-mpls-ldp-mrt] contains the IANA request for the Rainbow 1015 MRT MT-ID. 1017 10. Inter-area Forwarding Behavior 1019 Unless otherwise specified, in this section we will use the terms 1020 area and ABR to indicate either an OSPF area and OSPF ABR or ISIS 1021 level and ISIS LBR. 1023 An ABR/LBR has two forwarding roles. First, it forwards traffic 1024 within areas. Second, it forwards traffic from one area into 1025 another. These same two roles apply for MRT transit traffic. 1026 Traffic on MRT-Red or MRT-Blue destined inside the area needs to stay 1027 on MRT-Red or MRT-Blue in that area. However, it is desirable for 1028 traffic leaving the area to also exit MRT-Red or MRT-Blue and return 1029 to shortest path forwarding. 1031 For unicast MRT-FRR, the need to stay on an MRT forwarding topology 1032 terminates at the ABR/LBR whose best route is via a different area/ 1033 level. It is highly desirable to go back to the default forwarding 1034 topology when leaving an area/level. There are three basic reasons 1035 for this. First, the default topology uses shortest paths; the 1036 packet will thus take the shortest possible route to the destination. 1037 Second, this allows failures that might appear in multiple areas 1038 (e.g. ABR/LBR failures) to be separately identified and repaired 1039 around. Third, the packet can be fast-rerouted again, if necessary, 1040 due to a failure in a different area. 1042 An ABR/LBR that receives a packet on MRT-Red or MRT-Blue towards 1043 destination Z should continue to forward the packet along MRT-Red or 1044 MRT-Blue only if the best route to Z is in the same area as the 1045 interface that the packet was received on. Otherwise, the packet 1046 should be removed from MRT-Red or MRT-Blue and forwarded on the 1047 shortest-path default forwarding topology. 1049 To avoid per-interface forwarding state for MRT-Red and MRT-Blue, the 1050 ABR/LBR needs to arrange that packets destined to a different area 1051 arrive at the ABR/LBR already not marked as MRT-Red or MRT-Blue. 1053 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A 1055 For LDP forwarding where a single label specifies (MT-ID, FEC), the 1056 ABR/LBR is responsible for advertising the proper label to each 1057 neighbor. Assume that an ABR/LBR has allocated three labels for a 1058 particular destination; those labels are L_primary, L_blue, and 1059 L_red. To those routers in the same area as the best route to the 1060 destination, the ABR/LBR advertises the following FEC-label bindings: 1061 L_primary for the default topology, L_blue for the MRT-Blue MT-ID and 1062 L_red for the MRT-Red MT-ID, as expected. However, to routers in 1063 other areas, the ABR/LBR advertises the following FEC-label bindings: 1064 L_primary for the default topology, and L_primary for the Rainbow MRT 1065 MT-ID. Associating L_primary with the Rainbow MRT MT-ID causes the 1066 receiving routers to use L_primary for the MRT-Blue MT-ID and for the 1067 MRT-Red MT-ID. 1069 The ABR/LBR installs all next-hops for the best area: primary next- 1070 hops for L_primary, MRT-Blue next-hops for L_blue, and MRT-Red next- 1071 hops for L_red. Because the ABR/LBR advertised (Rainbow MRT MT-ID, 1072 FEC) with L_primary to neighbors not in the best area, packets from 1073 those neighbors will arrive at the ABR/LBR with a label L_primary and 1074 will be forwarded into the best area along the default topology. By 1075 controlling what labels are advertised, the ABR/LBR can thus enforce 1076 that packets exiting the area do so on the shortest-path default 1077 topology. 1079 10.1.1. Motivation for Creating the Rainbow-FEC 1081 The desired forwarding behavior could be achieved in the above 1082 example without using the Rainbow-FEC. This could be done by having 1083 the ABR/LBR advertise the following FEC-label bindings to neighbors 1084 not in the best area: L1_primary for the default topology, L1_primary 1085 for the MRT-Blue MT-ID, and L1_primary for the MRT-Red MT-ID. Doing 1086 this would require machinery to spoof the labels used in FEC-label 1087 binding advertisements on a per-neighbor basis. Such label-spoofing 1088 machinery does not currently exist in most LDP implmentations and 1089 doesn't have other obvious uses. 1091 Many existing LDP implmentations do however have the ability to 1092 filter FEC-label binding advertisements on a per-neighbor basis. The 1093 Rainbow-FEC allows us to re-use the existing per-neighbor FEC 1094 filtering machinery to achieve the desired result. By introducing 1095 the Rainbow FEC, we can use per-neighbor FEC-filtering machinery to 1096 advertise the FEC-label binding for the Rainbow-FEC (and filter those 1097 for MRT-Blue and MRT-Red) to non-best-area neighbors of the ABR. 1099 The use of the Rainbow-FEC by the ABR for non-best-area 1100 advertisements is RECOMMENDED. An ABR MAY advertise the label for 1101 the default topology in separate MRT-Blue and MRT-Red advertisements. 1102 However, a router that supports the LDP Label MRT Forwarding 1103 Mechanism MUST be able to receive and correctly interpret the 1104 Rainbow-FEC. 1106 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) 1108 If IP tunneling is used, then the ABR/LBR behavior is dependent upon 1109 the outermost IP address. If the outermost IP address is an MRT 1110 loopback address of the ABR/LBR, then the packet is decapsulated and 1111 forwarded based upon the inner IP address, which should go on the 1112 default SPT topology. If the outermost IP address is not an MRT 1113 loopback address of the ABR/LBR, then the packet is simply forwarded 1114 along the associated forwarding topology. A PLR sending traffic to a 1115 destination outside its local area/level will pick the MRT and use 1116 the associated MRT loopback address of the selected ABR/LBR 1117 advertising the lowest cost to the external destination. 1119 Thus, for these two MRT Forwarding Mechanisms( MRT LDP Label option 1120 1A and IP tunneling option 2), there is no need for additional 1121 computation or per-area forwarding state. 1123 10.3. ABR Forwarding Behavior with LDP Label option 1B 1125 The other MRT forwarding mechanism described in Section 6 uses two 1126 labels, a topology-id label, and a FEC-label. This mechanism would 1127 require that any router whose MRT-Red or MRT-Blue next-hop is an ABR/ 1128 LBR would need to determine whether the ABR/LBR would forward the 1129 packet out of the area/level. If so, then that router should pop off 1130 the topology-identification label before forwarding the packet to the 1131 ABR/LBR. 1133 For example, in Figure 3, if node H fails, node E has to put traffic 1134 towards prefix p onto MRT-Red. But since node D knows that ABR1 will 1135 use a best route from another area, it is safe for D to pop the 1136 Topology-Identification Label and just forward the packet to ABR1 1137 along the MRT-Red next-hop. ABR1 will use the shortest path in Area 1138 10. 1140 In all cases for ISIS and most cases for OSPF, the penultimate router 1141 can determine what decision the adjacent ABR will make. The one case 1142 where it can't be determined is when two ASBRs are in different non- 1143 backbone areas attached to the same ABR, then the ASBR's Area ID may 1144 be needed for tie-breaking (prefer the route with the largest OPSF 1145 area ID) and the Area ID isn't announced as part of the ASBR link- 1146 state advertisement (LSA). In this one case, suboptimal forwarding 1147 along the MRT in the other area would happen. If that becomes a 1148 realistic deployment scenario, OSPF extensions could be considered. 1149 This is not covered in [I-D.atlas-ospf-mrt]. 1151 +----[C]---- --[D]--[E] --[D]--[E] 1152 | \ / \ / \ 1153 p--[A] Area 10 [ABR1] Area 0 [H]--p +-[ABR1] Area 0 [H]-+ 1154 | / \ / | \ / | 1155 +----[B]---- --[F]--[G] | --[F]--[G] | 1156 | | 1157 | other | 1158 +----------[p]-------+ 1159 area 1161 (a) Example topology (b) Proxy node view in Area 0 nodes 1163 +----[C]<--- [D]->[E] 1164 V \ \ 1165 +-[A] Area 10 [ABR1] Area 0 [H]-+ 1166 | ^ / / | 1167 | +----[B]<--- [F]->[G] V 1168 | | 1169 +------------->[p]<--------------+ 1171 (c) rSPT towards destination p 1173 ->[D]->[E] -<[D]<-[E] 1174 / \ / \ 1175 [ABR1] Area 0 [H]-+ +-[ABR1] [H] 1176 / | | \ 1177 [F]->[G] V V -<[F]<-[G] 1178 | | 1179 | | 1180 [p]<------+ +--------->[p] 1182 (d) Blue MRT in Area 0 (e) Red MRT in Area 0 1184 Figure 3: ABR Forwarding Behavior and MRTs 1186 11. Prefixes Multiply Attached to the MRT Island 1188 How a computing router S determines its local MRT Island for each 1189 supported MRT profile is already discussed in Section 7. 1191 There are two types of prefixes or FECs that may be multiply attached 1192 to an MRT Island. The first type are multi-homed prefixes that 1193 usually connect at a domain or protocol boundary. The second type 1194 represent routers that do not support the profile for the MRT Island. 1196 The key difference is whether the traffic, once out of the MRT 1197 Island, remains in the same area/level and might reenter the MRT 1198 Island if a loop-free exit point is not selected. 1200 FRR using LFA has the useful property that it is able to protect 1201 multi-homed prefixes against ABR failure. For instance, if a prefix 1202 from the backbone is available via both ABR A and ABR B, if A fails, 1203 then the traffic should be redirected to B. This can be accomplished 1204 with MRT FRR as well. 1206 If ASBR protection is desired, this has additional complexities if 1207 the ASBRs are in different areas. Similarly, protecting labeled BGP 1208 traffic in the event of an ASBR failure has additional complexities 1209 due to the per-ASBR label spaces involved. 1211 As discussed in [RFC5286], a multi-homed prefix could be: 1213 o An out-of-area prefix announced by more than one ABR, 1215 o An AS-External route announced by 2 or more ASBRs, 1217 o A prefix with iBGP multipath to different ASBRs, 1219 o etc. 1221 There are also two different approaches to protection. The first is 1222 tunnel endpoint selection where the PLR picks a router to tunnel to 1223 where that router is loop-free with respect to the failure-point. 1224 Conceptually, the set of candidate routers to provide LFAs expands to 1225 all routers that can be reached via an MRT alternate, attached to the 1226 prefix. 1228 The second is to use a proxy-node, that can be named via MPLS label 1229 or IP address, and pick the appropriate label or IP address to reach 1230 it on either MRT-Blue or MRT-Red as appropriate to avoid the failure 1231 point. A proxy-node can represent a destination prefix that can be 1232 attached to the MRT Island via at least two routers. It is termed a 1233 named proxy-node if there is a way that traffic can be encapsulated 1234 to reach specifically that proxy-node; this could be because there is 1235 an LDP FEC for the associated prefix or because MRT-Red and MRT-Blue 1236 IP addresses are advertised in an as-yet undefined fashion for that 1237 proxy-node. Traffic to a named proxy-node may take a different path 1238 than traffic to the attaching router; traffic is also explicitly 1239 forwarded from the attaching router along a predetermined interface 1240 towards the relevant prefixes. 1242 For IP traffic, multi-homed prefixes can use tunnel endpoint 1243 selection. For IP traffic that is destined to a router outside the 1244 MRT Island, if that router is the egress for a FEC advertised into 1245 the MRT Island, then the named proxy-node approach can be used. 1247 For LDP traffic, there is always a FEC advertised into the MRT 1248 Island. The named proxy-node approach should be used, unless the 1249 computing router S knows the label for the FEC at the selected tunnel 1250 endpoint. 1252 If a FEC is advertised from outside the MRT Island into the MRT 1253 Island and the forwarding mechanism specified in the profile includes 1254 LDP, then the routers learning that FEC MUST also advertise labels 1255 for (MRT-Red, FEC) and (MRT-Blue, FEC) to neighbors inside the MRT 1256 Island. Any router receiving a FEC corresponding to a router outside 1257 the MRT Island or to a multi-homed prefix MUST compute and install 1258 the transit MRT-Blue and MRT-Red next-hops for that FEC. The FEC- 1259 label bindings for the topology-scoped FECs ((MT-ID 0, FEC), (MRT- 1260 Red, FEC), and (MRT-Blue, FEC)) MUST also be provided via LDP to 1261 neighbors inside the MRT Island. 1263 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint Selection 1265 Tunnel endpoint selection is a local matter for a router in the MRT 1266 Island since it pertains to selecting and using an alternate and does 1267 not affect the transit MRT-Red and MRT-Blue forwarding topologies. 1269 Let the computing router be S and the next-hop F be the node whose 1270 failure is to be avoided. Let the destination be prefix p. Have A 1271 be the router to which the prefix p is attached for S's shortest path 1272 to p. 1274 The candidates for tunnel endpoint selection are those to which the 1275 destination prefix is attached in the area/level. For a particular 1276 candidate B, it is necessary to determine if B is loop-free to reach 1277 p with respect to S and F for node-protection or at least with 1278 respect to S and the link (S, F) for link-protection. If B will 1279 always prefer to send traffic to p via a different area/level, then 1280 this is definitional. Otherwise, distance-based computations are 1281 necessary and an SPF from B's perspective may be necessary. The 1282 following equations give the checks needed; the rationale is similar 1283 to that given in [RFC5286]. 1285 Loop-Free for S: D_opt(B, p) < D_opt(B, S) + D_opt(S, p) 1287 Loop-Free for F: D_opt(B, p) < D_opt(B, F) + D_opt(F, p) 1289 The latter is equivalent to the following, which avoids the need to 1290 compute the shortest path from F to p. 1292 Loop-Free for F: D_opt(B, p) < D_opt(B, F) + D_opt(S, p) - D_opt(S, 1293 F) 1295 Finally, the rules for Endpoint selection are given below. The basic 1296 idea is to repair to the prefix-advertising router selected for the 1297 shortest-path and only to select and tunnel to a different endpoint 1298 if necessary (e.g. A=F or F is a cut-vertex or the link (S,F) is a 1299 cut-link). 1301 1. Does S have a node-protecting alternate to A? If so, select 1302 that. Tunnel the packet to A along that alternate. For example, 1303 if LDP is the forwarding mechanism, then push the label (MRT-Red, 1304 A) or (MRT-Blue, A) onto the packet. 1306 2. If not, then is there a router B that is loop-free to reach p 1307 while avoiding both F and S? If so, select B as the end-point. 1308 Determine the MRT alternate to reach B while avoiding F. Tunnel 1309 the packet to B along that alternate. For example, with LDP, 1310 push the label (MRT-Red, B) or (MRT-Blue, B) onto the packet. 1312 3. If not, then does S have a link-protecting alternate to A? If 1313 so, select that. 1315 4. If not, then is there a router B that is loop-free to reach p 1316 while avoiding S and the link from S to F? If so, select B as 1317 the endpoint and the MRT alternate for reaching B from S that 1318 avoid the link (S,F). 1320 The tunnel endpoint selected will receive a packet destined to itself 1321 and, being the egress, will pop that MPLS label (or have signaled 1322 Implicit Null) and forward based on what is underneath. This 1323 suffices for IP traffic since the tunnel endpoint can use the IP 1324 header of the original packet to continue forwarding the packet. 1325 However, tunneling will not work for LDP traffic without targeted LDP 1326 sesssions for learning the FEC-label binding at the tunnel endpoint. 1328 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 1330 Instead, the named proxy-node method works with LDP traffic without 1331 the need for targeted LDP sessions. It also has a clear advantage 1332 over tunnel endpoint selection, in that it is possible to explicitly 1333 forward from the MRT Island along an interface to a loop-free island 1334 neighbor when that interface may not be a primary next-hop. 1336 A named proxy-node represents one or more destinations and, for LDP 1337 forwarding, has a FEC associated with it that is signaled into the 1338 MRT Island. Therefore, it is possible to explicitly label packets to 1339 go to (MRT-Red, FEC) or (MRT-Blue, FEC); at the border of the MRT 1340 Island, the label will swap to meaning (MT-ID 0, FEC). It would be 1341 possible to have named proxy-nodes for IP forwarding, but this would 1342 require extensions to signal two IP addresses to be associated with 1343 MRT-Red and MRT-Blue for the proxy-node. A named proxy-node can be 1344 uniquely represented by the two routers in the MRT Island to which it 1345 is connected. The extensions to signal such IP addresses are not 1346 defined in [I-D.atlas-ospf-mrt]. The details of what label-bindings 1347 must be originated are described in [I-D.atlas-mpls-ldp-mrt]. 1349 Computing the MRT next-hops to a named proxy-node and the MRT 1350 alternate for the computing router S to avoid a particular failure 1351 node F is straightforward. The details of the simple constant-time 1352 functions, Select_Proxy_Node_NHs() and 1353 Select_Alternates_Proxy_Node(), are given in 1354 [I-D.ietf-rtgwg-mrt-frr-algorithm]. A key point is that computing 1355 these MRT next-hops and alternates can be done as new named proxy- 1356 nodes are added or removed without requiring a new MRT computation or 1357 impacting other existing MRT paths. This maps very well to, for 1358 example, how OSPFv2 [[RFC2328] Section 16.5] does incremental updates 1359 for new summary-LSAs. 1361 The key question is how to attach the named proxy-node to the MRT 1362 Island; all the routers in the MRT Island MUST do this consistently. 1363 No more than 2 routers in the MRT Island can be selected; one should 1364 only be selected if there are no others that meet the necessary 1365 criteria. The named proxy-node is logically part of the area/level. 1367 There are two sources for candidate routers in the MRT Island to 1368 connect to the named proxy-node. The first set are those routers 1369 that are advertising the prefix; the named-proxy-cost assigned to 1370 each prefix-advertising router is the announced cost to the prefix. 1371 The second set are those routers in the MRT Island that are connected 1372 to routers not in the MRT Island but in the same area/level; such 1373 routers will be defined as Island Border Routers (IBRs). The routers 1374 connected to the IBRs that are not in the MRT Island and are in the 1375 same area/level as the MRT island are Island Neighbors(INs). 1377 Since packets sent to the named proxy-node along MRT-Red or MRT-Blue 1378 may come from any router inside the MRT Island, it is necessary that 1379 whatever router to which an IBR forwards the packet be loop-free with 1380 regard to the whole MRT Island for the destination. Thus, an IBR is 1381 a candidate router only if it possesses at least one IN whose 1382 shortest path to the prefix does not enter the MRT Island. A method 1383 for identifying loop-free Island Neighbors(LFINs) is discussed below. 1384 The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) 1385 + D_opt(IN, prefix). 1387 From the set of prefix-advertising routers and the set of IBRs with 1388 at least one LFIN, the two routers with the lowest named-proxy-cost 1389 are selected. Ties are broken based upon the lowest Router ID. For 1390 ease of discussion, the two selected routers will be referred to as 1391 proxy-node attachment routers. 1393 A proxy-node attachment router has a special forwarding role. When a 1394 packet is received destined to (MRT-Red, prefix) or (MRT-Blue, 1395 prefix), if the proxy-node attachment router is an IBR, it MUST swap 1396 to the default topology (e.g. swap to the label for (MT-ID 0, prefix) 1397 or remove the outer IP encapsulation) and forward the packet to the 1398 IN whose cost was used in the selection. If the proxy-node 1399 attachment router is not an IBR, then the packet MUST be removed from 1400 the MRT forwarding topology and sent along the interface(s) that 1401 caused the router to advertise the prefix; this interface might be 1402 out of the area/level/AS. 1404 11.2.1. Computing if an Island Neighbor (IN) is loop-free 1406 As discussed, the Island Neighbor needs to be loop-free with regard 1407 to the whole MRT Island for the destination. Conceptually, the cost 1408 of transiting the MRT Island should be regarded as 0. This can be 1409 done by collapsing the MRT Island into a single node, as seen in 1410 Figure 4, and then computing SPFs from each Island Neighbor and from 1411 the MRT Island itself. 1413 [G]---[E]---(V)---(U)---(T) 1414 | \ | | | 1415 | \ | | | 1416 | \ | | | 1417 [H]---[F]---(R)---(S)----| 1419 (1) Network Graph with Partial Deployment 1421 [E],[F],[G],[H] : No support for MRT 1422 (R),(S),(T),(U),(V): MRT Island - supports MRT 1424 [G]---[E]----| |---(V)---(U)---(T) 1425 | \ | | | | | 1426 | \ | ( MRT Island ) [ proxy ] | | 1427 | \ | | | | | 1428 [H]---[F]----| |---(R)---(S)----| 1430 (2) Graph for determining (3) Graph for MRT computation 1431 loop-free neighbors 1433 Figure 4: Computing alternates to destinations outside the MRT Island 1435 The simple way to do this without manipulating the topology is to 1436 compute the SPFs from each IN and a node in the MRT Island (e.g. the 1437 GADAG root), but use a link metric of 0 for all links between routers 1438 in the MRT Island. The distances computed via SPF this way will be 1439 refered to as Dist_mrt0. 1441 An IN is loop-free with respect to a destination D if: Dist_mrt0(IN, 1442 D) < Dist_mrt0(IN, MRT Island Router) + Dist_mrt0(MRT Island Router, 1443 D). Any router in the MRT Island can be used since the cost of 1444 transiting between MRT Island routers is 0. The GADAG Root is 1445 recommended for consistency. 1447 11.3. MRT Alternates for Destinations Outside the MRT Island 1449 A natural concern with new functionality is how to have it be useful 1450 when it is not deployed across an entire IGP area. In the case of 1451 MRT FRR, where it provides alternates when appropriate LFAs aren't 1452 available, there are also deployment scenarios where it may make 1453 sense to only enable some routers in an area with MRT FRR. A simple 1454 example of such a scenario would be a ring of 6 or more routers that 1455 is connected via two routers to the rest of the area. 1457 Destinations inside the local island can obviously use MRT 1458 alternates. Destinations outside the local island can be treated 1459 like a multi-homed prefix and either Endpoint Selection or Named 1460 Proxy-Nodes can be used. Named Proxy-Nodes MUST be supported when 1461 LDP forwarding is supported and a label-binding for the destination 1462 is sent to an IBR. 1464 Naturally, there are more complicated options to improve coverage, 1465 such as connecting multiple MRT islands across tunnels, but the need 1466 for the additional complexity has not been justified. 1468 12. Network Convergence and Preparing for the Next Failure 1470 After a failure, MRT detours ensure that packets reach their intended 1471 destination while the IGP has not reconverged onto the new topology. 1472 As link-state updates reach the routers, the IGP process calculates 1473 the new shortest paths. Two things need attention: micro-loop 1474 prevention and MRT re-calculation. 1476 12.1. Micro-forwarding loop prevention and MRTs 1478 As is well known[RFC5715], micro-loops can occur during IGP 1479 convergence; such loops can be local to the failure or remote from 1480 the failure. Managing micro-loops is an orthogonal issue to having 1481 alternates for local repair, such as MRT fast-reroute provides. 1483 There are two possible micro-loop prevention mechanisms discussed in 1484 [RFC5715]. The first is Ordered FIB [I-D.ietf-rtgwg-ordered-fib]. 1485 The second is Farside Tunneling which requires tunnels or an 1486 alternate topology to reach routers on the farside of the failure. 1488 Since MRTs provide an alternate topology through which traffic can be 1489 sent and which can be manipulated separately from the SPT, it is 1490 possible that MRTs could be used to support Farside Tunneling. 1491 Details of how to do so are outside the scope of this document. 1493 Micro-loop mitigation mechanisms can also work when combined with 1494 MRT. 1496 12.2. MRT Recalculation 1498 When a failure event happens, traffic is put by the PLRs onto the MRT 1499 topologies. After that, each router recomputes its shortest path 1500 tree (SPT) and moves traffic over to that. Only after all the PLRs 1501 have switched to using their SPTs and traffic has drained from the 1502 MRT topologies should each router install the recomputed MRTs into 1503 the FIBs. 1505 At each router, therefore, the sequence is as follows: 1507 1. Receive failure notification 1509 2. Recompute SPT 1511 3. Install new SPT 1513 4. If the network was stable before the failure occured, wait a 1514 configured (or advertised) period for all routers to be using 1515 their SPTs and traffic to drain from the MRTs. 1517 5. Recompute MRTs 1519 6. Install new MRTs. 1521 While the recomputed MRTs are not installed in the FIB, protection 1522 coverage is lowered. Therefore, it is important to recalculate the 1523 MRTs and install them quickly. 1525 13. Implementation Status 1527 [RFC Editor: please remove this section prior to publication.] 1529 This section records the status of known implementations of the 1530 protocol defined by this specification at the time of posting of this 1531 Internet-Draft, and is based on a proposal described in [RFC6982]. 1532 The description of implementations in this section is intended to 1533 assist the IETF in its decision processes in progressing drafts to 1534 RFCs. Please note that the listing of any individual implementation 1535 here does not imply endorsement by the IETF. Furthermore, no effort 1536 has been spent to verify the information presented here that was 1537 supplied by IETF contributors. This is not intended as, and must not 1538 be construed to be, a catalog of available implementations or their 1539 features. Readers are advised to note that other implementations may 1540 exist. 1542 According to [RFC6982], "this will allow reviewers and working groups 1543 to assign due consideration to documents that have the benefit of 1544 running code, which may serve as evidence of valuable experimentation 1545 and feedback that have made the implemented protocols more mature. 1546 It is up to the individual working groups to use this information as 1547 they see fit". 1549 Juniper Networks Implementation 1551 o Organization responsible for the implementation: Juniper Networks 1553 o Implementation name: MRT-FRR algorithm 1554 o Implementation description: The MRT-FRR algorithm using OSPF as 1555 the IGP has been implemented and verified. 1557 o The implementation's level of maturity: prototype 1559 o Protocol coverage: This implementation of the MRT algorithm 1560 includes Island identification, GADAG root selection, Lowpoint 1561 algorithm, augmentation of GADAG with additional links, and 1562 calculation of MRT transit next-hops alternate next-hops based on 1563 draft "draft-ietf-rtgwg-mrt-frr-algorithm-00". This 1564 implementation also includes the M-bit in OSPF based on "draft- 1565 atlas-ospf-mrt-01" as well as LDP MRT Capability based on "draft- 1566 atlas-mpls-ldp-mrt-00". 1568 o Licensing: proprietary 1570 o Implementation experience: Implementation was useful for verifying 1571 functionality and lack of gaps. It has also been useful for 1572 improving aspects of the algorithm. 1574 o Contact information: akatlas@juniper.net, shraddha@juniper.net, 1575 kishoret@juniper.net 1577 Huawei Technology Implementation 1579 o Organization responsible for the implementation: Huawei Technology 1580 Co., Ltd. 1582 o Implementation name: MRT-FRR algorithm and IS-IS extensions for 1583 MRT. 1585 o Implementation description: The MRT-FRR algorithm, IS-IS 1586 extensions for MRT and LDP multi-topology have been implemented 1587 and verified. 1589 o The implementation's level of maturity: prototype 1591 o Protocol coverage: This implementation of the MRT algorithm 1592 includes Island identification, GADAG root selection, Lowpoint 1593 algorithm, augmentation of GADAG with additional links, and 1594 calculation of MRT transit next-hops alternate next-hops based on 1595 draft "draft-enyedi-rtgwg-mrt-frr-algorithm-03". This 1596 implementation also includes IS-IS extension for MRT based on 1597 "draft-li-mrt-00". 1599 o Licensing: proprietary 1600 o Implementation experience: It is important produce a second 1601 implementation to verify the algorithm is implemented correctly 1602 without looping. It is important to verify the ISIS extensions 1603 work for MRT-FRR. 1605 o Contact information: lizhenbin@huawei.com, eric.wu@huawei.com 1607 14. Acknowledgements 1609 The authors would like to thank Mike Shand for his valuable review 1610 and contributions. 1612 The authors would like to thank Joel Halpern, Hannes Gredler, Ted 1613 Qian, Kishore Tiruveedhula, Shraddha Hegde, Santosh Esale, Nitin 1614 Bahadur, Harish Sitaraman, and Raveendra Torvi for their suggestions 1615 and review. 1617 15. IANA Considerations 1619 Please create an MRT Profile registry for the MRT Profile TLV. The 1620 range is 0 to 255. The default MRT Profile has value 0. Values 1621 1-200 are by Standards Action. Values 201-220 are for 1622 experimentation. Values 221-255 are for vendor private use. 1624 Please allocate values from the LDP Multi-Topology (MT) ID Name Space 1625 [I-D.ietf-mpls-ldp-multi-topology] for the following: Default Profile 1626 MRT-Red MT-ID (TBA-MRT-ARCH-1) and Default Profile MRT-Blue MT-ID 1627 (TBA-MRT-ARCH-2). Please allocate MT-ID values less than 4096 so 1628 that they can also be signalled in PIM. 1630 16. Security Considerations 1632 This architecture is not currently believed to introduce new security 1633 concerns. 1635 17. References 1637 17.1. Normative References 1639 [I-D.ietf-rtgwg-mrt-frr-algorithm] 1640 Enyedi, G., Csaszar, A., Atlas, A., Bowers, C., and A. 1641 Gopalan, "Algorithms for computing Maximally Redundant 1642 Trees for IP/LDP Fast-Reroute", draft-rtgwg-mrt-frr- 1643 algorithm-01 (work in progress), July 2014. 1645 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 1646 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 1648 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 1649 5714, January 2010. 1651 17.2. Informative References 1653 [EnyediThesis] 1654 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 1655 Department of Telecommunications and Media Informatics, 1656 Budapest University of Technology and Economics Ph.D. 1657 Thesis, February 2011, 1658 . 1660 [I-D.atlas-mpls-ldp-mrt] 1661 Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ. 1662 Wijnands, "LDP Extensions to Support Maximally Redundant 1663 Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), 1664 July 2014. 1666 [I-D.atlas-ospf-mrt] 1667 Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF 1668 Extensions to Support Maximally Redundant Trees", draft- 1669 atlas-ospf-mrt-02 (work in progress), July 2014. 1671 [I-D.atlas-rtgwg-mrt-mc-arch] 1672 Atlas, A., Kebler, R., Wijnands, I., Csaszar, A., and G. 1673 Envedi, "An Architecture for Multicast Protection Using 1674 Maximally Redundant Trees", draft-atlas-rtgwg-mrt-mc- 1675 arch-02 (work in progress), July 2013. 1677 [I-D.bryant-ipfrr-tunnels] 1678 Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP 1679 Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03 1680 (work in progress), November 2007. 1682 [I-D.ietf-mpls-ldp-multi-topology] 1683 Zhao, Q., Raza, K., Zhou, C., Fang, L., Li, L., and D. 1684 King, "LDP Extensions for Multi Topology", draft-ietf- 1685 mpls-ldp-multi-topology-12 (work in progress), April 2014. 1687 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 1688 Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 1689 and MPLS Fast Reroute Using Not-via Addresses", draft- 1690 ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), 1691 May 2013. 1693 [I-D.ietf-rtgwg-ordered-fib] 1694 Shand, M., Bryant, S., Previdi, S., Filsfils, C., 1695 Francois, P., and O. Bonaventure, "Framework for Loop-free 1696 convergence using oFIB", draft-ietf-rtgwg-ordered-fib-12 1697 (work in progress), May 2013. 1699 [I-D.ietf-rtgwg-remote-lfa] 1700 Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 1701 So, "Remote Loop-Free Alternate Fast Re-Route", draft- 1702 ietf-rtgwg-remote-lfa-10 (work in progress), January 2015. 1704 [I-D.li-isis-mrt] 1705 Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. 1706 Tantsura, "Intermediate System to Intermediate System (IS- 1707 IS) Extensions for Maximally Redundant Trees(MRT)", draft- 1708 li-isis-mrt-01 (work in progress), July 2014. 1710 [I-D.psarkar-rtgwg-rlfa-node-protection] 1711 psarkar@juniper.net, p., Gredler, H., Hegde, S., 1712 Raghuveer, H., Bowers, C., and S. Litkowski, "Remote-LFA 1713 Node Protection and Manageability", draft-psarkar-rtgwg- 1714 rlfa-node-protection-04 (work in progress), April 2014. 1716 [LFARevisited] 1717 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 1718 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 1719 of IEEE INFOCOM , 2011, 1720 . 1723 [LightweightNotVia] 1724 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 1725 Fast ReRoute: Lightweight Not-Via without Additional 1726 Addresses", Proceedings of IEEE INFOCOM , 2009, 1727 . 1729 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1730 Requirement Levels", BCP 14, RFC 2119, March 1997. 1732 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1734 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1735 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1736 June 2001. 1738 [RFC5443] Jork, M., Atlas, A., and L. Fang, "LDP IGP 1739 Synchronization", RFC 5443, March 2009. 1741 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 1742 Convergence", RFC 5715, January 2010. 1744 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 1745 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 1746 Alternate (LFA) Applicability in Service Provider (SP) 1747 Networks", RFC 6571, June 2012. 1749 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 1750 Code: The Implementation Status Section", RFC 6982, July 1751 2013. 1753 Appendix A. General Issues with Area Abstraction 1755 When a multi-homed prefix is connected in two different areas, it may 1756 be impractical to protect them without adding the complexity of 1757 explicit tunneling. This is also a problem for LFA and Remote-LFA. 1759 50 1760 |----[ASBR Y]---[B]---[ABR 2]---[C] Backbone Area 0: 1761 | | ABR 1, ABR 2, C, D 1762 | | 1763 | | Area 20: A, ASBR X 1764 | | 1765 p ---[ASBR X]---[A]---[ABR 1]---[D] Area 10: B, ASBR Y 1766 5 p is a Type 1 AS-external 1768 Figure 5: AS external prefixes in different areas 1770 Consider the network in Figure 5 and assume there is a richer 1771 connective topology that isn't shown, where the same prefix is 1772 announced by ASBR X and ASBR Y which are in different non-backbone 1773 areas. If the link from A to ASBR X fails, then an MRT alternate 1774 could forward the packet to ABR 1 and ABR 1 could forward it to D, 1775 but then D would find the shortest route is back via ABR 1 to Area 1776 20. This problem occurs because the routers, including the ABR, in 1777 one area are not yet aware of the failure in a different area. 1779 The only way to get it from A to ASBR Y is to explicitly tunnel it to 1780 ASBR Y. If the traffic is unlabeled or the appropriate MPLS labels 1781 are known, then explicit tunneling MAY be used as long as the 1782 shortest-path of the tunnel avoids the failure point. In that case, 1783 A must determine that it should use an explicit tunnel instead of an 1784 MRT alternate. 1786 Authors' Addresses 1788 Alia Atlas (editor) 1789 Juniper Networks 1790 10 Technology Park Drive 1791 Westford, MA 01886 1792 USA 1794 Email: akatlas@juniper.net 1796 Robert Kebler 1797 Juniper Networks 1798 10 Technology Park Drive 1799 Westford, MA 01886 1800 USA 1802 Email: rkebler@juniper.net 1804 Chris Bowers 1805 Juniper Networks 1806 1194 N. Mathilda Ave. 1807 Sunnyvale, CA 94089 1808 USA 1810 Email: cbowers@juniper.net 1812 Gabor Sandor Enyedi 1813 Ericsson 1814 Konyves Kalman krt 11. 1815 Budapest 1097 1816 Hungary 1818 Email: Gabor.Sandor.Enyedi@ericsson.com 1820 Andras Csaszar 1821 Ericsson 1822 Konyves Kalman krt 11 1823 Budapest 1097 1824 Hungary 1826 Email: Andras.Csaszar@ericsson.com 1827 Jeff Tantsura 1828 Ericsson 1829 300 Holger Way 1830 San Jose, CA 95134 1831 USA 1833 Email: jeff.tantsura@ericsson.com 1835 Russ White 1836 VCE 1838 Email: russw@riw.us