[email protected]
[Top] [All Lists]

Re: ordered SPFs

Subject: Re: ordered SPFs
From: Olivier Bonaventure
Date: 20 Oct 2004 16:42:04 +0200
Alia,
> 
> 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
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/


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

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