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