draft-ietf-spring-conflict-resolution-04.txt   draft-ietf-spring-conflict-resolution-05.txt 
Networking Working Group L. Ginsberg Networking Working Group L. Ginsberg
Internet-Draft P. Psenak Internet-Draft P. Psenak
Intended status: Standards Track S. Previdi Intended status: Standards Track S. Previdi
Expires: November 25, 2017 Cisco Systems Expires: January 3, 2018 Cisco Systems
M. Pilka M. Pilka
May 24, 2017 July 2, 2017
Segment Routing MPLS Conflict Resolution Segment Routing MPLS Conflict Resolution
draft-ietf-spring-conflict-resolution-04.txt draft-ietf-spring-conflict-resolution-05.txt
Abstract Abstract
In support of Segment Routing (SR) for an MPLS data plane routing In support of Segment Routing (SR) for an MPLS data plane routing
protocols advertise a variety of identifiers used to define the protocols advertise a variety of identifiers used to define the
segments which direct forwarding of packets. In cases where the segments which direct forwarding of packets. In cases where the
information advertised by a given protocol instance is either information advertised by a given protocol instance is either
internally inconsistent or conflicts with advertisements from another internally inconsistent or conflicts with advertisements from another
protocol instance a means of achieving consistent forwarding behavior protocol instance a means of achieving consistent forwarding behavior
in the network is required. This document defines the policies used in the network is required. This document defines the policies used
skipping to change at page 1, line 45 skipping to change at page 1, line 45
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 25, 2017. This Internet-Draft will expire on January 3, 2018.
Copyright Notice Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the Copyright (c) 2017 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 26 skipping to change at page 2, line 26
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. SR Global Block Inconsistency . . . . . . . . . . . . . . . . 3 2. SR Global Block Inconsistency . . . . . . . . . . . . . . . . 3
3. SR-MPLS Segment Identifier Conflicts . . . . . . . . . . . . 5 3. SR-MPLS Segment Identifier Conflicts . . . . . . . . . . . . 5
3.1. SID Preference . . . . . . . . . . . . . . . . . . . . . 6 3.1. SID Preference . . . . . . . . . . . . . . . . . . . . . 6
3.2. Conflict Types . . . . . . . . . . . . . . . . . . . . . 6 3.2. Conflict Types . . . . . . . . . . . . . . . . . . . . . 7
3.2.1. Prefix Conflict . . . . . . . . . . . . . . . . . . . 7 3.2.1. Prefix Conflict . . . . . . . . . . . . . . . . . . . 7
3.2.2. SID Conflict . . . . . . . . . . . . . . . . . . . . 8 3.2.2. SID Conflict . . . . . . . . . . . . . . . . . . . . 9
3.3. Preference rule for resolving conflicts . . . . . . . . . 10 3.3. Preference rule for resolving conflicts . . . . . . . . . 12
3.4. Conflict Resolution Algorithm . . . . . . . . . . . . . . 11 3.4. Conflict Resolution Algorithm . . . . . . . . . . . . . . 13
3.5. Example Behavior - Single Topology/Address 3.5. Example Behavior - Single Topology/Address
Family/Algorithm . . . . . . . . . . . . . . . . . . . . 13 Family/Algorithm . . . . . . . . . . . . . . . . . . . . 14
3.6. Example Behavior - Multiple Topologies . . . . . . . . . 13 3.6. Example Behavior - Multiple Topologies . . . . . . . . . 15
3.7. Guaranteeing Database Consistency . . . . . . . . . . . . 14 3.7. Guaranteeing Database Consistency . . . . . . . . . . . . 16
3.8. Minimizing the occurence of conflicts . . . . . . . . . . 14 3.8. Minimizing the occurence of conflicts . . . . . . . . . . 16
4. Scope of SR-MPLS SID Conflicts . . . . . . . . . . . . . . . 15 4. Scope of SR-MPLS SID Conflicts . . . . . . . . . . . . . . . 16
5. Conflict Resolution and non-forwarding nodes . . . . . . . . 16 5. Conflict Resolution and non-forwarding nodes . . . . . . . . 17
6. Security Considerations . . . . . . . . . . . . . . . . . . . 16 6. Security Considerations . . . . . . . . . . . . . . . . . . . 17
7. IANA Consideration . . . . . . . . . . . . . . . . . . . . . 16 7. IANA Consideration . . . . . . . . . . . . . . . . . . . . . 18
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 16 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 16 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.1. Normative References . . . . . . . . . . . . . . . . . . 16 9.1. Normative References . . . . . . . . . . . . . . . . . . 18
9.2. Informational References . . . . . . . . . . . . . . . . 17 9.2. Informational References . . . . . . . . . . . . . . . . 19
Appendix A. Alternative SID Conflict Resolution Policy Appendix A. Alternative SID Conflict Resolution Policy
Discussion . . . . . . . . . . . . . . . . . . . . . 17 Discussion . . . . . . . . . . . . . . . . . . . . . 19
A.1. Policy: Ignore conflicting entries . . . . . . . . . . . 17 A.1. Policy: Ignore conflicting entries . . . . . . . . . . . 19
A.2. Policy: Preference Algorithm/Quarantine . . . . . . . . . 18 A.2. Policy: Preference Algorithm/Quarantine . . . . . . . . . 19
A.3. Policy: Preference algorithm/ignore overlap only . . . . 18 A.3. Policy: Preference algorithm/ignore overlap only . . . . 20
A.4. Example Behavior - Single Topology/Address A.4. Example Behavior - Single Topology/Address
Family/Algorithm . . . . . . . . . . . . . . . . . . . . 18 Family/Algorithm . . . . . . . . . . . . . . . . . . . . 20
A.5. Evaluation of Policy Alternatives . . . . . . . . . . . . 19 A.5. Evaluation of Policy Alternatives . . . . . . . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22
1. Introduction 1. Introduction
Segment Routing (SR) as defined in [SR-ARCH] utilizes forwarding Segment Routing (SR) as defined in [SR-ARCH] utilizes forwarding
instructions called "segments" to direct packets through the network. instructions called "segments" to direct packets through the network.
Depending on the forwarding plane architecture in use, routing Depending on the forwarding plane architecture in use, routing
protocols advertise various identifiers which define the permissible protocols advertise various identifiers which define the permissible
values which can be used as segments, which values are assigned to values which can be used as segments, which values are assigned to
specific prefixes, etc. Where segments have global scope it is specific prefixes, etc. Where segments have global scope it is
necessary to have non-conflicting assignments - but given that the necessary to have non-conflicting assignments - but given that the
skipping to change at page 5, line 37 skipping to change at page 5, line 37
T - Topology T - Topology
A - Algorithm (see [SR-ARCH]) A - Algorithm (see [SR-ARCH])
A Mapping Entry is then the tuple: (Prf, Pi/L, Si, R, T, A) A Mapping Entry is then the tuple: (Prf, Pi/L, Si, R, T, A)
Pe = (Pi + ((R-1) << (Lx-L)) Pe = (Pi + ((R-1) << (Lx-L))
Se = Si + (R-1) Se = Si + (R-1)
NOTE 1: The SID advertised in a prefix reachability advertisement NOTE 1: The SID advertised in a prefix reachability advertisement
always has an implicit range of 1. always has an implicit range of 1.
NOTE 2: IPv4/IPv6 addresses can be viewed as 32/128 bit integers.
Where operations such as addition, subtraction, and/or
bit shifting are specified for prefixes this should be
interpreted as operations on the integer representation
of a prefix.
Note: Topology is a locally scoped identifier assigned by each Note: Topology is a locally scoped identifier assigned by each
router. Although it may have an association with Multitopology router. Although it may have an association with Multitopology
Identifiers (MTID) advertised by routing protocols it is NOT Identifiers (MTID) advertised by routing protocols it is NOT
equivalent to these identifiers. MTIDs are scoped by a given routing equivalent to these identifiers. MTIDs are scoped by a given routing
protocol. MTID ranges are protocol specific and there may be protocol. MTID ranges are protocol specific and there may be
standardized protocol specific MTID assignments for topologies of a standardized protocol specific MTID assignments for topologies of a
specific type (e.g., an AFI specific topology). As mapping entries specific type (e.g., an AFI specific topology). As mapping entries
can be sourced from multiple protocols it is not possible to use a can be sourced from multiple protocols it is not possible to use a
network scoped identifier for a topology when storing mapping entries network scoped identifier for a topology when storing mapping entries
in the local datbase. in the local datbase.
skipping to change at page 6, line 47 skipping to change at page 7, line 9
mapping entry originated within the domain to become unusable as this mapping entry originated within the domain to become unusable as this
would introduce inconsistency in the set of SIDs considered usable by would introduce inconsistency in the set of SIDs considered usable by
a node which has the BGP originated mapping entries and the set a node which has the BGP originated mapping entries and the set
considered usable by nodes without the BGP originated mapping considered usable by nodes without the BGP originated mapping
entries. entries.
3.2. Conflict Types 3.2. Conflict Types
Two types of conflicts may occur - Prefix Conflicts and SID Two types of conflicts may occur - Prefix Conflicts and SID
Conflicts. Examples are provided in this section to illustrate these Conflicts. Examples are provided in this section to illustrate these
conflict types. conflict types and generic definitions of algorithms to determine
when there is a conflict are presented.
3.2.1. Prefix Conflict 3.2.1. Prefix Conflict
When different SIDs are assigned to the same prefix we have a "prefix When different SIDs are assigned to the same prefix we have a "prefix
conflict". Prefix conflicts are limited to mapping entries sharing conflict". Prefix conflicts are limited to mapping entries sharing
the same topology and algorithm. the same topology, algorithm, address-family, and prefix length.
3.2.1.1. Prefix Conflict Examples
The simplest example is when two advertisements with a range of 1
assign different SIDs to the same prefix.
Example PC1 Example PC1
(192, 192.0.2.120/32, 200, 1, 0, 0) (192, 192.0.2.120/32, 200, 1, 0, 0)
(192, 192.0.2.120/32, 30, 1, 0, 0) (192, 192.0.2.120/32, 30, 1, 0, 0)
The prefix 192.0.2.120/32 has been assigned two different SIDs: The prefix 192.0.2.120/32 has been assigned two different SIDs:
200 by the first advertisement 200 by the first advertisement
30 by the second advertisement 30 by the second advertisement
skipping to change at page 8, line 23 skipping to change at page 8, line 45
(128, 192.0.2.1/32, 200, 200, 0, 0) (128, 192.0.2.1/32, 200, 200, 0, 0)
(128, 192.0.2.121/32, 320, 10, 0, 0) (128, 192.0.2.121/32, 320, 10, 0, 0)
(128, 2001:DB8::1/128, 400, 200, 2, 0) (128, 2001:DB8::1/128, 400, 200, 2, 0)
(128, 2001:DB8::121/128, 520, 10, 2, 0) (128, 2001:DB8::121/128, 520, 10, 2, 0)
Although there is prefix overlap between the two IPv4 entries (and Although there is prefix overlap between the two IPv4 entries (and
the two IPv6 entries) the same SID is assigned to all of the shared the two IPv6 entries) the same SID is assigned to all of the shared
prefixes by the two entries. prefixes by the two entries.
3.2.1.2. Prefix Conflict Generic Algorithm
The following generic algorithm can be used to determine when any two
mapping entries have Prefix Conflicts and what the set of prefixes in
conflict are.
Given two mapping entries: Given two mapping entries:
(Prf, P1/L1, S1, R1, T1, A1) and (Prf, P1/L1, S1, R1, T1, A1) and
(Prf, P2/L2, S2, R2, T2, A2) (Prf, P2/L2, S2, R2, T2, A2)
where P1 <= P2 where P1 <= P2
a prefix conflict exists if all of the following are true: a prefix conflict exists if all of the following are true:
1)(T1 == T2) && (A1 == A2) && (L1 == L2) 1)Topologies, algorithms, and prefix lengths are identical
2)The prefixes are in the same address family.
3)(P1e >= P2) && ((S1 + (P2 - P1)) != S2) (T1 == T2) && (A1 == A2) && (L1 == L2)
2)The prefixes are in the same address-family.
3)If there are overlapping prefixes in the two ranges and
if there are different SIDs assigned to any of the prefixes
in the overlapping range
(P1e >= P2) && ((S1 + ((P2 - P1) >> (Lx-L1)) != S2)
Prefixes in the following range are in conflict: Prefixes in the following range are in conflict:
P2 through MIN(P1e,P2e) P2 through MIN(P1e,P2e)
3.2.2. SID Conflict 3.2.2. SID Conflict
When the same SID has been assigned to multiple prefixes we have a When the same SID has been assigned to multiple prefixes we have a
"SID conflict". SID conflicts are independent of address-family, "SID conflict". SID conflicts are independent of address-family,
independent of prefix len, independent of topology, and independent independent of prefix len, independent of topology, and independent
of algorithm. of algorithm.
3.2.2.1. SID Conflict Examples
The simplest example is when two mapping entries with a range of 1
assigns different SIDs to the same prefix.
Example SC1 Example SC1
(192, 192.0.2.1/32, 200, 1, 0, 0) (192, 192.0.2.1/32, 200, 1, 0, 0)
(192, 192.0.2.222/32, 200, 1, 0, 0) (192, 192.0.2.222/32, 200, 1, 0, 0)
SID 200 has been assigned to 192.0.2.1/32 by the SID 200 has been assigned to 192.0.2.1/32 by the
first advertisement. first advertisement.
The second advertisement assigns SID 200 to 192.0.2.222/32. The second advertisement assigns SID 200 to 192.0.2.222/32.
Example SC2 Example SC2
skipping to change at page 10, line 5 skipping to change at page 10, line 47
SIDs 500 - 509 have been assigned to two different prefixes. SIDs 500 - 509 have been assigned to two different prefixes.
The first advertisement assigns these SIDs to The first advertisement assigns these SIDs to
2001:DB8::101/128 - 2001:DB8::10A/128. 2001:DB8::101/128 - 2001:DB8::10A/128.
The second advertisement assigns these SIDs to The second advertisement assigns these SIDs to
2001:DB8:1::1/128 - 2001:DB8:1::A/128. 2001:DB8:1::1/128 - 2001:DB8:1::A/128.
Examples SC3 and SC4 illustrate a complication - only part of the Examples SC3 and SC4 illustrate a complication - only part of the
range advertised in the first advertisement is in conflict. range advertised in the first advertisement is in conflict.
SID conflicts may also occur because the same SID has been used in
two different algorithms, two different topologies, two different
address families, or prefixes with two different lengths.
Example SC5
(128, 192.0.2.1/32, 200, 1, 0, 0)
(128, 192.0.2.1/32, 200, 1, 0, 1)
SID 200 has been assigned to the same prefix with two different
algorithms.
Example SC6
(128, 192.0.2.1/32, 200, 1, 0, 0)
(128, 2001:DB8::1/128, 200, 1, 0, 0)
SID 200 has been assigned to prefixes in two different
address-families.
3.2.2.2. SID Conflict Generic Algorithm
The following generic algorithm can be used to determine when any two
mapping entries have SID Conflicts and what the set of SIDs in
conflict are.
Given two mapping entries: Given two mapping entries:
(Prf, P1/L1, S1, R1, T1, A1) and (Prf, P1/L1, S1, R1, T1, A1) and
(Prf, P2/L2, S2, R2, T2, A2) (Prf, P2/L2, S2, R2, T2, A2)
where S1 <= S2
a SID conflict exists if all of the following are true: a SID conflict exists if all of the following are true:
1)S1e >= S2 1)If the SID ranges overlap
2)P1 and P2 are NOT in the same address family OR
L1 != L2 OR (S1 <= S2) && (S1e >= S2)
(P1 + ((S1e-S2) << (L1x-L1))) != P2
2)If the same SID is assigned to prefixes with different
address-families, prefix lengths, topologies,
or algorithms or the same SID is assigned to two
different prefixes for any of the prefixes in either
range.
P1 and P2 are NOT in the same address family OR
L1 != L2 OR
T1 != T2 OR
A1 != A2 OR
(P1 + ((S1e-S2) << (L1x-L1))) != P2
SIDs in the following range are in conflict: SIDs in the following range are in conflict:
S2 through MIN(S1e,S2e) S2 through MIN(S1e,S2e)
3.3. Preference rule for resolving conflicts 3.3. Preference rule for resolving conflicts
When a conflict is detected the following algorithm is used to select When a conflict is detected the following algorithm is used to select
the preferred mapping entry. Evaluation is made in the order the preferred mapping entry. Evaluation is made in the order
specified. Prefix conflicts are evaluated first. SID conflicts are specified. Prefix conflicts are evaluated first. SID conflicts are
skipping to change at page 17, line 6 skipping to change at page 18, line 31
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <http://www.rfc-editor.org/info/rfc2119>.
[RFC4364] Rosen, E. and Y. Rekhter, "BGP/MPLS IP Virtual Private [RFC4364] Rosen, E. and Y. Rekhter, "BGP/MPLS IP Virtual Private
Networks (VPNs)", RFC 4364, DOI 10.17487/RFC4364, February Networks (VPNs)", RFC 4364, DOI 10.17487/RFC4364, February
2006, <http://www.rfc-editor.org/info/rfc4364>. 2006, <http://www.rfc-editor.org/info/rfc4364>.
[SR-BGP] "Segment Routing Prefix SID extensions for BGP, draft- [SR-BGP] "Segment Routing Prefix SID extensions for BGP, draft-
ietf-idr-bgp-prefix-sid-05(work in progress)", April 2017. ietf-idr-bgp-prefix-sid-06(work in progress)", June 2017.
[SR-IS-IS] [SR-IS-IS]
"IS-IS Extensions for Segment Routing, draft-ietf-isis- "IS-IS Extensions for Segment Routing, draft-ietf-isis-
segment-routing-extensions-12(work in progress)", April segment-routing-extensions-13(work in progress)", June
2017. 2017.
[SR-MPLS] "Segment Routing with MPLS dataplane, draft-ietf-spring- [SR-MPLS] "Segment Routing with MPLS dataplane, draft-ietf-spring-
segment-routing-mpls-08(work in progress)", March 2017. segment-routing-mpls-10(work in progress)", June 2017.
[SR-OSPF] "OSPF Extensions for Segment Routing, draft-ietf-ospf- [SR-OSPF] "OSPF Extensions for Segment Routing, draft-ietf-ospf-
segment-routing-extensions-16(work in progress)", May segment-routing-extensions-17(work in progress)", June
2017. 2017.
[SR-OSPFv3] [SR-OSPFv3]
"OSPFv3 Extensions for Segment Routing, draft-ietf-ospf- "OSPFv3 Extensions for Segment Routing, draft-ietf-ospf-
ospfv3-segment-routing-extensions-09(work in progress)", ospfv3-segment-routing-extensions-09(work in progress)",
March 2017. March 2017.
9.2. Informational References 9.2. Informational References
[SR-ARCH] "Segment Routing Architecture, draft-ietf-spring-segment- [SR-ARCH] "Segment Routing Architecture, draft-ietf-spring-segment-
routing-11(work in progress)", February 2017. routing-12(work in progress)", June 2017.
Appendix A. Alternative SID Conflict Resolution Policy Discussion Appendix A. Alternative SID Conflict Resolution Policy Discussion
A number of approaches to resolving SID conflicts were considered A number of approaches to resolving SID conflicts were considered
during the writing of this document. Two general approaches with a during the writing of this document. Two general approaches with a
total of three policy alternatives were considered. This total of three policy alternatives were considered. This
Appendix documents the alternatives considered. All content in this Appendix documents the alternatives considered. All content in this
section is non-normative. section is non-normative.
Two general approaches can be used to process conflicting entries. Two general approaches can be used to process conflicting entries.
skipping to change at page 20, line 40 skipping to change at page 22, line 25
Peter Psenak Peter Psenak
Cisco Systems Cisco Systems
Apollo Business Center Mlynske nivy 43 Apollo Business Center Mlynske nivy 43
Bratislava 821 09 Bratislava 821 09
Slovakia Slovakia
Email: ppsenak@cisco.com Email: ppsenak@cisco.com
Stefano Previdi Stefano Previdi
Cisco Systems Cisco Systems
Via Del Serafico 200
Rome 0144
Italy
Email: sprevidi@cisco.com Email: stefano@previdi.net
Martin Pilka Martin Pilka
Email: martin@infobox.sk Email: martin@infobox.sk
 End of changes. 25 change blocks. 
47 lines changed or deleted 109 lines changed or added

This html diff was produced by rfcdiff 1.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/