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

From: Chris Bowers <[email-masked]>
Date: Wed, 14 Sep 2016 17:06:43 +0000

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?

If not, what is the intended interpretation?

Thanks,
Chris

---

From: "Stefano Previdi (sprevidi)" <[email-masked]>
Date: Mon, 19 Sep 2016 09:43:01 +0000

> On Sep 14, 2016, at 7:06 PM, Chris Bowers <[email-masked]> wrote:
> 
> SPRING WG,
>  
> the “Strict Shortest Path” algorithm capability.  
>  

well, yes. Your example is a good one for the “strict-SPF” behavior.

s.

> _______________________________________________
> spring mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spring

---

From: Alexander Vainshtein <[email-masked]>
Date: Mon, 19 Sep 2016 10:17:16 +0000

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

> 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.
>  

s.

---

From: "Stefano Previdi (sprevidi)" <[email-masked]>
Date: Mon, 19 Sep 2016 10:21:30 +0000

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,

---

From: Jeff Tantsura <[email-masked]>
Date: Mon, 19 Sep 2016 14:08:49 +0200

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:
>

---

From: Alexander Vainshtein <[email-masked]>
Date: Mon, 19 Sep 2016 12:27:14 +0000

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

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

Regards,
Jeff

On Sep 19, 2016, at 12:21 PM, Stefano Previdi (sprevidi) <[email-masked]<mailto:[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.

s.

On Sep 19, 2016, at 12:17 PM, Alexander Vainshtein <[email-masked]<mailto:[email-masked]>> wrote:

Stefano, Chris and all,

What do I miss?
Regards,
Sasha

Office: +972-39266302
Cell:      +972-549266302
Email:   [email-masked]<mailto:[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]<mailto:[email-masked]>>
Cc: [email-masked]<mailto:[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]<mailto:[email-masked]>> wrote:

SPRING WG,

s.

Thanks,
Chris

_______________________________________________
spring mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/spring

_______________________________________________
spring mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/spring

_______________________________________________
spring mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/spring

---

From: "Stefano Previdi (sprevidi)" <[email-masked]>
Date: Mon, 19 Sep 2016 13:17:01 +0000

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,

---

From: Alexander Vainshtein <[email-masked]>
Date: Mon, 19 Sep 2016 13:28:15 +0000

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".

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

-----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,

s.

> Cc: Alexander Vainshtein <[email-masked]>; 
> [email-masked]; Chris Bowers <[email-masked]>

---

From: "Stefano Previdi (sprevidi)" <[email-masked]>
Date: Thu, 22 Sep 2016 13:57:03 +0000

> 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.

---

From: Alexander Vainshtein <[email-masked]>
Date: Thu, 22 Sep 2016 14:04:51 +0000

Stefano,
I think it really helps. Please consider adding this (or similar) explanation to the draft.

Regards,
Sasha

Office: +972-39266302
Cell:      +972-549266302

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

> 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: 

 _________G_________
|                   |

. Router A sends traffic with segment list (label stack): EZ . Now, assume router E has also a local policy in order to
  the label stack is now Z and router E swaps it with IZ . Now the packet travels through path EHIJZ while router A

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.

> To: Alexander Vainshtein <[email-masked]>; Jeff 
> Tantsura <[email-masked]>; Chris Bowers <[email-masked]>
> Cc: [email-masked]
>> The current text in draft-ietf-spring-segment-routing-09 regarding 
>> the "Strict Shortest Path" algorithm reads as follows.
>>

---

From: Jeff Tantsura <[email-masked]>
Date: Thu, 22 Sep 2016 07:47:10 -0700

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.
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.

Please let me know what you think.
 
Cheers,
Jeff

    
    
    Here’s an example: 

     _________G_________
    |                   |

    

    Hope this helps.
    
    s.

---

From: "Stefano Previdi (sprevidi)" <[email-masked]>
Date: Fri, 23 Sep 2016 07:57:30 +0000

Hi Jeff,

> On Sep 22, 2016, at 4:47 PM, Jeff Tantsura <[email-masked]> wrote:
> 
> Hi Stefano,
> 

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.

---

From: Jeff Tantsura <[email-masked]>
Date: Mon, 26 Sep 2016 16:23:36 -0700

Hi Stefano,

While a bit unorthodox view on SPF, I’d expect any deviations from default SPF to be in the context of the IGP – I’m OK with the definition as is.
Thanks for your response.
 
Cheers,
Jeff

On 9/23/16, 00:57, "Stefano Previdi (sprevidi)" <[email-masked]> wrote:

    Hi Jeff,

    

    Thanks.
    s.