[e2e] fast restoration/protection
Jon.Crowcroft at cl.cam.ac.uk
Fri Jun 16 01:29:30 PDT 2006
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:
>>>>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
>>> 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
>>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
More information about the end2end-interest