Re: Why recalculation from scratch?

["Manral, Vishwas" <[e-mail]>]

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.

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

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

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

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