[email protected]
[Top] [All Lists]

Re: ordered SPFs

Subject: Re: ordered SPFs
From: mike shand
Date: Thu, 21 Oct 2004 15:57:20 +0100
At 12:10 20/10/2004 -0400, Alia Atlas wrote:
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.
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.


At 10:42 AM 10/20/2004, Olivier Bonaventure wrote:
> 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.

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

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

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/

Rtgwg mailing list
[email protected]

Rtgwg mailing list
[email protected]

<Prev in Thread] Current Thread [Next in Thread>