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

FIELD OF THE INVENTION

[0001] 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.

BACKGROUND OF THE INVENTION

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

[0003] 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.

[0004] Often, it is necessary to find more than one path between a source and a destination. For example, a second path must be found after a failure disrupts a first path. A new path may be computed after a failure has occurred, but in many networks it is desirable to pre-calculate alternate paths before any failure occurs, so that a new path is immediately available in the event of a failure. Furthermore, it is desirable that the alternate path use, as much as possible, different network resources such as nodes and links, than the first path.

[0005] Fully disjoint shortest paths between the same source-destination pair are the shortest paths that do not share nodes or links. In real networks, fully disjoint paths may not be possible, and it is desired to find maximally disjoint shortest paths.

[0006] The problem of finding multiple disjoint paths is also a classical problem, but unlike the simple path search, does not have a known efficient (scaleable to large networks) perfect solution.

[0007] In U.S. Pat. No. 5,872,773 to Katzela et al. is disclosed a heuristic method for determining disjoint routing trees providing maximally disjoint paths in a cellular network. This method is based on destination rooted trees, suitable for cellular networks.

[0008] An algorithm for computing shortest and widest maximally disjoint paths is reported in a conference paper by R. Ogier, B. Bellur, and N. Taft-Plotkin entitled “An Efficient Algorithm for Computing Shortest and Widest Maximally Disjoint Paths”, SRI International Technical Report ITAD-1616-TR-170, November 1998. This method in turn is based upon an algorithm by J. W. Suurballe and R. E. Tarjan “A Quick Method for Finding Shortest Pairs of Disjoint Paths”, published in <i>Networks, </i>14, 1984. The disadvantages of this method are found to be the following:

[0009] All paths are pre-computed in advance of setup requests;

[0010] The algorithm only finds 2 disjoint path pairs;

[0011] The algorithm determines all disjoint path pairs from a source to all destinations (in tree format);

[0012] All paths are computed upon every receipt of a QoS (Quality of Service) message update.

[0013] The algorithm is based on a modified Suurballe/Tarjan algorithm for disjoint paths, and, overall, is complex, memory and computationally expensive. Below is provided a brief description of this algorithm.

[0014] Phase 1: Compute all Max Bandwidth disjoint path pairs from source to all destinations;

[0015] Phase 2: Transform Bandwidth/Cost of each link not used in the original tree;

[0016] Phase 3: Each node has five variables used in complex calculations;

[0017] Phase 4: Get the two paths from the resulting network, mark all links as unmarked, and then traverse the network topology (or graph).

[0018] With four complex phases, this algorithm is difficult to implement in software and to maintain in operation.

[0019] An extensive discussion of the general problem of finding multiple disjoint paths, and a proposed “split-node” solution to it, can be found in the text book “Survivable Networks: Algorithms for Diverse Routing” by Dr. Ramesh Bhandari, Kluwer Academic Publishers, 1999. This book contains detailed algorithms for calculating disjoint pairs of paths, maximally disjoint paths if full diversity does not exist, and K (K greater than 2) disjoint paths.

[0020] While the “split-node” method generates a solution to the problem, it requires a network transformation, in which many nodes are split (i.e. a single node is represented by two nodes), resulting in inefficiency in path computation for a large network.

[0021] Accordingly, there is a need in industry for the development of an alternative method, which would provide efficient and reliable generation of multiple maximally disjoint shortest paths in a network and would avoid the above mentioned drawbacks.

SUMMARY OF THE INVENTION

[0022] It is therefore an object of the invention to provide a method and apparatus for efficient and reliable generation of maximally disjoint shortest paths in a network.

[0023] According to one aspect of the invention there is provided a method for selecting two maximally disjoint shortest paths between a source node and destination node in a network, comprising the steps of:

[0024] determining a first explicit route between the source and destination nodes by using an original link cost for each link in the network;

[0025] transforming the network by introducing conditional link costs;

[0026] determining a second explicit route between the source and destination nodes in the transformed network taking into account the conditional link costs; and

[0027] determining the two maximally disjoint shortest paths between the source and destination nodes by coalescing the first and second explicit routes.

[0028] Beneficially, the step of introducing conditional link costs comprises the step of adding additional parameters to links in the network and determining the conditional link costs depending on the position of each link relative to the first explicit route.

[0029] Conveniently, the step of adding the additional parameters comprises adding a first conditional link cost (LC<b>1</b>), a second conditional link cost (LC<b>2</b>), and a router list parameter. The step of adding the first conditional link cost comprises adding the first conditional link cost, which is equal to one of the following:

[0030] original link cost;

[0031] original link cost plus a large cost, the large cost being of the order of several times the sum of the original link costs of all links in the network; and zero.

[0032] The step of adding the second conditional link cost comprises adding the second conditional link cost, which is equal to one of the following:

[0033] original link cost plus a large cost, the large cost being of the order of several times the sum of the original link costs of all links in the network; and zero.

[0034] The step of determining the conditional link costs depending on the position of each link relative to the first explicit route, comprises the step of assigning LC<b>1</b> equal to one of the following:

[0035] the original link cost plus the large cost, if the link is a link belonging to the first explicit route; and

[0036] the original link cost otherwise.

[0037] Advantageously, the step of determining the conditional link costs, depending on the position of each link relative to the first explicit route, comprises the step of assigning LC<b>1</b> equal to the original link cost plus the large cost, if the link is a link belonging to the first explicit route and not the first link of the first explicit route.

[0038] Beneficially, the step of determining the conditional link costs, depending on the position of each link relative to the first explicit route, comprises the step of assigning LC<b>2</b> equal to:

[0039] the original link cost plus the large cost, if the link does not belong to the first explicit route, but originates from a node on the first explicit route except the source and destination nodes; and

[0040] zero otherwise.

[0041] Conveniently, the step of adding the router list parameter comprises adding the router list parameter to a link, which originates from a node on the first explicit route and terminates on a node that is not the next node on the first explicit route, the router list parameter indicating the next node on the first explicit route.

[0042] In the method described above, the step of determining the second explicit route between the source and destination nodes in the transformed network comprises the step of determining a path from the source node to the destination node by using a conditional link cost LC, which is set equal to one of following:

[0043] LC<b>1</b>;

[0044] LC<b>2</b>; and

[0045] the original link cost.

[0046] The step of determining the path from the source node to the destination node by using the conditional link cost comprises setting LC equal to one of the following:

[0047] LC is equal to the original link cost if both LC<b>1</b> and LC<b>2</b> equal to zero;

[0048] LC=LC<b>2</b> if LC<b>2</b> is not zero, and if the router list parameter of the link is not indicating the previous node of the second explicit route; and

[0049] LC=LC<b>1</b> otherwise.

[0050] According to another aspect of the invention there is provided a method for selecting “N” maximally disjoint shortest paths between a source node and destination node in a network, “N” being equal or greater than two, the method comprising the steps of:

[0051] (a) determining a first explicit route between the source and destination nodes by using an original link cost for each link in the network;

[0052] (b) for each explicit route found so far, transforming the network by introducing conditional link costs;

[0053] (c) determining the next explicit route between the source and destination nodes in the transformed network taking into account the conditional link costs;

[0054] (d) removing conditional link costs;

[0055] (e) determining maximally disjoint shortest paths represented by the explicit routes found so far between the source and destination nodes by coalescing the explicit routes found so far; and

[0056] (f) repeating the steps (b) to (e) “i” number of times, wherein “i”=N−1.

[0057] Advantageously, the step of introducing conditional link costs comprises the step of adding additional parameters to links in the network and determining the conditional link costs depending on the position of each link relative to each explicit route found so far, e.g. adding a first conditional link cost (LC<b>1</b>), a second conditional link cost (LC<b>2</b>), and a router list parameter.

[0058] Beneficially, the step of adding the first conditional link cost comprises adding the first conditional link cost, which is equal to one of the following:

[0059] the original link cost;

[0060] the link cost assigned so far;

[0061] original link cost plus a large cost, the large cost being of the order of several times the sum of the original link costs of all links in the network;

[0062] the link cost assigned so far plus the large cost; and zero.

[0063] The step of adding the second conditional link cost comprises adding the second conditional link cost, which is equal to one of the following:

[0064] original link cost plus a large cost, the large cost being of the order of several times the sum of the original link costs of all links in the network;

[0065] the link cost assigned so far plus the large cost; and zero.

[0066] Conveniently, the step of determining the conditional link costs depending on the position of each link relative to each of the explicit routes found so far comprises the step of assigning LC<b>1</b> equal to one of the following, the step being performed for each of the explicit routes found so far:

[0067] the original link cost plus the large cost, if the link is a link belonging to the explicit route and LC<b>1</b>=0 before the step of assigning LC<b>1</b> is performed;

[0068] the link cost assigned so far plus the large cost, if the link is a link belonging to the explicit route and LC<b>1</b> is not zero before the step of assigning LC<b>1</b> is performed; and

[0069] the original link cost otherwise.

[0070] The step of assigning LC<b>1</b> comprises the step of assigning LC<b>1</b> equal to the original link cost plus the large cost, if the link is a link belonging to the explicit route and not the first link of the explicit route.

[0071] Conveniently, the step of determining the conditional link costs depending on the position of each link relative to the explicit routes found so far comprises the step of assigning LC<b>2</b> equal to one of the following, the step being performed for each of the explicit routes found so far:

[0072] the original link cost plus the large cost, if the link does not belong to the explicit route, but originates from a node on the explicit route except the source and destination nodes and LC<b>2</b>=0 before performing the step of assigning LC<b>2</b>;

[0073] the link cost assigned so far plus the large cost, if the link does not belong to the explicit route, but originates from a node on the explicit route except the source and destination nodes and LC<b>2</b> is not zero before performing the step of assigning LC<b>2</b>; and

[0074] zero otherwise.

[0075] In the method described above, the step of adding the router list parameter comprises adding the router list parameter to a link, which originates from a node on the explicit route and terminates on a node that is not the next node on the explicit route, the router list parameter indicating the next node on the explicit route, the step being performed for each of the explicit routes found so far.

[0076] The step of determining the next explicit route between the source and destination nodes in the transformed network comprises the step of determining a path from the source node to the destination node by using a conditional link cost LC, which is set equal to one of following:

[0077] LC<b>1</b>;

[0078] LC<b>2</b>; and

[0079] the original link cost.

[0080] The step of determining the path from the source node to the destination node comprises setting the conditional link cost equal to one of the following:

[0081] LC is equal to the original link cost if both LC<b>1</b> and LC<b>2</b> are equal to zero;

[0082] LC=LC<b>2</b> if LC<b>2</b> is not zero, and if the router list parameter of the link is not indicating the previous node of the second explicit route; and

[0083] LC=LC<b>1</b> otherwise.

[0084] According to another aspect of the invention there is provided a communications network having a plurality of nodes connected with links, the network comprising means for selecting two maximally disjoint shortest paths between source and destination nodes in the network, the means being capable of performing the steps of the method for selecting two maximally disjoint shortest paths in the network as described above.

[0085] According to yet another aspect of the invention there is provided a communications network having a plurality of nodes connected with links, the network comprising means for selecting “N” maximally disjoint shortest paths between source and destination nodes in the network, the means being capable of performing the steps of the method for selecting “N” maximally disjoint shortest paths in the network described above.

[0086] According to one more aspect of the invention there is provided an apparatus for selecting two maximally disjoint shortest paths between source and destination nodes in the network, the apparatus comprising a path computation processor capable of performing the steps of the method for selecting two maximally disjoint shortest paths in the network as described above.

[0087] According to one more aspect of the invention there is provided an apparatus for selecting “N” maximally disjoint shortest paths between source and destination nodes in the network, the apparatus comprising a path computation processor capable of performing the steps of the method for selecting “N” maximally disjoint shortest paths in the network described above.

[0088] Advantages of the embodiments of the invention lie in significant simplifications of finding maximally disjoint shortest paths in a network compared to the currently known methods. It results in a more efficient implementation of the method, which, in turn, permits maximally disjoint paths to be determined more quickly and for larger or more complex networks, for which existing methods would have been too slow or cumbersome.

BRIEF DESCRIPTION OF THE DRAWINGS

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

[0090]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;

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

[0092]FIG. 3 is a flow chart illustrating the step <b>26</b> of network transformation of FIG. 2 in more detail;

[0093]FIG. 4 is a flow chart illustrating the step <b>108</b> of examining outgoing links and assigning conditional link costs of FIG. 3 in more detail;

[0094]FIG. 5 is a flow chart illustrating the step <b>28</b> of obtaining a second explicit route of FIG. 2 in more detail;

[0095]FIG. 6 is a flow chart illustrating the step <b>306</b> of determining a conditional link cost of FIG. 5 in more detail;

[0096]FIG. 7 is a flow chart illustrating the step <b>310</b> of assigning an explicit route of FIG. 5 in more detail;

[0097]FIG. 8 is a flow chart illustrating the step <b>29</b> of removing conditional links of FIG. 2 in more detail;

[0098]FIG. 9 is a flow chart illustrating the step <b>608</b> of resetting outgoing links of FIG. 8 in more detail;

[0099]FIG. 10 is a flow chart illustrating a method for selecting N maximally disjoint shortest paths according to a second embodiment of the invention;

[0100]FIG. 11 is a flow chart illustrating the step <b>706</b> of network transformation of FIG. 10 in more detail;

[0101]FIG. 12 is a flow chart illustrating the step <b>808</b> of examining outgoing links and assigning conditional link costs of FIG. 11 in more detail; and

[0102]FIG. 13 is a flow chart illustrating the step <b>901</b> of examining prior settings of a conditional link of FIG. 12 in more detail.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0103] An example of a network <b>10</b> 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 <b>10</b> 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.

[0104] Also shown in FIG. 1 is a path computation processor <b>12</b>, associated with node “A”. There may be a path computation processor <b>12</b> associated with other nodes as well, but only the path computation processor <b>12</b> associated with node “A” is shown. The path computation processor <b>12</b> 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 <b>12</b>, 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.

[0105] 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 <b>10</b> illustrated in FIG. 1 is of great simplicity, but sufficient to illustrate the method.

[0106] A high-level flow chart <b>20</b> of the method of the first embodiment is shown in FIG. 2. The flow chart includes seven steps in a simple sequence, beginning at step <b>22</b> (“Start”), continuing through step <b>24</b> (“Get First Explicit Route”), step <b>26</b> (“Transform Network”), step <b>28</b> (“Get Second Explicit Route”), step <b>29</b> (“Remove Conditional Links”), step <b>30</b> (“Coalesce two Explicit Routes”), and ending at step <b>32</b> (“Return two Maximally Disjoint Paths”).

[0107] At the step <b>22</b> (“Start”), the network topology (for example, the network <b>10</b> of FIG. 1), including link costs, and the identities of the source and destination nodes between which paths are to be found (for example nodes A and Z of FIG. 1) are known.

[0108] The step “Get First Explicit Route” <b>24</b> uses a shortest path first (SPF) algorithm of the known art, for example a Dijkstra SPF algorithm, to find a first shortest path. Using the example network <b>10</b> of FIG. 1 again, step <b>24</b> will determine the first explicit route as AB-BC-CZ.

[0109] In the step “Transform Network” <b>26</b>, a transformation of the network <b>10</b> of FIG. 1 will be generated as described in detail later (FIGS. 3 and 4). Network transformation is a step that assigns conditional links, based on the first explicit route found in step <b>24</b>.

[0110] The step “Get Second Explicit Route” <b>28</b> uses a modified SPF algorithm on the transformed network to generate the second explicit route. This step will be described in more detail later (FIGS. 5, 6, and <b>7</b>). In the example network <b>10</b> of FIG. 1, the second explicit route will be determined by step <b>28</b> as AD-DC-CB-BE-EZ.

[0111] In the step “Remove Conditional Links” <b>29</b> the conditional links of the first explicit route that were assigned in step <b>26</b> (“Transform Network”) are removed as they are no longer needed. Step <b>29</b> will be described in detail later (FIGS. 8 and 9).

[0112] The step “Coalesce two Explicit Routes” <b>30</b> takes the two generated explicit routes and “coalesces” them. The process of explicit route coalescence is described in detail in the reference text book “Survivable Networks: Algorithms for Diverse Routing” by Dr. Ramesh Bhandari, Kluwer Academic Publishers, 1999. After coalescence performed by step <b>30</b>, the two explicit routes from steps <b>24</b> and <b>28</b>, again based on FIG. 1, will be AB-BE-EZ (shown as lines of long dashes, reference number <b>14</b>) and AD-DC-CZ (shown as lines of short dashes, reference number <b>16</b>).

[0113] The two explicit routes are finally returned as the result of the algorithm in step <b>32</b> “Return two Maximally Disjoint Paths”. Using the example of FIG. 1, the method has found the two explicit routes AB-BE-EZ (<b>14</b>) and AD-DC-CZ (<b>16</b>), which are disjoint (do not share any links or nodes) and are the shortest disjoint pair possible. The coalesced explicit routes thus constitute two maximally disjoint paths.

[0114] Network Transformation

[0115] The description of step <b>26</b> (“Transform Network”) of FIG. 2 will now be expanded with the aid of FIGS. 3 and 4. FIG. 3 is a more detailed flow chart of the step <b>26</b> “Transform Network”, including step <b>100</b> (“Assign Previous Node”), step <b>102</b> (“Assign Current Node”), step <b>104</b> (“Assign Next Node”), step <b>106</b> (“Is Next Node Empty?”), step <b>108</b> (“Examine Outgoing Links”), step <b>110</b> (“Set Previous Node”); step <b>112</b> (“Set Current Node”), and step <b>114</b> (“Set Next Node”).

[0116] As mentioned earlier, standard shortest path first algorithms use the concept of “link cost” to select the “shortest” path, where the link cost is an attribute of the network. Each link in the network has an associated link cost, which does not change during the path search. Furthermore, the link cost of a link is generally independent of link direction (link cost of link AB is the same as link cost of link BA in FIG. 1).

[0117] In the method of the invention, each link has three additional associated variables, a conditional link cost LC<b>1</b>, a conditional link cost LC<b>2</b>, and a router list RTR_List.

[0118] The conditional link costs LC<b>1</b> and LC<b>2</b>, and the RTR_List are assigned and used during step <b>26</b> (“Transform Network”), based on the result of the path search of step <b>24</b>.

[0119] The conditional link costs and RTR_List are assigned in step <b>108</b> (“Examine Outgoing Links”, a step of the step <b>26</b>, “Transform Network” of FIG. 2), and will be used in step <b>28</b> (“Get Second Explicit Route”) of FIG. 2, as described below. To differentiate conditional link costs (LC<b>1</b> and LC<b>2</b>) from the fixed “link cost” defined as an attribute of the network, the fixed link cost will be referred to as “original link cost”.

[0120] The step <b>26</b> includes a loop (steps <b>106</b> to <b>114</b>) in which all links of the first explicit route (see step <b>24</b>, FIG. 1) are processed to determine the conditional link costs.

[0121] To initialize the loop, the first node of the first explicit route (in the example, the source node A of FIG. 1) is assigned to a variable “Previous_Node” (step <b>100</b>), the second node of the first explicit route (node B in FIG. 1) is assigned to a variable “Current_Node” (step <b>102</b>), and the third node (C) of the first explicit route is assigned to a variable “Next_Node” (step <b>104</b>).

[0122] Before the loop is entered, a check is made to see if “Next_Node” is empty (step <b>106</b>). This handles the case where the explicit route contains only two nodes, in which case “Next_Node” is empty, and step <b>26</b> is completed (exit step <b>106</b> at “YES”, and continue to step <b>28</b>). In most cases, there are at least three nodes in the explicit route, and step <b>106</b> is exited through the path marked “NO”.

[0123] Step <b>108</b> (“Examine Outgoing Links”) is further expanded in FIG. 4 as will be described below.

[0124] In step <b>110</b> (“Set Previous Node”) the variable “Previous_Node” is set to the value of “Current_Node”, in step <b>112</b> (“Set Current Node”) the variable “Current_Node” is set to the value of “Next_Node”, and in step <b>114</b> (“Set Next Node”) the variable “Next_Node” is set to the value of the node after “Next_Node” in the explicit route. In effect, at the end of the first iteration of the loop (steps <b>106</b> to <b>114</b>), the three variables “Previous_Node”, “Current_Node” and “Next_Node” are set to reflect the second, third, and fourth nodes of the explicit route. After the second iteration they reflect the third, fourth, and fifth nodes, and so on.

[0125] When the end of the explicit route is reached, this will be evident in step <b>106</b>, when the variable “Next_Node” is found to be “empty”. This causes the loop to terminate through the YES exit of step <b>106</b>, and go to step <b>28</b> (FIG. 2).

[0126] Step <b>108</b> (“Examine Outgoing Links”) is expanded and described with the aid of FIG. 4. The purpose of step <b>108</b> is to evaluate all outgoing links from the “Current Node” and adjust their conditional link costs LC<b>1</b> and LC<b>2</b> and the RTR_List. Initially (before step <b>22</b>), the conditional link costs LC<b>2</b> of all links are set to zero, and the RTR_List is NULL.

[0127] Step <b>108</b> expands into the following steps:

[0128] “Select First Outgoing Link” <b>200</b>;

[0129] “Is This a Link to Previous Node” <b>202</b>;

[0130] “Set LC<b>1</b>=Original Link Cost” <b>204</b>;

[0131] “Is This a Link to Next Node” <b>206</b>;

[0132] “Set LC<b>1</b>=Original Link Cost+Large Cost” <b>208</b>;

[0133] “Set LC<b>1</b>=Original Link Cost, Set RTR_List=Next Node, and Set LC<b>2</b>=Original Link Cost+Large Cost” <b>210</b>;

[0134] “Is This the Last Outgoing Link?” <b>212</b>; and

[0135] “Select Next Outgoing Link” <b>214</b>.

[0136] These steps form a loop that examines all outgoing links from the current node. A first outgoing link is selected in step <b>200</b>. Step <b>202</b> examines if the link is a link to the Previous Node (assigned in step <b>100</b> or step <b>110</b> of FIG. 3). If it is a link to the Previous Node (exit labeled “YES” from step <b>202</b>), conditional link cost LC<b>1</b> is set to the original link cost (step <b>204</b>). If the link is not a link to the Previous Node (exit “NO” from step <b>202</b>), a further examination is made in step <b>206</b> to determine if the link is a link to the Next Node (assigned in step <b>104</b> or step <b>114</b> of FIG. 3). If it is a link to the Next Node (exit labeled “YES” from step <b>206</b>), conditional link cost LC<b>1</b> is set to the original link cost plus a large cost (step <b>208</b>), where the large cost is of the order of several times the sum of all original link costs in the network, e.g. as large as four times the sum of all original link costs in the network.

[0137] The value of the large cost is selected based on the following reason. As explained earlier, link cost is used to guide the path selection algorithm into finding the shortest path. A large link cost makes it less likely that a link is selected to become a link in the shortest path. After a large cost of the order of several times the sum of all original link costs in the network is added to the link cost of a link, it is guaranteed that this link will not be selected during a shortest path search unless there is no other link available.

[0138] If the link is not a link to the Next Node (exit “NO” from step <b>206</b>), LC<b>1</b> is set to the original link cost, RTR_List is set to the Next Node, and LC<b>2</b> is set to the original link cost plus the large cost (step <b>210</b>).

[0139] Step <b>212</b> (“Is This the Last Outgoing Link?”) is used to determine if all links have been processed. If the result is “YES”, step <b>108</b> of FIGS. 3 and 4 is complete, and the algorithm continues with step <b>110</b> as shown in FIG. 3. If there are more links to be processed (exit “NO” from step <b>212</b>), the next outgoing link is selected in step <b>214</b>, and the procedure <b>108</b> is repeated starting at step <b>202</b>.

[0140] Second Explicit Route Computation

[0141] The description of step <b>28</b> of FIG. 2 will now be expanded with the aid of FIGS. 5, 6 and <b>7</b>.

[0142] The computation of the second explicit route is a modified version of the SPF algorithm. It may be recalled that in SPF algorithm all nodes of the network are listed initially in a candidate list (of nodes). It may also be recalled that the purpose of the SPF algorithm is to find a shortest path from a source node to a destination node (for example, from node A to node Z in FIG. 1). A second list of nodes called the SPF list, is initially empty. At the start of the SPF algorithm, the source node is removed from the candidate list, becomes the “current node”, and is placed in the SPF list. As the SPF algorithm progresses, links to adjacent nodes of the “current node” are evaluated, and adjacent nodes are placed in the SPF list, based on the accumulated cost to reach them from the source node. At the same time an “explicit route” (list of nodes on the shortest path from the source node) is maintained. When all links of the “current node” have been evaluated, the last node of the current “explicit path” becomes the “current node”. The SPF algorithm terminates when the “explicit route” reaches the destination node.

[0143] For the SPF algorithm to work, it is not necessary to have all nodes of the network to be initially listed in the candidate list. The algorithm will also work if it starts at the source node and fills in the candidate list for all neighbors the source node is currently connecting to. The algorithm keeps on filling in the candidate list every time it reaches a new node.

[0144] The step <b>28</b> of FIG. 2 of the method of the first embodiment (“Get Second Explicit Route”) follows the SPF algorithm, but is modified to make use of the conditional link costs LC<b>1</b> and LC<b>2</b>, and the value of RTR_List (resulting from the step <b>26</b> “Transform Network” of FIG. 2) instead of the original link costs.

[0145] Step <b>28</b> expands into a number of steps shown in FIG. 5 (steps <b>300</b>-<b>318</b>), two of which are further expanded into more detailed steps (FIG. 6 is an expansion of step <b>306</b>, and FIG. 7 is an expansion of step <b>310</b>).

[0146] Coming from step <b>26</b> (see FIG. 2), step <b>28</b>, expanded in FIG. 5, starts with step <b>300</b> (“Set V=Source Node, Cost to Reach V=0”) and step <b>302</b> (“Select First Outgoing Link, Set W=Neighbor of V”). This is followed by a loop which starts with a decision step <b>304</b> (“Were all Links Processed?”) and ends with either the step <b>318</b> (“Select Next Outgoing Link, Set W=Neighbour of V”) or the step <b>316</b>(“Select First Outgoing Link, Set W=Neighbour of V”). Within the body of the loop, a first sequence of steps (from exit “NO” of step <b>304</b>) includes step <b>306</b> (“Determine Conditional Link Cost LC”), step <b>308</b> (“Explicit Route Cost=Cost to Reach V+LC”), and step <b>310</b> (“Compute Explicit Route”). A second sequence of steps starts from exit “YES” of step <b>304</b> and includes steps <b>312</b> (“Is Candidate List Empty?”), step <b>314</b> (“Select V=Lowest Cost Node from Candidate List”), step <b>315</b> (“Insert V into SPF List”), and step <b>316</b>(“Select First Outgoing Link, Set W=Neighbour of V”). Step <b>312</b> (“Is Candidate List Empty?”) is a decision step. If the result is “YES”, the loop is exited, and the algorithm goes to step <b>30</b> of FIG. 2. If the result is “NO”, the loop continues with step <b>314</b>.

[0147] Step <b>28</b> (“Get Second Explicit Route”) uses two node variables V and W, where V identifies a node (the “current node”), and W identifies a node which can be reached from V through an outgoing link, that is a link from V to W. Associated with each node is a “cost to reach” value, which is computed during the process of step <b>28</b>. The “cost to reach” of node V represents the accumulated (summed) cost of the links from the source node to the node V.

[0148] The links from the source node to the node V constitute the current “explicit route” to V. When step <b>28</b> finishes, V will be the destination node, and the “explicit route” to V will be the “Second Explicit Route”, which is computed by step <b>28</b>.

[0149] When step <b>28</b> starts, i.e. in step <b>300</b>, V is assigned to the source node (e.g. A in the example of FIG. 1), and the cost to reach V is set to 0.

[0150] In step <b>302</b>, the loop (steps <b>304</b> to <b>318</b>) is initialized by setting the variable W to the neighbor node of V that is reached over the first outgoing link of V.

[0151] Step <b>304</b> is a decision step that determines whether all links from V have been processed. If the result is “NO”, the flow of the algorithm is directed through steps <b>306</b>, <b>308</b>, and <b>310</b>, to step <b>318</b> (“Select Next Outgoing Link, Set W=Neighbor of V”). In step <b>318</b>, the next outgoing link of node V is selected, and the corresponding neighbor node of V is assigned to W. Processing then continues at the decision step <b>304</b>.

[0152] In step <b>306</b> (“Determine Conditional Link Cost LC”), a conditional link cost LC is determined. Step <b>306</b> is <b>5</b> expanded in FIG. 6 and described in more detail below.

[0153] The cost to reach node W is computed in step <b>308</b> as the sum of the “cost to reach” node V plus the conditional link cost LC from step <b>306</b>. It is assigned to the “Explicit Route Cost” (box <b>308</b>).

[0154] In step <b>310</b> (“Compute Explicit Route”), a number of special cases are considered, and the “explicit route” from the source node to the current node V is computed or re-computed. This step is expanded in FIG. 7 and described in more detail below.

[0155] When the result of the decision step <b>304</b> (“Were all Links Processed?”) is “YES”, all outgoing links of the node V have been processed, that is all neighboring nodes of node V have a “cost to reach” assigned to them. Processing then continues with the decision step <b>312</b> (“Is Candidate List Empty?”).

[0156] If the result of decision step <b>312</b> is “NO”, the candidate list is scanned to find the node with the lowest “cost to reach” (step <b>314</b> “Select V=Lowest Cost Node from Candidate List”) and assigned to the variable V. The selected node V is removed from the candidate list and inserted in the SPF list (step <b>315</b> “Insert V into SPF List”). In step <b>316</b> (“Select First Outgoing Link, Set W=Neighbour of V”), the loop (starting at step <b>304</b>) is initialized again by setting the variable W to the neighbor node of V that is reached over the first outgoing link of V.

[0157] If the result of decision step <b>312</b> is “YES”, there remain no more nodes in the candidate list, and step <b>28</b> is finished. The “Second Explicit Route”, computed by step <b>28</b>, is the last “explicit route” computed in step <b>310</b>.

[0158] The reader's attention is now directed to the detailed description of step <b>306</b> (“Determine Conditional Link Cost LC”), which is expanded in FIG. 6.

[0159] Step <b>306</b> includes the decision steps <b>400</b> (“Is LC<b>2</b>=Zero?”) and <b>402</b> (“Is Previous Node=RTR_List”), as well as the assignment steps <b>401</b> (“Set Previous Node=2^ndLast hop of the explicit route”), <b>404</b> (“Set Link Cost LC=LC<b>2</b>”) and <b>406</b> (“Set Link Cost LC=LC<b>1</b>”). The exit “NO” from step <b>400</b> leads through assignment step <b>401</b> to the further decision step <b>402</b>, while exit “YES” from step <b>400</b> leads to the assignment step <b>406</b>. Exit “NO” from decision step <b>402</b> leads to the assignment step <b>404</b>, and exit “YES” from step <b>402</b> leads to the assignment step <b>406</b>.

[0160] “Previous Node” is a temporary variable used only in step <b>306</b>. It is set in step <b>401</b> to a value, which is found by scanning the current “explicit route” back to the second last node. “Previous Node” is then compared in decision step <b>402</b> with the link's current RTR_List (that had been set in step <b>210</b> of FIG. 4).

[0161] The result of step <b>306</b> is the assignment of either LC<b>2</b> (step <b>406</b>) or LC<b>1</b> (step <b>404</b>) to the conditional link cost LC, which is used by the subsequent step <b>308</b> (in FIG. 5). The values of LC<b>1</b> and LC<b>2</b>, associated with each of the links in the network, were previously determined in step <b>26</b> (“Transform Network”) of the method. The decision logic (steps <b>400</b> and <b>402</b> together) has the result that the conditional link cost LC is set to the value LC<b>1</b> if either the value of LC<b>2</b> is zero, or if the previous node in the “explicit route” is equal to the link's RTR_list. Otherwise, LC is set to LC<b>2</b>.

[0162] The reader's attention is now directed to the detailed description of step <b>310</b> (“Compute Explicit Route”), which is expanded in FIG. 7.

[0163] The expanded step <b>310</b> in FIG. 7 includes a number of decision steps (steps <b>500</b>, <b>502</b>, <b>504</b>, <b>506</b>, <b>508</b>, <b>510</b>, <b>512</b>), three action steps (<b>514</b>, <b>518</b>, <b>520</b>), and a “no action” step (<b>516</b>). The decision steps <b>500</b> to <b>512</b> form a decision tree resulting in one of three actions <b>514</b>, <b>518</b>, <b>520</b>, or no action <b>516</b>.

[0164] Because of the complexity of the conditions upon which the decisions are based, some of the conditions are identified in FIG. 7 only as “Condition #i”, “i” ranging from 1 to 5. Similarly, the actions are identified in FIG. 7 only as “Action #j”, “j” ranging from 1 to 3.

[0165] The purpose of step <b>310</b> (“Compute Explicit Route”) is to evaluate the currently processed node W (assigned in steps <b>302</b> and <b>318</b> of FIG. 5), which is one of the neighbors of the current node V.

[0166] At the start of step <b>310</b>, the cost to reach node W has been determined as the “Explicit Route Cost” (step <b>308</b>, FIG. 5).

[0167] The node W will be found either in the SPF list (decision step <b>500</b> “Is W in SPF list?” exit “YES”), in the Candidate list (tracing through decision step <b>500</b> exit “NO” leading to decision step <b>504</b> “Is W in Candidate List?” exit “YES”), or in neither list (tracing through decision step <b>500</b> exit “NO” and decision step <b>504</b> exit “NO”).

[0168] If the node W is in the SPF list (decision step <b>500</b>, exit “YES”), condition #<b>1</b> is evaluated (decision step <b>502</b>). If the result of condition #<b>1</b> is “NO”, step <b>514</b> (action #<b>1</b>) is executed. If the result of condition #<b>1</b> is “YES”, then the series of conditions #<b>2</b> to #<b>4</b> (decision steps <b>506</b>, <b>510</b>, <b>512</b>) is evaluated. If the result of all these conditions is “YES”, action #<b>1</b> (step <b>514</b>) is also executed; however if the result of any of the conditions #<b>2</b>, #<b>3</b>, or #<b>4</b> is “NO”, then no action is taken (pro-forma step <b>516</b> “No Action”).

[0169] If the node W is in the Candidate list (exit “YES” from decision step <b>504</b>), then a further condition is tested (condition #<b>5</b> in decision step <b>508</b>). If the result of step <b>508</b> is “YES”, action #<b>2</b> is executed (step <b>518</b>, “Action #<b>2</b>”), otherwise no action is taken (pro-forma step <b>516</b> “No Action”).

[0170] If the result of the decision step <b>504</b> (“Is W in Candidate list?”) is “NO”, then action #<b>3</b> is taken (step <b>520</b>, “Action #<b>3</b>”).

[0171] After any of the actions #1, #2, #3 or no action <b>516</b>, step <b>310</b> is completed, and processing continues with step <b>318</b> (FIG. 5).

[0172] Having described the logical flow of the steps, which make up the step <b>310</b>, we will now describe in detail the conditions and actions of these steps.

[0173] The conditions generally constitute tests, involving the node W and its neighbours, namely:

[0174] Condition #1: Is the explicit route cost (computed in step <b>308</b>) greater than the previously recorded cost to reach W?

[0175] Condition #2: Is node W not equal to the destination node?

[0176] Condition #3: Are all nodes that are neighbors of node W not equal to the destination node?

[0177] Condition #4: Do any of the nodes that are neighbors of node W have a link that has RTR_List equal to W?

[0178] Condition #5: Is the explicit route cost (computed in step <b>308</b>) less than the previously recorded cost to reach W?

[0179] Action #1: Re-calculate the “explicit route” using the “explicit route” associated with node V; remove node W from the SPF list and put it back in the Candidate list.

[0180] Action #2: Re-calculate the “explicit route” using the “explicit route” associated with node V; record the “cost to reach” W as the value of the “explicit route cost” computed in step <b>308</b>.

[0181] Action #3: Calculate the “explicit route” using the “explicit route” associated with node V; insert node W into the Candidate list.

[0182] Remove Conditional Links

[0183] The description of step <b>29</b> of FIG. 2 will now be expanded with the aid of FIGS. 8 and 9.

[0184] Step <b>29</b>, expanded in FIG. 8, is similar to step <b>26</b>, which was expanded in FIG. 3. The purpose of step <b>29</b> (“Remove Conditional Links”) is to reset the values that were set in step <b>26</b> (“Transform Network”). To recall, step <b>26</b> (FIG. 3) includes a loop to visit nodes of the first explicit route. The operative step in step <b>26</b>, which sets the values LC<b>1</b>, LC<b>2</b> and RTR_List, is step <b>108</b> “Examine Outgoing Links”.

[0185] Step <b>29</b> includes the same loop structure as step <b>26</b>. The steps <b>600</b>, <b>602</b>, <b>604</b>, <b>606</b>, <b>610</b>, <b>612</b>, and <b>614</b>, in FIG. 8 are equivalent to the corresponding steps <b>100</b>, <b>102</b>, <b>104</b>, <b>106</b>, <b>110</b>, <b>112</b> and <b>114</b> in FIG. 3. The operative step in step <b>29</b>, which resets the values LC<b>1</b>, LC<b>2</b> and RTR_List, is step <b>608</b> “Reset Outgoing Links”.

[0186] Step <b>608</b> (“Reset Outgoing Links”) is further expanded and described with the aid of FIG. 9. The purpose of step <b>608</b> is to consider all outgoing links from the “Current Node” and reset their conditional link costs LC<b>1</b> and LC<b>2</b> and the RTR_List. This will restore these values to the same condition they had before step <b>26</b> (“Transform Network”), that is the conditional link costs LC<b>1</b> and LC<b>2</b> of all links are set to zero, and their RTR_List is set to NULL.

[0187] Step <b>608</b> expands into the following steps:

[0188] “Select First Outgoing Link” <b>620</b>;

[0189] “Is LC<b>1</b>=0 and LC<b>2</b>=0?” <b>622</b>;

[0190] “Set LC<b>1</b>=0, Set RTR_List=0, Set LC<b>2</b>=0” <b>624</b>;

[0191] “Is This the Last Outgoing Link?” <b>626</b>; and

[0192] “Select Next Outgoing Link” <b>628</b>.

[0193] These steps form a loop that processes all outgoing links from the current node.

[0194] A first outgoing link is selected in step <b>620</b>. The decision step <b>622</b> examines if the conditional link costs LC<b>1</b> and LC<b>2</b> of this link are zero. If either LC<b>1</b> or LC<b>2</b> are not zero (exit “NO” from step <b>622</b>), then step <b>624</b> follows, in which the conditional link cost LC<b>1</b> and LC<b>2</b> are set to zero and the RTR_List is set to NULL. If both LC<b>1</b> and LC<b>2</b> are zero (exit “YES” from step <b>622</b>), the step <b>624</b> is bypassed.

[0195] Step <b>626</b> (“Is This the Last Outgoing Link?”) is used to determine if all links have been processed. If the result is “YES”, step <b>608</b> of FIGS. 8 and 9 is complete, and the procedure continues with step <b>610</b> as shown in FIG. 8. If there are more links to be processed (exit “NO” from step <b>626</b>), the next outgoing link is selected in step <b>628</b>, and the loop of the procedure <b>608</b> is repeated starting at step <b>622</b>.

[0196] Thus, an efficient method is provided for determining two maximally disjoint shortest paths in a network. Using the method illustrated in FIG. 2 and further detailed in FIGS. <b>3</b>-<b>9</b>, two maximally disjoint shortest paths can be found from a source node to a destination node. For example, in the network illustrated in FIG. 1, the two maximally disjoint paths from source “A” to destination “Z” computed by the method are AB-BE-EZ (shown by lines of long dashes and designated by reference numeral <b>14</b>) and AD-DC-CZ (shown by lines of short dashes and designated by reference numeral <b>16</b>).

[0197] The method of the first embodiment described above is efficient because the network transformation of the method does not require the splitting of nodes, but rather relies on identifying conditional links, while the determination of the second explicit route is based on a SPF algorithm modified in a simple manner to take into account the conditional links.

[0198] Extension to Greater than Two Paths

[0199] A method for selecting N maximally disjoint shortest paths in a network according to the second embodiment of the invention is illustrated by flow chart <b>700</b> shown in FIG. 10. It is assumed that N is equal or greater than 2.

[0200] The flow chart <b>700</b> includes nine steps, beginning at step <b>702</b> (“Start”), continuing through step <b>704</b> (“Get First Explicit Route”), step <b>706</b> (“Transform Network”), decision step <b>708</b> (“Repeated for All Explicit Routes?”), step <b>710</b> (“Get Next Explicit Route”), step <b>712</b> (“Remove Conditional Links”), step <b>714</b> (“Coalesce the Explicit Routes”), a decision step <b>716</b> (“Is the number of paths found less than N?”), and step <b>718</b> (“Return The Maximally Disjoint Paths”). The exit labeled “NO” of the decision step <b>708</b> leads back to step <b>706</b>, forming a loop as long as the condition of <b>708</b> is not satisfied. The exit labeled “YES” of decision step <b>708</b> permits the method to continue with step <b>710</b>. The exit labeled “YES” of the decision step <b>716</b> leads back to step <b>706</b>, in effect forming a loop as long as the condition of <b>716</b> is satisfied. The exit labeled “NO” of step <b>716</b> leads to step <b>718</b>, which terminates the method.

[0201] The method of the second embodiment is presented in its entirety, but reference is made to equivalent and similar steps of the method of the first embodiment in order to simplify the description.

[0202] At the Start <b>702</b>, the network topology, including link costs and the identities of the source and destination nodes, are known. This step is equivalent to step <b>22</b> of FIG. 2.

[0203] The step “Get First Explicit Route” <b>704</b> uses a shortest path first (SPF) algorithm of the known art, for example a Dijkstra SPF algorithm, to find a first shortest route. This step is equivalent to step <b>24</b> of FIG. 2.

[0204] In the step “Transform Network” <b>706</b> a transformation of the network will be generated, taking into account one of the explicit routes found so far. This step is similar to, but not exactly the same as, step <b>26</b> of FIG. 2. Step <b>706</b> is described in detail with the help of FIGS. 11, 12, and <b>13</b>.

[0205] The step <b>706</b> (“Transform Network”) is expanded in FIG. 11. The step <b>706</b> has the same loop structure as step <b>26</b> in FIG. 3. The steps <b>800</b>, <b>802</b>, <b>804</b>, <b>806</b>, <b>810</b>, <b>812</b>, and <b>814</b> in FIG. 11 are equivalent to the corresponding steps <b>100</b>, <b>102</b>, <b>104</b>, <b>106</b>, <b>110</b>, <b>112</b>, and <b>114</b> in FIG. 3. The operative step in step <b>706</b>, which examines the outgoing links and sets the values LC<b>1</b>, LC<b>2</b> and RTR_List, is step <b>808</b> “Examine Outgoing Links”. The step <b>808</b> in FIG. 11 is similar to, but not the same as, the corresponding step <b>108</b> in FIG. 3. Step <b>808</b> is described in detail with the help of FIGS. 12 and 13.

[0206] The step <b>808</b> (“Examine Outgoing Links”) is expanded in FIG. 12. The step <b>808</b> is similar to the step <b>108</b>, shown in detail in FIG. 4. Steps <b>900</b>, <b>902</b>, <b>904</b>, <b>906</b>, <b>908</b>, <b>910</b>, <b>912</b>, and <b>914</b> in FIG. 12 are equivalent to the corresponding steps <b>200</b>, <b>202</b>, <b>204</b>, <b>206</b>, <b>208</b>, <b>210</b>, <b>212</b>, and <b>214</b> in FIG. 4. The step <b>808</b>, however, includes an additional step <b>901</b> (“Examine Prior Setting of Conditional Link”).

[0207] The step <b>901</b> is performed before the step <b>902</b>. The step <b>901</b> has one entry point, and can be reached from step <b>900</b> (“Select First Outgoing Link”), as well as from step <b>914</b> (“Select Next Outgoing Link”). The step <b>901</b> has two exits links labeled <b>916</b> and <b>918</b>. The exit link <b>916</b> of step <b>901</b> leads to the step <b>902</b>. The exit link <b>918</b> of step <b>901</b> leads to the step <b>912</b>.

[0208] The purpose of the step <b>901</b> (which was not needed in the first embodiment) is to examine the parameters LC<b>1</b> and LC<b>2</b>, which may already have been set during the computation of a previous network transformation (please, recall from FIG. 10, which shows that step <b>706</b> “Transform Network” may be entered a number of times).

[0209] The step <b>901</b> is expanded and described in detail in FIG. 13. The step <b>901</b> includes three steps, a decision step <b>920</b> (“Is LC<b>1</b>=0 and LC<b>2</b>=0?”), a decision step <b>922</b> (“Is LC<b>1</b>=Original Link Cost”), and a step <b>924</b> (“Set LC<b>1</b>=LC<b>1</b>+Large Cost”).

[0210] The decision step <b>920</b> (“Is LC<b>1</b>=0 and LC<b>2</b>=0?”) is reached from step <b>900</b> and from step <b>914</b> (FIG. 12). The exit labeled “YES” from step <b>920</b> leads via link <b>916</b> to step <b>902</b> (FIG. 12). The exit “NO” from step <b>920</b> leads to the decision step <b>922</b> (“Is LC<b>1</b>=Original Link Cost”). The exit of step <b>922</b> labeled “YES” leads via link <b>918</b> to step <b>912</b> (FIG. 12). The exit of step <b>922</b> labeled “NO” leads to the step <b>924</b> (“Set LC<b>1</b>=LC<b>1</b>+Large Cost”). The exit of step <b>924</b> leads via the link <b>918</b> to step <b>912</b> (FIG. 12).

[0211] In step <b>920</b> (“Is LC<b>1</b>=0 and LC<b>2</b>=0?”) a determination is made whether both LC<b>1</b> and LC<b>2</b> of the link being examined are zero. If this is true (exit labeled “YES”), this indicates that the link has not been set as a conditional link during a prior iteration of the network transformation step. Consequently, the procedure continues with step <b>902</b>.

[0212] If the determination of step <b>920</b> results in a decision of “NO”, this indicates that the link may have a prior setting as a conditional link, and step <b>922</b> is entered.

[0213] In step <b>922</b> (“Is LC<b>1</b>=Original Link Cost”), a comparison of the value of the LC<b>1</b> parameter with the original link cost of the link is made. If the two values are equal (exit labeled “YES”), the algorithm continues with step <b>912</b> (FIG. 12). If the two values are not equal (exit labeled “NO”), the procedure continues with step <b>924</b>.

[0214] In the step <b>924</b>, the conditional link cost LC<b>1</b>, whatever its current value, is incremented by the value of a large cost, where the large cost is of the order of several times the sum of all original link costs in the network, e.g. as large as four times the sum of all original link costs in the network (for the rationale, please see the description of step <b>108</b> in the first embodiment). After step <b>924</b>, the procedure continues with step <b>912</b> (FIG. 12).

[0215] The step “Get Next Explicit Route” <b>710</b> in FIG. 10 uses a modified SPF algorithm to generate the next explicit route. This step is equivalent to step <b>28</b> of FIG. 2 and expanded in detail in FIGS. 5, 6, and <b>7</b>, described earlier.

[0216] The step “Coalesce the Explicit Routes” <b>714</b> takes all explicit routes found so far and “coalesces” them. This step is similar to step <b>610</b> of FIG. 2, but not exactly the same. The process of explicit route coalescence for more than two routes is described in detail in the reference text book “Survivable Networks: Algorithms for Diverse Routing” by Dr. Ramesh Bhandari, Kluwer Academic Publishers, 1999.

[0217] The decision step <b>716</b> (“Is the number of paths found less than N?”) checks the loop condition, causing steps <b>706</b>, <b>708</b>, <b>710</b>, <b>712</b>, and <b>714</b> to be repeated until “N” paths have been found.

[0218] The “N” explicit routes found are finally returned as the “N” maximally disjoint paths in step <b>718</b> “Return the Maximally Disjoint Paths”.

[0219] Thus, the method of the second embodiment of the invention provides an efficient way for determining “N” maximally disjoint paths in a network, where “N” equals two or more.

[0220] The method of the second embodiment is efficient, especially in the case where “N” is greater than two, because the network transformation of the method does not require the splitting of nodes, but rather relies on identifying conditional links, while the determination of the additional explicit routes is based on the SPF algorithm modified in a simple manner to take into account the conditional links.

[0221] Although specific embodiments of the invention have been described in detail, it will be apparent to one skilled in the art that variations and modifications to the embodiments may be made within the scope of the following claims.