idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-architecture-07.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. == There are 5 instances of lines with non-RFC2606-compliant FQDNs in the document. 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 (October 15, 2015) is 3117 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 437, but not defined == Missing Reference: 'F' is mentioned on line 437, but not defined == Missing Reference: 'C' is mentioned on line 437, but not defined == Missing Reference: 'I' is mentioned on line 435, but not defined == Missing Reference: 'G' is mentioned on line 437, but not defined == Missing Reference: 'J' is mentioned on line 439, but not defined == Missing Reference: 'RFC 5331' is mentioned on line 598, but not defined == Missing Reference: 'A' is mentioned on line 1186, but not defined == Missing Reference: 'ABR1' is mentioned on line 1196, but not defined == Missing Reference: 'H' is mentioned on line 1196, but not defined == Unused Reference: 'RFC2328' is defined on line 1792, but no explicit reference was found in the text == Outdated reference: A later version (-09) exists of draft-ietf-rtgwg-mrt-frr-algorithm-05 ** Downref: Normative reference to an Informational RFC: RFC 5714 == Outdated reference: A later version (-02) exists of draft-francois-spring-segment-routing-ti-lfa-01 == Outdated reference: A later version (-03) exists of draft-ietf-isis-mrt-00 == Outdated reference: A later version (-07) exists of draft-ietf-mpls-ldp-mrt-00 == Outdated reference: A later version (-03) exists of draft-ietf-ospf-mrt-00 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-rlfa-node-protection-02 -- 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 (~~), 20 warnings (==), 3 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: April 17, 2016 Juniper Networks 6 G. Enyedi 7 A. Csaszar 8 J. Tantsura 9 Ericsson 10 R. White 11 VCE 12 October 15, 2015 14 An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees 15 draft-ietf-rtgwg-mrt-frr-architecture-07 17 Abstract 19 With increasing deployment of Loop-Free Alternates (LFA) [RFC5286], 20 it is clear that a complete solution for IP and LDP Fast-Reroute is 21 required. This specification provides that solution. IP/LDP Fast- 22 Reroute with Maximally Redundant Trees (MRT-FRR) is a technology that 23 gives link-protection and node-protection with 100% coverage in any 24 network topology that is still connected after the failure. 26 MRT removes all need to engineer for coverage. MRT is also extremely 27 computationally efficient. For any router in the network, the MRT 28 computation is less than the LFA computation for a node with three or 29 more neighbors. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on April 17, 2016. 48 Copyright Notice 50 Copyright (c) 2015 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1. Importance of 100% Coverage . . . . . . . . . . . . . . . 5 67 1.2. Partial Deployment and Backwards Compatibility . . . . . 6 68 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 6 69 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 70 4. Maximally Redundant Trees (MRT) . . . . . . . . . . . . . . . 8 71 5. Maximally Redundant Trees (MRT) and Fast-Reroute . . . . . . 10 72 6. Unicast Forwarding with MRT Fast-Reroute . . . . . . . . . . 11 73 6.1. MRT Forwarding Mechanisms . . . . . . . . . . . . . . . . 12 74 6.1.1. MRT LDP labels . . . . . . . . . . . . . . . . . . . 12 75 6.1.1.1. Topology-scoped FEC encoded using a single label 76 (Option 1A) . . . . . . . . . . . . . . . . . . . 12 77 6.1.1.2. Topology and FEC encoded using a two label stack 78 (Option 1B) . . . . . . . . . . . . . . . . . . . 13 79 6.1.1.3. Compatibility of Option 1A and 1B . . . . . . . . 13 80 6.1.1.4. Mandatory support for MRT LDP Label option 1A . . 14 81 6.1.2. MRT IP tunnels (Options 2A and 2B) . . . . . . . . . 14 82 6.2. Forwarding LDP Unicast Traffic over MRT Paths . . . . . . 14 83 6.2.1. Forwarding LDP traffic using MRT LDP Labels (Option 84 1A) . . . . . . . . . . . . . . . . . . . . . . . . . 15 85 6.2.2. Forwarding LDP traffic using MRT LDP Labels (Option 86 1B) . . . . . . . . . . . . . . . . . . . . . . . . . 15 87 6.2.3. Other considerations for forwarding LDP traffic using 88 MRT LDP Labels . . . . . . . . . . . . . . . . . . . 15 89 6.3. Forwarding IP Unicast Traffic over MRT Paths . . . . . . 16 90 6.3.1. Tunneling IP traffic using MRT LDP Labels . . . . . . 16 91 6.3.1.1. Tunneling IP traffic using MRT LDP Labels (Option 92 1A) . . . . . . . . . . . . . . . . . . . . . . . 16 93 6.3.1.2. Tunneling IP traffic using MRT LDP Labels (Option 94 1B) . . . . . . . . . . . . . . . . . . . . . . . 17 95 6.3.2. Tunneling IP traffic using MRT IP Tunnels . . . . . . 17 96 6.3.3. Required support . . . . . . . . . . . . . . . . . . 17 97 7. MRT Island Formation . . . . . . . . . . . . . . . . . . . . 17 98 7.1. IGP Area or Level . . . . . . . . . . . . . . . . . . . . 18 99 7.2. Support for a specific MRT profile . . . . . . . . . . . 18 100 7.3. Excluding additional routers and interfaces from the MRT 101 Island . . . . . . . . . . . . . . . . . . . . . . . . . 18 102 7.3.1. Existing IGP exclusion mechanisms . . . . . . . . . . 18 103 7.3.2. MRT-specific exclusion mechanism . . . . . . . . . . 19 104 7.4. Connectivity . . . . . . . . . . . . . . . . . . . . . . 19 105 7.5. Example algorithm . . . . . . . . . . . . . . . . . . . . 19 106 8. MRT Profile . . . . . . . . . . . . . . . . . . . . . . . . . 19 107 8.1. MRT Profile Options . . . . . . . . . . . . . . . . . . . 20 108 8.2. Router-specific MRT paramaters . . . . . . . . . . . . . 21 109 8.3. Default MRT profile . . . . . . . . . . . . . . . . . . . 21 110 9. LDP signaling extensions and considerations . . . . . . . . . 22 111 10. Inter-area Forwarding Behavior . . . . . . . . . . . . . . . 23 112 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A . . 23 113 10.1.1. Motivation for Creating the Rainbow-FEC . . . . . . 24 114 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) . . 24 115 10.3. ABR Forwarding Behavior with LDP Label option 1B . . . . 25 116 11. Prefixes Multiply Attached to the MRT Island . . . . . . . . 26 117 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint 118 Selection . . . . . . . . . . . . . . . . . . . . . . . 28 119 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 29 120 11.2.1. Computing if an Island Neighbor (IN) is loop-free . 31 121 11.3. MRT Alternates for Destinations Outside the MRT Island . 33 122 12. Network Convergence and Preparing for the Next Failure . . . 34 123 12.1. Micro-forwarding loop prevention and MRTs . . . . . . . 34 124 12.2. MRT Recalculation . . . . . . . . . . . . . . . . . . . 34 125 13. Implementation Status . . . . . . . . . . . . . . . . . . . . 35 126 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 37 127 15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37 128 16. Security Considerations . . . . . . . . . . . . . . . . . . . 37 129 17. References . . . . . . . . . . . . . . . . . . . . . . . . . 37 130 17.1. Normative References . . . . . . . . . . . . . . . . . . 37 131 17.2. Informative References . . . . . . . . . . . . . . . . . 37 132 Appendix A. General Issues with Area Abstraction . . . . . . . . 40 133 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 41 135 1. Introduction 137 This document gives a complete solution for IP/LDP fast-reroute 138 [RFC5714]. MRT-FRR creates two alternate trees separate from the 139 primary next-hop forwarding used during stable operation. These two 140 trees are maximally diverse from each other, providing link and node 141 protection for 100% of paths and failures as long as the failure does 142 not cut the network into multiple pieces. This document defines the 143 architecture for IP/LDP fast-reroute with MRT. The associated 144 protocol extensions are defined in [I-D.ietf-ospf-mrt] and 145 [I-D.ietf-mpls-ldp-mrt]. The exact MRT algorithm is defined in 146 [I-D.ietf-rtgwg-mrt-frr-algorithm]. 148 IP/LDP Fast-Reroute with MRT (MRT-FRR) uses two maximally diverse 149 forwarding topologies to provide alternates. A primary next-hop 150 should be on only one of the diverse forwarding topologies; thus, the 151 other can be used to provide an alternate. Once traffic has been 152 moved to one of MRTs, it is not subject to further repair actions. 153 Thus, the traffic will not loop even if a worse failure (e.g. node) 154 occurs when protection was only available for a simpler failure (e.g. 155 link). 157 In addition to supporting IP and LDP unicast fast-reroute, the 158 diverse forwarding topologies and guarantee of 100% coverage permit 159 fast-reroute technology to be applied to multicast traffic as 160 described in [I-D.atlas-rtgwg-mrt-mc-arch]. 162 Other existing or proposed solutions are partial solutions or have 163 significant issues, as described below. 165 Summary Comparison of IP/LDP FRR Methods 167 +---------+-------------+-------------+-----------------------------+ 168 | Method | Coverage | Alternate | Computation (in SPFs) | 169 | | | Looping? | | 170 +---------+-------------+-------------+-----------------------------+ 171 | MRT-FRR | 100% | None | less than 3 | 172 | | Link/Node | | | 173 | | | | | 174 | LFA | Partial | Possible | per neighbor | 175 | | Link/Node | | | 176 | | | | | 177 | Remote | Partial | Possible | per neighbor (link) or | 178 | LFA | Link/Node | | neighbor's neighbor (node) | 179 | | | | | 180 | Not-Via | 100% | None | per link and node | 181 | | Link/Node | | | 182 | | | | | 183 | TI-LFA | 100% | Possible | per neighbor (link) or | 184 | | Link/Node | | neighbor's neighbor (node) | 185 +---------+-------------+-------------+-----------------------------+ 187 Table 1 189 Loop-Free Alternates (LFA): LFAs [RFC5286] provide limited 190 topology-dependent coverage for link and node protection. 191 Restrictions on choice of alternates can be relaxed to improve 192 coverage, but this can cause forwarding loops if a worse failure 193 is experienced than protected against. Augmenting a network to 194 provide better coverage is NP-hard [LFARevisited]. [RFC6571] 195 discusses the applicability of LFA to different topologies with a 196 focus on common PoP architectures. 198 Remote LFA: Remote LFAs [RFC7490] improve coverage over LFAs for 199 link protection but still cannot guarantee complete coverage. The 200 trade-off of looping traffic to improve coverage is still made. 201 Remote LFAs can provide node-protection 202 [I-D.ietf-rtgwg-rlfa-node-protection] but not guaranteed coverage 203 and the computation required is quite high (an SPF for each PQ- 204 node evaluated). [I-D.bryant-ipfrr-tunnels] describes additional 205 mechanisms to further improve coverage, at the cost of added 206 complexity. 208 Not-Via: Not-Via [I-D.ietf-rtgwg-ipfrr-notvia-addresses] is the 209 only other solution that provides 100% coverage for link and node 210 failures and does not have potential looping. However, the 211 computation is very high (an SPF per failure point) and academic 212 implementations [LightweightNotVia] have found the address 213 management complexity to be high. 215 TI-LFA: Topology Independent Loop-free Alternate Fast Re-route (TI- 216 LFA) [I-D.francois-spring-segment-routing-ti-lfa] aims to provide 217 link and node protection of node and adjacency segments within the 218 Segment Routing (SR) framework. It guarantees complete coverage. 219 The TI-LFA computation for link-protection is fairly 220 straightforward, while the computation for node-protection is more 221 complex. For link-protection with symmetric link costs, TI-LFA 222 can provide complete coverage by pushing up to two additional 223 labels. For node protection on arbitrary topologies, the label 224 stack size can grow significantly based on repair path. Note that 225 TI-LFA requires shortest path forwarding based on SR Node-SIDs, as 226 opposed to LDP labels, in order to construct label stacks for 227 backups paths without relying on a large number of targeted LDP 228 sessions to learn remote FEC-label bindings. It also requires the 229 use of Adj-SIDs to achieve 100% coverage. 231 1.1. Importance of 100% Coverage 233 Fast-reroute is based upon the single failure assumption - that the 234 time between single failures is long enough for a network to 235 reconverge and start forwarding on the new shortest paths. That does 236 not imply that the network will only experience one failure or 237 change. 239 It is straightforward to analyze a particular network topology for 240 coverage. However, a real network does not always have the same 241 topology. For instance, maintenance events will take links or nodes 242 out of use. Simply costing out a link can have a significant effect 243 on what LFAs are available. Similarly, after a single failure has 244 happened, the topology is changed and its associated coverage. 245 Finally, many networks have new routers or links added and removed; 246 each of those changes can have an effect on the coverage for 247 topology-sensitive methods such as LFA and Remote LFA. If fast- 248 reroute is important for the network services provided, then a method 249 that guarantees 100% coverage is important to accomodate natural 250 network topology changes. 252 Asymmetric link costs are also a common aspect of networks. There 253 are at least three common causes for them. First, any broadcast 254 interface is represented by a pseudo-node and has asymmetric link 255 costs to and from that pseudo-node. Second, when routers come up or 256 a link with LDP comes up, it is recommended in [RFC5443] and 257 [RFC3137] that the link metric be raised to the maximum cost; this 258 may not be symmetric and for [RFC3137] is not expected to be. Third, 259 techniques such as IGP metric tuning for traffic-engineering can 260 result in asymmetric link costs. A fast-reroute solution needs to 261 handle network topologies with asymmetric link costs. 263 When a network needs to use a micro-loop prevention mechanism 264 [RFC5715] such as Ordered FIB[I-D.ietf-rtgwg-ordered-fib] or Farside 265 Tunneling[RFC5715], then the whole IGP area needs to have alternates 266 available so that the micro-loop prevention mechanism, which requires 267 slower network convergence, can take the necessary time without 268 adversely impacting traffic. Without complete coverage, traffic to 269 the unprotected destinations will be dropped for significantly longer 270 than with current convergence - where routers individually converge 271 as fast as possible. 273 1.2. Partial Deployment and Backwards Compatibility 275 MRT-FRR supports partial deployment. As with many new features, the 276 protocols (OSPF, LDP, ISIS) indicate their capability to support MRT. 277 Inside the MRT-capable connected group of routers (referred to as an 278 MRT Island), the MRTs are computed. Alternates to destinations 279 outside the MRT Island are computed and depend upon the existence of 280 a loop-free neighbor of the MRT Island for that destination. 282 2. Requirements Language 284 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 285 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 286 document are to be interpreted as described in [RFC2119] 288 3. Terminology 290 network graph: A graph that reflects the network topology where all 291 links connect exactly two nodes and broadcast links have been 292 transformed into the standard pseudo-node representation. 294 Redundant Trees (RT): A pair of trees where the path from any node 295 X to the root R along the first tree is node-disjoint with the 296 path from the same node X to the root along the second tree. 297 These can be computed in 2-connected graphs. 299 Maximally Redundant Trees (MRT): A pair of trees where the path 300 from any node X to the root R along the first tree and the path 301 from the same node X to the root along the second tree share the 302 minimum number of nodes and the minimum number of links. Each 303 such shared node is a cut-vertex. Any shared links are cut-links. 304 Any RT is an MRT but many MRTs are not RTs. 306 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 307 used to described the associated forwarding topology and MPLS MT- 308 ID. Specifically, MRT-Red is the decreasing MRT where links in 309 the GADAG are taken in the direction from a higher topologically 310 ordered node to a lower one. 312 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 313 used to described the associated forwarding topology and MPLS MT- 314 ID. Specifically, MRT-Blue is the increasing MRT where links in 315 the GADAG are taken in the direction from a lower topologically 316 ordered node to a higher one. 318 Rainbow MRT: It is useful to have an MPLS MT-ID that refers to the 319 multiple MRT topologies and to the default topology. This is 320 referred to as the Rainbow MRT MPLS MT-ID and is used by LDP to 321 reduce signalling and permit the same label to always be 322 advertised to all peers for the same (MT-ID, Prefix). 324 MRT Island: The set of routers that support a particular MRT 325 profile and the links connecting them that support MRT. 327 Island Border Router (IBR): A router in the MRT Island that is 328 connected to a router not in the MRT Island and both routers are 329 in a common area or level. 331 Island Neighbor (IN): A router that is not in the MRT Island but is 332 adjacent to an IBR and in the same area/level as the IBR. 334 cut-link: A link whose removal partitions the network. A cut-link 335 by definition must be connected between two cut-vertices. If 336 there are multiple parallel links, then they are referred to as 337 cut-links in this document if removing the set of parallel links 338 would partition the network graph. 340 cut-vertex: A vertex whose removal partitions the network graph. 342 2-connected: A graph that has no cut-vertices. This is a graph 343 that requires two nodes to be removed before the network is 344 partitioned. 346 2-connected cluster: A maximal set of nodes that are 2-connected. 348 2-edge-connected: A network graph where at least two links must be 349 removed to partition the network. 351 block: Either a 2-connected cluster, a cut-edge, or an isolated 352 vertex. 354 DAG: Directed Acyclic Graph - a graph where all links are directed 355 and there are no cycles in it. 357 ADAG: Almost Directed Acyclic Graph - a graph that, if all links 358 incoming to the root were removed, would be a DAG. 360 GADAG: Generalized ADAG - a graph that is the combination of the 361 ADAGs of all blocks. 363 named proxy-node: A proxy-node can represent a destination prefix 364 that can be attached to the MRT Island via at least two routers. 365 It is named if there is a way that traffic can be encapsulated to 366 reach specifically that proxy node; this could be because there is 367 an LDP FEC for the associated prefix or because MRT-Red and MRT- 368 Blue IP addresses are advertised in an undefined fashion for that 369 proxy-node. 371 4. Maximally Redundant Trees (MRT) 373 A pair of Maximally Redundant Trees is a pair of directed spanning 374 trees that provides maximally disjoint paths towards their common 375 root. Only links or nodes whose failure would partition the network 376 (i.e. cut-links and cut-vertices) are shared between the trees. The 377 algorithm to compute MRTs is given in 378 [I-D.ietf-rtgwg-mrt-frr-algorithm]. This algorithm can be computed 379 in O(e + n log n); it is less than three SPFs. Modeling results 380 comparing the alternate path lengths obtained with MRT to other 381 approaches are described in [I-D.ietf-rtgwg-mrt-frr-algorithm]. This 382 document describes how the MRTs can be used and not how to compute 383 them. 385 MRT provides destination-based trees for each destination. Each 386 router stores its normal primary next-hop(s) as well as MRT-Blue 387 next-hop(s) and MRT-Red next-hop(s) toward each destination. The 388 alternate will be selected between the MRT-Blue and MRT-Red. 390 The most important thing to understand about MRTs is that for each 391 pair of destination-routed MRTs, there is a path from every node X to 392 the destination D on the Blue MRT that is as disjoint as possible 393 from the path on the Red MRT. 395 For example, in Figure 1, there is a network graph that is 396 2-connected in (a) and associated MRTs in (b) and (c). One can 397 consider the paths from B to R; on the Blue MRT, the paths are 398 B->F->D->E->R or B->C->D->E->R. On the Red MRT, the path is B->A->R. 399 These are clearly link and node-disjoint. These MRTs are redundant 400 trees because the paths are disjoint. 402 [E]---[D]---| [E]<--[D]<--| [E]-->[D]---| 403 | | | | ^ | | | 404 | | | V | | V V 405 [R] [F] [C] [R] [F] [C] [R] [F] [C] 406 | | | ^ ^ ^ | | 407 | | | | | | V | 408 [A]---[B]---| [A]-->[B]---| [A]<--[B]<--| 410 (a) (b) (c) 411 a 2-connected graph Blue MRT towards R Red MRT towards R 413 Figure 1: A 2-connected Network 415 By contrast, in Figure 2, the network in (a) is not 2-connected. If 416 F, G or the link F<->G failed, then the network would be partitioned. 417 It is clearly impossible to have two link-disjoint or node-disjoint 418 paths from G, I or J to R. The MRTs given in (b) and (c) offer paths 419 that are as disjoint as possible. For instance, the paths from B to 420 R are the same as in Figure 1 and the path from G to R on the Blue 421 MRT is G->F->D->E->R and on the Red MRT is G->F->B->A->R. 423 [E]---[D]---| 424 | | | |----[I] 425 | | | | | 426 [R]---[C] [F]---[G] | 427 | | | | | 428 | | | |----[J] 429 [A]---[B]---| 431 (a) 432 a non-2-connected graph 434 [E]<--[D]<--| [E]-->[D] 435 | ^ | [I] | |----[I] 436 V | | | V V ^ 437 [R] [C] [F]<--[G] | [R]<--[C] [F]<--[G] | 438 ^ ^ ^ V ^ | | 439 | | |----[J] | | [J] 440 [A]-->[B]---| [A]<--[B]<--| 442 (b) (c) 443 Blue MRT towards R Red MRT towards R 445 Figure 2: A non-2-connected network 447 5. Maximally Redundant Trees (MRT) and Fast-Reroute 449 In normal IGP routing, each router has its shortest-path-tree to all 450 destinations. From the perspective of a particular destination, D, 451 this looks like a reverse SPT (rSPT). To use maximally redundant 452 trees, in addition, each destination D has two MRTs associated with 453 it; by convention these will be called the MRT-Blue and MRT-Red. 454 MRT-FRR is realized by using multi-topology forwarding. There is a 455 MRT-Blue forwarding topology and a MRT-Red forwarding topology. 457 Any IP/LDP fast-reroute technique beyond LFA requires an additional 458 dataplane procedure, such as an additional forwarding mechanism. The 459 well-known options are multi-topology forwarding (used by MRT-FRR), 460 tunneling (e.g. [I-D.ietf-rtgwg-ipfrr-notvia-addresses] or 461 [RFC7490]), and per-interface forwarding (e.g. Loop-Free Failure 462 Insensitive Routing in [EnyediThesis]). 464 When there is a link or node failure affecting, but not partitioning, 465 the network, each node will still have at least one path via one of 466 the MRTs to reach the destination D. For example, in Figure 2, C 467 would normally forward traffic to R across the C<->R link. If that 468 C<->R link fails, then C could use the Blue MRT path C->D->E->R. 470 As is always the case with fast-reroute technologies, forwarding does 471 not change until a local failure is detected. Packets are forwarded 472 along the shortest path. The appropriate alternate to use is pre- 473 computed. [I-D.ietf-rtgwg-mrt-frr-algorithm] describes exactly how 474 to determine whether the MRT-Blue next-hops or the MRT-Red next-hops 475 should be the MRT alternate next-hops for a particular primary next- 476 hop to a particular destination. 478 MRT alternates are always available to use. It is a local decision 479 whether to use an MRT alternate, a Loop-Free Alternate or some other 480 type of alternate. 482 As described in [RFC5286], when a worse failure than is anticipated 483 happens, using LFAs that are not downstream neighbors can cause 484 micro-looping. Section 1.1 of [RFC5286] gives an example of link- 485 protecting alternates causing a loop on node failure. Even if a 486 worse failure than anticipated happens, the use of MRT alternates 487 will not cause looping. Therefore, while node-protecting LFAs may be 488 preferred, the certainty that no alternate-induced looping will occur 489 is an advantage of using MRT alternates when the available node- 490 protecting LFA is not a downstream path. 492 6. Unicast Forwarding with MRT Fast-Reroute 494 As mentioned before, MRT FRR needs multi-topology forwarding. 495 Unfortunately, neither IP nor LDP provides extra bits for a packet to 496 indicate its topology. Once the MRTs are computed, the two sets of 497 MRTs can be used as two additional forwarding topologies. The same 498 considerations apply for forwarding along the MRTs as for handling 499 multiple topologies. 501 There are three possible types of routers involved in forwarding a 502 packet along an MRT path. At the MRT ingress router, the packet 503 leaves the shortest path to the destination and follows an MRT path 504 to the destination. In a FRR application, the MRT ingress router is 505 the PLR. An MRT transit router takes a packet that arrives already 506 associated with the particular MRT, and forwards it on that same MRT. 507 In some situations (to be discussed later), the packet will need to 508 leave the MRT path and return to the shortest path. This takes place 509 at the MRT egress router. The MRT ingress and egress functionality 510 may depend on the underlying type of packet being forwarded (LDP or 511 IP). The MRT transit functionality is independent of the type of 512 packet being forwarded. We first consider several MRT transit 513 forwarding mechanisms. Then we look at how these forwarding 514 mechanisms can be applied to carrying LDP and IP traffic. 516 6.1. MRT Forwarding Mechanisms 518 The following options for MRT forwarding mechanisms are considered. 520 1. MRT LDP Labels 522 A. Topology-scoped FEC encoded using a single label 524 B. Topology and FEC encoded using a two label stack 526 2. MRT IP Tunnels 528 A. MRT IPv4 Tunnels 530 B. MRT IPv6 Tunnels 532 6.1.1. MRT LDP labels 534 We consider two options for the MRT forwarding mechanisms using MRT 535 LDP labels. 537 6.1.1.1. Topology-scoped FEC encoded using a single label (Option 1A) 539 [RFC7307] provides a mechanism to distribute FEC-Label bindings 540 scoped to a given MPLS topology (represented by MPLS MT-ID). To use 541 multi-topology LDP to create MRT forwarding topologies, we associate 542 two MPLS MT-IDs with the MRT-Red and MRT-Blue forwarding topologies, 543 in addition to the default shortest path forwarding topology with MT- 544 ID=0. 546 With this forwarding mechanism, a single label is distributed for 547 each topology-scoped FEC. For a given FEC in the default topology 548 (call it default-FEC-A), two additional topology-scoped FECs would be 549 created, corresponding to the Red and Blue MRT forwarding topologies 550 (call them red-FEC-A and blue-FEC-A). A router supporting this MRT 551 transit forwarding mechanism advertises a different FEC-label binding 552 for each of the three topology-scoped FECs. When a packet is 553 received with a label corresponding to red-FEC-A (for example), an 554 MRT transit router will determine the next-hop for the MRT-Red 555 forwarding topology for that FEC, swap the incoming label with the 556 outgoing label corresponding to red-FEC-A learned from the MRT-Red 557 next-hop router, and forward the packet. 559 This forwarding mechanism has the useful property that the FEC 560 associated with the packet is maintained in the labels at each hop 561 along the MRT. We will take advantage of this property when 562 specifying how to carry LDP traffic on MRT paths using multi-topology 563 LDP labels. 565 This approach is very simple for hardware to support. However, it 566 reduces the label space for other uses, and it increases the memory 567 needed to store the labels and the communication required by LDP to 568 distribute FEC-label bindings. 570 This forwarding option uses the LDP signaling extensions described in 571 [RFC7307]. The MRT-specific LDP extensions required to support this 572 option are described in [I-D.ietf-mpls-ldp-mrt]. 574 6.1.1.2. Topology and FEC encoded using a two label stack (Option 1B) 576 With this forwarding mechanism, a two label stack is used to encode 577 the topology and the FEC of the packet. The top label (topology-id 578 label) identifies the MRT forwarding topology, while the second label 579 (FEC label) identifies the FEC. The top label would be a new FEC 580 type with two values corresponding to MRT Red and Blue topologies. 582 When an MRT transit router receives a packet with a topology-id 583 label, the router pops the top label and uses that it to guide the 584 next-hop selection in combination with the next label in the stack 585 (the FEC label). The router then swaps the FEC label, using the FEC- 586 label bindings learned through normal LDP mechanisms. The router 587 then pushes the topology-id label for the next-hop. 589 As with Option 1A, this forwarding mechanism also has the useful 590 property that the FEC associated with the packet is maintained in the 591 labels at each hop along the MRT. 593 This forwarding mechanism has minimal usage of additional labels, 594 memory and LDP communication. It does increase the size of packets 595 and the complexity of the required label operations and look-ups. 597 This forwarding option is consistent with context-specific label 598 spaces, as described in [RFC 5331]. However, the precise LDP 599 behavior required to support this option for MRT has not been 600 specified. 602 6.1.1.3. Compatibility of Option 1A and 1B 604 In principle, MRT transit forwarding mechanisms 1A and 1B can coexist 605 in the same network, with a packet being forwarding along a single 606 MRT path using the single label of option 1A for some hops and the 607 two label stack of option 1B for other hops. 609 6.1.1.4. Mandatory support for MRT LDP Label option 1A 611 If a router supports a profile that includes the MRT LDP Label option 612 for MRT transit forwarding mechanism, then it MUST support option 1A, 613 which encodes topology-scoped FECs using a single label. 615 6.1.2. MRT IP tunnels (Options 2A and 2B) 617 IP tunneling can also be used as an MRT transit forwarding mechanism. 618 Each router supporting this MRT transit forwarding mechanism 619 announces two additional loopback addresses and their associated MRT 620 color. Those addresses are used as destination addresses for MRT- 621 blue and MRT-red IP tunnels respectively. The special loopback 622 addresses allow the transit nodes to identify the traffic as being 623 forwarded along either the MRT-blue or MRT-red topology to reach the 624 tunnel destination. Announcements of these two additional loopback 625 addresses per router with their MRT color requires IGP extensions, 626 which have not been defined. 628 Either IPv4 (option 2A) or IPv6 (option 2B) can be used as the 629 tunneling mechanism. 631 Note that the two forwarding mechanisms using LDP Label options do 632 not require additional loopbacks per router, as is required by the IP 633 tunneling mechanism. This is because LDP labels are used on a hop- 634 by-hop basis to identify MRT-blue and MRT-red forwarding topologies. 636 6.2. Forwarding LDP Unicast Traffic over MRT Paths 638 In the previous section, we examined several options for providing 639 MRT transit forwarding functionality, which is independent of the 640 type of traffic being carried. We now look at the MRT ingress 641 functionality, which will depend on the type of traffic being carried 642 (IP or LDP). We start by considering LDP traffic. 644 We also simplify the initial discussion by assuming that the network 645 consists of a single IGP area, and that all routers in the network 646 participate in MRT. Other deployment scenarios that require MRT 647 egress functionality are considered later in this document. 649 In principle, it is possible to carry LDP traffic in MRT IP tunnels. 650 However, for LDP traffic, it is very desirable to avoid tunneling. 651 Tunneling LDP traffic to a remote node requires knowledge of remote 652 FEC-label bindings so that the LDP traffic can continue to be 653 forwarded properly when it leaves the tunnel. This requires targeted 654 LDP sessions which can add management complexity. The two MRT LDP 655 Label forwarding mechanisms have the useful property that the FEC 656 associated with the packet is maintained in the labels at each hop 657 along the MRT, as long as an MRT to the originator of the FEC is 658 used. The MRT IP tunneling mechanism does not have this useful 659 property. Therefore, this document only considers the two MRT LDP 660 Label forwarding mechanisms for protecting LDP traffic with MRT fast- 661 reroute. 663 6.2.1. Forwarding LDP traffic using MRT LDP Labels (Option 1A) 665 The MRT LDP Label option 1A forwarding mechanism uses topology-scoped 666 FECs encoded using a single label as described in section 667 Section 6.1.1.1. When a PLR receives an LDP packet that needs to be 668 forwarded on the Red MRT (for example), it does a label swap 669 operation, replacing the usual LDP label for the FEC with the Red MRT 670 label for that FEC received from the next-hop router in the Red MRT 671 computed by the PLR. When the next-hop router in the Red MRT 672 receives the packet with the Red MRT label for the FEC, the MRT 673 transit forwarding functionality continues as described in 674 Section 6.1.1.1. In this way the original FEC associated with the 675 packet is maintained at each hop along the MRT. 677 6.2.2. Forwarding LDP traffic using MRT LDP Labels (Option 1B) 679 The MRT LDP Label option 1B forwarding mechanism encodes the topology 680 and the FEC using a two label stack as described in Section 6.1.1.2. 681 When a PLR receives an LDP packet that needs to be forwarded on the 682 Red MRT, it first does a normal LDP label swap operation, replacing 683 the incoming normal LDP label associated with a given FEC with the 684 outgoing normal LDP label for that FEC learned from the next-hop on 685 the Red MRT. In addition, the PLR pushes the topology-identification 686 label associated with the Red MRT, and forward the packet to the 687 appropriate next-hop on the Red MRT. When the next-hop router in the 688 Red MRT receives the packet with the Red MRT label for the FEC, the 689 MRT transit forwarding functionality continues as described in 690 Section 6.1.1.2. As with option 1A, the original FEC associated with 691 the packet is maintained at each hop along the MRT. 693 6.2.3. Other considerations for forwarding LDP traffic using MRT LDP 694 Labels 696 Note that forwarding LDP traffic using MRT LDP Labels requires that 697 an MRT to the originator of the FEC be used. For example, one might 698 find it desirable to have the PLR use an MRT to reach the primary 699 next-next-hop for the FEC, and then continue forwarding the LDP 700 packet along the shortest path tree from the primary next-next-hop. 701 However, this would require tunneling to the primary next-next-hop 702 and a targeted LDP session for the PLR to learn the FEC-label binding 703 for primary next-next-hop to correctly forward the packet. 705 For greatest hardware compatibility, routers implementing MRT fast- 706 reroute of LDP traffic MUST support Option 1A of encoding the MT-ID 707 in the labels (See Section 9). 709 6.3. Forwarding IP Unicast Traffic over MRT Paths 711 For IP traffic, there is no currently practical alternative except 712 tunneling to gain the bits needed to indicate the MRT-Blue or MRT-Red 713 forwarding topology. The choice of tunnel egress MAY be flexible 714 since any router closer to the destination than the next-hop can 715 work. This architecture assumes that the original destination in the 716 area is selected (see Section 11 for handling of multi-homed 717 prefixes); another possible choice is the next-next-hop towards the 718 destination. As discussed in the previous section, for LDP traffic, 719 using the MRT to the original destination simplifies MRT-FRR by 720 avoiding the need for targeted LDP sessions to the next-next-hop. 721 For IP, that consideration doesn't apply. However, consistency with 722 LDP is RECOMMENDED. 724 Some situations require tunneling IP traffic along an MRT to a tunnel 725 endpoint that is not the destination of the IP traffic. These 726 situations will be discussed in detail later. We note here that an 727 IP packet with a destination in a different IGP area/level from the 728 PLR should be tunneled on the MRT to the ABR/LBR on the shortest path 729 to the destination. For a destination outside of the PLR's MRT 730 Island, the packet should be tunneled on the MRT to a non-proxy-node 731 immediately before the named proxy-node on that particular color MRT. 733 6.3.1. Tunneling IP traffic using MRT LDP Labels 735 An IP packet can be tunneled along an MRT path by pushing the 736 appropriate MRT LDP label(s). Tunneling using LDP labels, as opposed 737 to IP headers, has the the advantage that more installed routers can 738 do line-rate encapsulation and decapsulation using LDP than using IP. 739 Also, no additional IP addresses would need to be allocated or 740 signaled. 742 6.3.1.1. Tunneling IP traffic using MRT LDP Labels (Option 1A) 744 The MRT LDP Label option 1A forwarding mechanism uses topology-scoped 745 FECs encoded using a single label as described in section 746 Section 6.1.1.1. When a PLR receives an IP packet that needs to be 747 forwarded on the Red MRT to a particular tunnel endpoint, it does a 748 label push operation. The label pushed is the Red MRT label for a 749 FEC originated by the tunnel endpoint, learned from the next-hop on 750 the Red MRT. 752 6.3.1.2. Tunneling IP traffic using MRT LDP Labels (Option 1B) 754 The MRT LDP Label option 1B forwarding mechanism encodes the topology 755 and the FEC using a two label stack as described in Section 6.1.1.2. 756 When a PLR receives an IP packet that needs to be forwarded on the 757 Red MRT to a particular tunnel endpoint, the PLR pushes two labels on 758 the IP packet. The first (inner) label is the normal LDP label 759 learned from the next-hop on the Red MRT, associated with a FEC 760 originated by the tunnel endpoint. The second (outer) label is the 761 topology-identification label associated with the Red MRT. 763 For completeness, we note here a potential optimization. In order to 764 tunnel an IP packet over an MRT to the destination of the IP packet 765 (as opposed to an arbitrary tunnel endpoint), then we could just push 766 a topology-identification label directly onto the packet. An MRT 767 transit router would need to pop the topology-id label, do an IP 768 route lookup in the context of that topology-id , and push the 769 topology-id label. 771 6.3.2. Tunneling IP traffic using MRT IP Tunnels 773 In order to tunnel over the MRT to a particular tunnel endpoint, the 774 PLR encapsulates the original IP packet with an additional IP header 775 using the MRT-Blue or MRT-Red loopack address of the tunnel endpoint. 777 6.3.3. Required support 779 For greatest hardware compatibility and ease in removing the MRT- 780 topology marking at area/level boundaries, routers that support MPLS 781 and implement IP MRT fast-reroute MUST support tunneling of IP 782 traffic using MRT LDP Labels Option 1A (topology-scoped FEC encoded 783 using a single label). 785 7. MRT Island Formation 787 The purpose of communicating support for MRT in the IGP is to 788 indicate that the MRT-Blue and MRT-Red forwarding topologies are 789 created for transit traffic. The MRT architecture allows for 790 different, potentially incompatible options. In order to create 791 constistent MRT forwarding topologies, the routers participating in a 792 particular MRT Island need to use the same set of options. These 793 options are grouped into MRT profiles. In addition, the routers in 794 an MRT Island all need to use the same set of nodes and links within 795 the Island when computing the MRT forwarding topologies. This 796 section describes the information used by a router to determine the 797 nodes and links to include in a particular MRT Island. Some of this 798 information is shared among routers using the newly-defined IGP 799 signaling extensions for MRT described in [I-D.ietf-ospf-mrt] and 801 [I-D.ietf-isis-mrt]. Other information already exists in the IGPs 802 and can be used by MRT in Island formation, subject to the 803 interpretation defined here. 805 Deployment scenarios using multi-topology OSPF or IS-IS, or running 806 both ISIS and OSPF on the same routers is out of scope for this 807 specification. As with LFA, it is expected that OSPF Virtual Links 808 will not be supported. 810 7.1. IGP Area or Level 812 All links in an MRT Island MUST be bidirectional and belong to the 813 same IGP area or level. For ISIS, a link belonging to both level 1 814 and level 2 would qualify to be in multiple MRT Islands. A given ABR 815 or LBR can belong to multiple MRT Islands, corresponding to the areas 816 or levels in which it participates. Inter-area forwarding behavior 817 is discussed in Section 10. 819 7.2. Support for a specific MRT profile 821 All routers in an MRT Island MUST support the same MRT profile. A 822 router advertises support for a given MRT profile using the IGP 823 extensions defined in [I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt] 824 using an 8-bit Profile ID value. A given router can support multiple 825 MRT profiles and participate in multiple MRT Islands. The options 826 that make up an MRT profile, as well as the default MRT profile, are 827 defined in Section 8. 829 7.3. Excluding additional routers and interfaces from the MRT Island 831 MRT takes into account existing IGP mechanisms for discouraging 832 traffic from using particular links and routers, and it introduces an 833 MRT-specific exclusion mechanism for links. 835 7.3.1. Existing IGP exclusion mechanisms 837 Mechanisms for discouraging traffic from using particular links 838 already exist in ISIS and OSPF. In ISIS, an interface configured 839 with a metric of 2^24-2 (0xFFFFFE) will only be used as a last 840 resort. (An interface configured with a metric of 2^24-1 (0xFFFFFF) 841 will not be advertised into the topology.) In OSPF, an interface 842 configured with a metric of 2^16-1 (0xFFFF) will only be used as a 843 last resort. These metrics can be configured manually to enforce 844 administrative policy, or they can be set in an automated manner as 845 with LDP IGP synchronization [RFC5443]. 847 Mechanisms also exist in ISIS and OSPF to prevent transit traffic 848 from using a particular router. In ISIS, the overload bit is used 849 for this purpose. In OSPF, [RFC3137] specifies setting all outgoing 850 interface metrics to 0xFFFF to accomplish this. 852 The following rules for MRT Island formation ensure that MRT FRR 853 protection traffic does not use a link or router that is discouraged 854 from carrying traffic by existing IGP mechanisms. 856 1. A bidirectional link MUST be excluded from an MRT Island if 857 either the forward or reverse cost on the link is 0xFFFFFE (for 858 ISIS) or 0xFFFF for OSPF. 860 2. A router MUST be excluded from an MRT Island if it is advertised 861 with the overload bit set (for ISIS), or it is advertised with 862 metric values of 0xFFFF on all of its outgoing interfaces (for 863 OSPF). 865 7.3.2. MRT-specific exclusion mechanism 867 This architecture also defines a means of excluding an otherwise 868 usable link from MRT Islands. [I-D.ietf-ospf-mrt] and 869 [I-D.ietf-isis-mrt] define the IGP extensions for OSPF and ISIS used 870 to advertise that a link is MRT-Ineligible. A link with either 871 interface advertised as MRT-Ineligible MUST be excluded from an MRT 872 Island. Note that an interface advertised as MRT-Ineligigle by a 873 router is ineligible with respect to all profiles advertised by that 874 router. 876 7.4. Connectivity 878 All of the routers in an MRT Island MUST be connected by 879 bidirectional links with other routers in the MRT Island. 880 Disconnected MRT Islands will operate independently of one another. 882 7.5. Example algorithm 884 An algorithm that allows a computing router to identify the routers 885 and links in the local MRT Island satisfying the above rules is given 886 in section 5.1 of [I-D.ietf-rtgwg-mrt-frr-algorithm]. 888 8. MRT Profile 890 An MRT Profile is a set of values and options related to MRT 891 behavior. The complete set of options is designated by the 892 corresponding 8-bit Profile ID value. 894 8.1. MRT Profile Options 896 Below is a description of the values and options that define an MRT 897 Profile. 899 MRT Algorithm: This identifies the particular MRT algorithm used by 900 the router for this profile. Algorithm transitions can be managed 901 by advertising multiple MRT profiles. 903 MRT-Red MT-ID: This specifies the MT-ID to be associated with the 904 MRT-Red forwarding topology. It is needed for use in LDP 905 signaling. All routers in the MRT Island MUST agree on a value. 907 MRT-Blue MT-ID: This specifies the MT-ID to be associated with the 908 MRT-Blue forwarding topology. It is needed for use in LDP 909 signaling. All routers in the MRT Island MUST agree on a value. 911 GADAG Root Selection Policy: This specifes the manner in which the 912 GADAG root is selected. All routers in the MRT island need to use 913 the same GADAG root in the calculations used construct the MRTs. 914 A valid GADAG Root Selection Policy MUST be such that each router 915 in the MRT island chooses the same GADAG root based on information 916 available to all routers in the MRT island. GADAG Root Selection 917 Priority values, advertised in the IGP as router-specific MRT 918 parameters, MAY be used in a GADAG Root Selection Policy. 920 MRT Forwarding Mechanism: This specifies which forwarding mechanism 921 the router uses to carry transit traffic along MRT paths. A 922 router which supports a specific MRT forwarding mechanism must 923 program appropriate next-hops into the forwarding plane. The 924 current options are MRT LDP Labels, IPv4 Tunneling, IPv6 925 Tunneling, and None. If the MRT LDP Labels option is supported, 926 then option 1A and the appropriate signaling extensions MUST be 927 supported. If IPv4 is supported, then both MRT-Red and MRT-Blue 928 IPv4 Loopback Addresses SHOULD be specified. If IPv6 is 929 supported, both MRT-Red and MRT-Blue IPv6 Loopback Addresses 930 SHOULD be specified. The None option in may be useful for 931 multicast global protection. 933 Recalculation: As part of what process and timing should the new 934 MRTs be computed on a modified topology? Section 12.2 describes 935 the minimum behavior required to support fast-reroute. 937 Area/Level Border Behavior: Should inter-area traffic on the MRT- 938 Blue or MRT-Red be put back onto the shortest path tree? Should 939 it be swapped from MRT-Blue or MRT-Red in one area/level to MRT- 940 Red or MRT-Blue in the next area/level to avoid the potential 941 failure of an ABR? (See [I-D.atlas-rtgwg-mrt-mc-arch] for use- 942 case details. 944 Other Profile-Specific Behavior: Depending upon the use-case for 945 the profile, there may be additional profile-specific behavior. 947 If a router advertises support for multiple MRT profiles, then it 948 MUST create the transit forwarding topologies for each of those, 949 unless the profile specifies the None option for MRT Forwarding 950 Mechanism. A router MUST NOT advertise multiple MRT profiles that 951 overlap in their MRT-Red MT-ID or MRT-Blue MT-ID. 953 8.2. Router-specific MRT paramaters 955 For some profiles, additional router-specific MRT parameters may need 956 to be distributed via the IGP. While the set of options indicated by 957 the MRT Profile ID must be identical for all routers in an MRT 958 Island, these router-specific MRT parameters may differ between 959 routers in the same MRT island. Several such parameters are 960 described below. 962 GADAG Root Selection Priority: A GADAG Root Selection Policy MAY 963 rely on the GADAG Root Selection Priority values advertised by 964 each router in the MRT island. A GADAG Root Selection Policy may 965 use the GADAG Root Selection Priority to allow network operators 966 to configure a parameter to ensure that the GADAG root is selected 967 from a particular subset of routers. An example of this use of 968 the GADAG Root Selection Priority value by the GADAG Root 969 Selection Policy is given in the Default MRT profile below. 971 MRT-Red Loopback Address: This provides the router's loopback 972 address to reach the router via the MRT-Red forwarding topology. 973 It can be specified for either IPv4 and IPv6. 975 MRT-Blue Loopback Address: This provides the router's loopback 976 address to reach the router via the MRT-Blue forwarding topology. 977 It can be specified for either IPv4 and IPv6. 979 The extensions to OSPF and ISIS for advertising a router's GADAG Root 980 Selection Priority value are defined in [I-D.ietf-ospf-mrt] and 981 [I-D.ietf-isis-mrt]. IGP extensions for the advertising a router's 982 MRT-Red and MRT-Blue Loopback Addresses have not been defined. 984 8.3. Default MRT profile 986 The following set of options defines the default MRT Profile. The 987 default MRT profile is indicated by the MRT Profile ID value of 0. 989 MRT Algorithm: MRT Lowpoint algorithm defined in 990 [I-D.ietf-rtgwg-mrt-frr-algorithm]. 992 MRT-Red MPLS MT-ID: [I-D.ietf-mpls-ldp-mrt] contains the IANA 993 request for allocation of this value from the MPLS Multi-Topology 994 Identifiers Registry. Prototype experiments have used a value of 995 3997. 997 MRT-Blue MPLS MT-ID: [I-D.ietf-mpls-ldp-mrt] contains the IANA 998 request for allocation of this value from the MPLS Multi-Topology 999 Identifiers Registry. Prototype experiments have used a value of 1000 3998. 1002 GADAG Root Selection Policy: Among the routers in the MRT Island 1003 and with the highest priority advertised, an implementation MUST 1004 pick the router with the highest Router ID to be the GADAG root. 1006 Forwarding Mechanisms: MRT LDP Labels 1008 Recalculation: Recalculation of MRTs SHOULD occur as described in 1009 Section 12.2. This allows the MRT forwarding topologies to 1010 support IP/LDP fast-reroute traffic. 1012 Area/Level Border Behavior: As described in Section 10, ABRs/LBRs 1013 SHOULD ensure that traffic leaving the area also exits the MRT-Red 1014 or MRT-Blue forwarding topology. 1016 9. LDP signaling extensions and considerations 1018 The protocol extensions for LDP are defined in 1019 [I-D.ietf-mpls-ldp-mrt]. A router must indicate that it has the 1020 ability to support MRT; having this explicit allows the use of MRT- 1021 specific processing, such as special handling of FECs sent with the 1022 Rainbow MRT MT-ID. 1024 A FEC sent with the Rainbow MRT MT-ID indicates that the FEC applies 1025 to all the MRT-Blue and MRT-Red MT-IDs in supported MRT profiles. 1026 The FEC-label bindings for the default shortest-path based MT-ID 0 1027 MUST still be sent (even though it could be inferred from the Rainbow 1028 FEC-label bindings) to ensure continuous operation of normal LDP 1029 forwarding. The Rainbow MRT MT-ID is defined to provide an easy way 1030 to handle the special signaling that is needed at ABRs or LBRs. It 1031 avoids the problem of needing to signal different MPLS labels for the 1032 same FEC. Because the Rainbow MRT MT-ID is used only by ABRs/LBRs or 1033 an LDP egress router, it is not MRT profile specific. 1035 [I-D.ietf-mpls-ldp-mrt] contains the IANA request for the Rainbow MRT 1036 MPLS MT-ID. 1038 10. Inter-area Forwarding Behavior 1040 Unless otherwise specified, in this section we will use the terms 1041 area and ABR to indicate either an OSPF area and OSPF ABR or ISIS 1042 level and ISIS LBR. 1044 An ABR/LBR has two forwarding roles. First, it forwards traffic 1045 within areas. Second, it forwards traffic from one area into 1046 another. These same two roles apply for MRT transit traffic. 1047 Traffic on MRT-Red or MRT-Blue destined inside the area needs to stay 1048 on MRT-Red or MRT-Blue in that area. However, it is desirable for 1049 traffic leaving the area to also exit MRT-Red or MRT-Blue and return 1050 to shortest path forwarding. 1052 For unicast MRT-FRR, the need to stay on an MRT forwarding topology 1053 terminates at the ABR/LBR whose best route is via a different area/ 1054 level. It is highly desirable to go back to the default forwarding 1055 topology when leaving an area/level. There are three basic reasons 1056 for this. First, the default topology uses shortest paths; the 1057 packet will thus take the shortest possible route to the destination. 1058 Second, this allows failures that might appear in multiple areas 1059 (e.g. ABR/LBR failures) to be separately identified and repaired 1060 around. Third, the packet can be fast-rerouted again, if necessary, 1061 due to a failure in a different area. 1063 An ABR/LBR that receives a packet on MRT-Red or MRT-Blue towards 1064 destination Z should continue to forward the packet along MRT-Red or 1065 MRT-Blue only if the best route to Z is in the same area as the 1066 interface that the packet was received on. Otherwise, the packet 1067 should be removed from MRT-Red or MRT-Blue and forwarded on the 1068 shortest-path default forwarding topology. 1070 To avoid per-interface forwarding state for MRT-Red and MRT-Blue, the 1071 ABR/LBR needs to arrange that packets destined to a different area 1072 arrive at the ABR/LBR already not marked as MRT-Red or MRT-Blue. 1074 10.1. ABR Forwarding Behavior with MRT LDP Label Option 1A 1076 For LDP forwarding where a single label specifies (MT-ID, FEC), the 1077 ABR/LBR is responsible for advertising the proper label to each 1078 neighbor. Assume that an ABR/LBR has allocated three labels for a 1079 particular destination; those labels are L_primary, L_blue, and 1080 L_red. To those routers in the same area as the best route to the 1081 destination, the ABR/LBR advertises the following FEC-label bindings: 1082 L_primary for the default topology, L_blue for the MRT-Blue MT-ID and 1083 L_red for the MRT-Red MT-ID, as expected. However, to routers in 1084 other areas, the ABR/LBR advertises the following FEC-label bindings: 1085 L_primary for the default topology, and L_primary for the Rainbow MRT 1086 MT-ID. Associating L_primary with the Rainbow MRT MT-ID causes the 1087 receiving routers to use L_primary for the MRT-Blue MT-ID and for the 1088 MRT-Red MT-ID. 1090 The ABR/LBR installs all next-hops for the best area: primary next- 1091 hops for L_primary, MRT-Blue next-hops for L_blue, and MRT-Red next- 1092 hops for L_red. Because the ABR/LBR advertised (Rainbow MRT MT-ID, 1093 FEC) with L_primary to neighbors not in the best area, packets from 1094 those neighbors will arrive at the ABR/LBR with a label L_primary and 1095 will be forwarded into the best area along the default topology. By 1096 controlling what labels are advertised, the ABR/LBR can thus enforce 1097 that packets exiting the area do so on the shortest-path default 1098 topology. 1100 10.1.1. Motivation for Creating the Rainbow-FEC 1102 The desired forwarding behavior could be achieved in the above 1103 example without using the Rainbow-FEC. This could be done by having 1104 the ABR/LBR advertise the following FEC-label bindings to neighbors 1105 not in the best area: L1_primary for the default topology, L1_primary 1106 for the MRT-Blue MT-ID, and L1_primary for the MRT-Red MT-ID. Doing 1107 this would require machinery to spoof the labels used in FEC-label 1108 binding advertisements on a per-neighbor basis. Such label-spoofing 1109 machinery does not currently exist in most LDP implmentations and 1110 doesn't have other obvious uses. 1112 Many existing LDP implmentations do however have the ability to 1113 filter FEC-label binding advertisements on a per-neighbor basis. The 1114 Rainbow-FEC allows us to re-use the existing per-neighbor FEC 1115 filtering machinery to achieve the desired result. By introducing 1116 the Rainbow FEC, we can use per-neighbor FEC-filtering machinery to 1117 advertise the FEC-label binding for the Rainbow-FEC (and filter those 1118 for MRT-Blue and MRT-Red) to non-best-area neighbors of the ABR. 1120 The use of the Rainbow-FEC by the ABR for non-best-area 1121 advertisements is RECOMMENDED. An ABR MAY advertise the label for 1122 the default topology in separate MRT-Blue and MRT-Red advertisements. 1123 However, a router that supports the LDP Label MRT Forwarding 1124 Mechanism MUST be able to receive and correctly interpret the 1125 Rainbow-FEC. 1127 10.2. ABR Forwarding Behavior with IP Tunneling (option 2) 1129 If IP tunneling is used, then the ABR/LBR behavior is dependent upon 1130 the outermost IP address. If the outermost IP address is an MRT 1131 loopback address of the ABR/LBR, then the packet is decapsulated and 1132 forwarded based upon the inner IP address, which should go on the 1133 default SPT topology. If the outermost IP address is not an MRT 1134 loopback address of the ABR/LBR, then the packet is simply forwarded 1135 along the associated forwarding topology. A PLR sending traffic to a 1136 destination outside its local area/level will pick the MRT and use 1137 the associated MRT loopback address of the selected ABR/LBR 1138 advertising the lowest cost to the external destination. 1140 Thus, for these two MRT Forwarding Mechanisms( MRT LDP Label option 1141 1A and IP tunneling option 2), there is no need for additional 1142 computation or per-area forwarding state. 1144 10.3. ABR Forwarding Behavior with LDP Label option 1B 1146 The other MRT forwarding mechanism described in Section 6 uses two 1147 labels, a topology-id label, and a FEC-label. This mechanism would 1148 require that any router whose MRT-Red or MRT-Blue next-hop is an ABR/ 1149 LBR would need to determine whether the ABR/LBR would forward the 1150 packet out of the area/level. If so, then that router should pop off 1151 the topology-identification label before forwarding the packet to the 1152 ABR/LBR. 1154 For example, in Figure 3, if node H fails, node E has to put traffic 1155 towards prefix p onto MRT-Red. But since node D knows that ABR1 will 1156 use a best route from another area, it is safe for D to pop the 1157 Topology-Identification Label and just forward the packet to ABR1 1158 along the MRT-Red next-hop. ABR1 will use the shortest path in Area 1159 10. 1161 In all cases for ISIS and most cases for OSPF, the penultimate router 1162 can determine what decision the adjacent ABR will make. The one case 1163 where it can't be determined is when two ASBRs are in different non- 1164 backbone areas attached to the same ABR, then the ASBR's Area ID may 1165 be needed for tie-breaking (prefer the route with the largest OPSF 1166 area ID) and the Area ID isn't announced as part of the ASBR link- 1167 state advertisement (LSA). In this one case, suboptimal forwarding 1168 along the MRT in the other area would happen. If that becomes a 1169 realistic deployment scenario, OSPF extensions could be considered. 1170 This is not covered in [I-D.ietf-ospf-mrt]. 1172 +----[C]---- --[D]--[E] --[D]--[E] 1173 | \ / \ / \ 1174 p--[A] Area 10 [ABR1] Area 0 [H]--p +-[ABR1] Area 0 [H]-+ 1175 | / \ / | \ / | 1176 +----[B]---- --[F]--[G] | --[F]--[G] | 1177 | | 1178 | other | 1179 +----------[p]-------+ 1180 area 1182 (a) Example topology (b) Proxy node view in Area 0 nodes 1184 +----[C]<--- [D]->[E] 1185 V \ \ 1186 +-[A] Area 10 [ABR1] Area 0 [H]-+ 1187 | ^ / / | 1188 | +----[B]<--- [F]->[G] V 1189 | | 1190 +------------->[p]<--------------+ 1192 (c) rSPT towards destination p 1194 ->[D]->[E] -<[D]<-[E] 1195 / \ / \ 1196 [ABR1] Area 0 [H]-+ +-[ABR1] [H] 1197 / | | \ 1198 [F]->[G] V V -<[F]<-[G] 1199 | | 1200 | | 1201 [p]<------+ +--------->[p] 1203 (d) Blue MRT in Area 0 (e) Red MRT in Area 0 1205 Figure 3: ABR Forwarding Behavior and MRTs 1207 11. Prefixes Multiply Attached to the MRT Island 1209 How a computing router S determines its local MRT Island for each 1210 supported MRT profile is already discussed in Section 7. 1212 There are two types of prefixes or FECs that may be multiply attached 1213 to an MRT Island. The first type are multi-homed prefixes that 1214 usually connect at a domain or protocol boundary. The second type 1215 represent routers that do not support the profile for the MRT Island. 1217 The key difference is whether the traffic, once out of the MRT 1218 Island, remains in the same area/level and might re-enter the MRT 1219 Island if a loop-free exit point is not selected. 1221 FRR using LFA has the useful property that it is able to protect 1222 multi-homed prefixes against ABR failure. For instance, if a prefix 1223 from the backbone is available via both ABR A and ABR B, if A fails, 1224 then the traffic should be redirected to B. This can be accomplished 1225 with MRT FRR as well. 1227 If ASBR protection is desired, this has additional complexities if 1228 the ASBRs are in different areas. Similarly, protecting labeled BGP 1229 traffic in the event of an ASBR failure has additional complexities 1230 due to the per-ASBR label spaces involved. 1232 As discussed in [RFC5286], a multi-homed prefix could be: 1234 o An out-of-area prefix announced by more than one ABR, 1236 o An AS-External route announced by 2 or more ASBRs, 1238 o A prefix with iBGP multipath to different ASBRs, 1240 o etc. 1242 There are also two different approaches to protection. The first is 1243 tunnel endpoint selection where the PLR picks a router to tunnel to 1244 where that router is loop-free with respect to the failure-point. 1245 Conceptually, the set of candidate routers to provide LFAs expands to 1246 all routers that can be reached via an MRT alternate, attached to the 1247 prefix. 1249 The second is to use a proxy-node, that can be named via MPLS label 1250 or IP address, and pick the appropriate label or IP address to reach 1251 it on either MRT-Blue or MRT-Red as appropriate to avoid the failure 1252 point. A proxy-node can represent a destination prefix that can be 1253 attached to the MRT Island via at least two routers. It is termed a 1254 named proxy-node if there is a way that traffic can be encapsulated 1255 to reach specifically that proxy-node; this could be because there is 1256 an LDP FEC for the associated prefix or because MRT-Red and MRT-Blue 1257 IP addresses are advertised (in an as-yet undefined fashion) for that 1258 proxy-node. Traffic to a named proxy-node may take a different path 1259 than traffic to the attaching router; traffic is also explicitly 1260 forwarded from the attaching router along a predetermined interface 1261 towards the relevant prefixes. 1263 For IP traffic, multi-homed prefixes can use tunnel endpoint 1264 selection. For IP traffic that is destined to a router outside the 1265 MRT Island, if that router is the egress for a FEC advertised into 1266 the MRT Island, then the named proxy-node approach can be used. 1268 For LDP traffic, there is always a FEC advertised into the MRT 1269 Island. The named proxy-node approach should be used, unless the 1270 computing router S knows the label for the FEC at the selected tunnel 1271 endpoint. 1273 If a FEC is advertised from outside the MRT Island into the MRT 1274 Island and the forwarding mechanism specified in the profile includes 1275 LDP, then the routers learning that FEC MUST also advertise labels 1276 for (MRT-Red, FEC) and (MRT-Blue, FEC) to neighbors inside the MRT 1277 Island. Any router receiving a FEC corresponding to a router outside 1278 the MRT Island or to a multi-homed prefix MUST compute and install 1279 the transit MRT-Blue and MRT-Red next-hops for that FEC. The FEC- 1280 label bindings for the topology-scoped FECs ((MT-ID 0, FEC), (MRT- 1281 Red, FEC), and (MRT-Blue, FEC)) MUST also be provided via LDP to 1282 neighbors inside the MRT Island. 1284 11.1. Protecting Multi-Homed Prefixes using Tunnel Endpoint Selection 1286 Tunnel endpoint selection is a local matter for a router in the MRT 1287 Island since it pertains to selecting and using an alternate and does 1288 not affect the transit MRT-Red and MRT-Blue forwarding topologies. 1290 Let the computing router be S and the next-hop F be the node whose 1291 failure is to be avoided. Let the destination be prefix p. Have A 1292 be the router to which the prefix p is attached for S's shortest path 1293 to p. 1295 The candidates for tunnel endpoint selection are those to which the 1296 destination prefix is attached in the area/level. For a particular 1297 candidate B, it is necessary to determine if B is loop-free to reach 1298 p with respect to S and F for node-protection or at least with 1299 respect to S and the link (S, F) for link-protection. If B will 1300 always prefer to send traffic to p via a different area/level, then 1301 this is definitional. Otherwise, distance-based computations are 1302 necessary and an SPF from B's perspective may be necessary. The 1303 following equations give the checks needed; the rationale is similar 1304 to that given in [RFC5286]. 1306 Loop-Free for S: D_opt(B, p) < D_opt(B, S) + D_opt(S, p) 1308 Loop-Free for F: D_opt(B, p) < D_opt(B, F) + D_opt(F, p) 1310 The latter is equivalent to the following, which avoids the need to 1311 compute the shortest path from F to p. 1313 Loop-Free for F: D_opt(B, p) < D_opt(B, F) + D_opt(S, p) - D_opt(S, 1314 F) 1316 Finally, the rules for Endpoint selection are given below. The basic 1317 idea is to repair to the prefix-advertising router selected for the 1318 shortest-path and only to select and tunnel to a different endpoint 1319 if necessary (e.g. A=F or F is a cut-vertex or the link (S,F) is a 1320 cut-link). 1322 1. Does S have a node-protecting alternate to A? If so, select 1323 that. Tunnel the packet to A along that alternate. For example, 1324 if LDP is the forwarding mechanism, then push the label (MRT-Red, 1325 A) or (MRT-Blue, A) onto the packet. 1327 2. If not, then is there a router B that is loop-free to reach p 1328 while avoiding both F and S? If so, select B as the end-point. 1329 Determine the MRT alternate to reach B while avoiding F. Tunnel 1330 the packet to B along that alternate. For example, with LDP, 1331 push the label (MRT-Red, B) or (MRT-Blue, B) onto the packet. 1333 3. If not, then does S have a link-protecting alternate to A? If 1334 so, select that. 1336 4. If not, then is there a router B that is loop-free to reach p 1337 while avoiding S and the link from S to F? If so, select B as 1338 the endpoint and the MRT alternate for reaching B from S that 1339 avoid the link (S,F). 1341 The tunnel endpoint selected will receive a packet destined to itself 1342 and, being the egress, will pop that MPLS label (or have signaled 1343 Implicit Null) and forward based on what is underneath. This 1344 suffices for IP traffic since the tunnel endpoint can use the IP 1345 header of the original packet to continue forwarding the packet. 1346 However, tunnelling of LDP traffic requires targeted LDP sessions for 1347 learning the FEC-label binding at the tunnel endpoint. 1349 11.2. Protecting Multi-Homed Prefixes using Named Proxy-Nodes 1351 Instead, the named proxy-node method works with LDP traffic without 1352 the need for targeted LDP sessions. It also has a clear advantage 1353 over tunnel endpoint selection, in that it is possible to explicitly 1354 forward from the MRT Island along an interface to a loop-free island 1355 neighbor when that interface may not be a primary next-hop. 1357 A named proxy-node represents one or more destinations and, for LDP 1358 forwarding, has a FEC associated with it that is signalled into the 1359 MRT Island. Therefore, it is possible to explicitly label packets to 1360 go to (MRT-Red, FEC) or (MRT-Blue, FEC); at the border of the MRT 1361 Island, the label will swap to meaning (MT-ID 0, FEC). It would be 1362 possible to have named proxy-nodes for IP forwarding, but this would 1363 require extensions to signal two IP addresses to be associated with 1364 MRT-Red and MRT-Blue for the proxy-node. A named proxy-node can be 1365 uniquely represented by the two routers in the MRT Island to which it 1366 is connected. The extensions to signal such IP addresses are not 1367 defined in [I-D.ietf-ospf-mrt]. The details of what label-bindings 1368 must be originated are described in [I-D.ietf-mpls-ldp-mrt]. 1370 Computing the MRT next-hops to a named proxy-node and the MRT 1371 alternate for the computing router S to avoid a particular failure 1372 node F is straightforward. The details of the simple constant-time 1373 functions, Select_Proxy_Node_NHs() and 1374 Select_Alternates_Proxy_Node(), are given in 1375 [I-D.ietf-rtgwg-mrt-frr-algorithm]. A key point is that computing 1376 these MRT next-hops and alternates can be done as new named proxy- 1377 nodes are added or removed without requiring a new MRT computation or 1378 impacting other existing MRT paths. This maps very well to, for 1379 example, how OSPFv2 [[RFC2328] Section 16.5] does incremental updates 1380 for new summary-LSAs. 1382 The key question is how to attach the named proxy-node to the MRT 1383 Island; all the routers in the MRT Island MUST do this consistently. 1384 No more than 2 routers in the MRT Island can be selected; one should 1385 only be selected if there are no others that meet the necessary 1386 criteria. The named proxy-node is logically part of the area/level. 1388 There are two sources for candidate routers in the MRT Island to 1389 connect to the named proxy-node. The first set are those routers 1390 that are advertising the prefix; the named-proxy-cost assigned to 1391 each prefix-advertising router is the announced cost to the prefix. 1392 The second set are those routers in the MRT Island that are connected 1393 to routers not in the MRT Island but in the same area/level; such 1394 routers will be defined as Island Border Routers (IBRs). The routers 1395 connected to the IBRs that are not in the MRT Island and are in the 1396 same area/level as the MRT island are Island Neighbors(INs). 1398 Since packets sent to the named proxy-node along MRT-Red or MRT-Blue 1399 may come from any router inside the MRT Island, it is necessary that 1400 whatever router to which an IBR forwards the packet be loop-free with 1401 respect to the whole MRT Island for the destination. Thus, an IBR is 1402 a candidate router only if it possesses at least one IN whose 1403 shortest path to the prefix does not enter the MRT Island. A method 1404 for identifying loop-free Island Neighbors(LFINs) is discussed below. 1405 The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) 1406 + D_opt(IN, prefix). 1408 From the set of prefix-advertising routers and the set of IBRs with 1409 at least one LFIN, the two routers with the lowest named-proxy-cost 1410 are selected. Ties are broken based upon the lowest Router ID. For 1411 ease of discussion, the two selected routers will be referred to as 1412 proxy-node attachment routers. 1414 A proxy-node attachment router has a special forwarding role. When a 1415 packet is received destined to (MRT-Red, prefix) or (MRT-Blue, 1416 prefix), if the proxy-node attachment router is an IBR, it MUST swap 1417 to the shortest path forwarding topology (e.g. swap to the label for 1418 (MT-ID 0, prefix) or remove the outer IP encapsulation) and forward 1419 the packet to the IN whose cost was used in the selection. If the 1420 proxy-node attachment router is not an IBR, then the packet MUST be 1421 removed from the MRT forwarding topology and sent along the 1422 interface(s) that caused the router to advertise the prefix; this 1423 interface might be out of the area/level/AS. 1425 11.2.1. Computing if an Island Neighbor (IN) is loop-free 1427 As discussed above, the Island Neighbor needs to be loop-free with 1428 respect to the whole MRT Island for the destination. This can be 1429 accomplished by running the usual SPF algorithm while keeping track 1430 of which shortest paths have passed through the MRT island. Pseudo- 1431 code for this is shown in Figure 4. The Island_Marking_SPF() is run 1432 for each IN that needs to be evaluated for the loop-free condition, 1433 with the IN as the spf_root. Whether or not an IN is loop-free with 1434 respect to the MRT island can then be determined by evaluating 1435 node.PATH_HITS_ISLAND for each destination of interest. 1437 Island_Marking_SPF(spf_root) 1438 Initialize spf_heap to empty 1439 Initialize nodes' spf_metric to infinity and next_hops to empty 1440 and PATH_HITS_ISLAND to false 1441 spf_root.spf_metric = 0 1442 insert(spf_heap, spf_root) 1443 while (spf_heap is not empty) 1444 min_node = remove_lowest(spf_heap) 1445 foreach interface intf of min_node 1446 path_metric = min_node.spf_metric + intf.metric 1447 if path_metric < intf.remote_node.spf_metric 1448 intf.remote_node.spf_metric = path_metric 1449 if min_node is spf_root 1450 intf.remote_node.next_hops = make_list(intf) 1451 else 1452 intf.remote_node.next_hops = min_node.next_hops 1453 if intf.remote_node.IN_MRT_ISLAND 1454 intf.remote_node.PATH_HITS_ISLAND = true 1455 else 1456 intf.remote_node.PATH_HITS_ISLAND = 1457 min_node.PATH_HITS_ISLAND 1458 insert_or_update(spf_heap, intf.remote_node) 1459 else if path_metric == intf.remote_node.spf_metric 1460 if min_node is spf_root 1461 add_to_list(intf.remote_node.next_hops, intf) 1462 else 1463 add_list_to_list(intf.remote_node.next_hops, 1464 min_node.next_hops) 1465 if intf.remote_node.IN_MRT_ISLAND 1466 intf.remote_node.PATH_HITS_ISLAND = true 1467 else 1468 intf.remote_node.PATH_HITS_ISLAND = 1469 min_node.PATH_HITS_ISLAND 1471 Figure 4 1473 It is also possible that a given prefix is originated by a 1474 combination of non-island routers and island routers. The results of 1475 the Island_Marking_SPF computation can be used to determine if the 1476 shortest path from an IN to reach that prefix hits the MRT island. 1477 The shortest path for the IN to reach prefix P is determined by the 1478 total cost to reach prefix P, which is the sum of the cost for the IN 1479 to reach a prefix-advertising node and the cost with which that node 1480 advertises the prefix. The path with the minimum total cost to 1481 prefix P is chosen. If the prefix-advertising node for that minimum 1482 total cost path has PATH_HITS_ISLAND set to True, then the IN is not 1483 loop-free with respect to the MRT Island for reaching prefix P. If 1484 there multiple minimum total cost paths to reach prefix P, then all 1485 of the prefix-advertising routers involved in the minimum total cost 1486 paths MUST have PATH_HITS_ISLAND set to False for the IN to be 1487 considered loop-free to reach P. 1489 Note that there are other computations that could be used to 1490 determine if paths from a given IN _might_ pass through the MRT 1491 Island for a given prefix or destination. For example, a previous 1492 version of this draft specified running the SPF algorithm on modified 1493 topology which treats the MRT island as a single node (with intra- 1494 island links set to zero cost) in order to provide input to 1495 computations to determine if the path from IN to non-island 1496 destination hits the MRT island in this modified topology. This 1497 computation is enough to guarantee that a path will not hit the MRT 1498 island in the original topology. However, it is possible that a path 1499 which is disqualified for hitting the MRT island in the modified 1500 topology will not actually hit the MRT Island in the original 1501 topology. The algorithm described in Island_Marking_SPF() above does 1502 not modify the original topology, and will only disqualify a path if 1503 the actual path does in fact hit the MRT island. 1505 Since all routers need to come to the same conclusion about which 1506 routers qualify as LFINs, this specification requires that all 1507 routers computing LFINs MUST use an algorithm whose result is 1508 identical to that of the Island_Marking_SPF() in Figure 4. 1510 11.3. MRT Alternates for Destinations Outside the MRT Island 1512 A natural concern with new functionality is how to have it be useful 1513 when it is not deployed across an entire IGP area. In the case of 1514 MRT FRR, where it provides alternates when appropriate LFAs aren't 1515 available, there are also deployment scenarios where it may make 1516 sense to only enable some routers in an area with MRT FRR. A simple 1517 example of such a scenario would be a ring of 6 or more routers that 1518 is connected via two routers to the rest of the area. 1520 Destinations inside the local island can obviously use MRT 1521 alternates. Destinations outside the local island can be treated 1522 like a multi-homed prefix and either Endpoint Selection or Named 1523 Proxy-Nodes can be used. Named Proxy-Nodes MUST be supported when 1524 LDP forwarding is supported and a label-binding for the destination 1525 is sent to an IBR. 1527 Naturally, there are more complicated options to improve coverage, 1528 such as connecting multiple MRT islands across tunnels, but the need 1529 for the additional complexity has not been justified. 1531 12. Network Convergence and Preparing for the Next Failure 1533 After a failure, MRT detours ensure that packets reach their intended 1534 destination while the IGP has not reconverged onto the new topology. 1535 As link-state updates reach the routers, the IGP process calculates 1536 the new shortest paths. Two things need attention: micro-loop 1537 prevention and MRT re-calculation. 1539 12.1. Micro-forwarding loop prevention and MRTs 1541 As is well known[RFC5715], micro-loops can occur during IGP 1542 convergence; such loops can be local to the failure or remote from 1543 the failure. Managing micro-loops is an orthogonal issue to having 1544 alternates for local repair, such as MRT fast-reroute provides. 1546 There are two possible micro-loop prevention mechanisms discussed in 1547 [RFC5715]. The first is Ordered FIB [I-D.ietf-rtgwg-ordered-fib]. 1548 The second is Farside Tunneling which requires tunnels or an 1549 alternate topology to reach routers on the farside of the failure. 1551 Since MRTs provide an alternate topology through which traffic can be 1552 sent and which can be manipulated separately from the SPT, it is 1553 possible that MRTs could be used to support Farside Tunneling. 1554 Details of how to do so are outside the scope of this document. 1556 Micro-loop mitigation mechanisms can also work when combined with 1557 MRT. 1559 12.2. MRT Recalculation 1561 When a failure event happens, traffic is put by the PLRs onto the MRT 1562 topologies. After that, each router recomputes its shortest path 1563 tree (SPT) and moves traffic over to that. Only after all the PLRs 1564 have switched to using their SPTs and traffic has drained from the 1565 MRT topologies should each router install the recomputed MRTs into 1566 the FIBs. 1568 At each router, therefore, the sequence is as follows: 1570 1. Receive failure notification 1572 2. Recompute SPT 1574 3. Install new SPT 1576 4. If the network was stable before the failure occured, wait a 1577 configured (or advertised) period for all routers to be using 1578 their SPTs and traffic to drain from the MRTs. 1580 5. Recompute MRTs 1582 6. Install new MRTs. 1584 While the recomputed MRTs are not installed in the FIB, protection 1585 coverage is lowered. Therefore, it is important to recalculate the 1586 MRTs and install them quickly. 1588 13. Implementation Status 1590 [RFC Editor: please remove this section prior to publication.] 1592 This section records the status of known implementations of the 1593 protocol defined by this specification at the time of posting of this 1594 Internet-Draft, and is based on a proposal described in [RFC6982]. 1595 The description of implementations in this section is intended to 1596 assist the IETF in its decision processes in progressing drafts to 1597 RFCs. Please note that the listing of any individual implementation 1598 here does not imply endorsement by the IETF. Furthermore, no effort 1599 has been spent to verify the information presented here that was 1600 supplied by IETF contributors. This is not intended as, and must not 1601 be construed to be, a catalog of available implementations or their 1602 features. Readers are advised to note that other implementations may 1603 exist. 1605 According to [RFC6982], "this will allow reviewers and working groups 1606 to assign due consideration to documents that have the benefit of 1607 running code, which may serve as evidence of valuable experimentation 1608 and feedback that have made the implemented protocols more mature. 1609 It is up to the individual working groups to use this information as 1610 they see fit". 1612 Juniper Networks Implementation 1614 o Organization responsible for the implementation: Juniper Networks 1616 o Implementation name: MRT-FRR algorithm 1618 o Implementation description: The MRT-FRR algorithm using OSPF as 1619 the IGP has been implemented and verified. 1621 o The implementation's level of maturity: prototype 1623 o Protocol coverage: This implementation of the MRT algorithm 1624 includes Island identification, GADAG root selection, Lowpoint 1625 algorithm, augmentation of GADAG with additional links, and 1626 calculation of MRT transit next-hops alternate next-hops based on 1627 draft "draft-ietf-rtgwg-mrt-frr-algorithm-00". This 1628 implementation also includes the M-bit in OSPF based on "draft- 1629 atlas-ospf-mrt-01" as well as LDP MRT Capability based on "draft- 1630 atlas-mpls-ldp-mrt-00". 1632 o Licensing: proprietary 1634 o Implementation experience: Implementation was useful for verifying 1635 functionality and lack of gaps. It has also been useful for 1636 improving aspects of the algorithm. 1638 o Contact information: akatlas@juniper.net, shraddha@juniper.net, 1639 kishoret@juniper.net 1641 Huawei Technology Implementation 1643 o Organization responsible for the implementation: Huawei Technology 1644 Co., Ltd. 1646 o Implementation name: MRT-FRR algorithm and IS-IS extensions for 1647 MRT. 1649 o Implementation description: The MRT-FRR algorithm, IS-IS 1650 extensions for MRT and LDP multi-topology have been implemented 1651 and verified. 1653 o The implementation's level of maturity: prototype 1655 o Protocol coverage: This implementation of the MRT algorithm 1656 includes Island identification, GADAG root selection, Lowpoint 1657 algorithm, augmentation of GADAG with additional links, and 1658 calculation of MRT transit next-hops alternate next-hops based on 1659 draft "draft-enyedi-rtgwg-mrt-frr-algorithm-03". This 1660 implementation also includes IS-IS extension for MRT based on 1661 "draft-li-mrt-00". 1663 o Licensing: proprietary 1665 o Implementation experience: It is important produce a second 1666 implementation to verify the algorithm is implemented correctly 1667 without looping. It is important to verify the ISIS extensions 1668 work for MRT-FRR. 1670 o Contact information: lizhenbin@huawei.com, eric.wu@huawei.com 1672 14. Acknowledgements 1674 The authors would like to thank Mike Shand for his valuable review 1675 and contributions. 1677 The authors would like to thank Joel Halpern, Hannes Gredler, Ted 1678 Qian, Kishore Tiruveedhula, Shraddha Hegde, Santosh Esale, Nitin 1679 Bahadur, Harish Sitaraman, Raveendra Torvi, Anil Kumar SN, Bruno 1680 Decraene, Eric Wu, and Janos Farkas for their suggestions and review. 1682 15. IANA Considerations 1684 Please create an MRT Profile registry for the MRT Profile TLV. The 1685 range is 0 to 255. The default MRT Profile has value 0. Values 1686 1-200 are by Standards Action. Values 201-220 are for 1687 experimentation. Values 221-255 are for vendor private use. 1689 16. Security Considerations 1691 This architecture is not currently believed to introduce new security 1692 concerns. 1694 17. References 1696 17.1. Normative References 1698 [I-D.ietf-rtgwg-mrt-frr-algorithm] 1699 Envedi, G., Csaszar, A., Atlas, A., Bowers, C., and A. 1700 Gopalan, "Algorithms for computing Maximally Redundant 1701 Trees for IP/LDP Fast- Reroute", draft-ietf-rtgwg-mrt-frr- 1702 algorithm-05 (work in progress), July 2015. 1704 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 1705 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 1706 DOI 10.17487/RFC5286, September 2008, 1707 . 1709 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1710 RFC 5714, DOI 10.17487/RFC5714, January 2010, 1711 . 1713 17.2. Informative References 1715 [EnyediThesis] 1716 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 1717 Department of Telecommunications and Media Informatics, 1718 Budapest University of Technology and Economics Ph.D. 1719 Thesis, February 2011, 1720 . 1722 [I-D.atlas-rtgwg-mrt-mc-arch] 1723 Atlas, A., Kebler, R., Wijnands, I., Csaszar, A., and G. 1724 Envedi, "An Architecture for Multicast Protection Using 1725 Maximally Redundant Trees", draft-atlas-rtgwg-mrt-mc- 1726 arch-02 (work in progress), July 2013. 1728 [I-D.bryant-ipfrr-tunnels] 1729 Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP 1730 Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03 1731 (work in progress), November 2007. 1733 [I-D.francois-spring-segment-routing-ti-lfa] 1734 Francois, P., Filsfils, C., Bashandy, A., and B. Decraene, 1735 "Topology Independent Fast Reroute using Segment Routing", 1736 draft-francois-spring-segment-routing-ti-lfa-01 (work in 1737 progress), October 2014. 1739 [I-D.ietf-isis-mrt] 1740 Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. 1741 Tantsura, "Intermediate System to Intermediate System (IS- 1742 IS) Extensions for Maximally Redundant Trees (MRT)", 1743 draft-ietf-isis-mrt-00 (work in progress), February 2015. 1745 [I-D.ietf-mpls-ldp-mrt] 1746 Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and 1747 I. Wijnands, "LDP Extensions to Support Maximally 1748 Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in 1749 progress), January 2015. 1751 [I-D.ietf-ospf-mrt] 1752 Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, 1753 "OSPF Extensions to Support Maximally Redundant Trees", 1754 draft-ietf-ospf-mrt-00 (work in progress), January 2015. 1756 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 1757 Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 1758 and MPLS Fast Reroute Using Not-via Addresses", draft- 1759 ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), 1760 May 2013. 1762 [I-D.ietf-rtgwg-ordered-fib] 1763 Shand, M., Bryant, S., Previdi, S., Filsfils, C., 1764 Francois, P., and O. Bonaventure, "Framework for Loop-free 1765 convergence using oFIB", draft-ietf-rtgwg-ordered-fib-12 1766 (work in progress), May 2013. 1768 [I-D.ietf-rtgwg-rlfa-node-protection] 1769 Sarkar, P., Gredler, H., Hegde, S., Bowers, C., Litkowski, 1770 S., and H. Raghuveer, "Remote-LFA Node Protection and 1771 Manageability", draft-ietf-rtgwg-rlfa-node-protection-02 1772 (work in progress), June 2015. 1774 [LFARevisited] 1775 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 1776 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 1777 of IEEE INFOCOM , 2011, 1778 . 1781 [LightweightNotVia] 1782 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 1783 Fast ReRoute: Lightweight Not-Via without Additional 1784 Addresses", Proceedings of IEEE INFOCOM , 2009, 1785 . 1787 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1788 Requirement Levels", BCP 14, RFC 2119, 1789 DOI 10.17487/RFC2119, March 1997, 1790 . 1792 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1793 DOI 10.17487/RFC2328, April 1998, 1794 . 1796 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1797 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1798 DOI 10.17487/RFC3137, June 2001, 1799 . 1801 [RFC5443] Jork, M., Atlas, A., and L. Fang, "LDP IGP 1802 Synchronization", RFC 5443, DOI 10.17487/RFC5443, March 1803 2009, . 1805 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 1806 Convergence", RFC 5715, DOI 10.17487/RFC5715, January 1807 2010, . 1809 [RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene, 1810 B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 1811 Alternate (LFA) Applicability in Service Provider (SP) 1812 Networks", RFC 6571, DOI 10.17487/RFC6571, June 2012, 1813 . 1815 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 1816 Code: The Implementation Status Section", RFC 6982, 1817 DOI 10.17487/RFC6982, July 2013, 1818 . 1820 [RFC7307] Zhao, Q., Raza, K., Zhou, C., Fang, L., Li, L., and D. 1821 King, "LDP Extensions for Multi-Topology", RFC 7307, 1822 DOI 10.17487/RFC7307, July 2014, 1823 . 1825 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 1826 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 1827 RFC 7490, DOI 10.17487/RFC7490, April 2015, 1828 . 1830 Appendix A. General Issues with Area Abstraction 1832 When a multi-homed prefix is connected in two different areas, it may 1833 be impractical to protect them without adding the complexity of 1834 explicit tunneling. This is also a problem for LFA and Remote-LFA. 1836 50 1837 |----[ASBR Y]---[B]---[ABR 2]---[C] Backbone Area 0: 1838 | | ABR 1, ABR 2, C, D 1839 | | 1840 | | Area 20: A, ASBR X 1841 | | 1842 p ---[ASBR X]---[A]---[ABR 1]---[D] Area 10: B, ASBR Y 1843 5 p is a Type 1 AS-external 1845 Figure 5: AS external prefixes in different areas 1847 Consider the network in Figure 5 and assume there is a richer 1848 connective topology that isn't shown, where the same prefix is 1849 announced by ASBR X and ASBR Y which are in different non-backbone 1850 areas. If the link from A to ASBR X fails, then an MRT alternate 1851 could forward the packet to ABR 1 and ABR 1 could forward it to D, 1852 but then D would find the shortest route is back via ABR 1 to Area 1853 20. This problem occurs because the routers, including the ABR, in 1854 one area are not yet aware of the failure in a different area. 1856 The only way to get it from A to ASBR Y is to explicitly tunnel it to 1857 ASBR Y. If the traffic is unlabeled or the appropriate MPLS labels 1858 are known, then explicit tunneling MAY be used as long as the 1859 shortest-path of the tunnel avoids the failure point. In that case, 1860 A must determine that it should use an explicit tunnel instead of an 1861 MRT alternate. 1863 Authors' Addresses 1865 Alia Atlas (editor) 1866 Juniper Networks 1867 10 Technology Park Drive 1868 Westford, MA 01886 1869 USA 1871 Email: akatlas@juniper.net 1873 Robert Kebler 1874 Juniper Networks 1875 10 Technology Park Drive 1876 Westford, MA 01886 1877 USA 1879 Email: rkebler@juniper.net 1881 Chris Bowers 1882 Juniper Networks 1883 1194 N. Mathilda Ave. 1884 Sunnyvale, CA 94089 1885 USA 1887 Email: cbowers@juniper.net 1889 Gabor Sandor Enyedi 1890 Ericsson 1891 Konyves Kalman krt 11. 1892 Budapest 1097 1893 Hungary 1895 Email: Gabor.Sandor.Enyedi@ericsson.com 1896 Andras Csaszar 1897 Ericsson 1898 Konyves Kalman krt 11 1899 Budapest 1097 1900 Hungary 1902 Email: Andras.Csaszar@ericsson.com 1904 Jeff Tantsura 1905 Ericsson 1906 300 Holger Way 1907 San Jose, CA 95134 1908 USA 1910 Email: jeff.tantsura@ericsson.com 1912 Russ White 1913 VCE 1915 Email: russw@riw.us