[e2e] fast restoration/protection

[Puddinhead Wilson]

why not simply install all possible equal cost paths
as suggested in an IETF draft in the IDR WG by Manav
Bhatia and remove only those which are not needed/have
failed.




--- John Day <day at std.com> wrote:

> 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
> 
> 



	
	
		
___________________________________________________________ 
All new Yahoo! Mail "The new Interface is stunning in its simplicity and ease of use." - PC Magazine 
http://uk.docs.yahoo.com/nowyoucan.html