Re: Why recalculation from scratch?

[satish dattatri <[e-mail]>]

<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