Subject: Running time for SPF in ISIS

From: Jeff Parker <[email-masked]>
Date: Tue, 1 Oct 2002 15:31:14 -0400

I have changed the title, but will try not to post
any more follow-ups to this thread.

>   For example, quick sorts performance is O(N^2) and
>   merge/heap sort is O(log N).

This is way out of scope for the OSPF list, but
quicksort is only O(N^2) in theory.

>   That doesn't mean that quick sort
>   is a bad choice. Research showed that over some
>   probabilistic distributions (or even random generators),
>   quick sort outperforms merge/heap sort.

because Quicksort is O(N log(N)) with reasonable
assumptions and smart implementations, and has
far less overhead, as it moves things towards
their final resting spot from the start.  Search
for Quicksort and Sedgewick.

>   If my input is very small, I don't bother much about algo.
>   Again - IMHO, the performance gain you get by using small
>   set of metrics is very very less.
>   After all, this is my observation/opinion :)
>
> Venkata

So I'm not sure what we are left with.
If you have small networks, the SPF performance
is not an issue.  If you are using incremental
SPF, or good data structures, SPF is not an
issue.

There is a good, simple, cheap implementation
for SPF in the old narrow ISIS metric.  It is
not enough of a reason to prefer ISIS to OSPF,
and it doesn't apply to the wide metrics.
It is really just a historical note.

- jeff parker
- axiowave networks

---

From: mike shand <[email-masked]>
Date: Wed, 2 Oct 2002 09:49:13 +0100

>It is really just a historical note.

Absolutely. When IS-IS was designed, processors were so slow (and networks
were so large, even then) that this was thought to be a significant issue.
This is why the original IS-IS design was limited to 6 bit metrics. But
times have changed. Processors are orders of magnitude faster, and nobody
builds REALLY big networks (areas), so there is really no advantage in the
optimization, and people like using wide metric ranges.

There ARE efficient algorithms for queue management which give something
like O (loglogN) (I forget exactly what). But these tend to be fiendishly
complicated and just aren't worth the trouble for SPFs in communication
networks. However in other applications where it is desired to run an SPF
with (say) millions of nodes, then the use of these algorithms may become
important.

         Mike

---

From: "Naidu, Venkata" <[email-masked]>
Date: Wed, 2 Oct 2002 10:22:13 -0400

-> This is why the original IS-IS design was limited to 6 bit
-> metrics. But
-> times have changed. Processors are orders of magnitude
-> faster, and nobody
-> builds REALLY big networks (areas), so there is really no
-> advantage in the
-> optimization, and people like using wide metric ranges.

  Addition to what mike said - using wide metrics became
  necessity. Times have changed - today, links over which
  traditional routing protocols can run ranges from DCs to OCxxx.
  So the representation of link characteristics in a limited
  space [0, 2^6] is unreasonable. RIP suffered a lot because
  of its metric size (of course that was the tradeoff between
  how fast RIP can reach the infinity vs how well link can be
  represented etc etc).

--
Venkata.

---

From: Tony Przygienda <[email-masked]>
Date: Wed, 16 Oct 2002 06:18:41 -0400

>like O (loglogN) (I forget exactly what).

yes, fibonacci heaps are real good given you have >1E6 nodes to do
SPFs on.

> But these tend to be fiendishly

yes, same experience