The MPLS WG Archive

[Ramesh Bhandari <bhandari1@lucent.com>]

Hi Folks,

There has been a flurry of email exchanges on issues and algorithms pertaining to paths routed diversely within a network (e.g., the OTN) in accordance with client's request. Several interesting scenarios were briefly discussed: path routed diversely from existing paths, simultaneous calculation of diverse paths, efficiency of the algorithms, diverse paths requested by a client ingressing and egressing through the OTN network through different points( and how to achieve that), etc. In the process, my book on diversity algorithms was pointed out by John Strand. In light of the interest in diversity , I thought I mention a few important details about my book "Survivable Networks - Algorithms or Diverse Routing", Kluwer Academic Publishers (1999):

1) The book points out the pitfalls of finding the shortest path first and then routing the second path diversely from the first path; this approach produces nonoptimal solutions, and is sometimes unable to determine a diverse pair of paths, even when such a pair actually exists.

2) It provides detailed algorithms for simultaneously calculating the diverse pair of paths in an optimal (least total cost) manner. The algorithms are simple and efficient, basically requiring two runs of a (modified) Dijkstra algorithm. They are easily extended to finding K(>2) disjoint paths in he network (this is useful for protection against multiple failures and network and also efficient network design) When diversity simply does not exist due to insufficient network connectivity, maximally disjoint paths are found (this is important, since a customr may accept less than 100% diversity).

3) It provides extensions to the real-life physical networks, involving span-sharing links (or SRLG's, as they are now called)

4) It provides extensions to the types of cases brought out by Kireeti Kompella (different ingress and egress points for diverse routes)

Although the construction of algorithms in the book is driven by optimality, for complicated situations where fast, optimal solutions are not possible, suitable (fast) heuristics can be derived (see, e.g., Section 6.2 of the book) using the developed algorithms. Clearly, heuristic approaches which involve running the Dijkstra algorithm over and over again are to be avoided, as they become inefficient.

Regards,

Ramesh