Subject: Re: [spring] meaning of "Strict Shortest Path" algorithm in draft-ietf-spring-segment-routing-09

From: Chris Bowers <[email-masked]>
Date: Mon, 14 Nov 2016 23:22:01 +0000

Given the extensive discussion on this topic, it seems to me that the document needs text to clarify the intended meaning and use of the "strict shortest path" algorithm.

Have the authors added any text to draft-ietf-spring-segment-routing to do this?  

If so, when do you plan to publish that revision so that the WG can review it?

Chris

-----Original Message-----
From: Stefano Previdi (sprevidi) [mailto:[email-masked]] 
Sent: Friday, September 23, 2016 4:58 PM
To: Jeff Tantsura <[email-masked]>
Cc: Alexander Vainshtein <[email-masked]>; Chris Bowers <[email-masked]>; [email-masked]
Subject: Re: [spring] meaning of "Strict Shortest Path" algorithm in draft-ietf-spring-segment-routing-09

Hi Jeff,

> On Sep 22, 2016, at 4:47 PM, Jeff Tantsura <[email-masked]> wrote:
> 
> Hi Stefano,
> 
> Thanks for the explanation, I have got a bit of different view on the use of algorithm logic. 
> PBR is orthogonal to what an IGP does and IMO its presence should not be signaled.

please look at the example and you will see that there’s no signaling requirement.

the requirement is to have the ability to instruct the node on a specific routing paradigm.

> More logical would be to use 0 when only metric is taking into consideration when computing a path and other value otherwise, which is indeed deviation from the strict-SPF.
> 

are you suggesting that algorithm-0 (the default) must be strict-spf ? 

Thanks.
s.

> Please let me know what you think.
> 
> Cheers,
> Jeff
> 
> 
> 
> On 9/22/16, 06:57, "Stefano Previdi (sprevidi)" <[email-masked]> wrote:
> 
> 
>> On Sep 19, 2016, at 3:28 PM, Alexander Vainshtein <[email-masked]> wrote:
>> 
>> Stefano,
>> I think life would be simpler if you could provide a meaningful example of behavior that is "SPF" (defined as the default algorithm)  but not "Strict SPF”.
> 
> 
>    algorithm 0 is what you use by default. You compute your 
>    segment list with SIDs representing segments which are 
>    portion of shortest paths. However, you don’t know if in 
>    each node along the path you computed the behavior is 
>    exactly the one you intended.
> 
>    Strict-SPF allows you to be sure that the path you 
>    computed (and instantiated into a segment list) is 
>    exactly what each node will honor.
> 
>    Here’s an example: 
> 
>    Assume following topology:
>    . AG and GF links have metric of 20
>    . All other links have metric of 10
> 
>     _________G_________
>    |                   |
>    A---B---C---D---E---F---Z
>                    |       |
>                    H---I---J
> 
>    . Shortest path from A to Z is AGFZ.
>    . There’s a policy in router A in order to send traffic to Z
>      through the desired path: ABCDEFZ. The reason could be a
>      better delay
>    . Router A computes the path using its LSDB. We assume
>      that TE metric is available in the LSDB and representing
>      the delay of each link so to allow router A to compute a
>      delay-based shortest path.
>    . Router A figures out that it needs segment list EZ in order
>      to steer traffic along ABCDEFZ path.
>    . Router A sends traffic with segment list (label stack): EZ
>    . Now, assume router E has also a local policy in order to
>      send traffic to Z through the desired path: EHIJZ. This
>      may be due to some BW constraint that instructs router E
>      to split part of the traffic towards a different path.
>    . Therefore, router E imposes segment list (label stack) IZ
>      to traffic for Z.
>    . When a packet sent by A (with label stack EZ) arrives in E,
>      the label stack is now Z and router E swaps it with IZ
>    . Now the packet travels through path EHIJZ while router A
>      _thinks_ the packet would travel through path ABCDEFZ.
> 
>    Therefore, there’s a need for router A to instruct any router
>    in the path NOT to alter the shape of the path that router A
>    initially computed for that packet.
> 
>    Strict-SPF SID will do the job. A compliant implementation
>    will install the Strict-SPF SID and nexthop regardless any
>    local policy for that prefix.
> 
>    Now, regarding the ECMP use case, given that ECMP limitations 
>    still result in the use of paths all of which are IGP 
>    shortest-paths such limitations do not violate the definition 
>    of strict-spf behavior.
> 
>    Hope this helps.
> 
>    s.
> 
> 
> 
>> 
>> IMHO and FWIW Chris has tried to make such an example, but it does not look as valid to some people (me included). 
>> 
>> Without any such examples it is not clear why the "Strict SPF" algorithm is needed.
>> 
>> Regards,
>> Sasha
>> 
>> Office: +972-39266302
>> Cell:      +972-549266302
>> Email:   [email-masked]
>> 
>> 
>> -----Original Message-----
>> From: Stefano Previdi (sprevidi) [mailto:[email-masked]]
>> Sent: Monday, September 19, 2016 4:17 PM
>> To: Alexander Vainshtein <[email-masked]>; Jeff 
>> Tantsura <[email-masked]>; Chris Bowers 
>> <[email-masked]>
>> Cc: [email-masked]
>> Subject: Re: [spring] meaning of "Strict Shortest Path" algorithm in 
>> draft-ietf-spring-segment-routing-09
>> 
>> Chris, Jeff, Alex,
>> 
>> strict-SPF behavior has been intended as the forwarding of the packet according to spf, without any form of policy. 
>> 
>> It is true that ecmp is a matter of local implementation so we could extend the behavior description to:
>> 
>>    forwarding of the packet according to spf, 
>>    without any form of policy and according 
>>    to ecmp capability of the node.
>> 
>> Now, if you intentionally (through configuration) reduce the number of ecmp members, isn’t this fit the definition of a policy ?
>> 
>> The strict-spf behavior has been defined for exactly that purpose: allow an instruction to override any policy decision.
>> 
>> Note well, I’m not opposed to relax the constraint and allow ecmp differences in the “strict-spf” behavior. It’s just that at this stage I’m not (yet) convinced it’s a good thing.
>> 
>> s.
>> 
>> 
>>> On Sep 19, 2016, at 2:27 PM, Alexander Vainshtein <[email-masked]> wrote:
>>> 
>>> Jeff,
>>> I fully agree with what you say: from my POV restrictions on the number of ECMP next hops do not make an SPF less strict.
>>> 
>>> Regards,
>>> Sasha
>>> 
>>> Office: +972-39266302
>>> Cell:      +972-549266302
>>> Email:   [email-masked]
>>> 
>>> From: Jeff Tantsura [mailto:[email-masked]]
>>> Sent: Monday, September 19, 2016 3:09 PM
>>> To: Stefano Previdi (sprevidi) <[email-masked]>
>>> Cc: Alexander Vainshtein <[email-masked]>;
>>> [email-masked]; Chris Bowers <[email-masked]>
>>> Subject: Re: [spring] meaning of "Strict Shortest Path" algorithm in
>>> draft-ietf-spring-segment-routing-09
>>> 
>>> Number if ECMP paths is an implementation subject and would differ from platform to platform. The way subset of ECMP paths is chosen is local to the implementation.
>>> If you limit number of paths/size of ECMP bundle - it doesn't make it less SPF-strict as long as SPF(Dijkstra) has been applied to compute.
>>> 
>>> Regards,
>>> Jeff
>>> 
>>> On Sep 19, 2016, at 12:21 PM, Stefano Previdi (sprevidi) <[email-masked]> wrote:
>>> 
>>> sorry. What I meant is that if you restrict the number of ecmp path you have computed, it is not what the definition of strict-spf is.
>>> 
>>> IOW, strict-spf means that you forward according to what SPF algorithm has computed without applying any sort of constraint/policy/hack.
>>> 
>>> s.
>>> 
>>> 
>>> 
>>> On Sep 19, 2016, at 12:17 PM, Alexander Vainshtein <[email-masked]> wrote:
>>> 
>>> Stefano, Chris and all,
>>> I have to admit that I am completely confused:
>>>  - to the best of my understanding, Chris has asked whether a policy 
>>> that puts a limit on max. number of ECMP next hops is not compatible 
>>> with the Strict SPF algorithm
>>>  - Stefano says that "Yes, this policy is a good example when Strict SPF algorithm can be advertised".
>>> 
>>> 
>>> What do I miss?
>>> Regards,
>>> Sasha
>>> 
>>> Office: +972-39266302
>>> Cell:      +972-549266302
>>> Email:   [email-masked]
>>> 
>>> -----Original Message-----
>>> From: spring [mailto:[email-masked]] On Behalf Of Stefano 
>>> Previdi (sprevidi)
>>> Sent: Monday, September 19, 2016 12:43 PM
>>> To: Chris Bowers <[email-masked]>
>>> Cc: [email-masked]
>>> Subject: Re: [spring] meaning of "Strict Shortest Path" algorithm in
>>> draft-ietf-spring-segment-routing-09
>>> 
>>> 
>>> On Sep 14, 2016, at 7:06 PM, Chris Bowers <[email-masked]> wrote:
>>> 
>>> SPRING WG,
>>> 
>>> The current text in draft-ietf-spring-segment-routing-09 regarding 
>>> the "Strict Shortest Path" algorithm reads as follows.
>>> 
>>> o  "Strict Shortest Path": This algorithm mandates that the packet is
>>>   forwarded according to ECMP-aware SPF algorithm and instruct any
>>>   router in the path to ignore any possible local policy overriding
>>>   SPF decision.  The SID advertised with "Strict Shortest Path"
>>>   algorithm ensures that the path the packet is going to take is the
>>>   expected, and not altered, SPF path.
>>> 
>>> One example of a local policy that overrides the ECMP-aware SPF 
>>> algorithm decision is a limit on the number of ECMP next-hops.  The 
>>> text above implies that if a router places any limit on the number 
>>> of ECMP forwarding next-hops then it would be wrong for it to advertise the “Strict Shortest Path” algorithm capability.
>>> 
>>> Is this the intended interpretation?
>>> 
>>> 
>>> well, yes. Your example is a good one for the “strict-SPF” behavior.
>>> 
>>> s.
>>> 
>>> 
>>> 
>>> If not, what is the intended interpretation?
>>> 
>>> Thanks,
>>> Chris
>>> 
>>> _______________________________________________
>>> spring mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/spring
>>> 
>>> _______________________________________________
>>> spring mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/spring
>>> 
>>> _______________________________________________
>>> spring mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/spring
>> 
> 
> 
> 
> 
>