[e2e] fast restoration/protection

[Craig Partridge]

Hi Oliver:

I think you misunderstand the tenor of my note.

Regarding FIBS, my proposal was to compute multiple FIBs (not preserve
old ones) as routing updates came in, based on a history of the kinds
of outages that had occurred (e.g. which links seemed to fail most
often).  Then test (using outage information) how well the computed
backup FIBs would have done.  Pure research question of whether keeping
a limited set of FIBs around as backups (in the optimal case -- not
storing old ones but computing new ones) would work.

As for multiple FIBs in a line card.  Yes, it means more memory and,
in some cases it is perfectly feasible (been there, done that, as have
others).  But my broader point is that we should not treat the FIB
per-entry update time in a Cisco 12K as indicative of the kind of
solutions we should pick.  Rather, I'd argue, we should find our
solutions and then see what those solutions require of the hardware
(and whether that's feasible...).  Cisco FIBs exist the way they do
because of certain (well considered) expectations on the part of
Cisco engineers -- but we're playing here with changing expectations.

Thanks!

Craig

In message <4491B3F7.3070805 at uclouvain.be>, Olivier Bonaventure writes:

>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