[e2e] fast restoration/protection

[John Day]

Rather than try to compute all of the possible alternate FIBs that 
could occur (most won't happen) and  on the assumption, that networks 
tend to fail in the same places, ;-) as Jon first suggested why not 
just keep the a running history of the last several FIBs, assume 
after some amount of time or lack of use (a FIB replacement algorithm 
;-)) they are discarded, when a failure/change occurs if no existing 
FIB meets the evaluation criteria (not a close fit), then compute a 
new one, and add it to your cache, etc.

Of course the hard part is coming up with the evaluation criteria to 
determine whether the current situation matches previous ones. But as 
Jon suggests there are probably some pretty nice pattern matching 
schemes for this.

Take care,
John



At 9:29 +0100 2006/06/16, Jon Crowcroft wrote:
>what is interesting about that study is that it shows that the net
>_evolves_ almost more than it just changes - this means that a lot of
>_pre-computed_ protection schemes aren't going to work too well...assuming the
>study of the michnet is typical of other nets
>
>In missive <4491B3F7.3070805 at uclouvain.be>, Olivier Bonaventure typed:
>
>  >>Craig,
>  >>>
>  >>>>Yes, but this approach of precomputing FIBs has a few drawbacks :
>  >>>>- you may need to compute a lot of different FIB to cover all possible
>  >>>>failures in the network
>  >>>>- updating a FIB is not necessary fast on current routers. For example,
>  >>>>on a Cisco 12k, updating a FIB requries about 110 microsecond per prefix
>  >>>>http://citeseer.ist.psu.edu/francois05achieving.html
>  >>>
>  >>>
>  >>> Sounds like two good research problems.
>  >>>
>  >>> In fact, one solution to the second problem is known -- have two FIB
>  >>> memories -- one active, one backup -- and make it possible to switch.
>  >>> We showed how to do that about ten years ago in the MultiGigabit Router
>  >>> project (the major nuisance was invalidating the NP caches).
>  >>
>  >>The cost is to have two FIBs instead of one one each linecard.
>  >>
>  >>> As for the first -- do we know or have we thought of ways to determine
>  >>> which FIBs it would be useful to have?  I.e., don't solve all possible
>  >>> failures -- pick the best subset of FIBS given a limit on the number of
>  >>> FIBS (say 5) and current statistics on link outages.  There's 
>also a clear
>  >>> metric for goodness -- namely, take the list of outages, weighted by
>  >>> their likelihood, and see what fraction of [weighted] outages are covered
>  >>> by the set of alternate FIBS.  Obviously a metric of 1.0 is desired, but
>  >>> I'll bet any metric over, say, 0.6 has an impact.
>  >>
>  >>It could be possible to maintain a cache of the last N FIBs that have
>  >>been used, but this kind of approach may be difficult in practice for
>  >>two reasons :
>  >>- studies of ospf traces
>  >>http://citeseer.ist.psu.edu/watson03experiences.html
>  >>have shown that a router does not frequently reuse exactly the same
>  >>shortest path tree many times
>  >>- the link state database must be maintained together with the old FIB
>  >>and when a new link state packet is received with a change, then you
>  >>need to check whether the topology of the old FIB is exactly equal to
>  >>the current one
>  >>
>  >>
>  >>Olivier
>
>  cheers
>
>    jon