Subject: Re: Why recalculation from scratch?

From: "Manral, Vishwas" <[email-masked]>
Date: Thu, 15 Aug 2002 03:47:27 -0400

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:[email-masked]]
Sent: Thursday, August 15, 2002 12:52 PM
To: [email-masked]
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

---

From: satish dattatri <[email-masked]>
Date: Thu, 15 Aug 2002 01:09:34 -0700

<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

> jshen> the factors attracting more attention.

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

---

From: Yasuhiro Ohara <[email-masked]>
Date: Thu, 15 Aug 2002 17:37:11 +0900

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