Subject: Re: long SPF delays

From: "Naidu, Venkata" <[email-masked]>
Date: Tue, 10 Feb 2004 16:04:45 -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.
-> >
->
-> 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.)

  Ok. I got what you were saying. I think the problem you are
  trying to solve is way below the lower bound we could achieve
  in an asynchronous system where byzantine failures are expected
  and continuous.

  The problem you are talking about SPF is a local convergence
  problem. That means, only the computing router's routing table
  is expecting to be converted after a change some where in
  the network.

  1. Why anyone put a long delay between SPFs ? In implementations,
     I worked on, I insist below heuristics in the basic SPF
     design:

     a. SPF is triggered as an independent task taking complete
        advantage of underlying operating system and processor(s)
        (for example, as a separate task/thread using SMP etc)
        ONLY when there is a change in database. If multiple such
        protocols/processes/tasks are competing for resources,
        then it is a different story - it is a classic system
        performance/scheduling question.

     b. Never assume network is converged - that means never assume
        that there won't be any more new updates in near future.
        Assume, network/topology is ever changing.

     c. If there is no change in database (based on overall checksum
        check etc), then there is no need to wake-up/re-start SPF
        computation.

     d. If there is a change in database while doing an SPF run,
        then stopping and re-staring SPF run (even in the case of
        Dynamic SPFs) is a good thing to do. This can be done in
        constant time in SPF computation (using a global flag,
        every time after relaxing a node into SPT)

  2. For global convergence, as you said, rapid flooding is
     important. Parameter tuning, heuristics and algorithms for
     rapid flooding is another topic altogether.

Venkata.

---

From: Dave Katz <[email-masked]>
Date: Tue, 10 Feb 2004 14:26:38 -0800

>      I worked on, I insist below heuristics in the basic SPF

The reason that long inter-SPF intervals have been used in the past is
due to scheduling and queuing problems in particular implementations.
There are a number of implementations that will collapse if the CPU
load gets high enough, as a side effect of run-to-completion scheduling
and process starvation.  By putting a holddown on the recalculation,
such systems can be kept away from the cliff edge.

As you are no doubt aware, given what you said in your message, there
is no reason why SPF can't be running more or less continuously without
threatening system stability.

I'm not trying to solve any problems, I just like to complain.  ;-)

--Dave