Re: Why recalculation from scratch?

[satish dattatri <[e-mail]>]

Vishwas,
Please see inline
thanks,
satish

--- "Manral, Vishwas" <[e-mail]> wrote:
> Hi Satish,
>
> As I said the main reason why we do not want incremental
> SPF in the high
> congestion case is because we are overloaded and probably
> do not have the
> full topology.
>

Why not delay the SPF, if that makes sense among other
things.. Please note that a incremental SPF or FULL SPF will
have to be done on the amount of information in our LSDB.
Let us leave it to the creative implementor ...

> Section 2 of the draft talks about "Failure Experience and
> Analysis" the
> following was analysed as a cause of the problem
>
>      Route computation based on incomplete topology
> recovery, causing
>      routes to be generated based on transient,
> asynchronous topology
>      information and then in need of frequent
> re-computation.
>
> The latest version ISO10589v2-2001-07-04 of the doc I have
> in Annex C.2
> states: -
>
> "studies suggest that with a very small number of link
> changes (perhaps two)
> the expected computation complexity of the incremental
> update exceeds the
> complete recalculation."
>

That part of the document is just carried from the 1992
edition. Please, let us not take that verbatim.

> I however agree that the complexity would depend on the
> kind of
> change(ABR/ASBR) as well as the implementation details. I
> guess a better way
> could be to explain the exact problem, and perhaps leave it
> to the
> implementor. Agree??
>

I agree, that is the best choice.

> Yasu, 10589 and the RFC1195, are totally different, RFC1142
> is the ASCII
> version of ISO10589.
>

RFC1142 is a copy of ISO10589-1990 draft not the 1992
approved version. But anyways please use the latest draft
available free ;-), as you referred.

> Thanks,
> Vishwas
>
> -----Original Message-----
> From: satish dattatri [mailto:[e-mail]]
> Sent: Thursday, August 15, 2002 1:40 PM
> To: [e-mail]
> Subject: Re: Why recalculation from scratch?
>
>
> <Just a friendly note here:>
> The spirit of the words in ISO10589 is just meant to say
> that multiple changes and incremental SPF may be the same
> as the complete SPF. Also, remember when the original doc
> was
> written. The ball and string model paper I guess
> has proof to say that the worst case is no more worse than
> a
> full SPF. Depending on how the spf data structures are
> setup
> and the architecture the mileage will vary (as usual).
>
> Without more simulation/ hard data maybe leaving that
> statement out of the draft is probably more accurate.
>
> Thanks,
> Satish
>
> --- "Manral, Vishwas" <[e-mail]> wrote:
> > Hi Yasu,
> >
> > The idea is this. When we are under high-congestion, we
> are
> > in a state where
> > the topology information on the router is incomplete/out
> of
> > date, doing
> > incremental SPF only further loads the CPU. So instead of
> > doing incremental
> > SPF with every change, we instead club changes and do the
> > entire SPF after a
> > longer period of time, which anyway is best
> effort(because
> > of databse
> > discrepancies).
> >
> > Also check ISO10589, it states that the CPU load for two
> > incremental SPF's
> > can be as much as a single SPF, I dont remember the
> section
> > though(probably
> > in the Annex somewhere). However I  remember conflicting
> > numbers being
> > presented at NANOG.
> >
> > Thanks,
> > Vishwas
> >
> > -----Original Message-----
> > From: Yasuhiro Ohara [mailto:[e-mail]]
> > Sent: Thursday, August 15, 2002 12:52 PM
> > To: [e-mail]
> > Subject: Re: Why recalculation from scratch?
> >
> >
> > Hi,
> >
> > Related to this, I wonder why the congestion-control
> draft
> > saying "do
> > not do incremental SPF when congested" (in 4.2.2.4 Reduce
> > the Rate of
> > SPF Computation). Could you give me some more explanation
> > or a
> > reference pointer, authors ?
> >
> > IMHO simply we're just negative to have a lot of state
> > informations,
> > though there are some ways to avoid recalculation from
> > scratch
> > (i.e. incremental SPF calculation).
> >
> > regards.
> > yasu
> >
> > jshen> Bin Liu,
> > jshen>
> > jshen> The first, router does not maintains all
> information
> > as human does.
> > jshen> the second, each router computes its routing table
> > on its view of
> > network.
> > jshen> When state of some links varies, the logical view
> of
> > network changes
> > jshen> and the shortest path tree of the graph may become
> a
> > totally new one;
> > jshen> the third, as link state propagates by relaying
> hop
> > by hop, it can
> > not
> > jshen> be expected that every router update their routing
> > table
> > simulataneously,
> > jshen> so each time a new link state is received the
> > routing table must be
> > jshen> recomputed
> > jshen> to guarantee the convergence.
> > jshen>
> > jshen> Of course, in a network with thousands of prefix
> > such computing need
> > a lot
> > jshen> of
> > jshen> CPU time but it's just one of the key reasons.
> IMO,
> > Route flapping
> > and
> > jshen> looping is
> > jshen> the factors attracting more attention.
> > jshen>
> > jshen> Cheers
> > jshen>
> > jshen> Jing Shen


__________________________________________________
Do You Yahoo!?
HotJobs - Search Thousands of New Jobs
http://www.hotjobs.com