idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-architecture-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 21, 2015) is 3049 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 434, but not defined == Missing Reference: 'F' is mentioned on line 434, but not defined == Missing Reference: 'C' is mentioned on line 434, but not defined == Missing Reference: 'I' is mentioned on line 432, but not defined == Missing Reference: 'G' is mentioned on line 434, but not defined == Missing Reference: 'J' is mentioned on line 436, but not defined == Missing Reference: 'A' is mentioned on line 1188, but not defined == Missing Reference: 'ABR1' is mentioned on line 1198, but not defined == Missing Reference: 'H' is mentioned on line 1198, but not defined == Outdated reference: A later version (-09) exists of draft-ietf-rtgwg-mrt-frr-algorithm-06 == Outdated reference: A later version (-04) exists of draft-francois-rtgwg-segment-routing-ti-lfa-00 == Outdated reference: A later version (-03) exists of draft-ietf-isis-mrt-01 == Outdated reference: A later version (-07) exists of draft-ietf-mpls-ldp-mrt-02 == Outdated reference: A later version (-03) exists of draft-ietf-ospf-mrt-01 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-rlfa-node-protection-05 -- Obsolete informational reference (is this intentional?): RFC 4379 (Obsoleted by RFC 8029) -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) Summary: 0 errors (**), 0 flaws (~~), 16 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group A. Atlas 3 Internet-Draft C. Bowers 4 Intended status: Standards Track Juniper Networks 5 Expires: June 23, 2016 G. Enyedi 6 Ericsson 7 December 21, 2015 9 An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees 10 draft-ietf-rtgwg-mrt-frr-architecture-08 12 Abstract 14 This document defines the architecture for IP/LDP Fast-Reroute using 15 Maximally Redundant Trees (MRT-FRR). MRT-FRR is a technology that 16 gives link-protection and node-protection with 100% coverage in any 17 network topology that is still connected after the failure. 19 MRT removes the need to engineer for coverage. MRT is also extremely 20 computationally efficient. For any router in the network, the MRT 21 computation is less than the LFA computation for a node with three or 22 more neighbors. 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on June 23, 2016. 41 Copyright Notice 43 Copyright (c) 2015 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Importance of 100% Coverage . . . . . . . . . . . . . . . 5 60 1.2. Partial Deployment and Backwards Compatibility . . . . . 6 61 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 6 62 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 63 4. Maximally Redundant Trees (MRT) . . . . . . . . . . . . . . . 8 64 5. Maximally Redundant Trees (MRT) and Fast-Reroute . . . . . . 10 65 6. Unicast Forwarding with MRT Fast-Reroute . . . . . . . . . . 11 66 6.1. MRT Forwarding Mechanisms . . . . . . . . . . . . . . . . 11 67 6.1.1. MRT LDP labels . . . . . . . . . . . . . . . . . . . 12 68 6.1.1.1. Topology-scoped FEC encoded using a single label 69 (Option 1A) . . . . . . . . . . . . . . . . . . . 12 70 6.1.1.2. Topology and FEC encoded using a two label stack 71 (Option 1B) . . . . . . . . . . . . . . . . . . . 13 72 6.1.1.3. Compatibility of Option 1A and 1B . . . . . . . . 13 73 6.1.1.4. Mandatory support for MRT LDP Label option 1A . . 13 74 6.1.2. MRT IP tunnels (Options 2A and 2B) . . . . . . . . . 13 75 6.2. Forwarding LDP Unicast Traffic over MRT Paths . . . . . . 14 76 6.2.1. Forwarding LDP traffic using MRT LDP Labels (Option 77 1A) . . . . . . . . . . . . . . . . . . . . . . . . . 14 78 6.2.2. Forwarding LDP traffic using MRT LDP Labels (Option 79 1B) . . . . . . . . . . . . . . . . . . . . . . . . . 15 80 6.2.3. Other considerations for forwarding LDP traffic using 81 MRT LDP Labels . . . . . . . . . . . . . . . . . . . 15 82 6.3. Forwarding IP Unicast Traffic over MRT Paths . . . . . . 15 83 6.3.1. Tunneling IP traffic using MRT LDP Labels . . . . . . 16 84 6.3.1.1. Tunneling IP traffic using MRT LDP Labels (Option 85 1A) . . . . . . . . . . . . . . . . . . . . . . . 16 86 6.3.1.2. Tunneling IP traffic using MRT LDP Labels (Option 87 1B) . . . . . . . . . . . . . . . . . . . . . . . 16 88 6.3.2. Tunneling IP traffic using MRT IP Tunnels . . . . . . 17 89 6.3.3. Required support . . . . . . . . . . . . . . . . . . 17 90 7. MRT Island Formation . . . . . . . . . . . . . . . . . . . . 17 91 7.1. IGP Area or Level . . . . . . . . . . . . . . . . . . . . 18 92 7.2. Support for a specific MRT profile . . . . . . . . . . . 18 93 7.3. Excluding additional routers and interfaces from the MRT 94 Island . . . . . . . . . . . . . . . . . . . . . . . . . 18 95 7.3.1. Existing IGP exclusion mechanisms . . . . . . . . . . 18 96 7.3.2. MRT-specific exclusion mechanism . . . . . . . . . . 19 98 7.4. Connectivity . . . . . . . . . . . . . . . . . . . . . . 19 99 7.5. Example algorithm . . . . . . . . . . . . . . . . . . . . 19 100 8. MRT Profile . . . . . . . . . . . . . . . . . . . . . . . . . 19 101 8.1. MRT Profile Options . . . . . . . . . . . . . . . . . . . 20 102 8.2. Router-specific MRT paramaters . . . . . . . . . . . . . 21 103 8.3. Default MRT profile . . . . . . . . . . . . . . . . . . . 21 104 9. LDP signaling extensions and considerations . . . . . . . . . 22 105 10. Inter-area Forwarding Behavior . . . . . . . . . . . . . . . 23 106 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A . . 23 107 10.1.1. Motivation for Creating the Rainbow-FEC . . . . . . 24 108 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) . . 24 109 10.3. ABR Forwarding Behavior with LDP Label option 1B . . . . 25 110 11. Prefixes Multiply Attached to the MRT Island . . . . . . . . 26 111 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint 112 Selection . . . . . . . . . . . . . . . . . . . . . . . 28 113 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 29 114 11.3. MRT Alternates for Destinations Outside the MRT Island . 31 115 12. Network Convergence and Preparing for the Next Failure . . . 31 116 12.1. Micro-forwarding loop prevention and MRTs . . . . . . . 32 117 12.2. MRT Recalculation for the Default MRT Profile . . . . . 32 118 13. Implementation Status . . . . . . . . . . . . . . . . . . . . 33 119 14. Operations and Management Considerations . . . . . . . . . . 34 120 15. Applying Policy to Select from Multiple Possible Alternates 121 for FRR . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 122 16. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 35 123 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35 124 18. Security Considerations . . . . . . . . . . . . . . . . . . . 36 125 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 36 126 20. References . . . . . . . . . . . . . . . . . . . . . . . . . 36 127 20.1. Normative References . . . . . . . . . . . . . . . . . . 36 128 20.2. Informative References . . . . . . . . . . . . . . . . . 37 129 Appendix A. General Issues with Area Abstraction . . . . . . . . 40 130 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40 132 1. Introduction 134 This document describes a solution for IP/LDP fast-reroute [RFC5714]. 135 MRT-FRR creates two alternate trees separate from the primary next- 136 hop forwarding used during stable operation. These two trees are 137 maximally diverse from each other, providing link and node protection 138 for 100% of paths and failures as long as the failure does not cut 139 the network into multiple pieces. This document defines the 140 architecture for IP/LDP fast-reroute with MRT. The associated 141 protocol extensions are defined in [I-D.ietf-ospf-mrt] and 142 [I-D.ietf-mpls-ldp-mrt]. The exact MRT algorithm is defined in 143 [I-D.ietf-rtgwg-mrt-frr-algorithm]. 145 IP/LDP Fast-Reroute with MRT (MRT-FRR) uses two maximally diverse 146 forwarding topologies to provide alternates. A primary next-hop 147 should be on only one of the diverse forwarding topologies; thus, the 148 other can be used to provide an alternate. Once traffic has been 149 moved to one of MRTs, it is not subject to further repair actions. 150 Thus, the traffic will not loop even if a worse failure (e.g. node) 151 occurs when protection was only available for a simpler failure (e.g. 152 link). 154 In addition to supporting IP and LDP unicast fast-reroute, the 155 diverse forwarding topologies and guarantee of 100% coverage permit 156 fast-reroute technology to be applied to multicast traffic as 157 described in [I-D.atlas-rtgwg-mrt-mc-arch]. 159 Other existing or proposed solutions are partial solutions or have 160 significant issues, as described below. 162 Summary Comparison of IP/LDP FRR Methods 164 +---------+-------------+-------------+-----------------------------+ 165 | Method | Coverage | Alternate | Computation (in SPFs) | 166 | | | Looping? | | 167 +---------+-------------+-------------+-----------------------------+ 168 | MRT-FRR | 100% | None | less than 3 | 169 | | Link/Node | | | 170 | | | | | 171 | LFA | Partial | Possible | per neighbor | 172 | | Link/Node | | | 173 | | | | | 174 | Remote | Partial | Possible | per neighbor (link) or | 175 | LFA | Link/Node | | neighbor's neighbor (node) | 176 | | | | | 177 | Not-Via | 100% | None | per link and node | 178 | | Link/Node | | | 179 | | | | | 180 | TI-LFA | 100% | Possible | per neighbor (link) or | 181 | | Link/Node | | neighbor's neighbor (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 [RFC7490] improve coverage over LFAs for 196 link protection but still cannot guarantee complete coverage. The 197 trade-off of looping traffic to improve coverage is still made. 198 Remote LFAs can provide node-protection 199 [I-D.ietf-rtgwg-rlfa-node-protection] but not guaranteed coverage 200 and the computation required is quite high (an SPF for each PQ- 201 node evaluated). [I-D.bryant-ipfrr-tunnels] describes additional 202 mechanisms to further improve coverage, at the cost of added 203 complexity. 205 Not-Via: Not-Via [RFC6981] is the only other solution that provides 206 100% coverage for link and node failures and does not have 207 potential looping. However, the computation is very high (an SPF 208 per failure point) and academic implementations 209 [LightweightNotVia] have found the address management complexity 210 to be high. 212 TI-LFA: Topology Independent Loop-free Alternate Fast Re-route (TI- 213 LFA) [I-D.francois-rtgwg-segment-routing-ti-lfa] aims to provide 214 link and node protection of node and adjacency segments within the 215 Segment Routing (SR) framework. It guarantees complete coverage. 216 The TI-LFA computation for link-protection is fairly 217 straightforward, while the computation for node-protection is more 218 complex. For link-protection with symmetric link costs, TI-LFA 219 can provide complete coverage by pushing up to two additional 220 labels. For node protection on arbitrary topologies, the label 221 stack size can grow significantly based on repair path. Note that 222 TI-LFA requires shortest path forwarding based on SR Node-SIDs, as 223 opposed to LDP labels, in order to construct label stacks for 224 backups paths without relying on a large number of targeted LDP 225 sessions to learn remote FEC-label bindings. It also requires the 226 use of Adj-SIDs to achieve 100% coverage. 228 1.1. Importance of 100% Coverage 230 Fast-reroute is based upon the single failure assumption - that the 231 time between single failures is long enough for a network to 232 reconverge and start forwarding on the new shortest paths. That does 233 not imply that the network will only experience one failure or 234 change. 236 It is straightforward to analyze a particular network topology for 237 coverage. However, a real network does not always have the same 238 topology. For instance, maintenance events will take links or nodes 239 out of use. Simply costing out a link can have a significant effect 240 on what LFAs are available. Similarly, after a single failure has 241 happened, the topology is changed and its associated coverage. 242 Finally, many networks have new routers or links added and removed; 243 each of those changes can have an effect on the coverage for 244 topology-sensitive methods such as LFA and Remote LFA. If fast- 245 reroute is important for the network services provided, then a method 246 that guarantees 100% coverage is important to accomodate natural 247 network topology changes. 249 Asymmetric link costs are also a common aspect of networks. There 250 are at least three common causes for them. First, any broadcast 251 interface is represented by a pseudo-node and has asymmetric link 252 costs to and from that pseudo-node. Second, when routers come up or 253 a link with LDP comes up, it is recommended in [RFC5443] and 254 [RFC6987] that the link metric be raised to the maximum cost; this 255 may not be symmetric and for [RFC6987] is not expected to be. Third, 256 techniques such as IGP metric tuning for traffic-engineering can 257 result in asymmetric link costs. A fast-reroute solution needs to 258 handle network topologies with asymmetric link costs. 260 When a network needs to use a micro-loop prevention mechanism 261 [RFC5715] such as Ordered FIB[RFC6976] or Farside Tunneling[RFC5715], 262 then the whole IGP area needs to have alternates available so that 263 the micro-loop prevention mechanism, which requires slower network 264 convergence, can take the necessary time without adversely impacting 265 traffic. Without complete coverage, traffic to the unprotected 266 destinations will be dropped for significantly longer than with 267 current convergence - where routers individually converge as fast as 268 possible. 270 1.2. Partial Deployment and Backwards Compatibility 272 MRT-FRR supports partial deployment. As with many new features, the 273 protocols (OSPF, LDP, ISIS) indicate their capability to support MRT. 274 Inside the MRT-capable connected group of routers (referred to as an 275 MRT Island), the MRTs are computed. Alternates to destinations 276 outside the MRT Island are computed and depend upon the existence of 277 a loop-free neighbor of the MRT Island for that destination. 279 2. Requirements Language 281 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 282 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 283 document are to be interpreted as described in [RFC2119]. 285 3. Terminology 287 network graph: A graph that reflects the network topology where all 288 links connect exactly two nodes and broadcast links have been 289 transformed into the standard pseudo-node representation. 291 Redundant Trees (RT): A pair of trees where the path from any node 292 X to the root R along the first tree is node-disjoint with the 293 path from the same node X to the root along the second tree. 294 These can be computed in 2-connected graphs. 296 Maximally Redundant Trees (MRT): A pair of trees where the path 297 from any node X to the root R along the first tree and the path 298 from the same node X to the root along the second tree share the 299 minimum number of nodes and the minimum number of links. Each 300 such shared node is a cut-vertex. Any shared links are cut-links. 301 Any RT is an MRT but many MRTs are not RTs. 303 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 304 used to described the associated forwarding topology and MPLS MT- 305 ID. Specifically, MRT-Red is the decreasing MRT where links in 306 the GADAG are taken in the direction from a higher topologically 307 ordered node to a lower one. 309 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 310 used to described the associated forwarding topology and MPLS MT- 311 ID. Specifically, MRT-Blue is the increasing MRT where links in 312 the GADAG are taken in the direction from a lower topologically 313 ordered node to a higher one. 315 Rainbow MRT: It is useful to have an MPLS MT-ID that refers to the 316 multiple MRT topologies and to the default topology. This is 317 referred to as the Rainbow MRT MPLS MT-ID and is used by LDP to 318 reduce signaling and permit the same label to always be advertised 319 to all peers for the same (MT-ID, Prefix). 321 MRT Island: The set of routers that support a particular MRT 322 profile and the links connecting them that support MRT. 324 Island Border Router (IBR): A router in the MRT Island that is 325 connected to a router not in the MRT Island and both routers are 326 in a common area or level. 328 Island Neighbor (IN): A router that is not in the MRT Island but is 329 adjacent to an IBR and in the same area/level as the IBR. 331 cut-link: A link whose removal partitions the network. A cut-link 332 by definition must be connected between two cut-vertices. If 333 there are multiple parallel links, then they are referred to as 334 cut-links in this document if removing the set of parallel links 335 would partition the network graph. 337 cut-vertex: A vertex whose removal partitions the network graph. 339 2-connected: A graph that has no cut-vertices. This is a graph 340 that requires two nodes to be removed before the network is 341 partitioned. 343 2-connected cluster: A maximal set of nodes that are 2-connected. 345 2-edge-connected: A network graph where at least two links must be 346 removed to partition the network. 348 block: Either a 2-connected cluster, a cut-edge, or an isolated 349 vertex. 351 DAG: Directed Acyclic Graph - a graph where all links are directed 352 and there are no cycles in it. 354 ADAG: Almost Directed Acyclic Graph - a graph that, if all links 355 incoming to the root were removed, would be a DAG. 357 GADAG: Generalized ADAG - a graph that is the combination of the 358 ADAGs of all blocks. 360 named proxy-node: A proxy-node can represent a destination prefix 361 that can be attached to the MRT Island via at least two routers. 362 It is named if there is a way that traffic can be encapsulated to 363 reach specifically that proxy node; this could be because there is 364 an LDP FEC for the associated prefix or because MRT-Red and MRT- 365 Blue IP addresses are advertised in an undefined fashion for that 366 proxy-node. 368 4. Maximally Redundant Trees (MRT) 370 A pair of Maximally Redundant Trees is a pair of directed spanning 371 trees that provides maximally disjoint paths towards their common 372 root. Only links or nodes whose failure would partition the network 373 (i.e. cut-links and cut-vertices) are shared between the trees. The 374 algorithm to compute MRTs is given in 375 [I-D.ietf-rtgwg-mrt-frr-algorithm]. This algorithm can be computed 376 in O(e + n log n); it is less than three SPFs. Modeling results 377 comparing the alternate path lengths obtained with MRT to other 378 approaches are described in [I-D.ietf-rtgwg-mrt-frr-algorithm]. This 379 document describes how the MRTs can be used and not how to compute 380 them. 382 MRT provides destination-based trees for each destination. Each 383 router stores its normal primary next-hop(s) as well as MRT-Blue 384 next-hop(s) and MRT-Red next-hop(s) toward each destination. The 385 alternate will be selected between the MRT-Blue and MRT-Red. 387 The most important thing to understand about MRTs is that for each 388 pair of destination-routed MRTs, there is a path from every node X to 389 the destination D on the Blue MRT that is as disjoint as possible 390 from the path on the Red MRT. 392 For example, in Figure 1, there is a network graph that is 393 2-connected in (a) and associated MRTs in (b) and (c). One can 394 consider the paths from B to R; on the Blue MRT, the paths are 395 B->F->D->E->R or B->C->D->E->R. On the Red MRT, the path is B->A->R. 396 These are clearly link and node-disjoint. These MRTs are redundant 397 trees because the paths are disjoint. 399 [E]---[D]---| [E]<--[D]<--| [E]-->[D]---| 400 | | | | ^ | | | 401 | | | V | | V V 402 [R] [F] [C] [R] [F] [C] [R] [F] [C] 403 | | | ^ ^ ^ | | 404 | | | | | | V | 405 [A]---[B]---| [A]-->[B]---| [A]<--[B]<--| 407 (a) (b) (c) 408 a 2-connected graph Blue MRT towards R Red MRT towards R 410 Figure 1: A 2-connected Network 412 By contrast, in Figure 2, the network in (a) is not 2-connected. If 413 F, G or the link F<->G failed, then the network would be partitioned. 414 It is clearly impossible to have two link-disjoint or node-disjoint 415 paths from G, I or J to R. The MRTs given in (b) and (c) offer paths 416 that are as disjoint as possible. For instance, the paths from B to 417 R are the same as in Figure 1 and the path from G to R on the Blue 418 MRT is G->F->D->E->R and on the Red MRT is G->F->B->A->R. 420 [E]---[D]---| 421 | | | |----[I] 422 | | | | | 423 [R]---[C] [F]---[G] | 424 | | | | | 425 | | | |----[J] 426 [A]---[B]---| 428 (a) 429 a non-2-connected graph 431 [E]<--[D]<--| [E]-->[D] 432 | ^ | [I] | |----[I] 433 V | | | V V ^ 434 [R] [C] [F]<--[G] | [R]<--[C] [F]<--[G] | 435 ^ ^ ^ V ^ | | 436 | | |----[J] | | [J] 437 [A]-->[B]---| [A]<--[B]<--| 439 (b) (c) 440 Blue MRT towards R Red MRT towards R 442 Figure 2: A non-2-connected network 444 5. Maximally Redundant Trees (MRT) and Fast-Reroute 446 In normal IGP routing, each router has its shortest-path-tree to all 447 destinations. From the perspective of a particular destination, D, 448 this looks like a reverse SPT (rSPT). To use maximally redundant 449 trees, in addition, each destination D has two MRTs associated with 450 it; by convention these will be called the MRT-Blue and MRT-Red. 451 MRT-FRR is realized by using multi-topology forwarding. There is a 452 MRT-Blue forwarding topology and a MRT-Red forwarding topology. 454 Any IP/LDP fast-reroute technique beyond LFA requires an additional 455 dataplane procedure, such as an additional forwarding mechanism. The 456 well-known options are multi-topology forwarding (used by MRT-FRR), 457 tunneling (e.g. [RFC6981] or [RFC7490]), and per-interface 458 forwarding (e.g. Loop-Free Failure Insensitive Routing in 459 [EnyediThesis]). 461 When there is a link or node failure affecting, but not partitioning, 462 the network, each node will still have at least one path via one of 463 the MRTs to reach the destination D. For example, in Figure 2, C 464 would normally forward traffic to R across the C<->R link. If that 465 C<->R link fails, then C could use the Blue MRT path C->D->E->R. 467 As is always the case with fast-reroute technologies, forwarding does 468 not change until a local failure is detected. Packets are forwarded 469 along the shortest path. The appropriate alternate to use is pre- 470 computed. [I-D.ietf-rtgwg-mrt-frr-algorithm] describes exactly how 471 to determine whether the MRT-Blue next-hops or the MRT-Red next-hops 472 should be the MRT alternate next-hops for a particular primary next- 473 hop to a particular destination. 475 MRT alternates are always available to use. It is a local decision 476 whether to use an MRT alternate, a Loop-Free Alternate or some other 477 type of alternate. 479 As described in [RFC5286], when a worse failure than is anticipated 480 happens, using LFAs that are not downstream neighbors can cause 481 micro-looping. Section 1.1 of [RFC5286] gives an example of link- 482 protecting alternates causing a loop on node failure. Even if a 483 worse failure than anticipated happens, the use of MRT alternates 484 will not cause looping. Therefore, while node-protecting LFAs may be 485 preferred, the certainty that no alternate-induced looping will occur 486 is an advantage of using MRT alternates when the available node- 487 protecting LFA is not a downstream path. 489 6. Unicast Forwarding with MRT Fast-Reroute 491 There are three possible types of routers involved in forwarding a 492 packet along an MRT path. At the MRT ingress router, the packet 493 leaves the shortest path to the destination and follows an MRT path 494 to the destination. In a FRR application, the MRT ingress router is 495 the PLR. An MRT transit router takes a packet that arrives already 496 associated with the particular MRT, and forwards it on that same MRT. 497 In some situations (to be discussed later), the packet will need to 498 leave the MRT path and return to the shortest path. This takes place 499 at the MRT egress router. The MRT ingress and egress functionality 500 may depend on the underlying type of packet being forwarded (LDP or 501 IP). The MRT transit functionality is independent of the type of 502 packet being forwarded. We first consider several MRT transit 503 forwarding mechanisms. Then we look at how these forwarding 504 mechanisms can be applied to carrying LDP and IP traffic. 506 6.1. MRT Forwarding Mechanisms 508 The following options for MRT forwarding mechanisms are considered. 510 1. MRT LDP Labels 512 A. Topology-scoped FEC encoded using a single label 514 B. Topology and FEC encoded using a two label stack 516 2. MRT IP Tunnels 518 A. MRT IPv4 Tunnels 520 B. MRT IPv6 Tunnels 522 6.1.1. MRT LDP labels 524 We consider two options for the MRT forwarding mechanisms using MRT 525 LDP labels. 527 6.1.1.1. Topology-scoped FEC encoded using a single label (Option 1A) 529 [RFC7307] provides a mechanism to distribute FEC-Label bindings 530 scoped to a given MPLS topology (represented by MPLS MT-ID). To use 531 multi-topology LDP to create MRT forwarding topologies, we associate 532 two MPLS MT-IDs with the MRT-Red and MRT-Blue forwarding topologies, 533 in addition to the default shortest path forwarding topology with MT- 534 ID=0. 536 With this forwarding mechanism, a single label is distributed for 537 each topology-scoped FEC. For a given FEC in the default topology 538 (call it default-FEC-A), two additional topology-scoped FECs would be 539 created, corresponding to the Red and Blue MRT forwarding topologies 540 (call them red-FEC-A and blue-FEC-A). A router supporting this MRT 541 transit forwarding mechanism advertises a different FEC-label binding 542 for each of the three topology-scoped FECs. When a packet is 543 received with a label corresponding to red-FEC-A (for example), an 544 MRT transit router will determine the next-hop for the MRT-Red 545 forwarding topology for that FEC, swap the incoming label with the 546 outgoing label corresponding to red-FEC-A learned from the MRT-Red 547 next-hop router, and forward the packet. 549 This forwarding mechanism has the useful property that the FEC 550 associated with the packet is maintained in the labels at each hop 551 along the MRT. We will take advantage of this property when 552 specifying how to carry LDP traffic on MRT paths using multi-topology 553 LDP labels. 555 This approach is very simple for hardware to support. However, it 556 reduces the label space for other uses, and it increases the memory 557 needed to store the labels and the communication required by LDP to 558 distribute FEC-label bindings. 560 This forwarding option uses the LDP signaling extensions described in 561 [RFC7307]. The MRT-specific LDP extensions required to support this 562 option are described in [I-D.ietf-mpls-ldp-mrt]. 564 6.1.1.2. Topology and FEC encoded using a two label stack (Option 1B) 566 With this forwarding mechanism, a two label stack is used to encode 567 the topology and the FEC of the packet. The top label (topology-id 568 label) identifies the MRT forwarding topology, while the second label 569 (FEC label) identifies the FEC. The top label would be a new FEC 570 type with two values corresponding to MRT Red and Blue topologies. 572 When an MRT transit router receives a packet with a topology-id 573 label, the router pops the top label and uses that it to guide the 574 next-hop selection in combination with the next label in the stack 575 (the FEC label). The router then swaps the FEC label, using the FEC- 576 label bindings learned through normal LDP mechanisms. The router 577 then pushes the topology-id label for the next-hop. 579 As with Option 1A, this forwarding mechanism also has the useful 580 property that the FEC associated with the packet is maintained in the 581 labels at each hop along the MRT. 583 This forwarding mechanism has minimal usage of additional labels, 584 memory and LDP communication. It does increase the size of packets 585 and the complexity of the required label operations and look-ups. 587 This forwarding option is consistent with context-specific label 588 spaces, as described in [RFC5331]. However, the precise LDP behavior 589 required to support this option for MRT has not been specified. 591 6.1.1.3. Compatibility of Option 1A and 1B 593 In principle, MRT transit forwarding mechanisms 1A and 1B can coexist 594 in the same network, with a packet being forwarding along a single 595 MRT path using the single label of option 1A for some hops and the 596 two label stack of option 1B for other hops. 598 6.1.1.4. Mandatory support for MRT LDP Label option 1A 600 If a router supports a profile that includes the MRT LDP Label option 601 for MRT transit forwarding mechanism, then it MUST support option 1A, 602 which encodes topology-scoped FECs using a single label. 604 6.1.2. MRT IP tunnels (Options 2A and 2B) 606 IP tunneling can also be used as an MRT transit forwarding mechanism. 607 Each router supporting this MRT transit forwarding mechanism 608 announces two additional loopback addresses and their associated MRT 609 color. Those addresses are used as destination addresses for MRT- 610 blue and MRT-red IP tunnels respectively. The special loopback 611 addresses allow the transit nodes to identify the traffic as being 612 forwarded along either the MRT-blue or MRT-red topology to reach the 613 tunnel destination. For example, an MRT ingress router can cause a 614 packet to be tunneled along the MRT-red path to router X by 615 encapsulating the packet using the MRT-red loopback address 616 advertised by router X. Upon receiving the packet, router X would 617 remove the encapsulation header and forward the packet based on the 618 original destination address. 620 Announcements of these two additional loopback addresses per router 621 with their MRT color requires IGP extensions, which have not been 622 defined. 624 Either IPv4 (option 2A) or IPv6 (option 2B) can be used as the 625 tunneling mechanism. 627 Note that the two forwarding mechanisms using LDP Label options do 628 not require additional loopbacks per router, as is required by the IP 629 tunneling mechanism. This is because LDP labels are used on a hop- 630 by-hop basis to identify MRT-blue and MRT-red forwarding topologies. 632 6.2. Forwarding LDP Unicast Traffic over MRT Paths 634 In the previous section, we examined several options for providing 635 MRT transit forwarding functionality, which is independent of the 636 type of traffic being carried. We now look at the MRT ingress 637 functionality, which will depend on the type of traffic being carried 638 (IP or LDP). We start by considering LDP traffic. 640 We also simplify the initial discussion by assuming that the network 641 consists of a single IGP area, and that all routers in the network 642 participate in MRT. Other deployment scenarios that require MRT 643 egress functionality are considered later in this document. 645 In principle, it is possible to carry LDP traffic in MRT IP tunnels. 646 However, for LDP traffic, it is desirable to avoid tunneling. 647 Tunneling LDP traffic to a remote node requires knowledge of remote 648 FEC-label bindings so that the LDP traffic can continue to be 649 forwarded properly when it leaves the tunnel. This requires targeted 650 LDP sessions which can add management complexity. As described 651 below, the two MRT forwarding mechanisms that use LDP labels do not 652 require targeted LDP sessions. 654 6.2.1. Forwarding LDP traffic using MRT LDP Labels (Option 1A) 656 The MRT LDP Label option 1A forwarding mechanism uses topology-scoped 657 FECs encoded using a single label as described in section 658 Section 6.1.1.1. When a PLR receives an LDP packet that needs to be 659 forwarded on the Red MRT (for example), it does a label swap 660 operation, replacing the usual LDP label for the FEC with the Red MRT 661 label for that FEC received from the next-hop router in the Red MRT 662 computed by the PLR. When the next-hop router in the Red MRT 663 receives the packet with the Red MRT label for the FEC, the MRT 664 transit forwarding functionality continues as described in 665 Section 6.1.1.1. In this way the original FEC associated with the 666 packet is maintained at each hop along the MRT. 668 6.2.2. Forwarding LDP traffic using MRT LDP Labels (Option 1B) 670 The MRT LDP Label option 1B forwarding mechanism encodes the topology 671 and the FEC using a two label stack as described in Section 6.1.1.2. 672 When a PLR receives an LDP packet that needs to be forwarded on the 673 Red MRT, it first does a normal LDP label swap operation, replacing 674 the incoming normal LDP label associated with a given FEC with the 675 outgoing normal LDP label for that FEC learned from the next-hop on 676 the Red MRT. In addition, the PLR pushes the topology-identification 677 label associated with the Red MRT, and forward the packet to the 678 appropriate next-hop on the Red MRT. When the next-hop router in the 679 Red MRT receives the packet with the Red MRT label for the FEC, the 680 MRT transit forwarding functionality continues as described in 681 Section 6.1.1.2. As with option 1A, the original FEC associated with 682 the packet is maintained at each hop along the MRT. 684 6.2.3. Other considerations for forwarding LDP traffic using MRT LDP 685 Labels 687 Note that forwarding LDP traffic using MRT LDP Labels can be done 688 without the use of targeted LDP sessions when an MRT path to the 689 destination FEC is used. The alternates selected in 690 [I-D.ietf-rtgwg-mrt-frr-algorithm] use the MRT path to the 691 destination FEC, so targeted LDP sessions are not needed. If instead 692 one found it desirable to have the PLR use an MRT to reach the 693 primary next-next-hop for the FEC, and then continue forwarding the 694 LDP packet along the shortest path tree from the primary next-next- 695 hop, this would require tunneling to the primary next-next-hop and a 696 targeted LDP session for the PLR to learn the FEC-label binding for 697 primary next-next-hop to correctly forward the packet. 699 For greatest hardware compatibility, routers implementing MRT fast- 700 reroute of LDP traffic MUST support Option 1A of encoding the MT-ID 701 in the labels (See Section 9). 703 6.3. Forwarding IP Unicast Traffic over MRT Paths 705 For IPv4 traffic, there is no currently practical alternative except 706 tunneling to gain the bits needed to indicate the MRT-Blue or MRT-Red 707 forwarding topology. For IPv6 traffic, in principle one could define 708 bits in the IPv6 options header to indicate the MRT-Blue or MRT-Red 709 forwarding topology. However, in this document, we have chosen not 710 to define a solution that would work for IPv6 traffic but not for 711 IPv4 traffic. 713 The choice of tunnel egress MAY be flexible since any router closer 714 to the destination than the next-hop can work. This architecture 715 assumes that the original destination in the area is selected (see 716 Section 11 for handling of multi-homed prefixes); another possible 717 choice is the next-next-hop towards the destination. As discussed in 718 the previous section, for LDP traffic, using the MRT to the original 719 destination simplifies MRT-FRR by avoiding the need for targeted LDP 720 sessions to the next-next-hop. For IP, that consideration doesn't 721 apply. However, consistency with LDP is RECOMMENDED. 723 Some situations require tunneling IP traffic along an MRT to a tunnel 724 endpoint that is not the destination of the IP traffic. These 725 situations will be discussed in detail later. We note here that an 726 IP packet with a destination in a different IGP area/level from the 727 PLR should be tunneled on the MRT to the ABR/LBR on the shortest path 728 to the destination. For a destination outside of the PLR's MRT 729 Island, the packet should be tunneled on the MRT to a non-proxy-node 730 immediately before the named proxy-node on that particular color MRT. 732 6.3.1. Tunneling IP traffic using MRT LDP Labels 734 An IP packet can be tunneled along an MRT path by pushing the 735 appropriate MRT LDP label(s). Tunneling using LDP labels, as opposed 736 to IP headers, has the the advantage that more installed routers can 737 do line-rate encapsulation and decapsulation using LDP than using IP. 738 Also, no additional IP addresses would need to be allocated or 739 signaled. 741 6.3.1.1. Tunneling IP traffic using MRT LDP Labels (Option 1A) 743 The MRT LDP Label option 1A forwarding mechanism uses topology-scoped 744 FECs encoded using a single label as described in section 745 Section 6.1.1.1. When a PLR receives an IP packet that needs to be 746 forwarded on the Red MRT to a particular tunnel endpoint, it does a 747 label push operation. The label pushed is the Red MRT label for a 748 FEC originated by the tunnel endpoint, learned from the next-hop on 749 the Red MRT. 751 6.3.1.2. Tunneling IP traffic using MRT LDP Labels (Option 1B) 753 The MRT LDP Label option 1B forwarding mechanism encodes the topology 754 and the FEC using a two label stack as described in Section 6.1.1.2. 755 When a PLR receives an IP packet that needs to be forwarded on the 756 Red MRT to a particular tunnel endpoint, the PLR pushes two labels on 757 the IP packet. The first (inner) label is the normal LDP label 758 learned from the next-hop on the Red MRT, associated with a FEC 759 originated by the tunnel endpoint. The second (outer) label is the 760 topology-identification label associated with the Red MRT. 762 For completeness, we note here a potential variation that uses a 763 single label as opposed to two labels. In order to tunnel an IP 764 packet over an MRT to the destination of the IP packet (as opposed to 765 an arbitrary tunnel endpoint), then we could just push a topology- 766 identification label directly onto the packet. An MRT transit router 767 would need to pop the topology-id label, do an IP route lookup in the 768 context of that topology-id , and push the topology-id label. 770 6.3.2. Tunneling IP traffic using MRT IP Tunnels 772 In order to tunnel over the MRT to a particular tunnel endpoint, the 773 PLR encapsulates the original IP packet with an additional IP header 774 using the MRT-Blue or MRT-Red loopack address of the tunnel endpoint. 776 6.3.3. Required support 778 For greatest hardware compatibility and ease in removing the MRT- 779 topology marking at area/level boundaries, routers that support MPLS 780 and implement IP MRT fast-reroute MUST support tunneling of IP 781 traffic using MRT LDP Labels Option 1A (topology-scoped FEC encoded 782 using a single label). 784 7. MRT Island Formation 786 The purpose of communicating support for MRT in the IGP is to 787 indicate that the MRT-Blue and MRT-Red forwarding topologies are 788 created for transit traffic. The MRT architecture allows for 789 different, potentially incompatible options. In order to create 790 constistent MRT forwarding topologies, the routers participating in a 791 particular MRT Island need to use the same set of options. These 792 options are grouped into MRT profiles. In addition, the routers in 793 an MRT Island all need to use the same set of nodes and links within 794 the Island when computing the MRT forwarding topologies. This 795 section describes the information used by a router to determine the 796 nodes and links to include in a particular MRT Island. Some of this 797 information is shared among routers using the newly-defined IGP 798 signaling extensions for MRT described in [I-D.ietf-ospf-mrt] and 799 [I-D.ietf-isis-mrt]. Other information already exists in the IGPs 800 and can be used by MRT in Island formation, subject to the 801 interpretation defined here. 803 Deployment scenarios using multi-topology OSPF or IS-IS, or running 804 both ISIS and OSPF on the same routers is out of scope for this 805 specification. As with LFA, it is expected that OSPF Virtual Links 806 will not be supported. 808 7.1. IGP Area or Level 810 All links in an MRT Island MUST be bidirectional and belong to the 811 same IGP area or level. For ISIS, a link belonging to both level 1 812 and level 2 would qualify to be in multiple MRT Islands. A given ABR 813 or LBR can belong to multiple MRT Islands, corresponding to the areas 814 or levels in which it participates. Inter-area forwarding behavior 815 is discussed in Section 10. 817 7.2. Support for a specific MRT profile 819 All routers in an MRT Island MUST support the same MRT profile. A 820 router advertises support for a given MRT profile using the IGP 821 extensions defined in [I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt] 822 using an 8-bit Profile ID value. A given router can support multiple 823 MRT profiles and participate in multiple MRT Islands. The options 824 that make up an MRT profile, as well as the default MRT profile, are 825 defined in Section 8. 827 7.3. Excluding additional routers and interfaces from the MRT Island 829 MRT takes into account existing IGP mechanisms for discouraging 830 traffic from using particular links and routers, and it introduces an 831 MRT-specific exclusion mechanism for links. 833 7.3.1. Existing IGP exclusion mechanisms 835 Mechanisms for discouraging traffic from using particular links 836 already exist in ISIS and OSPF. In ISIS, an interface configured 837 with a metric of 2^24-2 (0xFFFFFE) will only be used as a last 838 resort. (An interface configured with a metric of 2^24-1 (0xFFFFFF) 839 will not be advertised into the topology.) In OSPF, an interface 840 configured with a metric of 2^16-1 (0xFFFF) will only be used as a 841 last resort. These metrics can be configured manually to enforce 842 administrative policy, or they can be set in an automated manner as 843 with LDP IGP synchronization [RFC5443]. 845 Mechanisms also exist in ISIS and OSPF to prevent transit traffic 846 from using a particular router. In ISIS, the overload bit is used 847 for this purpose. In OSPF, [RFC6987] specifies setting all outgoing 848 interface metrics to 0xFFFF to accomplish this. 850 The following rules for MRT Island formation ensure that MRT FRR 851 protection traffic does not use a link or router that is discouraged 852 from carrying traffic by existing IGP mechanisms. 854 1. A bidirectional link MUST be excluded from an MRT Island if 855 either the forward or reverse cost on the link is 0xFFFFFE (for 856 ISIS) or 0xFFFF for OSPF. 858 2. A router MUST be excluded from an MRT Island if it is advertised 859 with the overload bit set (for ISIS), or it is advertised with 860 metric values of 0xFFFF on all of its outgoing interfaces (for 861 OSPF). 863 7.3.2. MRT-specific exclusion mechanism 865 This architecture also defines a means of excluding an otherwise 866 usable link from MRT Islands. [I-D.ietf-ospf-mrt] and 867 [I-D.ietf-isis-mrt] define the IGP extensions for OSPF and ISIS used 868 to advertise that a link is MRT-Ineligible. A link with either 869 interface advertised as MRT-Ineligible MUST be excluded from an MRT 870 Island. Note that an interface advertised as MRT-Ineligigle by a 871 router is ineligible with respect to all profiles advertised by that 872 router. 874 7.4. Connectivity 876 All of the routers in an MRT Island MUST be connected by 877 bidirectional links with other routers in the MRT Island. 878 Disconnected MRT Islands will operate independently of one another. 880 7.5. Example algorithm 882 An algorithm that allows a computing router to identify the routers 883 and links in the local MRT Island satisfying the above rules is given 884 in section 5.2 of [I-D.ietf-rtgwg-mrt-frr-algorithm]. 886 8. MRT Profile 888 An MRT Profile is a set of values and options related to MRT 889 behavior. The complete set of options is designated by the 890 corresponding 8-bit Profile ID value. 892 This document specifies the values and options that correspond to the 893 Default MRT Profile (Profile ID = 0). Future documents may define 894 other MRT Profiles by specifying the MRT Profile Options below. 896 8.1. MRT Profile Options 898 Below is a description of the values and options that define an MRT 899 Profile. 901 MRT Algorithm: This identifies the particular MRT algorithm used by 902 the router for this profile. Algorithm transitions can be managed 903 by advertising multiple MRT profiles. 905 MRT-Red MT-ID: This specifies the MT-ID to be associated with the 906 MRT-Red forwarding topology. It is needed for use in LDP 907 signaling. All routers in the MRT Island MUST agree on a value. 909 MRT-Blue MT-ID: This specifies the MT-ID to be associated with the 910 MRT-Blue forwarding topology. It is needed for use in LDP 911 signaling. All routers in the MRT Island MUST agree on a value. 913 GADAG Root Selection Policy: This specifes the manner in which the 914 GADAG root is selected. All routers in the MRT island need to use 915 the same GADAG root in the calculations used construct the MRTs. 916 A valid GADAG Root Selection Policy MUST be such that each router 917 in the MRT island chooses the same GADAG root based on information 918 available to all routers in the MRT island. GADAG Root Selection 919 Priority values, advertised in the IGP as router-specific MRT 920 parameters, MAY be used in a GADAG Root Selection Policy. 922 MRT Forwarding Mechanism: This specifies which forwarding mechanism 923 the router uses to carry transit traffic along MRT paths. A 924 router which supports a specific MRT forwarding mechanism must 925 program appropriate next-hops into the forwarding plane. The 926 current options are MRT LDP Labels, IPv4 Tunneling, IPv6 927 Tunneling, and None. If the MRT LDP Labels option is supported, 928 then option 1A and the appropriate signaling extensions MUST be 929 supported. If IPv4 is supported, then both MRT-Red and MRT-Blue 930 IPv4 Loopback Addresses SHOULD be specified. If IPv6 is 931 supported, both MRT-Red and MRT-Blue IPv6 Loopback Addresses 932 SHOULD be specified. The None option in may be useful for 933 multicast global protection. 935 Recalculation: Recalculation specifies the process and timing by 936 which new MRTs are computed after the topology has been modified. 938 Area/Level Border Behavior: Should inter-area traffic on the MRT- 939 Blue or MRT-Red be put back onto the shortest path tree? Should 940 it be swapped from MRT-Blue or MRT-Red in one area/level to MRT- 941 Red or MRT-Blue in the next area/level to avoid the potential 942 failure of an ABR? (See [I-D.atlas-rtgwg-mrt-mc-arch] for use- 943 case details. 945 Other Profile-Specific Behavior: Depending upon the use-case for 946 the profile, there may be additional profile-specific behavior. 948 If a router advertises support for multiple MRT profiles, then it 949 MUST create the transit forwarding topologies for each of those, 950 unless the profile specifies the None option for MRT Forwarding 951 Mechanism. A router MUST NOT advertise multiple MRT profiles that 952 overlap in their MRT-Red MT-ID or MRT-Blue MT-ID. 954 8.2. Router-specific MRT paramaters 956 For some profiles, additional router-specific MRT parameters may need 957 to be distributed via the IGP. While the set of options indicated by 958 the MRT Profile ID must be identical for all routers in an MRT 959 Island, these router-specific MRT parameters may differ between 960 routers in the same MRT island. Several such parameters are 961 described below. 963 GADAG Root Selection Priority: A GADAG Root Selection Policy MAY 964 rely on the GADAG Root Selection Priority values advertised by 965 each router in the MRT island. A GADAG Root Selection Policy may 966 use the GADAG Root Selection Priority to allow network operators 967 to configure a parameter to ensure that the GADAG root is selected 968 from a particular subset of routers. An example of this use of 969 the GADAG Root Selection Priority value by the GADAG Root 970 Selection Policy is given in the Default MRT profile below. 972 MRT-Red Loopback Address: This provides the router's loopback 973 address to reach the router via the MRT-Red forwarding topology. 974 It can be specified for either IPv4 and IPv6. 976 MRT-Blue Loopback Address: This provides the router's loopback 977 address to reach the router via the MRT-Blue forwarding topology. 978 It can be specified for either IPv4 and IPv6. 980 The extensions to OSPF and ISIS for advertising a router's GADAG Root 981 Selection Priority value are defined in [I-D.ietf-ospf-mrt] and 982 [I-D.ietf-isis-mrt]. IGP extensions for the advertising a router's 983 MRT-Red and MRT-Blue Loopback Addresses have not been defined. 985 8.3. Default MRT profile 987 The following set of options defines the default MRT Profile. The 988 default MRT profile is indicated by the MRT Profile ID value of 0. 990 MRT Algorithm: MRT Lowpoint algorithm defined in 991 [I-D.ietf-rtgwg-mrt-frr-algorithm]. 993 MRT-Red MPLS MT-ID: [I-D.ietf-mpls-ldp-mrt] contains the IANA 994 request for allocation of this value from the MPLS Multi-Topology 995 Identifiers Registry. Prototype experiments have used a value of 996 3997. 998 MRT-Blue MPLS MT-ID: [I-D.ietf-mpls-ldp-mrt] contains the IANA 999 request for allocation of this value from the MPLS Multi-Topology 1000 Identifiers Registry. Prototype experiments have used a value of 1001 3998. 1003 GADAG Root Selection Policy: Among the routers in the MRT Island 1004 and with the highest priority advertised, an implementation MUST 1005 pick the router with the highest Router ID to be the GADAG root. 1007 Forwarding Mechanisms: MRT LDP Labels 1009 Recalculation: Recalculation of MRTs SHOULD occur as described in 1010 Section 12.2. This allows the MRT forwarding topologies to 1011 support IP/LDP fast-reroute traffic. 1013 Area/Level Border Behavior: As described in Section 10, ABRs/LBRs 1014 SHOULD ensure that traffic leaving the area also exits the MRT-Red 1015 or MRT-Blue forwarding topology. 1017 9. LDP signaling extensions and considerations 1019 The protocol extensions for LDP are defined in 1020 [I-D.ietf-mpls-ldp-mrt]. A router must indicate that it has the 1021 ability to support MRT; having this explicit allows the use of MRT- 1022 specific processing, such as special handling of FECs sent with the 1023 Rainbow MRT MT-ID. 1025 A FEC sent with the Rainbow MRT MT-ID indicates that the FEC applies 1026 to all the MRT-Blue and MRT-Red MT-IDs in supported MRT profiles. 1027 The FEC-label bindings for the default shortest-path based MT-ID 0 1028 MUST still be sent (even though it could be inferred from the Rainbow 1029 FEC-label bindings) to ensure continuous operation of normal LDP 1030 forwarding. The Rainbow MRT MT-ID is defined to provide an easy way 1031 to handle the special signaling that is needed at ABRs or LBRs. It 1032 avoids the problem of needing to signal different MPLS labels to 1033 different LDP neighbors for the same FEC. Because the Rainbow MRT 1034 MT-ID is used only by ABRs/LBRs or an LDP egress router, it is not 1035 MRT profile specific. 1037 [I-D.ietf-mpls-ldp-mrt] contains the IANA request for the Rainbow MRT 1038 MPLS MT-ID. 1040 10. Inter-area Forwarding Behavior 1042 Unless otherwise specified, in this section we will use the terms 1043 area and ABR to indicate either an OSPF area and OSPF ABR or ISIS 1044 level and ISIS LBR. 1046 An ABR/LBR has two forwarding roles. First, it forwards traffic 1047 within areas. Second, it forwards traffic from one area into 1048 another. These same two roles apply for MRT transit traffic. 1049 Traffic on MRT-Red or MRT-Blue destined inside the area needs to stay 1050 on MRT-Red or MRT-Blue in that area. However, it is desirable for 1051 traffic leaving the area to also exit MRT-Red or MRT-Blue and return 1052 to shortest path forwarding. 1054 For unicast MRT-FRR, the need to stay on an MRT forwarding topology 1055 terminates at the ABR/LBR whose best route is via a different area/ 1056 level. It is highly desirable to go back to the default forwarding 1057 topology when leaving an area/level. There are three basic reasons 1058 for this. First, the default topology uses shortest paths; the 1059 packet will thus take the shortest possible route to the destination. 1060 Second, this allows failures that might appear in multiple areas 1061 (e.g. ABR/LBR failures) to be separately identified and repaired 1062 around. Third, the packet can be fast-rerouted again, if necessary, 1063 due to a failure in a different area. 1065 An ABR/LBR that receives a packet on MRT-Red or MRT-Blue towards 1066 destination Z should continue to forward the packet along MRT-Red or 1067 MRT-Blue only if the best route to Z is in the same area as the 1068 interface that the packet was received on. Otherwise, the packet 1069 should be removed from MRT-Red or MRT-Blue and forwarded on the 1070 shortest-path default forwarding topology. 1072 To avoid per-interface forwarding state for MRT-Red and MRT-Blue, the 1073 ABR/LBR needs to arrange that packets destined to a different area 1074 arrive at the ABR/LBR already not marked as MRT-Red or MRT-Blue. 1076 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A 1078 For LDP forwarding where a single label specifies (MT-ID, FEC), the 1079 ABR/LBR is responsible for advertising the proper label to each 1080 neighbor. Assume that an ABR/LBR has allocated three labels for a 1081 particular destination; those labels are L_primary, L_blue, and 1082 L_red. To those routers in the same area as the best route to the 1083 destination, the ABR/LBR advertises the following FEC-label bindings: 1084 L_primary for the default topology, L_blue for the MRT-Blue MT-ID and 1085 L_red for the MRT-Red MT-ID, as expected. However, to routers in 1086 other areas, the ABR/LBR advertises the following FEC-label bindings: 1087 L_primary for the default topology, and L_primary for the Rainbow MRT 1088 MT-ID. Associating L_primary with the Rainbow MRT MT-ID causes the 1089 receiving routers to use L_primary for the MRT-Blue MT-ID and for the 1090 MRT-Red MT-ID. 1092 The ABR/LBR installs all next-hops for the best area: primary next- 1093 hops for L_primary, MRT-Blue next-hops for L_blue, and MRT-Red next- 1094 hops for L_red. Because the ABR/LBR advertised (Rainbow MRT MT-ID, 1095 FEC) with L_primary to neighbors not in the best area, packets from 1096 those neighbors will arrive at the ABR/LBR with a label L_primary and 1097 will be forwarded into the best area along the default topology. By 1098 controlling what labels are advertised, the ABR/LBR can thus enforce 1099 that packets exiting the area do so on the shortest-path default 1100 topology. 1102 10.1.1. Motivation for Creating the Rainbow-FEC 1104 The desired forwarding behavior could be achieved in the above 1105 example without using the Rainbow-FEC. This could be done by having 1106 the ABR/LBR advertise the following FEC-label bindings to neighbors 1107 not in the best area: L1_primary for the default topology, L1_primary 1108 for the MRT-Blue MT-ID, and L1_primary for the MRT-Red MT-ID. Doing 1109 this would require machinery to spoof the labels used in FEC-label 1110 binding advertisements on a per-neighbor basis. Such label-spoofing 1111 machinery does not currently exist in most LDP implmentations and 1112 doesn't have other obvious uses. 1114 Many existing LDP implmentations do however have the ability to 1115 filter FEC-label binding advertisements on a per-neighbor basis. The 1116 Rainbow-FEC allows us to re-use the existing per-neighbor FEC 1117 filtering machinery to achieve the desired result. By introducing 1118 the Rainbow FEC, we can use per-neighbor FEC-filtering machinery to 1119 advertise the FEC-label binding for the Rainbow-FEC (and filter those 1120 for MRT-Blue and MRT-Red) to non-best-area neighbors of the ABR. 1122 The use of the Rainbow-FEC by the ABR for non-best-area 1123 advertisements is RECOMMENDED. An ABR MAY advertise the label for 1124 the default topology in separate MRT-Blue and MRT-Red advertisements. 1125 However, a router that supports the LDP Label MRT Forwarding 1126 Mechanism MUST be able to receive and correctly interpret the 1127 Rainbow-FEC. 1129 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) 1131 If IP tunneling is used, then the ABR/LBR behavior is dependent upon 1132 the outermost IP address. If the outermost IP address is an MRT 1133 loopback address of the ABR/LBR, then the packet is decapsulated and 1134 forwarded based upon the inner IP address, which should go on the 1135 default SPT topology. If the outermost IP address is not an MRT 1136 loopback address of the ABR/LBR, then the packet is simply forwarded 1137 along the associated forwarding topology. A PLR sending traffic to a 1138 destination outside its local area/level will pick the MRT and use 1139 the associated MRT loopback address of the selected ABR/LBR 1140 advertising the lowest cost to the external destination. 1142 Thus, for these two MRT Forwarding Mechanisms( MRT LDP Label option 1143 1A and IP tunneling option 2), there is no need for additional 1144 computation or per-area forwarding state. 1146 10.3. ABR Forwarding Behavior with LDP Label option 1B 1148 The other MRT forwarding mechanism described in Section 6 uses two 1149 labels, a topology-id label, and a FEC-label. This mechanism would 1150 require that any router whose MRT-Red or MRT-Blue next-hop is an ABR/ 1151 LBR would need to determine whether the ABR/LBR would forward the 1152 packet out of the area/level. If so, then that router should pop off 1153 the topology-identification label before forwarding the packet to the 1154 ABR/LBR. 1156 For example, in Figure 3, if node H fails, node E has to put traffic 1157 towards prefix p onto MRT-Red. But since node D knows that ABR1 will 1158 use a best route from another area, it is safe for D to pop the 1159 Topology-Identification Label and just forward the packet to ABR1 1160 along the MRT-Red next-hop. ABR1 will use the shortest path in Area 1161 10. 1163 In all cases for ISIS and most cases for OSPF, the penultimate router 1164 can determine what decision the adjacent ABR will make. The one case 1165 where it can't be determined is when two ASBRs are in different non- 1166 backbone areas attached to the same ABR, then the ASBR's Area ID may 1167 be needed for tie-breaking (prefer the route with the largest OPSF 1168 area ID) and the Area ID isn't announced as part of the ASBR link- 1169 state advertisement (LSA). In this one case, suboptimal forwarding 1170 along the MRT in the other area would happen. If that becomes a 1171 realistic deployment scenario, OSPF extensions could be considered. 1172 This is not covered in [I-D.ietf-ospf-mrt]. 1174 +----[C]---- --[D]--[E] --[D]--[E] 1175 | \ / \ / \ 1176 p--[A] Area 10 [ABR1] Area 0 [H]--p +-[ABR1] Area 0 [H]-+ 1177 | / \ / | \ / | 1178 +----[B]---- --[F]--[G] | --[F]--[G] | 1179 | | 1180 | other | 1181 +----------[p]-------+ 1182 area 1184 (a) Example topology (b) Proxy node view in Area 0 nodes 1186 +----[C]<--- [D]->[E] 1187 V \ \ 1188 +-[A] Area 10 [ABR1] Area 0 [H]-+ 1189 | ^ / / | 1190 | +----[B]<--- [F]->[G] V 1191 | | 1192 +------------->[p]<--------------+ 1194 (c) rSPT towards destination p 1196 ->[D]->[E] -<[D]<-[E] 1197 / \ / \ 1198 [ABR1] Area 0 [H]-+ +-[ABR1] [H] 1199 / | | \ 1200 [F]->[G] V V -<[F]<-[G] 1201 | | 1202 | | 1203 [p]<------+ +--------->[p] 1205 (d) Blue MRT in Area 0 (e) Red MRT in Area 0 1207 Figure 3: ABR Forwarding Behavior and MRTs 1209 11. Prefixes Multiply Attached to the MRT Island 1211 How a computing router S determines its local MRT Island for each 1212 supported MRT profile is already discussed in Section 7. 1214 There are two types of prefixes or FECs that may be multiply attached 1215 to an MRT Island. The first type are multi-homed prefixes that 1216 usually connect at a domain or protocol boundary. The second type 1217 represent routers that do not support the profile for the MRT Island. 1219 The key difference is whether the traffic, once out of the MRT 1220 Island, remains in the same area/level and might re-enter the MRT 1221 Island if a loop-free exit point is not selected. 1223 FRR using LFA has the useful property that it is able to protect 1224 multi-homed prefixes against ABR failure. For instance, if a prefix 1225 from the backbone is available via both ABR A and ABR B, if A fails, 1226 then the traffic should be redirected to B. This can be accomplished 1227 with MRT FRR as well. 1229 If ASBR protection is desired, this has additional complexities if 1230 the ASBRs are in different areas. Similarly, protecting labeled BGP 1231 traffic in the event of an ASBR failure has additional complexities 1232 due to the per-ASBR label spaces involved. 1234 As discussed in [RFC5286], a multi-homed prefix could be: 1236 o An out-of-area prefix announced by more than one ABR, 1238 o An AS-External route announced by 2 or more ASBRs, 1240 o A prefix with iBGP multipath to different ASBRs, 1242 o etc. 1244 There are also two different approaches to protection. The first is 1245 tunnel endpoint selection where the PLR picks a router to tunnel to 1246 where that router is loop-free with respect to the failure-point. 1247 Conceptually, the set of candidate routers to provide LFAs expands to 1248 all routers that can be reached via an MRT alternate, attached to the 1249 prefix. 1251 The second is to use a proxy-node, that can be named via MPLS label 1252 or IP address, and pick the appropriate label or IP address to reach 1253 it on either MRT-Blue or MRT-Red as appropriate to avoid the failure 1254 point. A proxy-node can represent a destination prefix that can be 1255 attached to the MRT Island via at least two routers. It is termed a 1256 named proxy-node if there is a way that traffic can be encapsulated 1257 to reach specifically that proxy-node; this could be because there is 1258 an LDP FEC for the associated prefix or because MRT-Red and MRT-Blue 1259 IP addresses are advertised (in an as-yet undefined fashion) for that 1260 proxy-node. Traffic to a named proxy-node may take a different path 1261 than traffic to the attaching router; traffic is also explicitly 1262 forwarded from the attaching router along a predetermined interface 1263 towards the relevant prefixes. 1265 For IP traffic, multi-homed prefixes can use tunnel endpoint 1266 selection. For IP traffic that is destined to a router outside the 1267 MRT Island, if that router is the egress for a FEC advertised into 1268 the MRT Island, then the named proxy-node approach can be used. 1270 For LDP traffic, there is always a FEC advertised into the MRT 1271 Island. The named proxy-node approach should be used, unless the 1272 computing router S knows the label for the FEC at the selected tunnel 1273 endpoint. 1275 If a FEC is advertised from outside the MRT Island into the MRT 1276 Island and the forwarding mechanism specified in the profile includes 1277 LDP, then the routers learning that FEC MUST also advertise labels 1278 for (MRT-Red, FEC) and (MRT-Blue, FEC) to neighbors inside the MRT 1279 Island. Any router receiving a FEC corresponding to a router outside 1280 the MRT Island or to a multi-homed prefix MUST compute and install 1281 the transit MRT-Blue and MRT-Red next-hops for that FEC. The FEC- 1282 label bindings for the topology-scoped FECs ((MT-ID 0, FEC), (MRT- 1283 Red, FEC), and (MRT-Blue, FEC)) MUST also be provided via LDP to 1284 neighbors inside the MRT Island. 1286 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint Selection 1288 Tunnel endpoint selection is a local matter for a router in the MRT 1289 Island since it pertains to selecting and using an alternate and does 1290 not affect the transit MRT-Red and MRT-Blue forwarding topologies. 1292 Let the computing router be S and the next-hop F be the node whose 1293 failure is to be avoided. Let the destination be prefix p. Have A 1294 be the router to which the prefix p is attached for S's shortest path 1295 to p. 1297 The candidates for tunnel endpoint selection are those to which the 1298 destination prefix is attached in the area/level. For a particular 1299 candidate B, it is necessary to determine if B is loop-free to reach 1300 p with respect to S and F for node-protection or at least with 1301 respect to S and the link (S, F) for link-protection. If B will 1302 always prefer to send traffic to p via a different area/level, then 1303 this is definitional. Otherwise, distance-based computations are 1304 necessary and an SPF from B's perspective may be necessary. The 1305 following equations give the checks needed; the rationale is similar 1306 to that given in [RFC5286]. 1308 Loop-Free for S: D_opt(B, p) < D_opt(B, S) + D_opt(S, p) 1310 Loop-Free for F: D_opt(B, p) < D_opt(B, F) + D_opt(F, p) 1312 The latter is equivalent to the following, which avoids the need to 1313 compute the shortest path from F to p. 1315 Loop-Free for F: D_opt(B, p) < D_opt(B, F) + D_opt(S, p) - D_opt(S, 1316 F) 1318 Finally, the rules for Endpoint selection are given below. The basic 1319 idea is to repair to the prefix-advertising router selected for the 1320 shortest-path and only to select and tunnel to a different endpoint 1321 if necessary (e.g. A=F or F is a cut-vertex or the link (S,F) is a 1322 cut-link). 1324 1. Does S have a node-protecting alternate to A? If so, select 1325 that. Tunnel the packet to A along that alternate. For example, 1326 if LDP is the forwarding mechanism, then push the label (MRT-Red, 1327 A) or (MRT-Blue, A) onto the packet. 1329 2. If not, then is there a router B that is loop-free to reach p 1330 while avoiding both F and S? If so, select B as the end-point. 1331 Determine the MRT alternate to reach B while avoiding F. Tunnel 1332 the packet to B along that alternate. For example, with LDP, 1333 push the label (MRT-Red, B) or (MRT-Blue, B) onto the packet. 1335 3. If not, then does S have a link-protecting alternate to A? If 1336 so, select that. 1338 4. If not, then is there a router B that is loop-free to reach p 1339 while avoiding S and the link from S to F? If so, select B as 1340 the endpoint and the MRT alternate for reaching B from S that 1341 avoid the link (S,F). 1343 The tunnel endpoint selected will receive a packet destined to itself 1344 and, being the egress, will pop that MPLS label (or have signaled 1345 Implicit Null) and forward based on what is underneath. This 1346 suffices for IP traffic since the tunnel endpoint can use the IP 1347 header of the original packet to continue forwarding the packet. 1348 However, tunnelling of LDP traffic requires targeted LDP sessions for 1349 learning the FEC-label binding at the tunnel endpoint. 1351 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 1353 Instead, the named proxy-node method works with LDP traffic without 1354 the need for targeted LDP sessions. It also has a clear advantage 1355 over tunnel endpoint selection, in that it is possible to explicitly 1356 forward from the MRT Island along an interface to a loop-free island 1357 neighbor when that interface may not be a primary next-hop. 1359 A named proxy-node represents one or more destinations and, for LDP 1360 forwarding, has a FEC associated with it that is signalled into the 1361 MRT Island. Therefore, it is possible to explicitly label packets to 1362 go to (MRT-Red, FEC) or (MRT-Blue, FEC); at the border of the MRT 1363 Island, the label will swap to meaning (MT-ID 0, FEC). It would be 1364 possible to have named proxy-nodes for IP forwarding, but this would 1365 require extensions to signal two IP addresses to be associated with 1366 MRT-Red and MRT-Blue for the proxy-node. A named proxy-node can be 1367 uniquely represented by the two routers in the MRT Island to which it 1368 is connected. The extensions to signal such IP addresses are not 1369 defined in [I-D.ietf-ospf-mrt]. The details of what label-bindings 1370 must be originated are described in [I-D.ietf-mpls-ldp-mrt]. 1372 Computing the MRT next-hops to a named proxy-node and the MRT 1373 alternate for the computing router S to avoid a particular failure 1374 node F is straightforward. The details of the simple constant-time 1375 functions, Select_Proxy_Node_NHs() and 1376 Select_Alternates_Proxy_Node(), are given in 1377 [I-D.ietf-rtgwg-mrt-frr-algorithm]. A key point is that computing 1378 these MRT next-hops and alternates can be done as new named proxy- 1379 nodes are added or removed without requiring a new MRT computation or 1380 impacting other existing MRT paths. This maps very well to, for 1381 example, how OSPFv2 (see [RFC2328] Section 16.5) does incremental 1382 updates for new summary-LSAs. 1384 The remaining question is how to attach the named proxy-node to the 1385 MRT Island; all the routers in the MRT Island MUST do this 1386 consistently. No more than 2 routers in the MRT Island can be 1387 selected; one should only be selected if there are no others that 1388 meet the necessary criteria. The named proxy-node is logically part 1389 of the area/level. 1391 There are two sources for candidate routers in the MRT Island to 1392 connect to the named proxy-node. The first set are those routers in 1393 the MRT Island that are advertising the prefix; the named-proxy-cost 1394 assigned to each prefix-advertising router is the announced cost to 1395 the prefix. The second set are those routers in the MRT Island that 1396 are connected to routers not in the MRT Island but in the same area/ 1397 level; such routers will be defined as Island Border Routers (IBRs). 1398 The routers connected to the IBRs that are not in the MRT Island and 1399 are in the same area/level as the MRT island are Island 1400 Neighbors(INs). 1402 Since packets sent to the named proxy-node along MRT-Red or MRT-Blue 1403 may come from any router inside the MRT Island, it is necessary that 1404 whatever router to which an IBR forwards the packet be loop-free with 1405 respect to the whole MRT Island for the destination. Thus, an IBR is 1406 a candidate router only if it possesses at least one IN whose 1407 shortest path to the prefix does not enter the MRT Island. A method 1408 for identifying loop-free Island Neighbors(LFINs) is given in 1409 [I-D.ietf-rtgwg-mrt-frr-algorithm]. The named-proxy-cost assigned to 1410 each (IBR, IN) pair is cost(IBR, IN) + D_opt(IN, prefix). 1412 From the set of prefix-advertising routers and the set of IBRs with 1413 at least one LFIN, the two routers with the lowest named-proxy-cost 1414 are selected. Ties are broken based upon the lowest Router ID. For 1415 ease of discussion, the two selected routers will be referred to as 1416 proxy-node attachment routers. 1418 A proxy-node attachment router has a special forwarding role. When a 1419 packet is received destined to (MRT-Red, prefix) or (MRT-Blue, 1420 prefix), if the proxy-node attachment router is an IBR, it MUST swap 1421 to the shortest path forwarding topology (e.g. swap to the label for 1422 (MT-ID 0, prefix) or remove the outer IP encapsulation) and forward 1423 the packet to the IN whose cost was used in the selection. If the 1424 proxy-node attachment router is not an IBR, then the packet MUST be 1425 removed from the MRT forwarding topology and sent along the 1426 interface(s) that caused the router to advertise the prefix; this 1427 interface might be out of the area/level/AS. 1429 11.3. MRT Alternates for Destinations Outside the MRT Island 1431 A natural concern with new functionality is how to have it be useful 1432 when it is not deployed across an entire IGP area. In the case of 1433 MRT FRR, where it provides alternates when appropriate LFAs aren't 1434 available, there are also deployment scenarios where it may make 1435 sense to only enable some routers in an area with MRT FRR. A simple 1436 example of such a scenario would be a ring of 6 or more routers that 1437 is connected via two routers to the rest of the area. 1439 Destinations inside the local island can obviously use MRT 1440 alternates. Destinations outside the local island can be treated 1441 like a multi-homed prefix and either Endpoint Selection or Named 1442 Proxy-Nodes can be used. Named Proxy-Nodes MUST be supported when 1443 LDP forwarding is supported and a label-binding for the destination 1444 is sent to an IBR. 1446 Naturally, there are more complicated options to improve coverage, 1447 such as connecting multiple MRT islands across tunnels, but the need 1448 for the additional complexity has not been justified. 1450 12. Network Convergence and Preparing for the Next Failure 1452 After a failure, MRT detours ensure that packets reach their intended 1453 destination while the IGP has not reconverged onto the new topology. 1454 As link-state updates reach the routers, the IGP process calculates 1455 the new shortest paths. Two things need attention: micro-loop 1456 prevention and MRT re-calculation. 1458 12.1. Micro-forwarding loop prevention and MRTs 1460 As is well known[RFC5715], micro-loops can occur during IGP 1461 convergence; such loops can be local to the failure or remote from 1462 the failure. Managing micro-loops is an orthogonal issue to having 1463 alternates for local repair, such as MRT fast-reroute provides. 1465 There are two possible micro-loop prevention mechanisms discussed in 1466 [RFC5715]. The first is Ordered FIB [RFC6976]. The second is 1467 Farside Tunneling which requires tunnels or an alternate topology to 1468 reach routers on the farside of the failure. 1470 Since MRTs provide an alternate topology through which traffic can be 1471 sent and which can be manipulated separately from the SPT, it is 1472 possible that MRTs could be used to support Farside Tunneling. 1473 Details of how to do so are outside the scope of this document. 1475 Micro-loop mitigation mechanisms can also work when combined with 1476 MRT. 1478 12.2. MRT Recalculation for the Default MRT Profile 1480 This section describes how the MRT recalculation SHOULD be performed 1481 for the Default MRT Profile. This is intended to support FRR 1482 applications. Other approaches are possible, but they are not 1483 specified in this document. 1485 When a failure event happens, traffic is put by the PLRs onto the MRT 1486 topologies. After that, each router recomputes its shortest path 1487 tree (SPT) and moves traffic over to that. Only after all the PLRs 1488 have switched to using their SPTs and traffic has drained from the 1489 MRT topologies should each router install the recomputed MRTs into 1490 the FIBs. 1492 At each router, therefore, the sequence is as follows: 1494 1. Receive failure notification 1496 2. Recompute SPT 1498 3. Install new SPT 1500 4. If the network was stable before the failure occured, wait a 1501 configured (or advertised) period for all routers to be using 1502 their SPTs and traffic to drain from the MRTs. 1504 5. Recompute MRTs 1505 6. Install new MRTs. 1507 While the recomputed MRTs are not installed in the FIB, protection 1508 coverage is lowered. Therefore, it is important to recalculate the 1509 MRTs and install them quickly. 1511 13. Implementation Status 1513 [RFC Editor: please remove this section prior to publication.] 1515 This section records the status of known implementations of the 1516 protocol defined by this specification at the time of posting of this 1517 Internet-Draft, and is based on a proposal described in [RFC6982]. 1518 The description of implementations in this section is intended to 1519 assist the IETF in its decision processes in progressing drafts to 1520 RFCs. Please note that the listing of any individual implementation 1521 here does not imply endorsement by the IETF. Furthermore, no effort 1522 has been spent to verify the information presented here that was 1523 supplied by IETF contributors. This is not intended as, and must not 1524 be construed to be, a catalog of available implementations or their 1525 features. Readers are advised to note that other implementations may 1526 exist. 1528 According to [RFC6982], "this will allow reviewers and working groups 1529 to assign due consideration to documents that have the benefit of 1530 running code, which may serve as evidence of valuable experimentation 1531 and feedback that have made the implemented protocols more mature. 1532 It is up to the individual working groups to use this information as 1533 they see fit". 1535 Juniper Networks Implementation 1537 o Organization responsible for the implementation: Juniper Networks 1539 o Implementation name: MRT-FRR algorithm 1541 o Implementation description: The MRT-FRR algorithm using OSPF as 1542 the IGP has been implemented and verified. 1544 o The implementation's level of maturity: prototype 1546 o Protocol coverage: This implementation of the MRT algorithm 1547 includes Island identification, GADAG root selection, Lowpoint 1548 algorithm, augmentation of GADAG with additional links, and 1549 calculation of MRT transit next-hops alternate next-hops based on 1550 draft "draft-ietf-rtgwg-mrt-frr-algorithm-00". This 1551 implementation also includes the M-bit in OSPF based on "draft- 1552 atlas-ospf-mrt-01" as well as LDP MRT Capability based on "draft- 1553 atlas-mpls-ldp-mrt-00". 1555 o Licensing: proprietary 1557 o Implementation experience: Implementation was useful for verifying 1558 functionality and lack of gaps. It has also been useful for 1559 improving aspects of the algorithm. 1561 o Contact information: akatlas@juniper.net, shraddha@juniper.net, 1562 kishoret@juniper.net 1564 Huawei Technology Implementation 1566 o Organization responsible for the implementation: Huawei Technology 1567 Co., Ltd. 1569 o Implementation name: MRT-FRR algorithm and IS-IS extensions for 1570 MRT. 1572 o Implementation description: The MRT-FRR algorithm, IS-IS 1573 extensions for MRT and LDP multi-topology have been implemented 1574 and verified. 1576 o The implementation's level of maturity: prototype 1578 o Protocol coverage: This implementation of the MRT algorithm 1579 includes Island identification, GADAG root selection, Lowpoint 1580 algorithm, augmentation of GADAG with additional links, and 1581 calculation of MRT transit next-hops alternate next-hops based on 1582 draft "draft-enyedi-rtgwg-mrt-frr-algorithm-03". This 1583 implementation also includes IS-IS extension for MRT based on 1584 "draft-li-mrt-00". 1586 o Licensing: proprietary 1588 o Implementation experience: It is important produce a second 1589 implementation to verify the algorithm is implemented correctly 1590 without looping. It is important to verify the ISIS extensions 1591 work for MRT-FRR. 1593 o Contact information: lizhenbin@huawei.com, eric.wu@huawei.com 1595 14. Operations and Management Considerations 1597 An implementation SHOULD provide an operator with the ability to test 1598 MRT paths with OAM traffic. For example, when MRT paths are realized 1599 using LDP labels distributed for topology-scoped FECs, an 1600 implementation can use the MPLS ping and traceroute as defined in 1601 [RFC4379] and extended in [RFC7307] for topology-scoped FECs. 1603 15. Applying Policy to Select from Multiple Possible Alternates for FRR 1605 For a given topology, GADAG root, and profile, MRT will provide a 1606 node-protecting alternate path from each PLR to each destination for 1607 any single link or node failure, if such a path exists. Therefore, 1608 an implementation may choose to only use the alternates determined by 1609 MRT to provide 100% FRR coverage. 1611 However, it may be desirable to allow an operator to use MRT 1612 alternates together with alternates provided by other FRR 1613 technologies. A policy-based alternate selection process can allow 1614 an operator to select the best alternate from those provided by MRT 1615 and other FRR technologies. As an example, it may be desirable to 1616 implement a policy where a node-protecting LFA (if it exists for a 1617 given failure mode and destination) is preferred over a given MRT 1618 alternate. [I-D.ietf-rtgwg-lfa-manageability] discusses many of the 1619 potential criteria that one might take into account when evaluating 1620 different alternates for selection. 1622 Note that future documents may define MRT profiles in addition to the 1623 default profile defined here. Different MRT profiles will generally 1624 produce alternate paths with different properties. An implementation 1625 may allow an operator to use different MRT profiles instead of or in 1626 addition to the default profile. 1628 16. Acknowledgements 1630 The authors would like to thank Mike Shand for his valuable review 1631 and contributions. 1633 The authors would like to thank Joel Halpern, Hannes Gredler, Ted 1634 Qian, Kishore Tiruveedhula, Shraddha Hegde, Santosh Esale, Nitin 1635 Bahadur, Harish Sitaraman, Raveendra Torvi, Anil Kumar SN, Bruno 1636 Decraene, Eric Wu, and Janos Farkas for their suggestions and review. 1638 17. IANA Considerations 1640 Please create an MRT Profile registry for the MRT Profile TLV. The 1641 range is 0 to 255. The default MRT Profile has value 0. Values 1642 1-200 are by Standards Action. Values 201-220 are for 1643 experimentation. Values 221-255 are for vendor private use. 1645 18. Security Considerations 1647 In general, MRT forwarding paths do not follow shortest paths. The 1648 transit forwarding state corresponding to the MRT paths is created 1649 during normal operations (before a failure occurs). Therefore, a 1650 malicious packet with an appropriate header injected into the network 1651 from a compromised location would be forwarded to a destination along 1652 a non-shortest path. When this technology is deployed, a network 1653 security design should not rely on assumptions about potentially 1654 malicious traffic only following shortest paths. 1656 It should be noted that the creation of non-shortest forwarding paths 1657 is not unique to MRT. 1659 19. Contributors 1661 Robert Kebler 1662 Juniper Networks 1663 10 Technology Park Drive 1664 Westford, MA 01886 1665 USA 1666 Email: rkebler@juniper.net 1668 Andras Csaszar 1669 Ericsson 1670 Konyves Kalman krt 11 1671 Budapest 1097 1672 Hungary 1673 Email: Andras.Csaszar@ericsson.com 1675 Jeff Tantsura 1676 Ericsson 1677 300 Holger Way 1678 San Jose, CA 95134 1679 USA 1680 Email: jeff.tantsura@ericsson.com 1682 Russ White 1683 VCE 1684 Email: russw@riw.us 1686 20. References 1688 20.1. Normative References 1690 [I-D.ietf-rtgwg-mrt-frr-algorithm] 1691 Envedi, G., Csaszar, A., Atlas, A., Bowers, C., and A. 1692 Gopalan, "Algorithms for computing Maximally Redundant 1693 Trees for IP/LDP Fast- Reroute", draft-ietf-rtgwg-mrt-frr- 1694 algorithm-06 (work in progress), October 2015. 1696 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 1697 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 1698 DOI 10.17487/RFC5286, September 2008, 1699 . 1701 20.2. Informative References 1703 [EnyediThesis] 1704 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 1705 Department of Telecommunications and Media Informatics, 1706 Budapest University of Technology and Economics Ph.D. 1707 Thesis, February 2011, 1708 . 1710 [I-D.atlas-rtgwg-mrt-mc-arch] 1711 Atlas, A., Kebler, R., Wijnands, I., Csaszar, A., and G. 1712 Envedi, "An Architecture for Multicast Protection Using 1713 Maximally Redundant Trees", draft-atlas-rtgwg-mrt-mc- 1714 arch-02 (work in progress), July 2013. 1716 [I-D.bryant-ipfrr-tunnels] 1717 Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP 1718 Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03 1719 (work in progress), November 2007. 1721 [I-D.francois-rtgwg-segment-routing-ti-lfa] 1722 Francois, P., Filsfils, C., Bashandy, A., and B. Decraene, 1723 "Topology Independent Fast Reroute using Segment Routing", 1724 draft-francois-rtgwg-segment-routing-ti-lfa-00 (work in 1725 progress), August 2015. 1727 [I-D.ietf-isis-mrt] 1728 Li, Z., Wu, N., <>, Q., Atlas, A., Bowers, C., and J. 1729 Tantsura, "Intermediate System to Intermediate System (IS- 1730 IS) Extensions for Maximally Redundant Trees (MRT)", 1731 draft-ietf-isis-mrt-01 (work in progress), October 2015. 1733 [I-D.ietf-mpls-ldp-mrt] 1734 Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and 1735 I. Wijnands, "LDP Extensions to Support Maximally 1736 Redundant Trees", draft-ietf-mpls-ldp-mrt-02 (work in 1737 progress), September 2015. 1739 [I-D.ietf-ospf-mrt] 1740 Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, 1741 "OSPF Extensions to Support Maximally Redundant Trees", 1742 draft-ietf-ospf-mrt-01 (work in progress), October 2015. 1744 [I-D.ietf-rtgwg-lfa-manageability] 1745 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 1746 Horneffer, M., and P. Sarkar, "Operational management of 1747 Loop Free Alternates", draft-ietf-rtgwg-lfa- 1748 manageability-11 (work in progress), June 2015. 1750 [I-D.ietf-rtgwg-rlfa-node-protection] 1751 Sarkar, P., Hegde, S., Bowers, C., Gredler, H., and S. 1752 Litkowski, "Remote-LFA Node Protection and Manageability", 1753 draft-ietf-rtgwg-rlfa-node-protection-05 (work in 1754 progress), December 2015. 1756 [LFARevisited] 1757 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 1758 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 1759 of IEEE INFOCOM , 2011, 1760 . 1763 [LightweightNotVia] 1764 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 1765 Fast ReRoute: Lightweight Not-Via without Additional 1766 Addresses", Proceedings of IEEE INFOCOM , 2009, 1767 . 1769 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1770 Requirement Levels", BCP 14, RFC 2119, 1771 DOI 10.17487/RFC2119, March 1997, 1772 . 1774 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1775 DOI 10.17487/RFC2328, April 1998, 1776 . 1778 [RFC4379] Kompella, K. and G. Swallow, "Detecting Multi-Protocol 1779 Label Switched (MPLS) Data Plane Failures", RFC 4379, 1780 DOI 10.17487/RFC4379, February 2006, 1781 . 1783 [RFC5331] Aggarwal, R., Rekhter, Y., and E. Rosen, "MPLS Upstream 1784 Label Assignment and Context-Specific Label Space", 1785 RFC 5331, DOI 10.17487/RFC5331, August 2008, 1786 . 1788 [RFC5443] Jork, M., Atlas, A., and L. Fang, "LDP IGP 1789 Synchronization", RFC 5443, DOI 10.17487/RFC5443, March 1790 2009, . 1792 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1793 RFC 5714, DOI 10.17487/RFC5714, January 2010, 1794 . 1796 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 1797 Convergence", RFC 5715, DOI 10.17487/RFC5715, January 1798 2010, . 1800 [RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene, 1801 B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 1802 Alternate (LFA) Applicability in Service Provider (SP) 1803 Networks", RFC 6571, DOI 10.17487/RFC6571, June 2012, 1804 . 1806 [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., 1807 Francois, P., and O. Bonaventure, "Framework for Loop-Free 1808 Convergence Using the Ordered Forwarding Information Base 1809 (oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July 1810 2013, . 1812 [RFC6981] Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 1813 and MPLS Fast Reroute Using Not-Via Addresses", RFC 6981, 1814 DOI 10.17487/RFC6981, August 2013, 1815 . 1817 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 1818 Code: The Implementation Status Section", RFC 6982, 1819 DOI 10.17487/RFC6982, July 2013, 1820 . 1822 [RFC6987] Retana, A., Nguyen, L., Zinin, A., White, R., and D. 1823 McPherson, "OSPF Stub Router Advertisement", RFC 6987, 1824 DOI 10.17487/RFC6987, September 2013, 1825 . 1827 [RFC7307] Zhao, Q., Raza, K., Zhou, C., Fang, L., Li, L., and D. 1828 King, "LDP Extensions for Multi-Topology", RFC 7307, 1829 DOI 10.17487/RFC7307, July 2014, 1830 . 1832 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 1833 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 1834 RFC 7490, DOI 10.17487/RFC7490, April 2015, 1835 . 1837 Appendix A. General Issues with Area Abstraction 1839 When a multi-homed prefix is connected in two different areas, it may 1840 be impractical to protect them without adding the complexity of 1841 explicit tunneling. This is also a problem for LFA and Remote-LFA. 1843 50 1844 |----[ASBR Y]---[B]---[ABR 2]---[C] Backbone Area 0: 1845 | | ABR 1, ABR 2, C, D 1846 | | 1847 | | Area 20: A, ASBR X 1848 | | 1849 p ---[ASBR X]---[A]---[ABR 1]---[D] Area 10: B, ASBR Y 1850 5 p is a Type 1 AS-external 1852 Figure 4: AS external prefixes in different areas 1854 Consider the network in Figure 4 and assume there is a richer 1855 connective topology that isn't shown, where the same prefix is 1856 announced by ASBR X and ASBR Y which are in different non-backbone 1857 areas. If the link from A to ASBR X fails, then an MRT alternate 1858 could forward the packet to ABR 1 and ABR 1 could forward it to D, 1859 but then D would find the shortest route is back via ABR 1 to Area 1860 20. This problem occurs because the routers, including the ABR, in 1861 one area are not yet aware of the failure in a different area. 1863 The only way to get it from A to ASBR Y is to explicitly tunnel it to 1864 ASBR Y. If the traffic is unlabeled or the appropriate MPLS labels 1865 are known, then explicit tunneling MAY be used as long as the 1866 shortest-path of the tunnel avoids the failure point. In that case, 1867 A must determine that it should use an explicit tunnel instead of an 1868 MRT alternate. 1870 Authors' Addresses 1872 Alia Atlas 1873 Juniper Networks 1874 10 Technology Park Drive 1875 Westford, MA 01886 1876 USA 1878 Email: akatlas@juniper.net 1879 Chris Bowers 1880 Juniper Networks 1881 1194 N. Mathilda Ave. 1882 Sunnyvale, CA 94089 1883 USA 1885 Email: cbowers@juniper.net 1887 Gabor Sandor Enyedi 1888 Ericsson 1889 Konyves Kalman krt 11. 1890 Budapest 1097 1891 Hungary 1893 Email: Gabor.Sandor.Enyedi@ericsson.com