[e2e] fast restoration/protection

[Jon Crowcroft]

In missive <001a01c69088$8f7f1460$23d25ba5 at tamu.edu>, "Narasimha Reddy" typed:

 >>Jon, the following paper addresses the problem of fast rerouting:

 >>Y. Liu and ALN Reddy, "A fast rerouting scheme for OSPF/IS-IS Networks".
 >>http://www.ece.tamu.edu/~reddy/papers/yong_icccn04.pdf

yes, i've read that

 >>It is not enough for the local router by itself to choose a FIB computed
 >>earlier on the same link failure. This will likely lead to routing loops
 >>since the other nodes are using FIBs that assume the availability of the
 >>failed link.
 
sure - but i wasn't proposing this - its a bit more subtle - the point
is that you haev a set of link/node failure probabilities, and you
have a set of routing configurations  and you 
i) pick configs which match failures but ALSO
ii) pick configs that don't lead to loops if picked differently

so the system of routers
moves through a phasespace/ensemble of configs that gradually converge on 
a consistent new view as they learn of the link state change, but
without doing new computations since all the computations were done
once and once only for all the likely combinations of cases
(and before people tell me that that is a huge search space, i know,
but it is the _actual_ cases that matter that one records, not all
possible cases)

think of it like a distributed, incremental pattern matching scheme:)

 >>
 >>-----Original Message-----
 >>From: end2end-interest-bounces at postel.org
 >>[mailto:end2end-interest-bounces at postel.org] On Behalf Of Jon Crowcroft
 >>Sent: Thursday, June 15, 2006 7:28 AM
 >>Cc: Jon.Crowcroft at cl.cam.ac.uk; end2end-interest at postel.org
 >>Subject: Re: [e2e] fast restoration/protection
 >>
 >>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=20
 >>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=20
 >> >>algoriithm for path finding, but give it some memory:)
 >> >>
 >> >>j.
 >>
 >> cheers
 >>
 >>   jon
 >>
 >>

 cheers

   jon