Subject: Re: long SPF delays

From: "Naidu, Venkata" <[email-masked]>
Date: Tue, 10 Feb 2004 10:45:51 -0500

-> Absurdly long SPF delays are the biggest impediment to
-> progress in this area.

  Yes. But only in the worst case. Progress in theoretical
  computer science is far rapid to catch-up.

  Let me take this opportunity to share some information which
  I came across and thought very useful for this community.
  In a recent paper by Thorup et. al., "Speeding up Dynamic
  Shortest Path Algorithms", Sept 2003 (not yet published)
  http://www.research.att.com/~mgcr/doc/dspa.pdf
  authors compared 4 Dynamic Dijkstra algorithms. The paper
  is so practical in a way, it gives complete algorithms with
  full statistical results in a larger simulated topologies
  (very large when compared to Internet IGP domains).

  For theoretical interest, most of the Dynamic SPF algorithms
  are based on Ramalingam and Reps "Generalization of Incremental
  SPF" paper - which is based on to Knuth's Static Dijkstra SPF
  generalization using finite automata.

  Look at Chapter 2 in a recent MIT PhD thesis for a general
  framework for Dynamic SPF (don't look at Chapter 3 which is
  based on linear programming - different from Dijkstra SPF)
  http://citeseer.nj.nec.com/335235.html

  In his classic paper, Thorup reduced static SPF computation
  to linear time O(m), m is number of edges. His approach is
  different from Dijkstra, to break the log sorting time.
  http://citeseer.nj.nec.com/thorup97undirected.html
  (This may be impractical to adapt to IGPs, for the implicit
  assumptions by the algorithms)

  For comprehensive list of literature on Dynamic SPF algos,
  look at: http://www.cs.uwaterloo.ca/~y6yang/page.htm

  In conclusion, I feel that, OSPF/ISIS SPF computations can
  be speed-up dramatically (at least in expected case) using
  recent advances in systems engineering and theoretical
  computer science without loss of generality (esp. in
  asynchronous distributed algorithms in arbitrary connected
  network problem space).

  Any comments, please discuss.

Venkata.

---

From: Dave Katz <[email-masked]>
Date: Tue, 10 Feb 2004 11:46:17 -0800

>   computer science is far rapid to catch-up.

You misunderstood me.  The problem is not the duration of the SPF
calculation (which is typically in the millisecond range) but in
implementations that put a long delay between successive calculations
in order to stave off instability (due to insufficiently robust code.)

I have yet to see any evidence that SPF calculations in any practical
OSPF/ISIS networks are taking long enough to make it necessary to add
the complexity of optimizing the SPF calculation.  It's an interesting
theoretical problem, and it probably has practical application in other
realms, but not in IP networks.  Lots of things besides the SPF
calculation cause problems if you try to build an O(10000) node network.

---

From: Erblichs <[email-masked]>
Date: Tue, 10 Feb 2004 13:15:15 -0800

This sounds that you believe that SPF throttling and packet pacing
functionality by some companies isn't necessary.

If packet pacing is implimented by some routers, then without SPF
throttling,
wouldn't sucessive SPF calculations occur? Of course, packet pacing
is to spread out peak LSA xmits to min input buffer overflows, etc..

Lastly, with vastly cheaper memory subsystems and larger phys memories
it is possible to decrease the amount of route aggregation to achieve
better path routing. However, this will and does significantly increase
the LSDB sizing, and secondarily normally increases the SPF computation
duration beyond ms durations (in a large number of deployed routers)
with LSDB sizing ranging from 500k to 2.5M

Mitchell Erblich
-----------------------------

---

From: Dave Katz <[email-masked]>
Date: Tue, 10 Feb 2004 15:27:37 -0800

> functionality by some companies isn't necessary.

I believe packet pacing is absolutely necessary (since there's no flow
control in the protocol, and the receiver may be dropping packets), but
that's quite distinct from LSA generation holddown.  You're right, I
don't believe that SPF throttling is necessary, nor is it desirable
(except as a self-preservation measure when it looks like things are
really hosed.)

> is to spread out peak LSA xmits to min input buffer overflows, etc..

Yes, successive SPF calculations may occur.  That's a good thing,
unless the system tends to melt down in such cases, as you'll reach
convergence nirvana sooner.

> with LSDB sizing ranging from 500k to 2.5M

This doesn't increase the complexity of the SPF calculation, just the
sheer volume of leaf nodes to process.  Optimizing this does not
require the relatively arcane algorithms that are favorites of
researchers;  we're not talking about 500K vertices after all.  This
case is just a matter of trying to minimize the amount of linear
slogging you have to do.

Trying to run giant LSDBs will require a lot more things to scale than
just the SPF, which unfortunately is what people like to think about.
You also have to deal with the sheer volume of database exchange, the
max size of the Router LSA, and downloading all of those routes to the
forwarding engine, among other things.

--Dave

---

From: Tony Przygienda <[email-masked]>
Date: Wed, 11 Feb 2004 10:39:21 +0100

> (except as a self-preservation measure when it looks like things are

Hmm, yes, so I had an interesting implementation experience (actually
quite foreseable). And that was, that even if SPF is not
running-to-completion
but preemptively with optimistic shared-read locks
[I slightly disagree with what Dave said, that people hold down because of
running-to-completion, well implemented it's a pro-cons tradeoff of at
least same
quality and performance
as preemptive, prefereable to me actually, since you have to put more
work into implementation upfront but end up with less problems in
deployment]
there is the necessity to throttle SPF runs since otherwise
fine-granularity locking
and flooding stepping on spf locks and vice-versa at a certain p oint causes
enough thrashing to make you back SPF off. So yes, I agree with Dave, it's
only a self-preservation measure but I found, a necessary one.

>> is to spread out peak LSA xmits to min input buffer overflows, etc..
well, spreading LSA xmits is another cause of longer convergence time.
You end up with more SPF runs, most of them with incomplete information.
So yes, you run SPF 'immediately' but since you don't have your LSAs around,
you just have the illusion of having converged. Globally, you didn't.
So, some
packet pacing is necessary but it's not desirable for fast convergence.

BTW, there is a decent Ph.D. thesis by George Apostopopoulus (oh, god, I
probably misspelled) where he looked exactly into packet packing/LSA
generation
intervals/SPF delays vs. global convergence times. This was done in context
of OSPF carrying QoS around so fairly close to this interest group.

> forwarding engine, among other things.

yepp, in this scenario optimizing SPF is a blip on the horizon only (and
it's only
a linear problem anyway). In fact,
you start to push the architectural capability of the protocols
(assuming you
want it converged in time << infinity and even then, at certain point in
time you start to regenerate LSAs before they got all places in the
network ==
no convergence)

    thanks

    -- -tony

---

From: Jing Shen <[email-masked]>
Date: Wed, 11 Feb 2004 20:34:12 +0800

Hi,

I'm looking for some recommandations or guidelines for
OSPF area planning in ISP networks or enterprise
networks. The target is to reach optimal point in
cost-performance space.

Is there someone would do me a favor ?

thanks

Jing Shen

_________________________________________________________
Do You Yahoo!?
完全免费的雅虎电邮，马上注册获赠额外60兆网络存储空间
http://cn.rd.yahoo.com/mail_cn/tag/?http://cn.mail.yahoo.com

---

From: Dave Katz <[email-masked]>
Date: Wed, 11 Feb 2004 09:49:35 -0800

> only a self-preservation measure but I found, a necessary one.

There are more subtle methods than fixed-time holddowns that will
accomplish the same thing (avoiding database lockout), but none of it
is fundamentally necessary unless you are actually running into
contention problems (I think we're in violent agreement here.)

My point wasn't that nonpreemptive scheduling is the cause (or the only
cause) of people doing long SPF holddowns;  rather, long SPF holddowns
were implemented as a bandaid for problems exacerbated by nonpreemptive
environments.  (I actually think that nonpreemptive environments are
best for *most* of what goes on in a protocol;  it makes for much more
robust code if done properly.)

> packet pacing is necessary but it's not desirable for fast convergence.

The fundamental problem is that there are competing goals:  fast
convergence and stability.  Stability is primary, since it doesn't
matter how fast your unstable network converges.  The trick is to
choose what cases you want to optimize (say, the fiber cut that
requires rerouting 500,000 VoIP calls) and then Do the Right Thing.

--Dave

---

From: Tony Przygienda <[email-masked]>
Date: Thu, 12 Feb 2004 02:40:11 +0100

> robust code if done properly.)

100% in sync

    -- tony