Paul,
set T = set of vertices under consideration

Computation time of SPF algo = O(LlogN) where L is nos of links and N, the
nos. of nodes. The logN factor results when selecting the next best router
during the main loop of SPF algo from the elements of set T. These elements
in set T are presorted by cost to avoid the need for linear search in
selecting the element with the lowest cost. The processing time required by
the binary search mechanism used in sorting T while inserting new entries
introduces the logN factor. By using a finite path cost based on 6 bit
field, it was possible to further optimize and reduce the order of
complexity to just O(N) eliminating the logN factor. This was achieved
using quick array sort data structures, which sorts nodes by hashing them
according to path cost rather than logical distance. Unfortunately, over
time, the 6 bits have proven insufficient for providing flexibility in
designing ISIS networks, as well as in other applications of ISIS routing
(e.g. MPLS TE)

And yes, the adoption of larger path costs (wide metrics) in ISIS takes
away the optimization opportunity with small finite path costs (narrow
metrics) but then CPU are really fast these days and nobody builds really
very big networks anyway.

Regards,
Manav

----- Original Message -----
From: "Paul Jak" <paul_j1SUBDIMENSION.COM>
To: <OSPFDISCUSS.MICROSOFT.COM>
Sent: Friday, September 27, 2002 12:34 PM
Subject: Re: Paper comparing OSPF and ISIS

| 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
|
| P.S.
| I understand that this question is not related to OSPF but
| since this paper was not posted on the ISIS WG (why?) i had
| to ask this here!
| _____________________________________________________________________
| // free anonymous email || forums \\ subZINE || anonymous browsing
| subDIMENSION -- http://www.subdimension.com

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]