Re: Why recalculation from scratch?

["Liu B." <[e-mail]>]

Hello there,

In page 159, RFC2328 (OSPF version 2), it said that "The routing table is
built again from scratch", which does not say whether the routing table
rebuilding process is done in a long interval, or for each change.
(Actually, can we not rebuild routing table for any change?)

Vishwas, as you said (chapter 2 of which draft? Is it RFC) that "the main
reason for full SPF is not having full topology in each node", also that
"route comuptation based on incomplete topology ... causes the need of
frequent re-computation..." How can we prove the performance of full SPF is
better than that of incremental SPF in respects of accuracy and CPU cost,
when recomputation happens frequently?

"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." Does it mean that in the case of two link
changes, the cost of full SPF is less than that of incremental SPF? I don't
see how, because the incremental SPF is designed to save cost ...... Does it
imply that full SPF is done only once upon two changes? But upon which?

My feeling is that using full SPF to rebuild routing table from scratch is
to sacrifice some "unrarely"(?) resources (i.e., CPU power) to simplify
problem, in order to improve protocol stability. Meanwhile, it does not
cause significant negative effect on routing performance (e.g., longer
convergence time and bandwith cost).

I am reading RFC1195 and 1142 (the latest version ISO10589v2-2001-07-04?)
now and hopefully, I can find some quantified performance comparation
between the full SPF and the incremental one. Satish, would you please tell
me where can I find the ball and string model paper you mentioned?

Thanks all and best wishes

Bin

-----Original Message-----
From: Manral, Vishwas [mailto:[e-mail]]
Sent: 15 August 2002 10:51
To: [e-mail]
Subject: Re: Why recalculation from scratch?


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

-----Original Message-----
From: Yasuhiro Ohara [mailto:[e-mail]]
Sent: 15 August 2002 09:37
To: [e-mail]
Subject: Re: Why recalculation from scratch?


VishwasM> Hi Yasu,

Hi.

VishwasM> The idea is this. When we are under high-congestion, we are
VishwasM> in a state where the topology information on the router is
VishwasM> incomplete/out of date, doing incremental SPF only further
VishwasM> loads the CPU. So instead of doing incremental SPF with
VishwasM> every change, we instead club changes and do the entire SPF
VishwasM> after a longer period of time, which anyway is best
VishwasM> effort(because of databse discrepancies).

OK. I understand that SPFs from scratch in a long interval is more
prefered than incremental SPFs for each changes. But still wondering
if there's any further reason of prefering "SPF from scratch in a long
interval" than "incremental SPF *in a long interval*" ...

VishwasM> Also check ISO10589, it states that the CPU load for two
VishwasM> incremental SPF's can be as much as a single SPF, I dont
VishwasM> remember the section though(probably in the Annex
VishwasM> somewhere). However I  remember conflicting numbers being
VishwasM> presented at NANOG.

Thank you. I will check RFC1195 (it seems the same as ISO10589).

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