Subject: RE: Comment on ISIS extensions for traffic engineering

From: "David Oran" <[email-masked]>
Date: Wed, 4 Aug 1999 11:19:15 -0400

Sorry to jump in with a useless nit, but...

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On
> Behalf Of Jeff Learman
> Sent: Friday, July 23, 1999 1:48 PM
> To: [email-masked]
> Subject: Comment on ISIS extensions for traffic engineering
>
>
[snip]

> Second, the low value of MAX_PATH_METRIC was chosen to permit an
> optimization in SPF calculation that reduced it from O(NlogN) to
> approach O(N).

Standard SPF is O(Elog N), where E is the number of edges (links) and N is
the number of nodes), not O(Nlog N). The optimization removes the log N
factor by eliminating the sort. Now, on sparse networks, E tends to be very
small, usually a factor of 3 or 4 smaller than N, so  the nit was worth
pointing out (maybe...).

> Has the processing power on routers outpaced the
> growth in subdomain size sufficiently that this optimization is
> no longer necessary?
>
It's been clear for a while that despite the extra computation, the
advantages of a large dynamic range are pretty compelling in making network
engineering more flexible, especially given the ever increasing speed
disparity between the fastest and slowest links in a network.

Dave.

---

From: [email-masked] (Daniel Awduche)
Date: Wed, 4 Aug 1999 12:14:23 -0400 (EDT)

Dave, a few more nits to your nit....

> small, usually a factor of 3 or 4 smaller than N, so  the nit was worth

- Actually, a straight forward implementation of Dijkstra's algorithm
  (for example using a linear array as priority queue) is O(N^2).

- Using a binary heap, you can reduce it to O(ElogN).

- Using a Fibonacci heap, you can reduce it further to O(NlogN).

- Finally, assuming the metric space is small and isomorphic to a
  small finite field, you can reduce it to a theoretical limit 
  of O(N). 

- Last nit, for a minimally connected topology (a spanning tree), 
  E = N-1, so E cannot be a factor of 3 or 4 smaller than N in any
  practical network.

Regards,
/Dan

---

From: root <[email-masked]>
Date: Wed, 04 Aug 1999 09:38:12 -0700

>   small finite field, you can reduce it to a theoretical limit

For the record, theoretically you're right of course but
theory and practice are different things. Unless you consider networks with
thousands of nodes & 10E3s of links , Fibonacci heaps will be slower in any
practical implementation (and k-ary heaps have their troubles as well) than a
decent binary data structure due to elaborate maintainance necessary.

There have quite a couple of very good measurement papers published on
practical speed of Dijkstra vs. Floyd and different underlying structures in
Dijkstra.

>   E = N-1, so E cannot be a factor of 3 or 4 smaller than N in any

;-)

        thanks

    -- tony

----- End forwarded message -----

---

From: root <[email-masked]>
Date: Wed, 04 Aug 1999 10:08:15 -0700

htanks

    -- -tony

---

From: [email-masked] (Daniel Awduche)
Date: Wed, 4 Aug 1999 13:48:25 -0400 (EDT)

Tony, thanks for the clarification. This is, of course, a basic
problem with the theoretical notations for algorithmic efficieny 
-- by capturing only asymptotics and discounting multiplicative 
and additive constants, they mask important aspects which determine 
real implementation performance.

Regards,
/Dan

---

From: Tony Li <[email-masked]>
Date: Wed, 04 Aug 1999 11:13:08 -0700

> real implementation performance.

They also ignore other relevant dimensions such as code complexity, maintainability,
and subsequent reliability.

KISS

Tony

---

From: Jeff Learman <[email-masked]>
Date: Thu, 05 Aug 1999 09:57:05 -0400

OK, to sum it up: the proposal may eliminate the feasibility
of implementing SPF in the more efficient way (defined in ISO
10589) that reduces calculation time on the order of at most logN. 
This will reduce the scalability (maximum supportable subdomain
size) on routers where CPU power for calculating SPF is the
limiting factor.  This should be pointed out in the RFC.

This disadvantage may be more than compensated for by the ability to
describe a network accurately in terms of link metrics.  If so, an
argument (or at least a statement) to this effect should be included
in the RFC.  I suspect that it is indeed so.

Of course, vendors are free to implement the feature as a configurable
option, giving customers the choice.  Unfortunately, though,
use of the option will be tempting when building a network, but
the disadvantage would only appear after the network grows.  By
then, it will not be practical to switch a subdomain back to the
original method without an interruption in service.

Does anyone have any practical experience that would shed light
on whether SPF processing time is likely to be a limiting factor
on subdomain size?  Most of my experience is for SONET management
networks, where telecommunications network elements support
routing on embedded management links as a secondary function, and the
same (usually underpowered) CPU is used for routing protocols and
relaying of management data packets.  Maximum subdomain sizes range
from 50 to 500 routers, and most links are point-to-point.  I doubt
whether any data from this situation is very relevant to the purposes
of this discussion group.

What are the practical limits on subdomain size supported by routers?
If it's a relatively small number like 1000, then the factor of logN
may not be very significant.

Regards,
Jeff

>  E = N-1, so E cannot be a factor of 3 or 4 smaller than N in any
____________________________________________________________________

  Jeff Learman                           Internet:     [email-masked]
  Engineering Manager                    Voice:     (734)-975-7323
  ONE (Open Networks Engineering, Inc)   Fax:       (734)-975-6940
  2725 South Industrial Pkwy, Suite 100
  Ann Arbor, MI  48104  USA
____________________________________________________________________