idnits 2.17.1 draft-ginsberg-spring-conflict-resolution-00.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 : ---------------------------------------------------------------------------- == There are 3 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. -- The document has examples using IPv4 documentation addresses according to RFC6890, but does not use any IPv6 documentation addresses. Maybe there should be IPv6 examples, too? Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to contain a disclaimer for pre-RFC5378 work, but was first submitted on or after 10 November 2008. The disclaimer is usually necessary only for documents that revise or obsolete older RFCs, and that take significant amounts of text from those RFCs. If you can contact all authors of the source material and they are willing to grant the BCP78 rights to the IETF Trust, you can and should remove the disclaimer. Otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 14, 2015) is 3110 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-15) exists of draft-ietf-spring-segment-routing-05 == Outdated reference: A later version (-25) exists of draft-ietf-isis-segment-routing-extensions-05 == Outdated reference: A later version (-27) exists of draft-ietf-ospf-segment-routing-extensions-05 Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Networking Working Group L. Ginsberg 3 Internet-Draft P. Psenak 4 Intended status: Standards Track S. Previdi 5 Expires: April 16, 2016 Cisco Systems 6 October 14, 2015 8 Segment Routing Conflict Resolution 9 draft-ginsberg-spring-conflict-resolution-00.txt 11 Abstract 13 In support of Segment Routing (SR) routing protocols advertise a 14 variety of identifiers used to define the segments which direct 15 forwarding of packets. In cases where the information advertised by 16 a given protocol instance is either internally inconsistent or 17 conflicts with advertisements from another protocol instance a means 18 of achieving consistent forwarding behavior in the network is 19 required. This document defines the policies used to resolve these 20 occurrences. 22 Requirements Language 24 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 25 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 26 document are to be interpreted as described in RFC 2119 [RFC2119]. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on April 16, 2016. 45 Copyright Notice 47 Copyright (c) 2015 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 This document may contain material from IETF Documents or IETF 61 Contributions published or made publicly available before November 62 10, 2008. The person(s) controlling the copyright in some of this 63 material may not have granted the IETF Trust the right to allow 64 modifications of such material outside the IETF Standards Process. 65 Without obtaining an adequate license from the person(s) controlling 66 the copyright in such materials, this document may not be modified 67 outside the IETF Standards Process, and derivative works of it may 68 not be created outside the IETF Standards Process, except to format 69 it for publication as an RFC or to translate it into languages other 70 than English. 72 Table of Contents 74 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 75 2. SR Global Block Inconsistency . . . . . . . . . . . . . . . . 3 76 3. Segment Identifier Conflicts . . . . . . . . . . . . . . . . 5 77 3.1. Conflict Types . . . . . . . . . . . . . . . . . . . . . 6 78 3.1.1. Prefix Conflict . . . . . . . . . . . . . . . . . . . 6 79 3.1.2. SID Conflict . . . . . . . . . . . . . . . . . . . . 7 80 3.2. Processing conflicting entries . . . . . . . . . . . . . 8 81 3.2.1. Ignore conflicting entries . . . . . . . . . . . . . 8 82 3.2.2. Preference Algorithm . . . . . . . . . . . . . . . . 8 83 3.2.3. Candidate Preference Algorithm . . . . . . . . . . . 9 84 3.2.4. Example Behavior . . . . . . . . . . . . . . . . . . 9 85 3.2.5. Other Preference Factors to consider . . . . . . . . 10 86 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 87 5. Security Considerations . . . . . . . . . . . . . . . . . . . 11 88 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 89 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 90 7.1. Normative References . . . . . . . . . . . . . . . . . . 11 91 7.2. Informational References . . . . . . . . . . . . . . . . 12 92 Appendix A. Alternate Prefix Conflict Algorithm . . . . . . . . 12 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14 95 1. Introduction 97 Segment Routing (SR) as defined in [SR-ARCH] utilizes forwarding 98 instructions called "segments" to direct packets through the network. 99 Depending on the forwarding plane architecture in use, routing 100 protocols advertise various identifiers which define the permissible 101 values which can be used as segments, which values are assigned to 102 specific prefixes, etc. Where segments have global scope it is 103 necessary to have non-conflicting assignments - but given that the 104 advertisements may originate from multiple nodes the possibility 105 exists that advertisements may be received which are either 106 internally inconsistent or conflicting with advertisements originated 107 by other nodes. In such cases it is necessary to have consistent 108 resolution of conflicts network-wide in order to avoid forwarding 109 loops. 111 The problem to be addressed is protocol independent i.e., segment 112 related advertisements may be originated by multiple nodes using 113 different protocols and yet the conflict resolution MUST be the same 114 on all nodes regardless of the protocol used to transport the 115 advertisements. 117 The remainder of this document defines conflict resolution policies 118 which meet these requirements. All protocols which support SR MUST 119 adhere to the policies defined in this document. 121 2. SR Global Block Inconsistency 123 In support of an MPLS dataplane routing protocols advertise an SR 124 Global Block (SRGB) which defines a set of label ranges reserved for 125 use by the advertising node in support of SR. The details of how 126 protocols advertise this information can be found in the protocol 127 specific drafts e.g., [SR-OSPF] and [SR-IS-IS]. However the protocol 128 independent semantics are illustrated by the following example: 130 The originating router advertises the following ranges: 132 Range 1: (100, 199) 133 Range 2: (1000, 1099) 134 Range 3: (500, 5990 136 The receiving routers concatenate the ranges and build the Segment 137 Routing Global Block (SRGB) as follows: 139 SRGB = (100, 199) 140 (1000, 1099) 141 (500, 599) 143 The indexes span multiple ranges: 145 index=0 means label 100 146 ... 147 index 99 means label 199 148 index 100 means label 1000 149 index 199 means label 1099 150 ... 151 index 200 means label 500 152 ... 154 Note that the ranges are an ordered set - what labels are mapped to a 155 given index depends on the placement of a given label range in the 156 set of ranges advertised. 158 For the set of ranges to be usable the ranges MUST be disjoint. The 159 question then arises what receiving routers should do if they receive 160 an SRGB which includes overlapping ranges. In such a case the 161 following rule is defined: 163 Each range is examined in the order it was advertised. If it does 164 not overlap with any advertised range which preceded it the 165 advertised range is used. If the range overlaps with any preceding 166 range it MUST NOT be used and all ranges advertised after the first 167 encountered overlapping range also MUST NOT be used. 169 Consider the following example: 171 The originating router advertises the following ranges: 173 Range 1: (100, 199] 174 Range 2: (1000, 1099) 175 Range 3: (100, 599) 176 Range 4: (2000, 2099) 178 Range 3 overlaps with Range 1. 179 Only Ranges #1 and #2 are usable. 180 Ranges #3 and #4 are ignored. 181 Note that Range #4 is not used even though it does not overlap 182 with any of the other ranges. 184 3. Segment Identifier Conflicts 186 In support of an MPLS dataplane Segment identifiers (SIDs) are 187 advertised and associated with a given prefix. SIDs may be 188 advertised in the prefix reachability advertisements originated by a 189 routing protocol. SIDs may also be advertised by a Segment Routing 190 Mapping Server (SRMS). 192 A generalized mapping entry can be represented using the following 193 definitions: 195 Pi - Initial prefix 196 Pe - End prefix 197 L - Prefix length 198 Lx - Maximum prefix length (32 for IPv4, 128 for IPv6) 199 Si - Initial SID value 200 Se - End SID value 201 R - Range value 203 Mapping Entry is then the tuple: (Pi/L, Si, R) 204 Pe = (Pi + ((R-1) << (Lx-L)) 205 Se = Si + (R-1) 207 Note that the SID advertised in a prefix reachability advertisement 208 can be more generally represented as a mapping entry with a range 209 of 1. 211 Conflicts in SID advertisements may occur as a result of 212 misconfiguration. Conflicts may occur either in the set of 213 advertisements originated by a single node or between advertisements 214 originated by different nodes. When conflicts occur, it is not 215 possible for routers to know which of the conflicting advertisements 216 is "correct". If a router chooses to use one of the conflicting 217 entries forwarding loops and/or blackholes may result unless it can 218 be guaranteed that all other routers in the network make the same 219 choice. Making the same choice requires that all routers have 220 identical sets of advertisements and that they all use the same 221 selection algorithm. 223 3.1. Conflict Types 225 Various types of conflicts may occur. 227 3.1.1. Prefix Conflict 229 When different SIDs are assigned to the same prefix we have a "prefix 230 conflict". Consider the following set of advertisements: 232 (192.0.2.120/32, 200, 1) 233 (192.0.2.120/32, 30, 1) 235 The prefix 192.0.2.120/32 has been assigned two different SIDs - 200 236 by the first advertisement - 30 by the second advertisement. 238 Prefix conflicts may also occur as a result of overlapping prefix 239 ranges. Consider the following set of advertisements: 241 (192.0.2.1/32, 200, 200) 242 (192.0.2.121/32, 30, 10) 244 Prefixes 192.0.2.121/32 - 192.0.2.130/32 are assigned two different 245 SIDs - 320 through 329 by the first advertisement - 30 through 39 by 246 the second advertisement. 248 The second example illustrates a complication - only part of the 249 range advertised in the first advertisement is in conflict. It is 250 logically possible to isolate the conflicting portion and try to use 251 the non-conflicting portion(s) at the cost of increased 252 implementation complexity. The algorithm defined here does NOT 253 attempt to support use of a partial range. 255 A variant of the overlapping prefix range is a case where we have 256 overlapping prefix ranges but no actual SID conflict. 258 (192.0.2.1/32, 200, 200) 259 (192.0.2.121/32, 320, 10) 261 Although there is prefix overlap between the two entries the same SID 262 is assigned to all of the shared prefixes by the two entries. It is 263 possible to utilize both entries but it complicates the 264 implementation of the database required to support this. See 265 Appendix A for a more complete discussion of this case. An 266 alternative is to ensure at the nodes which originate these 267 advertisements that no such overlap is allowed to be configured. 268 Such overlaps can then be considered as a conflict if they are 269 received. This allows a simpler and more efficient implementation of 270 the database. This is the approach assumed in this document. 272 Given two mapping entries: 274 (P1/L1, S1, R1) and (P2/L2, S2, R2) 276 a prefix conflict exists if all of the following are true: 278 1)The prefixes are in the same address family. 279 2)L1 == L2 280 3)((P1 < P2) && (P1e >= P2)) || ((P2 < P1 ) && (P2e >= P1)) 282 3.1.2. SID Conflict 284 When the same SID has been assigned to multiple prefixes we have a 285 "SID conflict". Consider the following example: 287 (192.0.2.1/32, 200, 1) 288 (192.0.2.222/32, 200,1) 290 SID 200 has been assigned to 192.0.2.1/32 by the first advertisement. 291 The second advertisement assigns SID 200 to 192.0.2.222/32. 293 SID conflicts may also occur as a result of overlapping SID ranges. 294 Consider the following set of advertisements: 296 (192.0.2.1/32, 200, 200) 297 (192.1.2.1/32, 300, 10) 299 SIDs 300 - 309 have been assigned to two different prefixes. The 300 first advertisement assigns these SIDs to 192.0.2.101/32 - 301 192.0.2.110/32. The second advertisement assigns these SIDs to 302 192.1.2.1/32 - 192.1.2.10/32. 304 The second example illustrates a complication - only part of the 305 range advertised in the first advertisement is in conflict. It is 306 logically possible to isolate the conflicting portion and try to use 307 the non-conflicting portion(s) at the cost of increased 308 implementation complexity. The algorithm defined here does NOT 309 attempt to support use of a partial range. 311 SID conflicts are independent of address-family and independent of 312 prefix len. A SID conflict occurs when a mapping entry which has 313 previously been checked to have no prefix conflict assigns one or 314 more SIDs that are assigned by another entry which also has no prefix 315 conflicts. 317 3.2. Processing conflicting entries 319 Two general approaches can be used to process conflicting entries. 321 1. Conflicting entries can be ignored 323 2. A standard preference algorithm can be used to choose which of 324 the conflicting entries will be used 326 The following sections discuss these two approaches in more detail. 328 Note: This document does not discuss any implementation details i.e. 329 what type of data structure is used to store the entries (trie, radix 330 tree, etc.) nor what type of keys may be used to perform lookups in 331 the database. 333 3.2.1. Ignore conflicting entries 335 In cases where entries are in conflict none of the conflicting 336 entries are used i.e., the network operates as if the conflicting 337 advertisements were not present. 339 Ikplementation requires identifying the conflicting entries and 340 ensuring that they are not used. The occurrence of conflicts is 341 easily diagnosed from the behavior of the network as the forwarding 342 of traffic which would, in the absence of conflicts, utilize segments 343 no longer does so. Which prefixes are impacted is easily seen and 344 therefore the entries which are misconfigured are easily identified. 345 Unintended traffic flow will never occur. 347 The downside of ignoring conflicting entries is that forwarding of 348 all packets with destinations covered by the conflicting entries will 349 always be negatively impacted. 351 3.2.2. Preference Algorithm 353 For entries which are in conflict properties of the advertisement 354 (e.g. prefix value, prefix length, SID value, etc.) are used to 355 determine which of the conflicting entries are used in forwarding and 356 which are ignored. 358 This approach requires that conflicting entries first be identified 359 and then evaluated based on the preference rule. Based on which 360 entry is preferred this in turn may impact what other entries are 361 considered in conflict i.e. if A conflicts with B and B conflicts 362 with C - it is possible that A does NOT conflict with C. Hence if as 363 a result of the evaluation of the conflict between A and B, entry B 364 is not used the conflict between B and C will not be considered. 366 As at least some of the traffic continues to be forwarded after the 367 conflict is detected, the presence of the conflict may be harder to 368 diagnose based on traffic flowthan when using the ignore policy. 370 The upside of the preference algorithm is that in some cases 371 forwarding of traffic may continue to be correct despite the 372 existence of the conflict. If the preference algorithm happens to 373 prefer the intended configuration traffic will still be successfully 374 delivered. Whether this will occur is a random outcome since the 375 preference algorithm cannot know which of the conflicting entries is 376 the "correct" entry. 378 3.2.3. Candidate Preference Algorithm 380 The following algorithm is proposed. Evaluation is made in the order 381 specified. 383 1. IPv4 entry wins over IPv6 entry 385 2. Smaller prefix length wins 387 3. Smaller starting address (considered as an unsigned integer 388 value) wins 390 4. Smaller starting SID wins 392 5. Smaller range wins 394 6. non-attached entries preferred over attached entries (SRMS 395 attached flag) 397 3.2.4. Example Behavior 399 Consider the following simple case. The following mapping entries 400 exist: 402 1. (192.0.2.1/32, 100, 200) 404 2. (192.0.2.200/32, 150, 300) !Prefix conflict with entry #1 405 3. (193.3.3.3/32, 400, 100) !SID conflict with entry #2 407 Using the Ignore conflicts behavior we would not use any of the above 408 entries. 410 Using a preference rule which favors smaller prefixes, entries #1 and 411 #3 would be used. 413 o Entry #1 would be used as 192.0.200.1 is less than 192.0.2.200. 415 o Entry #3 would be used because once Entry #2 has been excluded, 416 entry #3 no longer conflicts with any entry which is being used. 417 (An example of lack of transitivity of conflicts) 419 If we now add 421 4. (192.0.1.1/32, 50, 100) ! Prefix conflict with #1 423 Using ignore policy still none of the entries would be used. 425 Using a preference rule which favors smaller prefixes , entries #4 426 and #2 would be used. 428 o Entry #4 would be used in preference to entry #1 because 192.0.1.1 429 < 192.0.2.1. 431 o Entry #2 would be used because once Entry #1 is excluded entry #2 432 no longer has a prefix conflict with any active entry. 434 o Entry #3 would NOT be used because once Entry #2 becomes active 435 entry #3 loses due to the SID conflict with Entry #2 since the 436 latter has a smaller prefix. 438 3.2.5. Other Preference Factors to consider 440 Prefix to SID mapping is based on a variety of sources. 442 o SIDs can be configured locally for prefixes assigned to interfaces 443 on the router itself 445 o SIDs can be received in prefix reachability advertisements from 446 protocol peers. These advertisements may originate from peers 447 local to the area or be leaked from other areas and/or 448 redistributed from other routing protocols 450 o SIDs can be received from SRMS advertisements - these 451 advertisements can originate from routers local to the area or 452 leaked from other areas 454 SIDs configured locally for prefixes associated with interfaces on 455 the router itself are only used by the originating router in prefix 456 advertisements - they are not installed in the forwarding plane 457 locally. Therefore, they do not need to be considered in conflict 458 resolution. 460 For other sources, It may seem intuitive to assign priority based on 461 point of origination (e.g. intra-area preferred over inter-area, 462 prefix reachability advertisements preferred over SRMS 463 advertisements, etc.). However, any such policy makes it more likely 464 that inconsistent choices will be made by routers in the network and 465 increase the likelihood of forwarding loops or blackholes. The 466 algorithms defined in this document assume that prefix reachability 467 advertisements are part of the set of entries considered when 468 determining conflicts and conflict resolution and no preference is 469 associated with prefix reachability advertisements over SRMS 470 advertisements. 472 It is common to use the identity of the advertising source router 473 (e.g. router ID) as a tie breaker. However, in the case of SID 474 advertisements it is possible that the source ID is not known. For 475 example, when leaking SRMS advertisements the source ID may appear to 476 be the Area Border Router (ABR) which performed the leaking. But 477 this means that the relative preference of the SIDs associated with 478 the leaked advertisements will have a different priority in different 479 areas. Therefore router ID is not used in the algorithms discussed 480 above. 482 4. IANA Considerations 484 None. 486 5. Security Considerations 488 TBD 490 6. Acknowledgements 492 The authors would like to thank Martin Pilka for sharing his 493 knowledge of algorithm implementation and complexity. 495 7. References 497 7.1. Normative References 499 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 500 Requirement Levels", BCP 14, RFC 2119, 501 DOI 10.17487/RFC2119, March 1997, 502 . 504 7.2. Informational References 506 [SR-ARCH] "Segment Routing Architecture, draft-ietf-spring-segment- 507 routing-05(work in progress)", September 2015. 509 [SR-IS-IS] 510 "IS-IS Extensions for Segment Routing, draft-ietf-isis- 511 segment-routing-extensions-05(work in progress)", June 512 2015. 514 [SR-OSPF] "OSPF Extensions for Segment Routing, draft-ietf-ospf- 515 segment-routing-extensions-05(work in progress)", June 516 2015. 518 Appendix A. Alternate Prefix Conflict Algorithm 520 It is possible when encountering overlapping prefix ranges to allow 521 use of such entries when there is no actual SID conflict. This case 522 can be avoided if configuration of such entries is blocked at the 523 source - which allows a far simpler implementation when processing 524 received entries. The latter model is what is described in the body 525 of this document. What is described below is the algorithm and 526 consequences of trying to use overlapping ranges when the SID 527 assignments do not conflict. 529 The algorithm used to determine if two entries are in conflict is as 530 follows. 532 Given two mapping entries: 534 (P1/L1, S1, R1) and (P2/L2, S2, R2) 536 a prefix conflict exists if all of the following are true: 538 1)The prefixes are in the same address family. 539 2)L1 == L2 540 3)(P1 < P2) && (P1e >= P2) && (((P2-P1)>>(Lx-L)) + S1) != S2) 541 || 542 (P2 < P1 ) && (P2e >= P1) && (((P1-P2)>>(Lx-L)) + S2) != S1) 544 From an implementation standpoint, the complexity comes in supporting 545 lookup of the SID for a given prefix in the presence of overlapping 546 ranges which are in use. Consider the following simple example: 548 Entry #1: (192.0.2.1/32, 100, 250) 550 Entry #2: (192.0.2.101/32, 200, 10) 552 Entry #3: (192.0.2.201/32, 300, 100) 554 Using the conflict detection algorithm described in this section 555 there is no conflict in the three ranges since all prefixes which 556 overlap between the entries are assigned the same SID in all ranges. 558 If however we want to find the SID for the prefix 192.0.2.150, here 559 are the steps one might go through: 561 1)Find the entry with the largest value of starting prefix which is 562 less than or equal to 192.0.2.150. In the example this would be 563 Entry #2 above. 565 2)Determine if the range covers 192.0.2.150. In the example the 566 answer to this would be "no". 568 If we were not required to support overlapping entries at this point 569 we would be done and conclude that no SID was assigned. But because 570 we know that we may have overlapping entries we have to walk 571 backwards (conceptually) and look at all of the entries with starting 572 prefixes (of prefix length 32) which are less than 192.0.2.150 and 573 check if their range is large enough to include that prefix. In the 574 presence of a large # of entries this would be very slow. To avoid 575 this problem we could build a local entry which contained all of 576 overlapping entries (in this example all three of the entries shown) 577 and use that in our actiuve database to do the lookups. In this 578 example we would generate: 580 (192.0.2.1/32, 100, 300) 582 Then we could use steps #1 and #2 above and be confident in the 583 answer we get. 585 However, since we are no longer using the entries we received in our 586 active database we would need to maintain a link between the 587 generated entry and the set of overlapping entries we received which 588 caused its generation so that if one of those entries was removed or 589 modified we could properly update our active database. 591 Authors' Addresses 593 Les Ginsberg 594 Cisco Systems 595 510 McCarthy Blvd. 596 Milpitas, CA 95035 597 USA 599 Email: ginsberg@cisco.com 601 Peter Psenak 602 Cisco Systems 603 Apollo Business Center Mlynske nivy 43 604 Bratislava 821 09 605 Slovakia 607 Email: ppsenak@cisco.com 609 Stefano Previdi 610 Cisco Systems 611 Via Del Serafico 200 612 Rome 0144 613 Italy 615 Email: sprevidi@cisco.com