[Docs] [txt|pdf|xml] [Tracker] [WG] [Email] [Nits]

Versions: 00 01 draft-ietf-spring-conflict-resolution

Networking Working Group                                     L. Ginsberg
Internet-Draft                                                 P. Psenak
Intended status: Standards Track                              S. Previdi
Expires: April 16, 2016                                    Cisco Systems
                                                        October 14, 2015


                  Segment Routing Conflict Resolution
            draft-ginsberg-spring-conflict-resolution-00.txt

Abstract

   In support of Segment Routing (SR) routing protocols advertise a
   variety of identifiers used to define the segments which direct
   forwarding of packets.  In cases where the information advertised by
   a given protocol instance is either internally inconsistent or
   conflicts with advertisements from another protocol instance a means
   of achieving consistent forwarding behavior in the network is
   required.  This document defines the policies used to resolve these
   occurrences.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on April 16, 2016.








Ginsberg, et al.         Expires April 16, 2016                 [Page 1]


Internet-Draft           sr-conflict-resolution             October 2015


Copyright Notice

   Copyright (c) 2015 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

   This document may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008.  The person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to allow
   modifications of such material outside the IETF Standards Process.
   Without obtaining an adequate license from the person(s) controlling
   the copyright in such materials, this document may not be modified
   outside the IETF Standards Process, and derivative works of it may
   not be created outside the IETF Standards Process, except to format
   it for publication as an RFC or to translate it into languages other
   than English.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  SR Global Block Inconsistency . . . . . . . . . . . . . . . .   3
   3.  Segment Identifier Conflicts  . . . . . . . . . . . . . . . .   5
     3.1.  Conflict Types  . . . . . . . . . . . . . . . . . . . . .   6
       3.1.1.  Prefix Conflict . . . . . . . . . . . . . . . . . . .   6
       3.1.2.  SID Conflict  . . . . . . . . . . . . . . . . . . . .   7
     3.2.  Processing conflicting entries  . . . . . . . . . . . . .   8
       3.2.1.  Ignore conflicting entries  . . . . . . . . . . . . .   8
       3.2.2.  Preference Algorithm  . . . . . . . . . . . . . . . .   8
       3.2.3.  Candidate Preference Algorithm  . . . . . . . . . . .   9
       3.2.4.  Example Behavior  . . . . . . . . . . . . . . . . . .   9
       3.2.5.  Other Preference Factors to consider  . . . . . . . .  10
   4.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  11
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  11
   6.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  11
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  11
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .  11
     7.2.  Informational References  . . . . . . . . . . . . . . . .  12
   Appendix A.  Alternate Prefix Conflict Algorithm  . . . . . . . .  12



Ginsberg, et al.         Expires April 16, 2016                 [Page 2]


Internet-Draft           sr-conflict-resolution             October 2015


   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  14

1.  Introduction

   Segment Routing (SR) as defined in [SR-ARCH] utilizes forwarding
   instructions called "segments" to direct packets through the network.
   Depending on the forwarding plane architecture in use, routing
   protocols advertise various identifiers which define the permissible
   values which can be used as segments, which values are assigned to
   specific prefixes, etc.  Where segments have global scope it is
   necessary to have non-conflicting assignments - but given that the
   advertisements may originate from multiple nodes the possibility
   exists that advertisements may be received which are either
   internally inconsistent or conflicting with advertisements originated
   by other nodes.  In such cases it is necessary to have consistent
   resolution of conflicts network-wide in order to avoid forwarding
   loops.

   The problem to be addressed is protocol independent i.e., segment
   related advertisements may be originated by multiple nodes using
   different protocols and yet the conflict resolution MUST be the same
   on all nodes regardless of the protocol used to transport the
   advertisements.

   The remainder of this document defines conflict resolution policies
   which meet these requirements.  All protocols which support SR MUST
   adhere to the policies defined in this document.

2.  SR Global Block Inconsistency

   In support of an MPLS dataplane routing protocols advertise an SR
   Global Block (SRGB) which defines a set of label ranges reserved for
   use by the advertising node in support of SR.  The details of how
   protocols advertise this information can be found in the protocol
   specific drafts e.g., [SR-OSPF] and [SR-IS-IS].  However the protocol
   independent semantics are illustrated by the following example:















Ginsberg, et al.         Expires April 16, 2016                 [Page 3]


Internet-Draft           sr-conflict-resolution             October 2015


   The originating router advertises the following ranges:

         Range 1: (100, 199)
         Range 2: (1000, 1099)
         Range 3: (500, 5990

    The receiving routers concatenate the ranges and build the Segment
    Routing Global Block (SRGB) as follows:

      SRGB = (100, 199)
             (1000, 1099)
             (500, 599)

    The indexes span multiple ranges:

         index=0 means label 100
         ...
         index 99 means label 199
         index 100 means label 1000
         index 199 means label 1099
         ...
         index 200 means label 500
         ...

   Note that the ranges are an ordered set - what labels are mapped to a
   given index depends on the placement of a given label range in the
   set of ranges advertised.

   For the set of ranges to be usable the ranges MUST be disjoint.  The
   question then arises what receiving routers should do if they receive
   an SRGB which includes overlapping ranges.  In such a case the
   following rule is defined:

   Each range is examined in the order it was advertised.  If it does
   not overlap with any advertised range which preceded it the
   advertised range is used.  If the range overlaps with any preceding
   range it MUST NOT be used and all ranges advertised after the first
   encountered overlapping range also MUST NOT be used.

   Consider the following example:











Ginsberg, et al.         Expires April 16, 2016                 [Page 4]


Internet-Draft           sr-conflict-resolution             October 2015


   The originating router advertises the following ranges:

         Range 1: (100, 199]
         Range 2: (1000, 1099)
         Range 3: (100, 599)
         Range 4: (2000, 2099)

   Range 3 overlaps with Range 1.
   Only Ranges #1 and #2 are usable.
   Ranges #3 and #4 are ignored.
   Note that Range #4 is not used even though it does not overlap
   with any of the other ranges.


3.  Segment Identifier Conflicts

   In support of an MPLS dataplane Segment identifiers (SIDs) are
   advertised and associated with a given prefix.  SIDs may be
   advertised in the prefix reachability advertisements originated by a
   routing protocol.  SIDs may also be advertised by a Segment Routing
   Mapping Server (SRMS).

   A generalized mapping entry can be represented using the following
   definitions:

     Pi - Initial prefix
     Pe - End prefix
     L -  Prefix length
     Lx - Maximum prefix length (32 for IPv4, 128 for IPv6)
     Si - Initial SID value
     Se - End SID value
     R -  Range value

     Mapping Entry is then the tuple: (Pi/L, Si, R)
     Pe = (Pi + ((R-1) << (Lx-L))
     Se = Si + (R-1)

     Note that the SID advertised in a prefix reachability advertisement
     can be more generally represented as a mapping entry with a range
     of 1.


   Conflicts in SID advertisements may occur as a result of
   misconfiguration.  Conflicts may occur either in the set of
   advertisements originated by a single node or between advertisements
   originated by different nodes.  When conflicts occur, it is not
   possible for routers to know which of the conflicting advertisements
   is "correct".  If a router chooses to use one of the conflicting



Ginsberg, et al.         Expires April 16, 2016                 [Page 5]


Internet-Draft           sr-conflict-resolution             October 2015


   entries forwarding loops and/or blackholes may result unless it can
   be guaranteed that all other routers in the network make the same
   choice.  Making the same choice requires that all routers have
   identical sets of advertisements and that they all use the same
   selection algorithm.

3.1.  Conflict Types

   Various types of conflicts may occur.

3.1.1.  Prefix Conflict

   When different SIDs are assigned to the same prefix we have a "prefix
   conflict".  Consider the following set of advertisements:

   (192.0.2.120/32, 200, 1)
   (192.0.2.120/32, 30, 1)

   The prefix 192.0.2.120/32 has been assigned two different SIDs - 200
   by the first advertisement - 30 by the second advertisement.

   Prefix conflicts may also occur as a result of overlapping prefix
   ranges.  Consider the following set of advertisements:

   (192.0.2.1/32, 200, 200)
   (192.0.2.121/32, 30, 10)

   Prefixes 192.0.2.121/32 - 192.0.2.130/32 are assigned two different
   SIDs - 320 through 329 by the first advertisement - 30 through 39 by
   the second advertisement.

   The second example illustrates a complication - only part of the
   range advertised in the first advertisement is in conflict.  It is
   logically possible to isolate the conflicting portion and try to use
   the non-conflicting portion(s) at the cost of increased
   implementation complexity.  The algorithm defined here does NOT
   attempt to support use of a partial range.

   A variant of the overlapping prefix range is a case where we have
   overlapping prefix ranges but no actual SID conflict.

   (192.0.2.1/32, 200, 200)
   (192.0.2.121/32, 320, 10)

   Although there is prefix overlap between the two entries the same SID
   is assigned to all of the shared prefixes by the two entries.  It is
   possible to utilize both entries but it complicates the
   implementation of the database required to support this.  See



Ginsberg, et al.         Expires April 16, 2016                 [Page 6]


Internet-Draft           sr-conflict-resolution             October 2015


   Appendix A for a more complete discussion of this case.  An
   alternative is to ensure at the nodes which originate these
   advertisements that no such overlap is allowed to be configured.
   Such overlaps can then be considered as a conflict if they are
   received.  This allows a simpler and more efficient implementation of
   the database.  This is the approach assumed in this document.

   Given two mapping entries:

   (P1/L1, S1, R1) and (P2/L2, S2, R2)

   a prefix conflict exists if all of the following are true:

   1)The prefixes are in the same address family.
   2)L1 == L2
   3)((P1 < P2) && (P1e >= P2)) || ((P2 < P1 ) && (P2e >= P1))


3.1.2.  SID Conflict

   When the same SID has been assigned to multiple prefixes we have a
   "SID conflict".  Consider the following example:

   (192.0.2.1/32, 200, 1)
   (192.0.2.222/32, 200,1)


   SID 200 has been assigned to 192.0.2.1/32 by the first advertisement.
   The second advertisement assigns SID 200 to 192.0.2.222/32.

   SID conflicts may also occur as a result of overlapping SID ranges.
   Consider the following set of advertisements:

   (192.0.2.1/32, 200, 200)
   (192.1.2.1/32, 300, 10)


   SIDs 300 - 309 have been assigned to two different prefixes.  The
   first advertisement assigns these SIDs to 192.0.2.101/32 -
   192.0.2.110/32.  The second advertisement assigns these SIDs to
   192.1.2.1/32 - 192.1.2.10/32.

   The second example illustrates a complication - only part of the
   range advertised in the first advertisement is in conflict.  It is
   logically possible to isolate the conflicting portion and try to use
   the non-conflicting portion(s) at the cost of increased
   implementation complexity.  The algorithm defined here does NOT
   attempt to support use of a partial range.



Ginsberg, et al.         Expires April 16, 2016                 [Page 7]


Internet-Draft           sr-conflict-resolution             October 2015


   SID conflicts are independent of address-family and independent of
   prefix len.  A SID conflict occurs when a mapping entry which has
   previously been checked to have no prefix conflict assigns one or
   more SIDs that are assigned by another entry which also has no prefix
   conflicts.

3.2.  Processing conflicting entries

   Two general approaches can be used to process conflicting entries.

   1.  Conflicting entries can be ignored

   2.  A standard preference algorithm can be used to choose which of
       the conflicting entries will be used

   The following sections discuss these two approaches in more detail.

   Note: This document does not discuss any implementation details i.e.
   what type of data structure is used to store the entries (trie, radix
   tree, etc.) nor what type of keys may be used to perform lookups in
   the database.

3.2.1.  Ignore conflicting entries

   In cases where entries are in conflict none of the conflicting
   entries are used i.e., the network operates as if the conflicting
   advertisements were not present.

   Ikplementation requires identifying the conflicting entries and
   ensuring that they are not used.  The occurrence of conflicts is
   easily diagnosed from the behavior of the network as the forwarding
   of traffic which would, in the absence of conflicts, utilize segments
   no longer does so.  Which prefixes are impacted is easily seen and
   therefore the entries which are misconfigured are easily identified.
   Unintended traffic flow will never occur.

   The downside of ignoring conflicting entries is that forwarding of
   all packets with destinations covered by the conflicting entries will
   always be negatively impacted.

3.2.2.  Preference Algorithm

   For entries which are in conflict properties of the advertisement
   (e.g. prefix value, prefix length, SID value, etc.) are used to
   determine which of the conflicting entries are used in forwarding and
   which are ignored.





Ginsberg, et al.         Expires April 16, 2016                 [Page 8]


Internet-Draft           sr-conflict-resolution             October 2015


   This approach requires that conflicting entries first be identified
   and then evaluated based on the preference rule.  Based on which
   entry is preferred this in turn may impact what other entries are
   considered in conflict i.e. if A conflicts with B and B conflicts
   with C - it is possible that A does NOT conflict with C.  Hence if as
   a result of the evaluation of the conflict between A and B, entry B
   is not used the conflict between B and C will not be considered.

   As at least some of the traffic continues to be forwarded after the
   conflict is detected, the presence of the conflict may be harder to
   diagnose based on traffic flowthan when using the ignore policy.

   The upside of the preference algorithm is that in some cases
   forwarding of traffic may continue to be correct despite the
   existence of the conflict.  If the preference algorithm happens to
   prefer the intended configuration traffic will still be successfully
   delivered.  Whether this will occur is a random outcome since the
   preference algorithm cannot know which of the conflicting entries is
   the "correct" entry.

3.2.3.  Candidate Preference Algorithm

   The following algorithm is proposed.  Evaluation is made in the order
   specified.

   1.  IPv4 entry wins over IPv6 entry

   2.  Smaller prefix length wins

   3.  Smaller starting address (considered as an unsigned integer
       value) wins

   4.  Smaller starting SID wins

   5.  Smaller range wins

   6.  non-attached entries preferred over attached entries (SRMS
       attached flag)

3.2.4.  Example Behavior

   Consider the following simple case.  The following mapping entries
   exist:

   1.  (192.0.2.1/32, 100, 200)

   2.  (192.0.2.200/32, 150, 300) !Prefix conflict with entry #1




Ginsberg, et al.         Expires April 16, 2016                 [Page 9]


Internet-Draft           sr-conflict-resolution             October 2015


   3.  (193.3.3.3/32, 400, 100) !SID conflict with entry #2

   Using the Ignore conflicts behavior we would not use any of the above
   entries.

   Using a preference rule which favors smaller prefixes, entries #1 and
   #3 would be used.

   o  Entry #1 would be used as 192.0.200.1 is less than 192.0.2.200.

   o  Entry #3 would be used because once Entry #2 has been excluded,
      entry #3 no longer conflicts with any entry which is being used.
      (An example of lack of transitivity of conflicts)

   If we now add

      4. (192.0.1.1/32, 50, 100) ! Prefix conflict with #1

   Using ignore policy still none of the entries would be used.

   Using a preference rule which favors smaller prefixes , entries #4
   and #2 would be used.

   o  Entry #4 would be used in preference to entry #1 because 192.0.1.1
      < 192.0.2.1.

   o  Entry #2 would be used because once Entry #1 is excluded entry #2
      no longer has a prefix conflict with any active entry.

   o  Entry #3 would NOT be used because once Entry #2 becomes active
      entry #3 loses due to the SID conflict with Entry #2 since the
      latter has a smaller prefix.

3.2.5.  Other Preference Factors to consider

   Prefix to SID mapping is based on a variety of sources.

   o  SIDs can be configured locally for prefixes assigned to interfaces
      on the router itself

   o  SIDs can be received in prefix reachability advertisements from
      protocol peers.  These advertisements may originate from peers
      local to the area or be leaked from other areas and/or
      redistributed from other routing protocols

   o  SIDs can be received from SRMS advertisements - these
      advertisements can originate from routers local to the area or
      leaked from other areas



Ginsberg, et al.         Expires April 16, 2016                [Page 10]


Internet-Draft           sr-conflict-resolution             October 2015


   SIDs configured locally for prefixes associated with interfaces on
   the router itself are only used by the originating router in prefix
   advertisements - they are not installed in the forwarding plane
   locally.  Therefore, they do not need to be considered in conflict
   resolution.

   For other sources, It may seem intuitive to assign priority based on
   point of origination (e.g. intra-area preferred over inter-area,
   prefix reachability advertisements preferred over SRMS
   advertisements, etc.).  However, any such policy makes it more likely
   that inconsistent choices will be made by routers in the network and
   increase the likelihood of forwarding loops or blackholes.  The
   algorithms defined in this document assume that prefix reachability
   advertisements are part of the set of entries considered when
   determining conflicts and conflict resolution and no preference is
   associated with prefix reachability advertisements over SRMS
   advertisements.

   It is common to use the identity of the advertising source router
   (e.g. router ID) as a tie breaker.  However, in the case of SID
   advertisements it is possible that the source ID is not known.  For
   example, when leaking SRMS advertisements the source ID may appear to
   be the Area Border Router (ABR) which performed the leaking.  But
   this means that the relative preference of the SIDs associated with
   the leaked advertisements will have a different priority in different
   areas.  Therefore router ID is not used in the algorithms discussed
   above.

4.  IANA Considerations

   None.

5.  Security Considerations

   TBD

6.  Acknowledgements

   The authors would like to thank Martin Pilka for sharing his
   knowledge of algorithm implementation and complexity.

7.  References

7.1.  Normative References







Ginsberg, et al.         Expires April 16, 2016                [Page 11]


Internet-Draft           sr-conflict-resolution             October 2015


   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.

7.2.  Informational References

   [SR-ARCH]  "Segment Routing Architecture, draft-ietf-spring-segment-
              routing-05(work in progress)", September 2015.

   [SR-IS-IS]
              "IS-IS Extensions for Segment Routing, draft-ietf-isis-
              segment-routing-extensions-05(work in progress)", June
              2015.

   [SR-OSPF]  "OSPF Extensions for Segment Routing, draft-ietf-ospf-
              segment-routing-extensions-05(work in progress)", June
              2015.

Appendix A.  Alternate Prefix Conflict Algorithm

   It is possible when encountering overlapping prefix ranges to allow
   use of such entries when there is no actual SID conflict.  This case
   can be avoided if configuration of such entries is blocked at the
   source - which allows a far simpler implementation when processing
   received entries.  The latter model is what is described in the body
   of this document.  What is described below is the algorithm and
   consequences of trying to use overlapping ranges when the SID
   assignments do not conflict.

   The algorithm used to determine if two entries are in conflict is as
   follows.

   Given two mapping entries:

   (P1/L1, S1, R1) and (P2/L2, S2, R2)

   a prefix conflict exists if all of the following are true:

   1)The prefixes are in the same address family.
   2)L1 == L2
   3)(P1 < P2) && (P1e >= P2) && (((P2-P1)>>(Lx-L)) + S1) != S2)
      ||
     (P2 < P1 ) && (P2e >= P1) && (((P1-P2)>>(Lx-L)) + S2) != S1)







Ginsberg, et al.         Expires April 16, 2016                [Page 12]


Internet-Draft           sr-conflict-resolution             October 2015


   From an implementation standpoint, the complexity comes in supporting
   lookup of the SID for a given prefix in the presence of overlapping
   ranges which are in use.  Consider the following simple example:

   Entry #1: (192.0.2.1/32, 100, 250)

   Entry #2: (192.0.2.101/32, 200, 10)

   Entry #3: (192.0.2.201/32, 300, 100)

   Using the conflict detection algorithm described in this section
   there is no conflict in the three ranges since all prefixes which
   overlap between the entries are assigned the same SID in all ranges.

   If however we want to find the SID for the prefix 192.0.2.150, here
   are the steps one might go through:

   1)Find the entry with the largest value of starting prefix which is
   less than or equal to 192.0.2.150.  In the example this would be
   Entry #2 above.

   2)Determine if the range covers 192.0.2.150.  In the example the
   answer to this would be "no".

   If we were not required to support overlapping entries at this point
   we would be done and conclude that no SID was assigned.  But because
   we know that we may have overlapping entries we have to walk
   backwards (conceptually) and look at all of the entries with starting
   prefixes (of prefix length 32) which are less than 192.0.2.150 and
   check if their range is large enough to include that prefix.  In the
   presence of a large # of entries this would be very slow.  To avoid
   this problem we could build a local entry which contained all of
   overlapping entries (in this example all three of the entries shown)
   and use that in our actiuve database to do the lookups.  In this
   example we would generate:

   (192.0.2.1/32, 100, 300)

   Then we could use steps #1 and #2 above and be confident in the
   answer we get.

   However, since we are no longer using the entries we received in our
   active database we would need to maintain a link between the
   generated entry and the set of overlapping entries we received which
   caused its generation so that if one of those entries was removed or
   modified we could properly update our active database.





Ginsberg, et al.         Expires April 16, 2016                [Page 13]


Internet-Draft           sr-conflict-resolution             October 2015


Authors' Addresses

   Les Ginsberg
   Cisco Systems
   510 McCarthy Blvd.
   Milpitas, CA  95035
   USA

   Email: ginsberg@cisco.com


   Peter Psenak
   Cisco Systems
   Apollo Business Center Mlynske nivy 43
   Bratislava  821 09
   Slovakia

   Email: ppsenak@cisco.com


   Stefano Previdi
   Cisco Systems
   Via Del Serafico 200
   Rome  0144
   Italy

   Email: sprevidi@cisco.com
























Ginsberg, et al.         Expires April 16, 2016                [Page 14]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/