idnits 2.17.1 draft-psarkar-rtgwg-multihomed-prefix-lfa-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 244 has weird spacing: '... 2a. If not s...' -- The document date (February 20, 2015) is 3346 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'RFC 5286' is mentioned on line 216, but not defined == Missing Reference: 'RFC 2328' is mentioned on line 220, but not defined -- Looks like a reference, but probably isn't: '5286' on line 222 == Missing Reference: 'RFC2328' is mentioned on line 272, but not defined Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group P. Sarkar, Ed. 3 Internet-Draft H. Gredler 4 Intended status: Informational S. Hegde 5 Expires: August 24, 2015 C. Bowers 6 Juniper Networks, Inc. 7 B. Decraene 8 Orange 9 February 20, 2015 11 LFA selection for Multi-Homed Prefixes 12 draft-psarkar-rtgwg-multihomed-prefix-lfa-01 14 Abstract 16 This document shares experience gained from implementing algorithms 17 to determine Loop-Free Alternates for multi-homed prefixes. In 18 particular, this document provides explicit inequalities that can be 19 used to evaluate neighbors as a potential alternates for multi-homed 20 prefixes. It also provides detailed criteria for evaluating 21 potential alternates for external prefixes advertised by OSPF ASBRs. 23 Requirements Language 25 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 26 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 27 document are to be interpreted as described in RFC2119 [RFC2119]. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on August 24, 2015. 46 Copyright Notice 48 Copyright (c) 2015 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 64 2. LFA inequalities for MHPs . . . . . . . . . . . . . . . . . . 3 65 3. LFA selection for the multi-homed prefixes . . . . . . . . . 4 66 4. LFA selection for the multi-homed external prefixes . . . . . 5 67 4.1. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . 5 68 4.2. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . 5 69 4.2.1. Rules to select alternate ASBR . . . . . . . . . . . 5 70 4.2.2. Multiple ASBRs belonging different area . . . . . . . 6 71 4.2.3. Type 1 and Type 2 costs . . . . . . . . . . . . . . . 7 72 4.2.4. RFC1583compatibility is set to enabled . . . . . . . 7 73 4.2.5. Type 7 routes . . . . . . . . . . . . . . . . . . . . 7 74 4.2.6. Inequalities to be applied for alternate ASBR 75 selection . . . . . . . . . . . . . . . . . . . . . . 7 76 4.2.6.1. Forwarding address set to non zero value . . . . 7 77 4.2.6.2. ASBRs advertising type1 and type2 cost . . . . . 8 78 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 79 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 9 81 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 82 8.1. Normative References . . . . . . . . . . . . . . . . . . 9 83 8.2. Informative References . . . . . . . . . . . . . . . . . 10 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 86 1. Introduction 88 The use of Loop-Free Alternates (LFA) for IP Fast Reroute is 89 specified in [RFC5286]. Section 6.1 of [RFC5286] describes a method 90 to determine loop-free alternates for a multi-homed prefixes (MHPs). 91 This document describes a procedure using explicit inequalities that 92 can be used by a computing router to evaluate a neighbor as a 93 potential alternate for a multi-homed prefix. The results obtained 94 are equivalent to those obtained using the method described in 95 Section 6.1 of [RFC5286]. However, some may find this formulation 96 useful. 98 Section 6.3 of [RFC5286] discusses complications associated with 99 computing LFAs for multi-homed prefixes in OSPF. This document 100 provides detailed criteria for evaluating potential alternates for 101 external prefixes advertised by OSPF ASBRs, as well as explicit 102 inequalities. 104 2. LFA inequalities for MHPs 106 This document proposes the following set of LFA inequalities for 107 selecting the most appropriate LFAs for multi-homed prefixes (MHPs). 108 They can be derived from the inequalities in [RFC5286] combined with 109 the observation that D_opt(N,P) = Min (D_opt(N,PO_i) + cost(PO_i,P)) 110 over all PO_i 112 Link-Protection: 113 D_opt(N,PO_i)+ cost(PO_i,P) < D_opt(N,S) + 114 D_opt(S,PO_best) + cost(PO_best,P) 116 Link-Protection + Downstream-paths-only: 117 D_opt(N,PO_i)+ cost(PO_i,P) < D_opt(S,PO_best) + cost(PO_best,P) 119 Node-Protection: 120 D_opt(N,PO_i)+ cost(PO_i,P) < D_opt(N,E) + 121 D_opt(E,PO_best) + cost(PO_best,P) 123 Where, 124 S - The computing router 125 N - The alternate router being evaluated 126 E - The primary next-hop on shortest path from S to 127 prefix P. 128 PO_i - The specific prefix-originating router being 129 evaluated. 130 PO_best - The prefix-originating router on the shortest path 131 from the computing router S to prefix P. 132 Cost (X,P) - Cost of reaching the prefix P from prefix 133 originating node X. 134 D_opt(X,Y) - Distance on the shortest path from node X to node 135 Y. 137 Figure 1: LFA inequalities for MHPs 139 3. LFA selection for the multi-homed prefixes 141 To compute a valid LFA for a given multi-homed prefix P, through an 142 alternate neighbor N a computing router S MUST follow one of the 143 appropriate procedures below. 145 Link-Protection : 146 ================= 147 1. If alternate neighbor N is also prefix-originator of P, 148 1.a. Select N as a LFA for prefix P (irrespective of 149 the metric advertised by N for the prefix P). 150 2. Else, evaluate the link-protecting LFA inequality for P with 151 the N as the alternate neighbor. 152 2.a. If LFA inequality condition is met, 153 select N as a LFA for prefix P. 154 2.b. Else, N is not a LFA for prefix P. 156 Link-Protection + Downstream-paths-only : 157 ========================================= 158 1. Evaluate the link-protecting + downstream-only LFA inequality 159 for P with the N as the alternate neighbor. 160 1.a. If LFA inequality condition is met, 161 select N as a LFA for prefix P. 162 1.b. Else, N is not a LFA for prefix P. 164 Node-Protection : 165 ================= 166 1. If alternate neighbor N is also prefix-originator of P, 167 1.a. Select N as a LFA for prefix P (irrespective of 168 the metric advertised by N for the prefix P). 169 2. Else, evaluate the apporpriate node-protecting LFA inequality 170 for P with the N as the alternate neighbor. 171 2.a. If LFA inequality condition is met, 172 select N as a LFA for prefix P. 173 2.b. Else, N is not a LFA for prefix P. 175 Figure 2: Rules for selecting LFA for MHPs 177 In case an alternate neighbor N is also one of the prefix-originators 178 of prefix P, N MAY be selected as a valid LFA for P. 180 However if N is not a prefix-originator of P, the computing router 181 SHOULD evaluate one of the corresponding LFA inequalities, as 182 mentioned in Figure 1, once for each remote node that originated the 183 prefix. In case the inequality is satisfied by the neighbor N router 184 S MUST choose neighbor N, as one of the valid LFAs for the prefix P. 186 When computing a dowstream-only LFA, in addition to being a prefix- 187 originator of P, router N MUST also satisfy the downstream-only LFA 188 inequality specified in Figure 1. 190 For more specific rules please refer to the later sections of this 191 document. 193 4. LFA selection for the multi-homed external prefixes 195 Redistribution of external routes into IGP is required in case of two 196 different networks getting merged into one or during protocol 197 migrations. External routes could be distributed into an IGP domain 198 via multiple nodes to avoid a single point of failure. 200 During LFA calculation, alternate LFA next-hops to reach the best 201 ASBR could be used as LFA for the routes redistributed via that ASBR. 202 When there is no LFA available to the best ASBR, it may be desirable 203 to consider the other ASBRs (referred to as alternate ASBR hereafter) 204 redistributing the external routes for LFA selection as defined in 205 [RFC5286] and leverage the advantage of having multiple re- 206 distributing nodes in the network. 208 4.1. IS-IS 210 LFA evaluation for multi-homed external prefixes in IS-IS is similar 211 to the multi-homed internal prefixes. Inequalities described in sec 212 2 would also apply to multi-homed external prefixes as well. 214 4.2. OSPF 216 Loop free Alternates [RFC 5286] describes mechanisms to apply 217 inequalities to find the the loop free alternate neighbor. For the 218 selection of alternate ASBR for LFA consideration, additional rules 219 have to be applied in selecting the alternate ASBR due to the 220 external route calculation rules imposed by [RFC 2328]. 222 This document also defines the inequalities defined in RFC [5286] 223 specifically for the alternate loop-free ASBR evaluation. 225 4.2.1. Rules to select alternate ASBR 227 The process to select an alternate ASBR is best explained using the 228 rules below. The below process is applied when primary ASBR for the 229 concerned prefix is chosen and there is an alternate ASBR originating 230 same prefix. 232 1. If RFC1583Compatibility is disabled 234 1a. if primary ASBR and alternate ASBR are intra area 235 non-backbone path go to step 2. 236 1b. If primary ASBR and alternate ASBR belong to 237 intra-area backbone and/or inter-area path go 238 to step 2. 239 1c. for other paths, skip the alternate ASBR and 240 consider next ASBR. 242 2. If cost type (type1/type2) advertised by alternate 243 ASBR same as primary 244 2a. If not same skip alternate ASBR and consider next ASBR. 246 3. If cost type is type1 247 3a. If cost is same, program ECMP 248 3b. else go to step 5. 250 4 If cost type is type 2 251 4a. If cost is different, skip alternate ASBR and 252 consider next ASBR 253 4b. If type2 cost is same, compare type 1 cost. 254 4c. If type1 cost is also same program ECMP. 255 4d. If type 1 cost is different go to step 5. 257 5. If route type (type 5/type 7) 258 5a. If route type is same, check route p-bit, 259 forwarding address field for routes from both 260 ASBRs 261 match. If not skip alternate ASBR and consider 262 next ASBR. 263 5b. If route type is not same, skip ASBR 264 and consider next ASBR. 266 6. Apply inequality on the alternate ASBR. 268 Figure 3: Rules for selecting alternate ASBR in OSPF 270 4.2.2. Multiple ASBRs belonging different area 272 When "RFC1583compatibility" is set to disabled, OSPF[RFC2328] defines 273 certain rules of preference to choose the ASBRs. While selecting 274 alternate ASBR for loop evaluation for LFA, these rules should be 275 applied and ensured that the alternate neighbor does not loop the 276 traffic back. 278 When there are multiple ASBRs belonging to different area advertising 279 the same prefix, pruning rules as defined in RFC 2328 section 16.4.1 280 are applied. The alternate ASBRs pruned using above rules are not 281 considered for LFA evaluation. 283 4.2.3. Type 1 and Type 2 costs 285 If there are multiple ASBRs not pruned via rules defined in 3.2.2, 286 the cost type advertised by the ASBRs is compared. ASBRs advertising 287 Type1 costs are preferred and the type2 costs are pruned. If two 288 ASBRs advertise same type2 cost, the alternate ASBRs are considered 289 along with their type1 cost for evaluation.If the two ASBRs with same 290 type2 as well as type1 cost, ECMP FRR is programmed.If there are two 291 ASBRs with different type2 cost, the higher cost ASBR is pruned.The 292 inequalities for evaluating alternate ASBR for type 1 and type 2 293 costs are same, as the alternate ASBRs with different type2 costs are 294 pruned and the evaluation is based on equal type 2 cost ASBRS. 296 4.2.4. RFC1583compatibility is set to enabled 298 When RFC1583Compatibility is set to enabled, multiple ASBRs belonging 299 to different area advertising same prefix are chosen based on cost 300 and hence are valid alternate ASBRs for the LFA evaluation. 302 4.2.5. Type 7 routes 304 Type 5 routes always get preference over Type 7 and the alternate 305 ASBRs chosen for LFA calculation should belong to same type.Among 306 Type 7 routes, routes with p-bit and forwarding address set have 307 higher preference than routes without these attributes. Alternate 308 ASBRs selected for LFA comparison should have same p-bit and 309 forwarding address attributes. 311 4.2.6. Inequalities to be applied for alternate ASBR selection 313 The alternate ASBRs selected using above mechanism described in 314 3.2.1, are evaluated for Loop free criteria using below inequalities. 316 4.2.6.1. Forwarding address set to non zero value 317 Link-Protection: 318 F_opt(N,PO_i)+ cost(PO_i,P) < D_opt(N,S) + 319 F_opt(S,PO_best) + cost(PO_best,P) 321 Link-Protection + Downstream-paths-only: 322 F_opt(N,PO_i)+ cost(PO_i,P) < F_opt(S,PO_best) + cost(PO_best,P) 324 Node-Protection: 325 F_opt(N,PO_i)+ cost(PO_i,P) < D_opt(N,E) + 326 F_opt(E,PO_best) + cost(PO_best,P) 328 Where, 329 S - The computing router 330 N - The alternate router being evaluated 331 E - The primary next-hop on shortest path from S to 332 prefix P. 333 PO_i - The specific prefix-originating router being 334 evaluated. 335 PO_best - The prefix-originating router on the shortest path 336 from the computing router S to prefix P. 337 cost(X,Y) - External cost for Y as advertised by X 338 F_opt(X,Y) - Distance on the shortest path from node X to Forwarding 339 address specified by ASBR Y. 340 D_opt(X,Y) - Distance on the shortest path from node X to node Y. 342 Figure 4: LFA inequality definition when forwarding address in non- 343 zero 345 4.2.6.2. ASBRs advertising type1 and type2 cost 346 Link-Protection: 347 D_opt(N,PO_i)+ cost(PO_i,P) < D_opt(N,S) + 348 D_opt(S,PO_best) + cost(PO_best,P) 350 Link-Protection + Downstream-paths-only: 351 D_opt(N,PO_i)+ cost(PO_i,P) < D_opt(S,PO_best) + cost(PO_best,P) 353 Node-Protection: 354 D_opt(N,PO_i)+ cost(PO_i,P) < D_opt(N,E) + 355 D_opt(E,PO_best) + cost(PO_best,P) 357 Where, 358 S - The computing router 359 N - The alternate router being evaluated 360 E - The primary next-hop on shortest path from S to 361 prefix P. 362 PO_i - The specific prefix-originating router being 363 evaluated. 364 PO_best - The prefix-originating router on the shortest path 365 from the computing router S to prefix P. 366 cost(X,Y) - External cost for Y as advertised by X. 367 D_opt(X,Y) - Distance on the shortest path from node X to node Y. 369 Figure 5: LFA inequality definition for type1 and type 2 cost 371 5. Acknowledgements 373 Thanks to Alia Atlas and Salih K A for their useful feedback and 374 inputs. 376 6. IANA Considerations 378 N/A. - No protocol changes are proposed in this document. 380 7. Security Considerations 382 This document does not introduce any change in any of the protocol 383 specifications. It simply proposes additional inequalities for 384 selecting LFAs for multi-homed prefixes. 386 8. References 388 8.1. Normative References 390 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 391 Requirement Levels", BCP 14, RFC 2119, March 1997. 393 8.2. Informative References 395 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 396 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 398 Authors' Addresses 400 Pushpasis Sarkar (editor) 401 Juniper Networks, Inc. 402 Electra, Exora Business Park 403 Bangalore, KA 560103 404 India 406 Email: psarkar@juniper.net 408 Hannes Gredler 409 Juniper Networks, Inc. 410 1194 N. Mathilda Ave. 411 Sunnyvale, CA 94089 412 US 414 Email: hannes@juniper.net 416 Shraddha Hegde 417 Juniper Networks, Inc. 418 Electra, Exora Business Park 419 Bangalore, KA 560103 420 India 422 Email: shraddha@juniper.net 424 Chris Bowers 425 Juniper Networks, Inc. 426 1194 N. Mathilda Ave. 427 Sunnyvale, CA 94089 428 US 430 Email: cbowers@juniper.net 432 Bruno Decraene 433 Orange 435 Email: bruno.decraene@orange.com