The MPLS WG Archive

["Naidu, Venkata" <Venkata.Naidu@Marconi.com>]

Mark,

-> But do they both have the same definition of what a shortest 
-> path is? Which is really the point I was trying to make at 
-> the beginning of this. We can argue about what an algorithm 
-> is (of course we can assert there is only one definition 
-> which wouldn't be entirely out of character for this group) 
-> or we can argue about whether some some common basis of 
-> defining a shortest path is understood. We know routing 
-> loops occur when two different routers have a different 
-> understanding of the topology. I guess the question I am 
-> asking is if two different algorithms have a different 
-> concept about what shortest path means, does that not mean 
-> in essence they have a different view of the topology?

  IP routing protocols *view* of shortest path is not different. 
  For years, Distance Vector, Path Vector, Link-State IP routing
  protocols view of shortest path is same.

  Black-holes and/or cycles in Routing Protocols never result
  from using different algorithms. But, strictly because of 
  topological input mismatch.

  There are some SPF algorithms which are different from
  Dijkstra algorithm which are in use today. Recently, Thorup
  has given hierarchical SPF algo which is linear time :
  O(edges) for undirected non-negative edge weights (which   
  is the case for IP routing protocols).

  What ever algorithm is used, the SSSP using same edge 
  weights in the graph results in same DAG. I mean, Directed
  *Acyclic* Graph. More over, Dijkstra algo works with 
  non-negative edge weights only. So, it always finds a DAG
  (iff the graph is connected).

  Most of the deployed link-state algos use different flavors
  of Diakstra (i.e., using different data structures). But,
  what every flavor of data structure used and/or what ever 
  SSSP algo is used, the result is same as long as the 
  semantics assumed are same.

Venkata.