Subject: Re: ordered SPFs

From: mike shand <[email-masked]>
Date: Wed, 20 Oct 2004 13:05:58 +0100

At 01:12 20/10/2004 -0400, Alia Atlas wrote:
>Hi Mike & Stewart,
>
>I was taking another look at the Ordered SPF idea and what you've written 
>in draft-bryant-shand-lf-conv-frmwk-00.txt and have a few comments/questions.
>
>First, I'd picked up the idea (looking through emails I'm not sure where 
>:) that you'd calculate a reverse spanning tree from each router connected 
>to the failure and wait based on the minimum hops.   It sounds like you 
>are actually calculating from the failed component itself.  For a 
>point-to-point link failure, I don't think it matters, but for a node or 
>broadcast link failure, it definitely does.  I think that you may need the 
>same thing when computing for a new link coming up.   More details, 
>particularly on the ECMP cases would be useful.

Yes. In each case you compute the reverse SPF rooted at the far end of the 
failed link as indicated in the LSP you are considering. A node failure 
does not appear as a single event, but causes multiple LSPs to be sent (1 
for each link failure). Each of these is considered as for a link failure. 
It can be shown that in the special case of an "SRLG" which is a node 
failure, there can be no conflict in the required ordering of SPFs.

>There's also a bit more complexity to the reverse spanning tree in terms 
>of what paths are inherited in the ECMP case.  If you just break ties 
>based on IP address or keep the first shortest path that's found, you 
>could end up with rather bad results.  Also, you'd need to keep track of 
>the highest hop-count on a shortest path to know how long to wait.

Yes, exactly. You need the highest hop count of any ECMP paths. This is 
because the SPT isn't a simple tree in the case of ECMP.

Note that there is a general problem with (I think) all the methods we are 
talking about for loop prevention and repair, where you have routers which 
are imposing different ECMP limits. Any calculation should be made assuming 
the "worst" case which is the largest number of path splits.

>I do see why the delay isn't computed based on destination; all the 
>affected traffic took the same shortest paths to the failed component (or 
>will take the same shortest paths to the added component).
>
>Where I think this method may have a problem is with SRLGs.  For what I've 
>been calling local SRLGs (all members connected to the same router), there 
>wouldn't be an issue, b/c you could pretend that the node had failed from 
>the perspective of rooting your reverse spanning tree.  For more general 
>SRLGs, there would be a problem.  At a minimum, one would need to do 
>destination-based delay and determine which destinations were reached via 
>which failed element(s).  One would also have to decide how to handle 
>destinations which were reached via equal-cost paths, where each 
>equal-cost path went via a different failed element.   One would need to 
>couple the separate reverse spanning trees at the point where the ECMP 
>existed and bump up the hop-count equivalently (or something 
>similar).  Have you thought about the implications of SRLGs?

Yes. Clearly it is possible for unrelated SRLG (as opposed to the special 
case of node failure), to introduce conflicting ordering requirements on 
the whole FIB. As you say this would introduce a lot of extra complexity, 
and require per destination (or at least per destination set) ordering of 
the FIB.

>I realize that we have not been discussing SRLGs substantially in the 
>context of IP FRR.  I think this is just b/c of wanting to get the basics 
>down first, before starting to embellish with all the details.  It is, of 
>course, completely possible to consider SRLGs.  This can just be an 
>additional factor in the acceptance criteria of a loop-free alternate; the 
>same thing works for U-turn alternates.  The concern would be the 
>additional computation such tracking would require.

Absolutely. The other problem with SRLG as far as repair is concerned is 
that you cannot be sure about your SRLGs. On the one hand you may have a 
failure of a single link which is part of an SRLG, and hence you may invoke 
a more complex repair strategy that actually required (or worse, decide 
that the failure was irreparable, when in fact the single link failure 
could have been repaired). On the other hand, you may get multiple link 
failures occurring as a result of a real world SRLG of which you were 
previously aware.

>Another issue, of course, is how much engineering current networks would 
>require to have protection if important SRLGs were considered.

Indeed.

>What do you think?
>
>Alia
>
>
>_______________________________________________
>Rtgwg mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/rtgwg

_______________________________________________
Rtgwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rtgwg

---

From: Alia Atlas <[email-masked]>
Date: Wed, 20 Oct 2004 12:25:31 -0400

Mike,

>failure, there can be no conflict in the required ordering of SPFs.

How do you combine/determine the node position to use if there are multiple 
trees?  I assume that it must be the furthest away hopCount (for the 
failure case) and, if a node were to instantly come up with multiple links, 
then it would be the closest hopCount (for the recovery case).

It would also be very good to specify what topology the RSPT is being 
calculated on.  I.e., this requires that one store the old topology, which 
is a slightly different complication.

>are imposing different ECMP limits. Any calculation should be made 
>assuming the "worst" case which is the largest number of path splits.

I don't think that one needs to assume the "worst" case; I think you just 
need correct inheritance rules within the SPF.   Certainly, that is what I 
have for the loop-free and for the U-turn alternates.

The problem otherwise isn't just with different ECMP limits, but with 
different tie-breaking criteria within those.

>and require per destination (or at least per destination set) ordering of 

Do you see this as a problem or as a reasonable trade-off given we have 
per-destination hold-down for the local repair?

Also, how would you combine hopCounts from different trees?  Can this work 
for SRLGs?

>>additional factor in the acceptance criteria of a loop-free alternate; 
>>the same thing works for U-turn alternates.  The concern would be the 
>failure of a single link which is part of an SRLG, and hence you may 
>invoke a more complex repair strategy that actually required (or worse, 
>decide that the failure was irreparable, when in fact the single link 
>failure could have been repaired). On the other hand, you may get multiple 
>link failures occurring as a result of a real world SRLG of which you were 
>previously aware.

Sure, it's a question of how paranoid does one really want to be.  Do you 
always use an alternate (if available) that will provide SRLG protection?

I tend to be in the paranoid in planning (i.e. get the most protective 
alternate you can) and simplistic in the set of repair strategies.  A 
separate one for link & node is not unreasonable, given BFD to make a very 
quick determination.  Beyond that, I don't see how a router could know 
about an SRLG-caused failure in the appropriate time frame.

Alia