[e2e] fast restoration/protection

Amund Kvalbein amundk at simula.no
Thu Jun 15 07:19:16 PDT 2006


If I understand your idea correctly, what you would gain with respect to 
restoration time is to eliminate the time it takes to compute a new FIB 
after a link state change. That is fine, but running dijkstra constitutes 
only a small part of the total convergence time (what dominates is the 
time it takes to load the new FIB to the line cards, see paper by Francois 
et al. in CCR July 2005).

Also, you would still have the problem of transient loops if the routers 
do not switch to the new FIB synchronously. Allowing the detecting router 
to locally switch to an alternate path while avoiding forwarding loops is 
an important goal for fast restoration schemes.


On Thu, 15 Jun 2006, Jon Crowcroft wrote:

> to clarify - what happens in a link state protocol is that you
> distribute states each epoch to all routers who construct a RIB
> and do a dijkstra to compute a local FIB - what i am saying is
> save the output of the dijkstra for all cases you see, and then
> when you get a link state delta that _matches_ the FIB for a previous
> case, load the FIB immediately
> for distance or path vector, this is harder as you need to add info
> (BGP in practice already has loadsa add ons to achieve some of these
> effects in an ad hoc way, but it might be nice to do it in some sort
> of principled fashion:-)
> In missive <E1FqqRl-0000uA-00 at mta1.cl.cam.ac.uk>, Jon Crowcroft typed:
> >>there's loads and loads of fancy algorithms for computing alternate
> >>routes and building k-resiliency etc etc, but does anyone know if
> >>there's a paper on the obvious - if routers were to log routing
> >>tables, and then one correlated this with faults, one could simply
> >>_load_ the alternate forwarding table directly after a link or node
> >>outage from the previous time there had been an outage at that point -
> >>i.e. simply use the fact that the routing system is a distributed
> >>algoriithm for path finding, but give it some memory:)
> >>
> >>j.
> cheers
>   jon

More information about the end2end-interest mailing list