Method and apparatus for selecting maximally disjoint shortest paths in a network

#The invention relates generally to methods for performing path searches in communications networks, and in particular, to a method and apparatus for selecting maximally disjoint shortest paths in a network.

#Methods for searching suitable paths in a network is a well established discipline with many solved and unsolved problems.

#A Shortest Path First (SPF) algorithm, often referred to as the Dijkstra algorithm, is a method commonly used to find the shortest path between nodes in a network. A brief description of this classical problem and of some algorithms which solve it, can be found at the Internet website http://hissa.nist.gov/dads/HTML/shortestpath.html.

#The invention will now be described in greater detail with reference to the attached drawings, in which:

#FIG. 1 is an exemplary diagram of a network for illustrating a method of selecting maximally disjoint shortest paths of the embodiments of the invention;

#FIG. 2 is a flow chart illustrating a method for selecting two maximally disjoint shortest paths according to a first embodiment of the invention;

#An example of a network 10 to be used for illustrating a method for selecting maximally disjoint paths according to the embodiments of the invention is shown in FIG. 1. The network 10 has six nodes (A, B, C, D, E, Z) and eight links, wherein each link is identified by its endpoints, for example link AD joins node A to node D. Each link is further labeled with a number indicating a link cost, for example, the link cost of link AD is 5. Link cost is a parameter commonly used in path search algorithms to reflect the length or other property of a link where a higher link cost makes a link less desirable to be used.

#Also shown in FIG. 1 is a path computation processor 12, associated with node “A”. There may be a path computation processor 12 associated with other nodes as well, but only the path computation processor 12 associated with node “A” is shown. The path computation processor 12 is adapted to perform the steps of the method of the embodiments of the invention described hereunder. It is understood that the path computation processor 12, in order to perform its function, has memory means, in which is stored information about the network, including the link costs. This information may be obtained with any of numerous known methods, the details of which are outside the scope of the present invention.

#The method of the first embodiment of the invention provides selection of two disjoint paths between node “A” and node “Z”. Additionally, the method of the first embodiment provides the two paths in the network that are as short as possible, where their length is defined as the sum of the link costs of the links forming a path. The solution found by the algorithm will be in the form of an “explicit route” for each path found. An explicit route is a list of links that form a path, for example, one path from “A” to “Z” may be expressed as the explicit route AB-BC-CZ including the three links AB, BC, CZ, in order. The explicit route AB-BC-CZ extends from node “A” through nodes “B” and “C” to node “Z”. The network 10 illustrated in FIG. 1 is of great simplicity, but sufficient to illustrate the method.