[e2e] fast restoration/protection

[Jon Crowcroft]

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