Re: [spring] SID Conflict Resolution: A Simpler Proposal

[<[e-mail]>]

Les,

Please see inline [Buno]

From: Les Ginsberg (ginsberg) [mailto:[e-mail]]
Sent: Tuesday, December 13, 2016 3:07 AM
To: DECRAENE Bruno IMT/OLN
Cc: [e-mail]
Subject: RE: SID Conflict Resolution: A Simpler Proposal

Bruno -

There is absolutely nothing in the draft which discusses implementation choices. In Section 3.3.7 there is a conceptual discussion that states in part:

"Mapping entries with a range greater than
   1 which are in conflict with other mapping entries have to internally
   be split into 2 or more "derived mapping entries".  The derived
   mapping entries then fall into two categories - those that are in
   conflict with other mapping entries and those which are NOT in
   conflict.  The former are ignored and the latter are used."

This isn't specifying an implementation data structure - it is simply stating the fact that for a mapping entry with a range greater than one has to be to identify which portions of that mapping entry are "unusable" because of conflict and which portions are usable. Conceptually this results in "derived mapping entries"
[Bruno] Equally conceptually, this result in decompressing the Mapping Server (MS) range by attaching the MS SID to each FEC. Then we get a per FEC resolution. IMHO I find this concept less complex.
- but how one chooses to implement them is deliberately not stated. One could (as you suggest below) expand the entry into individual per FEC entries - or one could associate some adjunct data structure which tracks the usability status of each prefix - or one could recalculate the conflict on demand whenever one needs to know the usable SID for a prefix and eliminate the need for additional data structures - or one could link child derived mapping entries to the "raw" received mapping entry. The draft is agnostic in this regard.

[Bruno] My use of the term « data structure » was probably incorrect. However the draft does propose a specific algorithm (split mapping entries) with an associated "Information Model" (derived entries). Then slides and discussion highlight the complexity of this algorithm, which brings some specific additional points perceived as additional complexity. e.g. we now need to specify whether the preference is to use the protocol entries or the derived entries.
My point is that such text, discussions and perceived complexity is specific to this algorithm, and standardizing this is debatable. e.g. some implementation may feel obliged to use this algorithm. I'd rather have a text which is not specific to the algorithm used to achieve the end result/rule.

The point I am making is that there are two issues which only arise with "ignore overlap only":

1)One has to come up with a way to track the usability of each prefix/SID pair covered by the advertised range while still remembering the original advertisement because the granularity of usability is NOT the raw advertisement
[Bruno] Agreed. One has to "decompress" the Mapping Server range field. But to me this is specific to the choice made to compress this information. The (de)compression algo seems reasonably simple to me.
If we don't want to handle the decompression on the receiving side, because this is too complex, then we probably shouldn't compress it in the first place. This would typically require the network operator to decompress it in the configuration file of the Mapping Server (sending side). Even for such a non-software professional, the script seems doable. But on the protocol side, this would present a scaling impact to have the Mapping Server advertise 100s of individual FEC. And the justification for this seem poor (it's too complex for a software company to write the code to decompress the range field, so we chose to ask N network operators to write the script to generate 100s of configuration lines, by mostly decompressing the range field).

2)When one implements the conflict resolution algorithm there are subtleties which can affect the outcome which are peculiar to "ignore overlap only" because of the possible partial use of a raw mapping entry. See Slide 18 of the slides for IETF97.
[Bruno] Exactly my point. This slide and subtleties are specific to the specific algorithm chosen. Alternatively, if you decompress the received mapping entries, you don't have such subtleties/complexity

Neither of these issue arise with "Ignore".

Now, can we specify the normative behavior of "ignore overlap only" such that it is clear? Yes
Is it possible to implement "ignore overlap only"? Yes

However, bugs exist despite everyone's best efforts, and part of the argument for simplicity includes:


·         Simpler requirements make implementation bugs less likely

·         As conflict resolution is an error pathway it inevitably gets exercised less often - so bugs are less likely to be found
[Bruno] Debatable. By design, we'll need redundant MS hence redundant MS entries. Then if MS is used to incrementally deploy SR in a LDP network, which was its goal, we'll also have SID prefix entries. So in nominal case, we'll have 2 or 3 SID advertisement per FEC, and the conflict resolution draft/code needs to handle this. (Whichever policy is chosen).

·         Additional test effort is then required to adequately test "ignore overlap only"

·         All of the above could result in non-interoperable implementations

Perhaps the words used to describe "ignore overlap only" could be reduced or revised to be more clear - but that would not alter the functional requirements.
Everyone gets to decide what value to put on the differences between the two approaches, but I don't think I have incorrectly identified what is required to implement "ignore overlap only".
[Bruno] indeed. But the perceived complexity may be different: decompressing the range field is relatively simple to understand, then selecting the best SID among a set is nothing new in the routing space.
-- Bruno
   Les

From: [e-mail]<mailto:[e-mail]> [mailto:[e-mail]]
Sent: Monday, December 12, 2016 8:13 AM
To: Les Ginsberg (ginsberg)
Cc: [e-mail]<mailto:[e-mail]>
Subject: RE: SID Conflict Resolution: A Simpler Proposal

Les,

On the complexity side, I have the feeling that a portion of this complexity comes from editorial choices in the draft. And in particular that the text and concepts used for the per FEC policy could be simplified.

Indeed, what we need for a consistent behavior across all implementations, is to specify the behavior of the end result. We should not need to discuss implementation internals.
A priori, the following text should be enough:

"In step 1, Prefix conflicts are resolved on a per FEC/IP prefix/Segment basis. For each FEC, the preferred SID is selected, as per the preference function (e.g. best Preference field, then smallest SID)
                Note that following this step, each prefix covered by an IGP SID advertisement has exactly one SID.
In step 2, SID conflicts are resolved. For each SID, the preferred Prefix is selected as per the preference function.
                Note that following this step, each SID has a single prefix. However some prefix may have no SID."

With the above text, there is no need for the draft to introduce generalized mapping entries, nor to split original entries into multiple ranges, nor to clarify whether the info are to be taken from the original or derived entries...

Then each implementation is free to choose its own data-structure and implementation details.
e.g one may split original entries into multiple ranges if this is your choice.
Another one may simply decompress the MS advertisement by adding the SID to each prefix, as if it were coming from a prefixSID. (As the MS range is "essentially a compression scheme") so if its too complex to handle in its compress form, lets decompress).
e.g. after receiving the MS entry (128, 1.1.1.1/32 100 range 255), the SID 100 (resp. 101...354) is added to the IP prefix 1.1.1.1 (resp. 1.1.1.2... 1.1.1.255)
Following this decompression, comparison is much more simple as there is no more MS entries which are not directly comparable to prefix SID.
e.g. in the worst case, a prefix as a set of SID, and one is selected using the preference function. A simple preference may be to select the highest Preference, and then the smallest SID to tie-brake.

In summary, having multiple advertisements for a routing entries and having to select one, is not new in the routing space/area. In this case, the complexity comes from the Mapping Server range, rather than the selection of one SID. So let's just decompress this Mapping Server range, and the problem gets simpler and very similar to what we are used to in the routing space, i.e. select the best route/path/entry


2) Preference function
For all policy except "ignore all", there is a need for a preference function. So this point is not a changing the complexity between a per advertisement policy (quarantine/new proposal) and a per FEC policy (e.g. ignore overlap)

Thanks,
--Bruno

From: Les Ginsberg (ginsberg) [mailto:[e-mail]]
Sent: Friday, December 09, 2016 7:31 PM
To: DECRAENE Bruno IMT/OLN
Cc: [e-mail]<mailto:[e-mail]>
Subject: RE: SID Conflict Resolution: A Simpler Proposal

Bruno -

Welcome back to the discussion. :)
Inline.

From: [e-mail]<mailto:[e-mail]> [mailto:[e-mail]]
Sent: Friday, December 09, 2016 2:07 AM
To: Les Ginsberg (ginsberg)
Cc: [e-mail]<mailto:[e-mail]>
Subject: RE: SID Conflict Resolution: A Simpler Proposal

Hi Les,

As a individual contributor, please find below some clarification questions [Bruno]

From: spring [mailto:[e-mail]] On Behalf Of Les Ginsberg (ginsberg)
Sent: Monday, December 05, 2016 1:04 AM
To: [e-mail]<mailto:[e-mail]>
Subject: [spring] SID Conflict Resolution: A Simpler Proposal


When the problem addressed by draft-ietf-spring-conflict-resolution was first

presented at IETF 94, the authors defined the following priorities:



1)Detect the problem

2)Report the problem

This alerts the network operator to the existence of a conflict so that

the configuration error can be corrected.

3)Define consistent behavior

This avoids mis-forwarding while the conflict exists.

4)Don't overengineer the solution

Given that it is impossible to know which of the conflicting entries

is the correct one, we should apply a simple algorithm to resolve the conflict.

5)Agree on the resolution behavior



The resolution behavior was deliberately the last point because it was

considered the least important.



Input was received over the past year which emphasized the importance of

trying to "maximize forwarding" in the presence of conflicts. Subsequent

revisions of the draft have tried to address this concern. However the authors

have repeatedly stressed that the solution being proposed

("ignore overlap only") was more complex than other offered alternatives and

would be more difficult to guarantee interoperability because subtle

differences in an implementation could produce different results.



At IETF97 significant feedback was received preferring a simpler solution to

the problem. The authors are very sympathetic to this feedback and therefore

are proposing a solution based on what the draft defines as the "Ignore"

policy - where all entries which are in conflict are ignored. We believe this

is far more desirable and aligns with the priorities listed above.



[Bruno] In the draft, the "Ignore" policy (§3.3.1) ignores all conflicting entries.

In your below proposition, the policy seems to pick the most preferred entry. This looks like more similar to the "Quarantine" policy proposed in the draft (§3.3.2)

Am I missing something?



[Les:] At the time "Ignore" was introduced (over a year ago) the notion of "SRMS preference" did not exist - that was only added in the most recent version of the draft.

We (the authors) feel that this is a useful construct because:



1)It provides an explicit basis on which to choose between conflicting entries.

2)It is particularly useful when bringing up a new SRMS as it allows the advertised values to be verified before they are used.



So, your comment is correct in that there is now a preference algorithm in use - whereas with the original definition of "Ignore" there was no preference algorithm. But the sole criteria of the preference rule is the explicitly configured preference - none of the other criteria proposed for Quarantine are used - and in particular we do not make partial use of a mapping entry as is the case with "Ignore Overlap Only".



I am happy to modify the nomenclature - but the point of this thread is not to replace a new draft revision - it is to get the sense of the WG before we publish a new revision as to whether we should continue down the "Ignore Overlap only" path or move to a simpler strategy - so let's not be too picky about the naming.



We outline the proposed solution below and would like to receive feedback from

the WG before publishing the next revision of the draft.



   Les (on behalf of the authors)



New Proposal



In the latest revision of the draft "SRMS Preference" was introduced. This

provides a way for a numerical preference to be explicitly associated with an

SRMS advertisement. Using this an operator can indicate which advertisement is

to be preferred when a conflict is present. The authors think this is a useful

addition and we therefore want to include this in the new solution.



The new preference rule used to resolve conflicts is defined as follows:



A given mapping entry is compared against all mapping entries in the database

with a preference greater than or equal to its own. If there is a conflict,

the mapping entry with lower preference is ignored. If two mapping entries are

in conflict and have equal preference then both entries are ignored.



Implementation of this policy is defined as follows:



Step 1: Within a single address-family/algorithm/topology sort entries

based on preference

[Bruno] I'm not sure what you are refering to by "preference". Is this the IGP "SRMS Preference sub-TLV" or is this the preference defined in the draft (§3.3.4)?



[Les:] It is the former.



Assuming you meant the SRMS preference, why limiting to this field, rather than including all fields defined in the draft preference algo?

Using the latter would reduce the risk of ignoring all entries (i.e. having no entry in output of this algo). Also a priori,  a sort would not be required as a single pass could select the most preferred entry.



[Les:] The point of the alternative proposal is a simplification. The presentation in Seoul (check out the slides) highlighted complexities in the implementation of "ignore-overlap-only" - in particular subtleties in the order in which an implementation looks at entries which could produce interoperability issues even though implementations are using the same preference rule. The alternative reduces the chances of these interoperability issues occurring because the algorithm used is simpler and less subject to subtle implementation differences.



If you want to argue that these are solvable problems I won't disagree with you - it is a question of where we want to put our time and effort. A number of folks are commenting that they prefer to focus on fixing the configuration and not invest  time in validating that conflict resolution is implemented in an interoperable way. As we (the authors) have stated from the beginning, we believe the emphasis should be on detecting and reporting the conflicts - not spending cycles implementing the most robust means of trying to operate optimally while the misconfiguration exists. I know you disagree on this point - but that is exactly what the WG is debating - not whether it is possible to make "ignore overlap only" work.



   Les



Thanks

-- Bruno



Step 2: Starting with the lowest preference entries, resolve prefix conflicts

using the above preference rule. The output is an active policy per topology.

Step 3: Take the outputs from Step 2 and again sort them by preference

Step 4: Starting with the lowest preference entries, resolve SID conflicts

using the above preference rule



The output from Step 4 is then the current Active Policy.



Here are a few examples. Each mapping entry is represented by the tuple:

(Preference, Prefix/mask Index range <#>)



Example 1:



1. (150, 1.1.1.1/32 100 range 100)

2. (149, 1.1.1.10/32 200 range 200)

3. (148, 1.1.1.101/32 500 range 10)



Entry 3 conflicts with entry 2, it is ignored.

Entry 2 conflicts with entry 1, it is ignored.

Active policy:



(150, 1.1.1.1/32 100 range 100)



Example 2:



1. (150, 1.1.1.1/32 100 range 100)

2. (150, 1.1.1.10/32 200 range 200)

3. (150, 1.1.1.101/32 500 range 10)

4. (150, 2.2.2.1/32 1000 range 1)



Entry 1 conflicts with entry 2, both are marked as ignore.

Entry 3 conflicts with entry 2. It is marked as ignore.

Entry 4 has no conflicts with any entries



Active policy:

(150, 2.2.2.1/32 1000 range 1)



Example 3:



1. (150, 1.1.1.1/32 100 range 500)

2. (150, 1.1.1.10/32 200 range 200)

3. (150, 1.1.1.101/32 500 range 10)

4. (150, 2.2.2.1/32 1000 range 1)



Entry 1 conflicts with entries 2, 3, and  4. All entries are marked ignore.



Active policy:

Empty



Example 4:



1. (150, 1.1.1.1/32 100 range 10)

2. (149, 1.1.1.10/32 200 range 300)

3. (149, 1.1.1.101/32 500 range 10)

4. (148, 2.2.2.1/32 1000 range 1)



Entry 4 conflicts with entry 2. It is marked ignore.

Entry 2 conflicts with entry 3. Entries 2 and 3 are marked ignore.



Active policy:

(150, 1.1.1.1/32 100 range 10)









_________________________________________________________________________________________________________________________



Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc

pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler

a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,

Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.



This message and its attachments may contain confidential or privileged information that may be protected by law;

they should not be distributed, used or copied without authorisation.

If you have received this email in error, please notify the sender and delete this message and its attachments.

As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.

Thank you.

_________________________________________________________________________________________________________________________



Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc

pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler

a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,

Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.



This message and its attachments may contain confidential or privileged information that may be protected by law;

they should not be distributed, used or copied without authorisation.

If you have received this email in error, please notify the sender and delete this message and its attachments.

As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.

Thank you.

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.