Subject: Re: Paper comparing OSPF and ISIS

From: Jeff Parker <[email-masked]>
Date: Tue, 1 Oct 2002 12:02:11 -0400

> Manav,
> In your paper you said that keeping the metrics as 6 bits
> (as specified in ISO 10589) wide in ISIS helps in SPF
> optimization. Can you elaborate a little on how this is
> achieved?
>
> Moreover with the adoption of larger path costs (wide
> metrics) in ISIS this optimization goes away .. right?
>
> Thanks,
> Paul

Paul -
        You can use a priority queue to select the next cheapest
router during the main loop of the SPF computation.  Having a
small finite number of possible metrics allows you to implement
a very efficient priority queue as an array of linked lists.
With a larger metric, this array becomes prohibitively large.
Insertion is O(1), and deletion can be made quite fast as well.

- jeff parker
- axiowave networks

---

From: "Naidu, Venkata" <[email-masked]>
Date: Tue, 1 Oct 2002 12:40:28 -0400

Jeff,

-> > Manav,
-> > In your paper you said that keeping the metrics as 6 bits
-> > (as specified in ISO 10589) wide in ISIS helps in SPF
-> > optimization. Can you elaborate a little on how this is
-> > achieved?
-> >
-> > Moreover with the adoption of larger path costs (wide
-> > metrics) in ISIS this optimization goes away .. right?
-> >
-> > Thanks,
-> > Paul
->
-> Paul -
->         You can use a priority queue to select the next cheapest
-> router during the main loop of the SPF computation.  Having a
-> small finite number of possible metrics allows you to implement
-> a very efficient priority queue as an array of linked lists.
-> With a larger metric, this array becomes prohibitively large.
-> Insertion is O(1), and deletion can be made quite fast as well.

  The algorithmic growth function or polynomial degree will
  not increase whether the metric sizes (input) are small or
  large (esp in the above case). The effect of increasing number
  of metrics does have an affect on the constants in the run-time
  performance, but on the growth function.

  In any case, whether you use small size fixed number of
  metrics or large size fixed number of metrics, the
  performance difference w.r.t insertion/deleting is very small
  (at least with the current day machines).

  Finally, I am not convinced by your answer w.r.t the 6-bits
  metric vs large 32-bit metric _and_ the relation to arrays
  and performance. Can you elaborate more ?

--
Venkata.

---

From: Jeff Parker <[email-masked]>
Date: Tue, 1 Oct 2002 13:51:01 -0400

>   and performance. Can you elaborate more ?

Venkata -
        There are fast Priority Queue implementations that
can deal with arbitrary costs.  But Heaps, Fibonacci Heaps,
skew heaps, leftist heaps, etc. have log(n) insertion and/or
deletion cost.

        With metrics in the range [0..2^8-1], you can implement
a Priority Queue as an array of 256 queues or stacks, and
insert in constant time.  Since you remove items in ascending
order, you can delete in O(1) time as well by simply keeping
track of where your last deletion was.
        Building an array of 2^32 links is prohibitive, so
while it is possible to do the same in theory, in practice
it doesn't scale.  Note that O(2^8) is O(1), while
O(2^32) is O(1) in theory only.

        As you know, the difference between N * O(1) and
N * O(log(N)) is significant in practice.  So I am
probably missing what you want elaboration on.

- jeff parker

---

From: "Naidu, Venkata" <[email-masked]>
Date: Tue, 1 Oct 2002 14:32:44 -0400

Jeff,

-> So I am probably missing what you want elaboration on.

  No. you didn't miss my point. You explained it right.
  You are right there! Please see comments inline.

-> Venkata -
->         There are fast Priority Queue implementations that
-> can deal with arbitrary costs.  But Heaps, Fibonacci Heaps,
-> skew heaps, leftist heaps, etc. have log(n) insertion and/or
-> deletion cost.
->
->         With metrics in the range [0..2^8-1], you can implement
-> a Priority Queue as an array of 256 queues or stacks, and
-> insert in constant time.  Since you remove items in ascending
-> order, you can delete in O(1) time as well by simply keeping
-> track of where your last deletion was.

  I got your point. Since you have small metrics, you have
  the freedom of maintaining an array. As you know, the memory
  consumption (in-place algorithms) and run-time cost of algorithms
  are not the same. There are algorithms which are in-place
  and can run linear time (not necessary *comparison based
  algos* you described above).

->         Building an array of 2^32 links is prohibitive, so
-> while it is possible to do the same in theory, in practice
-> it doesn't scale.

  Yes! if the metrics sizes are more, I am prohibited to use
  an array (preferably, I don't want to use all the virtual
  memory I have - definitely I can't use the physical available
  memory :)).

-> Note that O(2^8) is O(1), while O(2^32) is O(1) in theory
-> only.

  Exactly. But, the number O(2^32) comes when I prefer to
  use 2^32 array. If I go for an hash based, radix or
  Patricia based algos then the constant will be much
  less than O(2^32) - no wonder even if it is less than
  O(2^8). But as you said, the growth rate may not be same
  (depending on the algo - may be O(logN) or even more).

  But all my assertion is simple - the performance gain
  you get by using algos which are not linear over simple/small
  sets is not much. Insertion sort with O(n^2) also perfectly suits
  well if the number of metrics are less (again, the size of
  the metrics have very little effect - total count will effect).

->         As you know, the difference between N * O(1) and
-> N * O(log(N)) is significant in practice.

  As you know, difference between N * O(2^8) and c * O(N) is
  significant in practice, if c and N are relatively small.

  For example, quick sorts performance is O(N^2) and
  merge/heap sort is O(log N). 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.

  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.