idnits 2.17.1 draft-tian-frr-alt-shortest-path-01.txt: ** The Abstract section seems to be numbered Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3667, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 485. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack an RFC 3978 Section 5.4 (updated by RFC 4748) Copyright Line. ** The document seems to lack an RFC 3978 Section 5.4 Reference to BCP 78. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 11 longer pages, the longest (page 6) being 71 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 11 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 2004) is 7225 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) == Unused Reference: 'IPFRR' is defined on line 382, but no explicit reference was found in the text == Unused Reference: 'LDP' is defined on line 419, but no explicit reference was found in the text == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-ipfrr-framework-01 ** Downref: Normative reference to an Informational draft: draft-ietf-rtgwg-ipfrr-framework (ref. 'IPFRR') == Outdated reference: A later version (-01) exists of draft-shen-nhop-fastreroute-00 -- Possible downref: Normative reference to a draft: ref. 'NHFRR' -- Possible downref: Non-RFC (?) normative reference: ref. 'IP-TE-RSP' == Outdated reference: A later version (-01) exists of draft-shen-pim-nnhop-nodes-00 -- Possible downref: Normative reference to a draft: ref. 'NHFRR-MCAST' -- Possible downref: Normative reference to a draft: ref. 'LSP-SRC-RT' -- Possible downref: Normative reference to a draft: ref. 'LOOSE-OPT' -- Possible downref: Normative reference to a draft: ref. 'LOOPFREE' == Outdated reference: A later version (-03) exists of draft-atlas-ip-local-protect-uturn-00 -- Possible downref: Normative reference to a draft: ref. 'UTURN' == Outdated reference: A later version (-03) exists of draft-bryant-ipfrr-tunnels-00 ** Downref: Normative reference to an Historic draft: draft-bryant-ipfrr-tunnels (ref. 'TUNNEL') ** Obsolete normative reference: RFC 3036 (ref. 'LDP') (Obsoleted by RFC 5036) Summary: 17 errors (**), 0 flaws (~~), 10 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Albert J. Tian 3 Internet Draft Naiming Shen 4 Expiration Date: Jan 2005 Redback Networks 5 July 2004 7 Fast Reroute using Alternative Shortest Paths 9 draft-tian-frr-alt-shortest-path-01.txt 11 1. Status of this Memo 13 By submitting this Internet-Draft, I certify that any applicable 14 patent or other IPR claims of which I am aware have been disclosed, 15 or will be disclosed, and any of which I become aware will be 16 disclosed, in accordance with RFC 3668. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as ``work in progress.'' 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 2. Abstract 36 Repair path mechanism is an important element in IP/LDP fast reroute. 37 In this document we propose a way to calculate local repair paths 38 using alternative shortest paths. The solution can provide complete 39 coverage for all destinations within an IGP area that can possibly be 40 protected. 42 In this document we also suggested an "Explicit Path with Loose 43 Segment" model that can be used to characterize, classify, and 44 analyse repair paths. We proved some of the common properties of 45 loose segments, and showed that the model can be used to characterize 46 all existing fast reroute solutions. 48 Based on the properties of loose segments, we also provided a way to 49 maximize the use of loose segments in a repair path based on 50 alternative shortest path, in order to simplify the repair path 51 implementation. 53 3. Introduction 55 To construct a repair path, the termination point of the repair path 56 must be determined first. Then we can calculate the repair path from 57 the router at point of local repair (PLR) to the termination point 58 without going through the nexthop router being protected. The 59 resulting explicit path from the calculation is usually a strict path 60 that lists all nodes on the path. The path can then be simplified by 61 maximizing the use of loose hops. The resulting path can then be 62 implemented using mechanisms such as LSP source route or RSVP-TE. 64 4. Select the Termination Point of Repair Path 66 Since node protection can also cover link failure and its in general 67 difficult to distinguish between link and node failure, node failure 68 is always assumed, unless the nexthop is a single point of failure. 70 On a PLR router P, to protect a destination D from the failure of 71 nexthop N, the termination point T of a repair path can be one of the 72 following: 74 If the nexthop N is not the primary egress point E for D, then 75 either 76 a) terminate at the primary egress point E for D, or 77 b) terminate at the next-nexthop node from P to E [NHFRR]. 79 If the nexthop N is the primary egress point E for D, then 80 c) if there exists an alternative egress point E' for D, terminate 81 at E'; 82 d) if there are no alternative egress points, terminate at E and 83 attempt link protection. 85 Terminating repair path at next-nexthop has several advantages over 86 terminating at egress point: 88 1) since there are usually much less next-nexthops than egress 89 points, next-nexthop based solution requires much less repair 90 paths to be calculated and maintained. 92 2) next-nexthop based repair path can protect multicast traffic 93 [NHFRR-MCAST], while egress based repair path can not. 95 In some cases, next-nexthop based repair paths may be less optimal 96 for some destinations, but this usually is not a concern. 98 If the nexthop is the only egress, then it is a single point of 99 failure. In this case, link protection is attempted. Repair paths can 100 be calculated easily by disqualifying the link between P and N. The 101 rest of the discussions in this document will focus on the node 102 protection cases (i.e. cases a, b and c above). 104 5. Use Alternative Shortest Paths as Repair Paths 106 Once the termination point T is decided, we can move on to the 107 calculation of repair paths from P to T. 109 Repair paths are used by the PLR router P to quickly recover from the 110 failure of a nexthop N, therefore the repair path can not go through 111 the nexthop N that is being protected. 113 For a destination D, one way to find the repair path on PLR router P 114 to protect nexthop N's failure is to calculate shortest alternative 115 paths from P to termination point T that do not go through N. 117 For networks that are running link state IGP such as OSPF or ISIS, a 118 simple way to calculate alternative shortest paths is to remove N 119 from the link state database and re-run SPF from PLR P's point of 120 view. This SPF will find all the alternative shortest paths from P to 121 all possible T not going through N, therefore it will find out all 122 the repair paths needed to cover N's failure, except for cases where 123 N is a single point of failure. To protect all P's nexthops, the same 124 calculation needs to be done for each nexthop. 126 We use the notion ASP-N to represent the set of alternative 127 shortest paths between A and B that do not go through N. 129 6. Construct Repair Paths using Explicit Paths 131 Since repair paths can not follow normal IP routing, therefore they 132 have to be explicitly paths. Even in ECMP cases, when one of the ECMP 133 nexthop fails, traffic has to be explicitly directed to the other 134 ECMP nexthops. Therefore the ECMP based repair paths are still 135 explicit paths. 137 An explicit path can be expressed as a list of nexthops that the path 138 must traverse. Each hop can be either strict or loose. 140 In general there are two ways to implement an explicit path: 142 a) Stateful Explicit Path: this method installs special forwarding 143 state on each router that is specified in the explicit path. An 144 example of this method is RSVP-TE. There is little or no per 145 packet overhead, but states need to be maintained in the network. 146 This method can handle arbitrary explicit paths. Also RSVP-TE can 147 support QoS along the path. 149 b) Source Routed Explicit Path: this method use some form of source 150 routing to encode the path in the packet itself. An example of 151 this method is LSP source route [LSP-SRC-RT]. The benefit of 152 this method is that no state need to be maintained in the 153 network, therefore this method can scale to a large number of 154 explicit paths. The limitation is that due to the per packet 155 overhead, this method is only suitable for simple paths with 156 small number of routers specified. Please note that a simple path 157 is not necessarily short. One loose hop specified in the path can 158 traverse a large number of routers. 160 There are other solutions for fast reroute. They can all be viewed as 161 some form of limited source routing. We will discuss this later in 162 appendix A. 164 7. Loose Hops in Explicit Repair Paths 166 There are several benefits of using loose segments in repair paths. 168 7.1. Reduce Number of Hops Specified 170 In any case, there is incentive to reduce the number of hops that 171 need to be specified in an explicit path. The simplest way to reduce 172 the number of routers that need to be specified in an explicit path 173 is through the use of loose hops. 175 For stateful explicit paths, if loose segment optimization using 176 tunnels is enabled [LOOSE-OPT], then the use of loose segments can 177 reduce the amount of state installed in the network. 179 For source routed explicit paths, the use of loose segments can 180 reduce the per packet overhead. 182 7.2. Trailing Loose Hop Optimization 184 If the last segment of an explicit repair path is a loose segment, 185 then as an optimization the explicit path can terminate early at the 186 beginning of the trailing loose segment. From there on, the packets 187 can be forwarded towards destination based on normal routing, and the 188 actual path traversed by the packets will not be affected by the 189 failure of the router being protected. 191 It can be proven that this optimization is also valid for repair 192 paths terminating on next-nexthop router. 194 Consider the following topology where P is the PLR, N is the nexthop 195 being protected, H is the next-nexthop, E is the egress. Path P-A-B-H 196 is the next-nexthop based repair path. All links shown below except 197 link are loose segments that may traverse multiple routers. 199 A-----B--------+ 200 / \ / \ | 201 / \ / \ | 202 P-----N-----H-----E 204 Figure 2 206 It can be proven that if segment can be a loose hop for repair 207 path P-A-B-H, then repair path P-A-B is sufficient to protect all 208 traffic from P that passes through next-nexthop H. 210 7.3. Characters of Loose Hops 212 One requirement for a repair path is that it can not pass through the 213 router being protected regardless of its status. Therefore any loose 214 hop in an explicit repair path must not pass through the router being 215 protected. 217 7.3.1. Theorem 1 219 The following theorem can help identifying the loose segments in an 220 explicit path. 222 Theorem 1: 224 Let SP be the set of shortest paths between A and B. If paths in 225 SP do not pass through N when N is available, then the set 226 SP will not change when N and only N becomes unavailable. 228 Proof: 230 When node N becomes unavailable, the cost of the links between N and 231 its neighbors increase from some finite value to infinity. If the 232 cost of any path between A and B is changed after N's failure, it can 233 only become higher. Therefore N's failure will not add any new paths 234 to SP. 236 If N is the only node that becomes unavailable, then the costs of 237 links not connected to N will not be changed. Therefore the cost of 238 the paths not passing through N will not be changed. That means the 239 costs of the paths in SP will not be changed. Therefore N's 240 failure will not remove any paths from SP. 242 So N's failure will not change SP. 244 END. 246 Basically theorem 1 means that if the shortest paths between A and B 247 do not pass through the router N being protected, then segment 248 can be safely used as a loose segment in a repair path protecting N, 249 because the actual path for the loose segment will not be affected by 250 N's failure. 252 7.3.2. Theorem 2 254 The following theorem can further improve theorem 1. 256 Theorem 2: 258 Let ASP_N be the set of alternative shortest paths between A and 259 B that do not go through N. Let l(ASP_N) be the path length for 260 ASP_N. It is the shortest distance between A and B for paths 261 that do not go through N. Let d(A,N) be the shortest distance 262 between A and N. Let d(N,B) be the shortest distance between N and 263 B. 265 If the following condition holds, then SP do not go through N. 267 l(ASP_N) < d(A,N) + d(N,B) ....... Condition 1 269 Proof 271 All the paths between A and B can be divided into two sets, those 272 that pass through N, and those that do not pass through N. For paths 273 that pass through N, the shortest distance between A and B is d(A,N) 274 + d(N,B). For paths that do not pass through N, by definition the 275 shortest path is ASP_N, and its length is l(ASP_N). Because 276 condition 1 is true, ASP_N is shorter than any path that goes 277 through N. Therefore ASP_N is the shortest among all paths 278 between A and B. Therefore ASP_N is SP. Since ASP_N do 279 not go through N, SP do not go through N. 281 END. 283 Essentially Theorem 2 means that if the length of the alternative 284 shortest path between A and B that do not go through N is shorter 285 than the distance between A and N plus the distance between N and B, 286 then the segment can be used as a loose segment in a repair 287 path protecting N. 289 7.4. Finding Loose Segments in Alternative Shortest Path 291 Based on theorem 1 and theorem 2, an algorithm can be devised to find 292 loose hops in alternative shortest paths. 294 Given an alternative shortest path ASP_N = 295 from PLR P to termination point T not going through nexthop N, it can 296 be used to protect N. 298 Run SPF from N's point of view to find out d(N,X), for all X. 300 If all link metrics are symmetrical, then d(X,N) = d(N,X), for all X. 301 If some link metrics are asymmetrical, then run an additional reverse 302 metric SPF from N's point of view to find out d(X,N), for all X. 304 Let c(Ri, Rj) be the link metric from Ri to Rj. 306 The following algorithm maximizes the length of loose hops in the 307 alternative shortest path. It evaluates a segment on the path against 308 theorem 2, if it can be a loose hop, then extend the segment by one 309 hop and re-evaluate again, till a point that the segment is no longer 310 a loose segment. In this way the algorithm finds the longest loose 311 segment on the path for a given starting point. 313 Algorithm Find_Loose_Hops 314 { 315 len = 0; 316 start = 1; 317 end = start; 318 while (end < m) { 319 if (len + c(R[end],R[end+1]) >= d(R[start],N) + d(N,R[end])) { 320 if (len == 0) { 321 output segment as a strict hop; 322 end = end+1; 323 start = end; 324 if (start > m) break; 325 } else { 326 output segment as a loose hop; 327 start = end; 328 } 329 } else { 330 len = len + c(R[end],R[end+1]); 331 end = end+1; 332 if (end == m) { 333 output segment as a loose hop; 334 } 335 } 336 } 337 } 339 7.5. Implementing Repair Paths 341 IP TE Route Switched Path [IP-TE-RSP] can be used to implement 342 arbitrary repair paths in a pure IP network. 344 If MPLS is enabled, then LSP source route [LSP-SRC-RT] and RSVP-TE 345 (possibly with loose segment optimization [LOOSE-OPT]), can be used 346 to construct arbiturary repair paths using MPLS. 348 All of the above mechanisms can benefit from the use of loose 349 segments in repair paths. In most cases, a repair path is expected to 350 conatin some loose segments, in perticular a long loose segment at 351 the end. For RSVP based solutions, if optimization of loose segments 352 is enabled, then the actual amount of state information maintained in 353 a network can be greatly reduced. For LSP source route, the use of 354 loose segments can reduce the label stack size. 356 Please note that under some topologies the repair paths may require 357 multiple strict hops to route around the router being protected. For 358 example, in the following topology as shown in Figure 1, P-N-H-E was 359 the primary path. In order for PLR P to implement repair path P-A-B- 360 H-E to protect failure in N, the first three segments must all be 361 strict. The repair path is of type SSSL. Link metrics are show next 362 to the links. 364 2 365 A-----B 366 2 / \ / \ 2 367 / 1\ /1 \ 368 P-----N-----H-----E 369 1 1 10 371 Figure 2 A sample topology that requires complex repair path 373 This repair path can only be supported by IP TE RSP, LSP source 374 route, and RSVP-TE today. 376 8. Security Considerations 378 This document does not introduce any new security issues. 380 9. References 382 [IPFRR] M. Shand, "IP Fast Reroute Framework", 383 draft-ietf-rtgwg-ipfrr-framework-01.txt, Work in progress. 385 [NHFRR] N. Shen, P. Pang, "Nexthop Fast ReRoute for IP and MPLS", 386 draft-shen-nhop-fastreroute-00.txt, Work in progress. 388 [IP-TE-RSP] N. Shen, A. Tian, J, Zhuang, "IP Traffic Engineering 389 With Route Switched Paths (RSPs)", Work in progress. 391 [NHFRR-MCAST] N. Shen, L. Wei, D. Farinacci, "Discovering PIM-SM 392 Next-Nexthop Downstream Nodes", 393 draft-shen-pim-nnhop-nodes-00.txt, Work in progress. 395 [LSP-SRC-RT] A. Tian, G. Apostolopoulos, "Source Routed MPLS LSP 396 using Domain Wide Label", 397 draft-tian-mpls-lsp-source-route-01.txt, July 2004, Work in 398 progress. 400 [LOOSE-OPT] A. Tian, N. Shen, "Loose Segment Optimization in 401 Explicit Paths", draft-tian-rsvp-loose-seg-opt-00.txt, 402 Work in progress. 404 [LOOPFREE] Atlas, Torvi, Choudhury, Martin, Imhoff, Fedyk, 405 "IP/LDP Local Protection", 406 draft-atlas-ip-local-protect-loopfree-00.txt, Work in progress. 408 [UTURN] Atlas, et al., "U-turn Alternates for IP/LDP Local 409 Protection", draft-atlas-ip-local-protect-uturn-00.txt, Work in 410 progress. 412 [TUNNEL] Bryant, Filsfils, Previdi, Shand, "IP Fast Reroute using 413 tunnels", draft-bryant-ipfrr-tunnels-00.txt, May 2004, Work In 414 Progress. 416 [RSVPTE] Awduche, et al., "Extensions to RSVP for LSP Tunnels", 417 RFC 3209, December 2001. 419 [LDP] L. Andersson, P. Doolan, N. Feldman, A. Fredette, and B. 420 Thomas, "LDP Specification", RFC 3036, January 2001. 422 10. Author Information 424 Albert Jining Tian 425 Redback Networks, Inc. 426 300 Holger Way 427 San Jose, CA 95134 428 Email: tian@redback.com 430 Naiming Shen 431 Redback Networks, Inc. 432 300 Holger Way 433 San Jose, CA 95134 434 Email: naiming@redback.com 436 11. Appendix A: Classification of Repair Path Mechanisms 438 11.1. Two Hops: Strict - Loose (Type SL) 440 Downstream Path (Loop-Free Alternative) [LOOPFREE] 441 ECMP 443 11.2. Two Hops: Loose - Loose (Type LL) 445 Tunnel Approach without directed forwarding [TUNNEL]. 447 11.3. Three Hops: Loose - Strict - Loose (Type LSL) 449 Tunnel Approach with directed forwarding [TUNNEL]. 451 11.4. Three Hops: Strict - Strict - Loose (Type SSL) 453 U-Turn: only support a subset of the cases where the first hop node 454 must be an upstream node. [UTURN] 456 11.5. Three Hops: Strict - Loose - Loose (Type SLL) 458 Tunnel Approach with first strict hop optimization and without 459 directed forwarding [TUNNEL]. 461 11.6. Four Hops - Strict, Loose, then Strict, Loose (Type SLSL) 463 Tunnel Approach with first strict hop optimization and directed 464 forwarding [TUNNEL]. 466 11.7. Arbitrary Mix of Loose and Strict Hops 468 IP TE RSP [IP-TE-RSP] 469 LSP Source Route [LSP-SRC-RT] 470 RSVP-TE [RSVPTE] 471 RSVP-TE with Loose Hop Optimization [LOOSE-OPT]. 473 12. Full Copyright Statement 475 Copyright (C) The Internet Society (year). This document is subject 476 to the rights, licenses and restrictions contained in BCP 78, and 477 except as set forth therein, the authors retain all their rights. 479 This document and the information contained herein are provided on an 480 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 481 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 482 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 483 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 484 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 485 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.