idnits 2.17.1 draft-agv-rtgwg-spring-segment-routing-mrt-02.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 ([RFC7811]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (July 8, 2016) is 2842 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: 'RFC 7811' is mentioned on line 154, but not defined == Unused Reference: 'I-D.ietf-rtgwg-mrt-frr-algorithm' is defined on line 241, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-mrt-frr-architecture' is defined on line 248, but no explicit reference was found in the text == Unused Reference: 'RFC5036' is defined on line 255, but no explicit reference was found in the text == Unused Reference: 'RFC5561' is defined on line 260, but no explicit reference was found in the text == Unused Reference: 'RFC6420' is defined on line 265, but no explicit reference was found in the text == Unused Reference: 'RFC7307' is defined on line 270, but no explicit reference was found in the text == Unused Reference: 'I-D.atlas-rtgwg-mrt-mc-arch' is defined on line 293, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-isis-mrt' is defined on line 299, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-ospf-mrt' is defined on line 305, but no explicit reference was found in the text == Unused Reference: 'I-D.wijnands-mpls-mldp-node-protection' is defined on line 310, but no explicit reference was found in the text == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-mrt-frr-architecture-05 -- Possible downref: Non-RFC (?) normative reference: ref. 'EnyediThesis' -- Possible downref: Non-RFC (?) normative reference: ref. 'MRTLinear' == Outdated reference: A later version (-03) exists of draft-ietf-isis-mrt-00 == Outdated reference: A later version (-03) exists of draft-ietf-ospf-mrt-00 Summary: 1 error (**), 0 flaws (~~), 16 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Anil Kumar S N 3 INTERNET-DRAFT Gaurav Agrawal 4 Intended Status: Standard Track Vinod Kumar S 5 Expires: January 9, 2017 Huawei Technologies India 6 July 8, 2016 8 Maximally Redundant Trees in Segment Routing 9 draft-agv-rtgwg-spring-segment-routing-mrt-02 11 Abstract 13 This document presents a Fast Reroute (FRR) approach aimed at 14 providing link and node protection of node and adjacency segments 15 within the Segment Routing (SR) framework based on Maximally 16 Redundant Trees (MRT) FRR algorithm [RFC 7811]. 18 Fast-Reroute with Maximally Redundant Trees (MRT-FRR) for Segment 19 routing network is to provide link-protection and node- protection 20 with 100% coverage in Segment routing network topology that is still 21 connected after the failure. MRT is computational efficient. 23 Status of this Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on January 9, 2017. 40 Copyright Notice 42 Copyright (c) 2013 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 1.1 Standard Terminology . . . . . . . . . . . . . . . . . . . . 3 59 2. Draft Specific Terminology . . . . . . . . . . . . . . . . . . 3 60 3. MRT segment routing requirements . . . . . . . . . . . . . . . 5 61 4. MRT segment routing overview . . . . . . . . . . . . . . . . . 5 62 5. Requirements for SR MRT implementation . . . . . . . . . . . . 7 63 3 Security Considerations . . . . . . . . . . . . . . . . . . . . 7 64 4 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 65 5 References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 66 5.1 Normative References . . . . . . . . . . . . . . . . . . . 8 67 5.2. Informative References . . . . . . . . . . . . . . . . . . 10 68 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 70 1 Introduction 72 Segment routing MRT FRR is one among the local repair mechanisms 73 for Segment routing network. Another well known local repair 74 mechanism for SR is Topology Independent Fast Reroute which is also 75 capable of restoring end-to-end connectivity in case of a failure of 76 a link or a node, with guaranteed coverage properties. MRT guarantees 77 100% recovery for single failures when the network is 2-connected. 78 This guaranteed coverage does not depend on the link metrics, which 79 an operator may be using to traffic-engineer the IP network. The 80 link metrics and general network topology are largely decoupled from 81 the guaranteed coverage. 83 The advantage of MRT over TI-LFA would be the computation 84 complexities involved in MRT is much lesser then TI-LFA with 85 additional cost of memory usage. MRT is best suited for 86 access/aggregate ring network or low end devices which has low 87 computing capacity but could afford to have enough memory to hold 88 more FIB entries. 90 1.1 Standard Terminology 92 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 93 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 94 document are to be interpreted as described in RFC 2119 [RFC2119]. 96 2. Draft Specific Terminology 98 For ease of reading, some of the terminology defined in [RFC 7811] is 99 repeated here. 101 Redundant Trees (RT): A pair of trees where the path from any node 102 X to the root R along the first tree is node-disjoint with the path 103 from the same node X to the root along the second tree. These can be 104 computed in 2-connected graphs. 106 Maximally Redundant Trees (MRT): A pair of trees where the path 107 from any node X to the root R along the first tree and the path from 108 the same node X to the root along the second tree share the minimum 109 number of nodes and the minimum number of links. Each such shared 110 node is a cut-vertex. Any shared links are cut-links. Any RT is an 111 MRT but many MRTs are not RTs. The two MRTs are referred to as MRT- 112 Blue and MRT-Red. 114 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 115 used to described the associated forwarding topology and MT-ID. 116 Specifically, MRT-Red is the decreasing MRT where links in the GADAG 117 are taken in the direction from a higher topologically ordered node 118 to a lower one. 120 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 121 used to described the associated forwarding topology and MT-ID. 122 Specifically, MRT-Blue is the increasing MRT where links in the GADAG 123 are taken in the direction from a lower topologically ordered node to 124 a higher one. 126 Rainbow MRT MT-ID: It is useful to have an MT-ID that refers to the 127 multiple MRT topologies and to the default topology. This is 128 referred to as the Rainbow MRT MT-ID and is used by LDP to reduce 129 signaling and permit the same label to always be advertised to all 130 peers for the same (MT-ID, Prefix). 132 MRT Island: From the computing router, the set of routers that 133 support a particular MRT profile and are connected via MRT- eligible 134 links. 136 Island Border Router (IBR): A router in the MRT Island that is 137 connected to a router not in the MRT Island and both routers are in a 138 common area or level. 140 Island Neighbor (IN): A router that is not in the MRT Island but is 141 adjacent to an IBR and in the same area/level as the IBR.. 143 3. MRT segment routing requirements 145 To extend MRT support to Segment routing following requirement 146 need to be achieved : 148 1. SR MRT Capabilities must be advertised using IGP extension for SR 149 MRT. Also SR MRT capabilities must be in sync with IGP specific MRT 150 capabilities advertisement. If the peer has not advertised the SR MRT 151 capability, then it indicates that LSR does not support MRT 152 procedures. 154 2. As specified in MRT Architecture [RFC 7811], both Option 1A and 155 Option 1B can be used for the implementation of SR MRT. 157 For Option 1A, two additional Prefix SID's/Label for RED and BLUE MT 158 must be advertised in addition to default prefix SID/Label. The IGP 159 extension carrying prefix SID for RED and BLUE MT must have 160 corresponding MT-ID allocated by IANA for default MRT profile. 162 For Option 1B, Global Unique Context SID/Label for Red & Blue as 163 topology identifier must be used. 165 4. MRT segment routing overview 167 Segment routing devices has to undergo no changes with respect to 168 forwarding plane. Segment Routing (SR) allows a flexible definition 169 of end-to-end paths within IGP topologies by encoding paths as 170 sequences of topological sub-paths, called "segments". These 171 segments are advertised by the link-state routing protocols (IS-IS 172 and OSPF). Prefix segments represent an ECMP-aware shortest-path to 173 a prefix (or a node), as per the state of the IGP topology. 174 Adjacency segments represent a hop over a specific adjacency between 175 two nodes in the IGP. 177 MRT FRR in segment routing network does not require any additional 178 signaling (other than IGP extensions). 180 Basically MRT Fast Reroute requires that packets to be forwarded not 181 only on the shortest-path tree, but also on two Maximally Redundant 182 Trees (MRTs), referred to as the MRT-Blue and the MRT-Red. A router 183 that experiences a local failure must also have predetermined which 184 alternate to use. The MRT algorithm is based on those presented in 185 [MRTLinear] and expanded in [EnyediThesis]. Default MRT Profile path 186 calculation uses Lowpoint algorithm to calculate Maximally Redundant 187 Trees. 189 Just as packets routed on a hop-by-hop basis require that each router 190 compute a shortest-path tree that is consistent, it is necessary for 191 each router to compute the MRT-Blue next hops and MRT-Red next hops 192 in a consistent fashion. 194 A router's Labeled Forwarding Information Base (L-FIB) will continue 195 to contain primary next hops segment entries for the current 196 shortest-path tree for forwarding traffic. In addition, a router's 197 L-FIB will contain primary next hops segments for the MRT-Blue for 198 forwarding received traffic on the MRT-Blue and primary next hops 199 segments for the MRT-Red for forwarding received traffic on the MRT- 200 Red. 202 Within a link-state IGP domain, an SR-capable IGP node advertises 203 segments for its attached prefixes and adjacencies. These segments 204 are called IGP segments or IGP SIDs. They play a key role in Segment 205 Routing and use-cases as they enable the expression of any 206 topological path throughout the IGP domain. Such a topological path 207 is either expressed as a single IGP segment or a list of multiple IGP 208 segments. After running MRT lowpoint algorithm IGP will advertise two 209 more additional labels as MRT-BLUE and MRT-RED for each such IGP 210 segments. 212 Since segment Routing is directly applied to the MPLS architecture 213 with no change on the forwarding plane and The ingress node of an SR 214 domain encodes an ordered list of segments as a stack of labels. By 215 default The ingress node encode only default path labels. The 216 protecting router after detecting the node or link failure switches 217 the top label with MRT label[MRT-RED or MRT-BLUE is selected based on 218 algorithm] for the same destination. Till packet reaches the 219 destination MRT colored label path is followed by the packet. 221 5. Requirements for SR MRT implementation 223 REQ1 : IGP Extension to carry the Segment Routing Node MRT Capability 224 in addition to exiting IGP extension carrying IGP MRT Capability 226 REQ2 : IGP Extension to carry Red & Blue MRT SR Segments in addition 227 to existing Default SR Segment 229 3 Security Considerations 231 None of the security consideration are identified 233 4 IANA Considerations 235 None of the IANA consideration are identified 237 5 References 239 5.1 Normative References 241 [I-D.ietf-rtgwg-mrt-frr-algorithm] 243 Envedi, G., Csaszar, A., Atlas, A., Bowers, C., and A. 244 Gopalan, "Algorithms for computing Maximally Redundant 245 Trees for IP/LDP Fast- Reroute", draft-ietf-rtgwg-mrt-frr- 246 algorithm-05 (work in progress), July 2015. 248 [I-D.ietf-rtgwg-mrt-frr-architecture] 249 Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, 250 A., Tantsura, J., and R. White, "An Architecture for IP/ 251 LDP Fast-Reroute Using Maximally Redundant Trees", draft- 252 ietf-rtgwg-mrt-frr-architecture-05 (work in progress), 253 January 2015. 255 [RFC5036] 256 Andersson, L., Ed., Minei, I., Ed., and B. Thomas, Ed., 257 "LDP Specification", RFC 5036, DOI 10.17487/RFC5036, 258 October 2007, . 260 [RFC5561] 261 Thomas, B., Raza, K., Aggarwal, S., Aggarwal, R., and JL. 262 Le Roux, "LDP Capabilities", RFC 5561, DOI 263 10.17487/RFC5561, July 2009, . 265 [RFC6420] 266 Cai, Y. and H. Ou, "PIM Multi-Topology ID (MT-ID) Join 267 Attribute", RFC 6420, DOI 10.17487/RFC6420, November 2011, 268 . 270 [RFC7307] 271 Zhao, Q., Raza, K., Zhou, C., Fang, L., Li, L., and D. 272 King, "LDP Extensions for Multi-Topology", RFC 7307, DOI 273 10.17487/RFC7307, July 2014, . 276 [EnyediThesis] 277 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 278 Department of Telecommunications and Media Informatics, 279 Budapest University of Technology and Economics Ph.D. 280 Thesis, February 2011, 281 . 284 [MRTLinear] 285 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 286 Maximally Redundant Trees in Strictly Linear Time", IEEE 287 Symposium on Computers and Communications (ISCC), 2009, 288 . 291 5.2. Informative References 293 [I-D.atlas-rtgwg-mrt-mc-arch] 294 Atlas, A., Kebler, R., Wijnands, I., Csaszar, A., and G. 295 Envedi, "An Architecture for Multicast Protection Using 296 Maximally Redundant Trees", draft-atlas-rtgwg-mrt-mc- 297 arch-02 (work in progress), July 2013. 299 [I-D.ietf-isis-mrt] 300 Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. 301 Tantsura, "Intermediate System to Intermediate System (IS- 302 IS) Extensions for Maximally Redundant Trees (MRT)", 303 draft-ietf-isis-mrt-00 (work in progress), February 2015. 305 [I-D.ietf-ospf-mrt] 306 Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, 307 "OSPF Extensions to Support Maximally Redundant Trees", 308 draft-ietf-ospf-mrt-00 (work in progress), January 2015. 310 [I-D.wijnands-mpls-mldp-node-protection] 311 Wijnands, I., Rosen, E., Raza, K., Tantsura, J., Atlas, 312 A., and Q. Zhao, "mLDP Node Protection", draft-wijnands- 313 mpls-mldp-node-protection-04 (work in progress), June 314 2013. 316 [RFC2119] 317 Bradner, S., "Key words for use in RFCs to Indicate 318 Requirement Levels", BCP 14, RFC 2119, DOI 319 10.17487/RFC2119, March 1997, . 322 Authors' Addresses 324 Anil Kumar S N 325 Huawei Technologies India Pvt. Ltd, 326 Near EPIP Industrial Area, 327 Kundalahalli Village, 328 Whitefield, 329 Bangalore - 560066 331 EMail: anil.ietf@gmail.com 333 Gaurav Agrawal 335 Huawei Technologies India Pvt. Ltd, 336 Near EPIP Industrial Area, 337 Kundalahalli Village, 338 Whitefield, 339 Bangalore - 560066 341 EMail: gaurav.agrawal@huawei.com 343 Vinod Kumar S 344 Huawei Technologies India Pvt. Ltd, 345 Near EPIP Industrial Area, 346 Kundalahalli Village, 347 Whitefield, 348 Bangalore - 560066 350 EMail: vinods.kumar@huawei.com