Subject: ordered SPFs

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

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.

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.

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?

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.

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

What do you think?

Alia

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

---

From: Olivier Bonaventure <[email-masked]>
Date: 20 Oct 2004 16:42:04 +0200

Alia,
> particularly on the ECMP cases would be useful.

Pierre Francois and I have worked on the problem of ordering the updates
of the FIBs in the routers in an IP network after link and router
failures. We have proposed in a paper under submission a formal proof
that such an ordering is possible for link up, link down and changes in
the IGP weights events.

First, the two directions of each link are considered independently for
the ordering. This is because a single router cannot use both X->Y and
Y->X to send packets. It will have at most one direction of each link in
its own SPT.

In the case of link down or metric increase events, the ordering of the
FIB updates should be along the RSPT centered on the directed link. A
router can only update its FIB once all of its children in the RSPT have
updated their FIB. draft-bryant-shand-lf-conv-frmwk-00.txt uses this
ordering.

In the case of link up or metric decrease events, the ordering of the
FIB updates is different. A router can only update its FIB once its
parents on the RSPT centered on the new directed link have updated their
FIB.

A similar ordering can be defined for the router failures and similarly
for the router up events. For a router down a router should update its
FIB only once its children in the RPST centered on the failing router
have all updated their FIBs. For a router up event, a router should
update its FIB only when its parents in the RSPT centered on the
upcoming router have all updated their FIB. A consequence is that the
upcoming router must be the first to update its FIB.

We have a formal proof for those orderings in our submitted paper but it
would be too long for this email.  

Best regards,

Olivier Bonaventure and Pierre François

-- 
CSE Dept. UCL, Belgium - http://www.info.ucl.ac.be/people/OBO/

---

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

Olivier & Mike,

I agree that what you are describing works for a node failure if the node 
is the root for the RSPT.

My question/confusion is what is actually done for a node failure.  Mike 
seems to indicate that a separate RSPT is computed for each end connected 
to each down link.     The RSPT must be computed on the topology before any 
of the failures occurred.  Then I guess that a node takes its furthest 
hop-count to use as its position.

Alia

---

From: mike shand <[email-masked]>
Date: Thu, 21 Oct 2004 15:57:20 +0100

At 12:10 20/10/2004 -0400, Alia Atlas wrote:
>to each down link.     The RSPT must be computed on the topology before 
>any of the failures occurred.  Then I guess that a node takes its furthest 

Yes. If the arrival of a second (or subsequent) LSP causes you to increase 
your delay, then you do so, but if it would cause you to decrease it you 
keep the existing delay. Note that if you have already made a change with 
no delay, this can only have affected destinations which would not be 
affected by the subsequent LSP.

There is an assumption that all the LSPs concerning the failure arrive 
within the first delay period. If this is not the case, then even link 
failure loop protection cannot work. i.e. if some router somewhere doesn't 
receive an LSP until after the other routers around it have already waited 
their delay, there will be de-synchronization.

         Mike

---

From: Alia Atlas <[email-masked]>
Date: Thu, 21 Oct 2004 11:25:48 -0400

Mike,

At 10:57 AM 10/21/2004, mike shand wrote:
>>any of the failures occurred.  Then I guess that a node takes its 
>>furthest hop-count to use as its position.
>

That doesn't make sense to me.  The further away (in hopCount) one is, the 
shorter the delay, right, b/c you are removing the dependency.  In the ECMP 
cases, it seems entirely possible that one will want to decrease the 
delay.  I'm thinking of the case where there's a broadcast link that 
fails.  Otherwise, there's a race condition that depends on when the LSPs 
are received.

Also, why would a change made with no delay have affected only destinations 
that wouldn't be affected by the subsequent LSP?  I'm clearly missing 
something here.

>their delay, there will be de-synchronization.

Sure.  There's definitely a required information gathering delay.

Alia

---

From: mike shand <[email-masked]>
Date: Thu, 21 Oct 2004 16:33:18 +0100

At 11:25 21/10/2004 -0400, Alia Atlas wrote:
>I'm thinking of the case where there's a broadcast link that 

Could you give an example?

         Mike

---

From: Alia Atlas <[email-masked]>
Date: Thu, 21 Oct 2004 12:56:11 -0400

>Could you give an example?

I'm working on it.   Basically, I'm assuming that arbitrary failures of 
connectivity can happen inside a broadcast link due to layer-2 equipment.

Could you give an example where the correct behavior is to increase the 
delay in the event of a failure?

I believe that the correct behavior would be the other way (for a failure 
case), because of the need to remove dependencies; also, all the nodes 
upstream of the one whose hopCount was increased would also have increased 
hopCounts, so reducing the delay is appropriate.

The example that I have so far is rather contrived and assumes arbitrary 
(including 1-way) failure at layer-2.  It is as follows:

     50
    ----[ I ]
    |     |
    |  10 |
    |     |    3       3
    |   [ S ]----[ H ]---[ G ]
    |     |                | 3
    |  12 |              [ F ]
    |     |                | 3
    |     |                |
    |   [ A ]            [ B ]
    |     |              5 |
    |   5 |----------------|
    |             |        |
    |             | 5      | 5
    |           [ C ]    [ E ]
    |             |
    |----[ D ]----| 10

Consider the above topology where D is the destination for the traffic
under consideration.  A partial failure occurs on the broadcast link
between A, B and C, as could occur due to a layer-2 switch.  After the
failure, the following connections exist:
         A to C, A to E,
         B to A, B to E,
         C to E,
         E to A, E to B, E to C

Before the failure, S had equal-cost paths to D via A and via H.

As a result of this failure, 3 LSPs would be sent out:
      LSP 1 from A: reports connection to B is down
      LSP 2 from B: reports connection to C is down
      LSP 3 from C: reports connections to A and B are down

The following are the hopCounts from doing RSPTs on A, B and C based
on the topology before the failure.

Node  |  hopCount | hopCount | max from | hopCount |
       |   from A  | from B   |  A & B   |  from C  |
------+-----------+----------+----------+----------+
   A   |     0     |   1      |   1      |   1
   B   |     1     |   0      |   1      |   1
   C   |     1     |   1      |   1      |   0
   D   |     2     |   2      |   2      |   1
   E   |     1     |   1      |   1      |   1
   F   |     2     |   1      |   2      |   2
   G   |     3     |   2      |   3      |   3
   H   |     4     |   3      |   4      |   4
   S   |     1     |   4      |   4      |   5
   I   |     2     |   5      |   5      |   6

Assume that LSP 1 arrives before LSP 2 or LSP 3.

In that case, H and S would use the same delay and thereby cause a micro-loop.

Does this match with what you are saying?

I realize that the Ordered SPFs works most of the time; I'm trying to 
understand the corner cases (however improbable) better.

Thanks,
Alia

---

From: Alia Atlas <[email-masked]>
Date: Thu, 21 Oct 2004 13:59:22 -0400

Mike,

Here are a couple other questions about ordered SPFs.

First, how does this interact/work with OSPF Virtual Links?
Second, how does this interact with different areas?

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Oct 2004 01:18:38 -0400

Mike,

To clarify a bit further on the inter-area issue, does this handle the case 
where the cost of a route advertised into the area changes so that a 
different ABR is selected?  What if the cost to the different ABR changes 
semi-simultaneously?

Alia

---

From: mike shand <[email-masked]>
Date: Fri, 22 Oct 2004 12:49:37 +0100

At 01:18 22/10/2004 -0400, Alia Atlas wrote:
>Mike,
>
>To clarify a bit further on the inter-area issue, does this handle the 
>case where the cost of a route advertised into the area changes so that a 
>different ABR is selected?

I hadn't thought about that, but off hand I would say that you can model 
this scenario as if you have two (or more) ABRs (say A and B) each of which 
has a "link" to the external route X. So the scenario you describe is 
equivalent to a failure (or cost change) of the AX or BX link. As such, the 
normal mechanisms should handle it. But it would require special casing to 
for the code to make this interpretation.

>  What if the cost to the different ABR changes semi-simultaneously?

I think that is a case of the generalized SRLG isn't it?

         Mike

---

From: mike shand <[email-masked]>
Date: Fri, 22 Oct 2004 13:02:34 +0100

Alia,

         You are assuming I think, that the broadcast "link" is actually 
made up of a full mesh of pt-pt links, and what you are describing is a 
failure of 3 of those links simultaneously (don't forget the reverse 
connectivity check), breaking connectivity of the triangle ABC. As such, 
this is neither node failure nor single link failure, but probably comes in 
the category of unrelated SRLG, so it is not surprising that an incorrect 
ordering may occur (I haven't analyzed it yet to be sure, but it seems likely).

         However, if the broadcast link were represented as it normally 
would be as a pseudonode (or the OSPF equivalent), then the situation would 
be rather different, and would depend on which router was DR. What you 
describe would cause the loss of adjacencies between AB,AC and BC.

         If E were DR, there would be no change in the LSPs, since A,B & 
C's links to and from the pseudonode would still be intact. In IS-IS (I 
don't know for sure about OSPF), there would be no break in connectivity 
either, since if (for example) A needed to send a packet to C it would send 
it to the DR(E), which would in turn send it to C. This is how IS-IS deals 
with partial adjacency formation on a LAN.

         If A (or B or C) were DR, then all sorts of interesting 
possibilities arise. If (for example) B had the next highest priority/mac 
address to A, then when B lost its adjacency to A it would elect itself as 
a second DR. The consequences are probably too horrible to imagine.

         The bottom line is that the broadcast link protocols do not handle 
this sort of non-transitive broadcast medium failure at all well. Indeed 
they were not designed to. See the following extract from clause 6.7 of 
ISO/IEC 10589

c) The following events are "very low probability", which
means performance will be impacted unless they are extremely
rare, on the order of less than one event per four
years
1) Delivery of NPDUs with undetected data corruption;
and
2) Nontransitive connectivity, i.e. where system A can
receive transmissions from systems B and C, but system
B cannot receive transmissions from system C.

SO now going back to your analysis of the pt-pt link case. I think you may 
have misunderstood how the reverse SPF is used. Remember that it is ONLY 
the portion of the RSPF which crosses the link under consideration which is 
interesting.

So I think this gives the following values, for delay (which is horizon hop 
count - hop count)

Node  |   delay   | delay    | max from |  delay   |
       |   from A  | from B   |  A & B   |  from C  |
------+-----------+----------+----------+----------+
   A   |     0     |   0      |   0      |   5
   B   |     3     |   0      |   3      |   5
   C   |     0     |   1      |   1      |   0
   D   |     0     |   0      |   0      |   0
   E   |     0     |   0      |   0      |   0
   F   |     2     |   0      |   2      |   4
   G   |     1     |   0      |   1      |   3
   H   |     0     |   0      |   0      |   2
   S   |     0     |   0      |   0      |   0
   I   |     0     |   0      |   0      |   1

I don't THINK there is a conflict here, so despite the link failure not 
being "related" (in the sense of all applying to the same node), at least 
in this case I think it doesn't cause a problem.

But these things are somewhat tricky to evaluate by hand, and my simulator 
doesn't (yet :-) deal with such "unrelated" failures. So it is possible I 
have missed something here.

I'll try to do a proper analysis when I get time.

         Mike

At 12:56 21/10/2004 -0400, Alia Atlas wrote:
>>>fails.  Otherwise, there's a race condition that depends on when the 
>>>LSPs are received.
>>

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Oct 2004 08:51:28 -0400

At 07:49 AM 10/22/2004, mike shand wrote:
>this scenario as if you have two (or more) ABRs (say A and B) each of 
>which has a "link" to the external route X. So the scenario you describe 
>is equivalent to a failure (or cost change) of the AX or BX link. As such, 
>the normal mechanisms should handle it. But it would require special 
>casing to for the code to make this interpretation.

Such would be necessary to prevent micro-loops for inter-area routes; those 
matter too :-)

I don't think that the distance to the prefix matters, so the same trick 
could work for inter-AS routes, where what changes is whether there is 
connectivity.

>I think that is a case of the generalized SRLG isn't it?

Well, the key is that the costs could only increase or decrease together, 
due to a single link or node failure, so if one does the fake node trick, 
then you get the correct RSPT for ordering.

>>>First, how does this interact/work with OSPF Virtual Links?

Virtual Links seem to present much more of a problem.  Only the routers 
connected to the virtual link knows the current length of it in hops.  All 
the other routers would probably assume it was a single hop.

Any thoughts on that?

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Oct 2004 09:10:54 -0400

Mike,

At 08:02 AM 10/22/2004, mike shand wrote:
> this is neither node failure nor single link failure, but probably comes 
> in the category of unrelated SRLG, so it is not surprising that an 
> incorrect ordering may occur (I haven't analyzed it yet to be sure, but 
> it seems likely).

Granted.  I said it was very contrived.  Could you please send me an 
example where you believe it is correct to increase the delay  (but not 
decrease it)?  That is the part that I am objecting to.

For this to matter in a scenario, it seems that one needs both ECMP, so 
that the traffic is flowing across more than one link, and to have not 
computed the RSPT from the node which merges the paths.

Clearly, you believe you have such a scenario where the proper behavior is 
to increase delay, but not decrease it.  Could you please send me that such 
a topology?

Do you have such an example?  Could you explain why you believe it is safe 
to increase the delay but not decrease it?

> would be as a pseudonode (or the OSPF equivalent), then the situation 
> would be rather different, and would depend on which router was DR. What 
> you describe would cause the loss of adjacencies between AB,AC and BC.

Yes, that was the idea :-)

> either, since if (for example) A needed to send a packet to C it would 
> send it to the DR(E), which would in turn send it to C. This is how IS-IS 
> deals with partial adjacency formation on a LAN.

I put E in to be the DR.  I believe that in OSPF, A, B and C would report 
the different connectivity, regardless of who was the DR.  I can certainly 
double-check.

>the portion of the RSPF which crosses the link under consideration which 
>is interesting.

It's only that portion which matters b/c it's only that traffic which is 
affected, sure.

>So I think this gives the following values, for delay (which is horizon 
>hop count - hop count)
>

This can't be correct.   I is dependent on S to reach D via the broadcast link.

>in this case I think it doesn't cause a problem.

The topology tried to have H and S on different unconnected branches of the 
RSPT for the first LSP/LSA and then have them on a connected branch for the 
second.

>I'll try to do a proper analysis when I get time.

I'm not focused on this particular example, but on trying to understand 
your rationale for believing it is acceptable to increase the delay and not 
decrease it.

Intuitively, that doesn't make sense to me because what you are doing is 
not removing a dependency as early as was required.  That original 
dependency doesn't go away.

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Oct 2004 09:38:28 -0400

>the portion of the RSPF which crosses the link under consideration which 

If I understand this correctly, what you are saying is that you do an RSPF 
for each end of the link and take the results from the one whose first hop 
is across the link which just failed.  This is how you resolve the multiple 
RSPFs required for a single link failure.

If multiple link failures are reported in the same LSP/LSA, then how do you 
decide which of the RSPFs to use?  Do you take the maximum hopCount of all 
RSPFs which go across a failed link?

If additional link failures are reported in a different LSP/LSA, then how 
do you decide which of the RSPFs to use (among the one selected for this 
LSP/LSA and the current one)?

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Oct 2004 11:48:50 -0400

At 09:38 AM 10/22/2004, Alia Atlas wrote:
>>SO now going back to your analysis of the pt-pt link case. I think you 
>>may have misunderstood how the reverse SPF is used. Remember that it is 
>>ONLY the portion of the RSPF which crosses the link under consideration 
>>which is interesting.

Are you saying that you only take the branch of the RSPT that goes across 
the failed link?  Presumably this is to reduce the set of affected nodes, 
which makes sense.

Looking at the following ECMP example, I think we may be arguing the same 
thing.

                    50
            [ I ]-----------------------|
              |                         |
            5 |                         |
              |    2        2           |
            [ S ]----[ A ]----[ B ]     |
              |                 | 2     |
              |               [ C ]     |
              | 15              | 2     |
              |               [ E ]     |
              |                 |       |
              |                 | 2     |
              |    5       10   |       |
            [ H ]----[ G ]----[ F ]     |
                       |                |
                       | 5              |
                       |                |
                     [ D ]--------------|

In the above topology, D is the destination and G is the node which
fails.  Before the failure, S has two equal-cost paths to D, via H-G-D
or via A-B-C-E-F-G-D.  According to the Ordered SPFs idea, when G
fails, each router will do three reverse spanning trees (based on
distance), from each of H, F and D, and only take the branch that goes
across the particular failed link (H-G, F-G and D-G).

Assume that S hears about the H-G failure first.  S will compute its
hopCount as 1; the maxHorizon is 2.  So the delay is 1.

Then S hears about the F-G failure.  Now, S will compute its hopCount
as 5 and the maxHorizon is 6.  So the delay is 1.

I was thinking of computing the delay essentially based on the final 
hopCount and the final maxHorizon.  Instead, I think you are taking the 
delay based on each hopCount and maxHorizon, for each failed link, and then 
taking the max.

Sorry for being confused; I do think this needs substantially more description.

Alia

---

From: mike shand <[email-masked]>
Date: Fri, 22 Oct 2004 17:54:56 +0100

>the failed link?  Presumably this is to reduce the set of affected nodes, 

Yes, exactly.

>            [ S ]----[ A ]----[ B ]     |

Yes.

>as 5 and the maxHorizon is 6.  So the delay is 1.

Yes. I agree.

>delay based on each hopCount and maxHorizon, for each failed link, and 
>then taking the max.

Yes. That is correct. I think this explains both our confusions!

>Sorry for being confused; I do think this needs substantially more 

  The whole thing is confusing at the best of times.!

Sorry I haven't been able to give this much time this week.

         Mike

---

From: Alia Atlas <[email-masked]>
Date: Fri, 22 Oct 2004 13:45:26 -0400

>Yes. That is correct. I think this explains both our confusions!

Well, a combo of that and my not realizing you were pruning the RSPT.  I 
knew it had to be an ECMP case that caused the issue, but without the 
pruning, I couldn't find a way to have the different updates matter.

>Sorry I haven't been able to give this much time this week.

It's a busy week for everyone :-)
As you can tell, I think the ordered SPFs is a very interesting idea.  The 
question is how it works in practice with all the extra details.

Alia

---

From: Alex Zinin <[email-masked]>
Date: Fri, 22 Oct 2004 13:43:01 -0700

> Sorry I haven't been able to give this much time this week.

Mike-

 I think at this point it would be very useful to see a detailed description of
 the method from you guys. Do you think you could do this before DC (I could put
 the draft on the WG web-site and you'd submit it after the meeting)?

 Regards.

Alex