Method and apparatus for selecting maximally disjoint shortest paths in a network
View Patent ↗A method for selecting two maximally disjoint shortest paths between a source node and destination node in a network is provided. The method comprises determining a first explicit route between the source and destination nodes by using an original link cost for each link in the network, transforming the network by introducing conditional link costs, determining a second explicit route between the source and destination nodes in the transformed network taking into account the conditional link costs, and determining the two maximally disjoint shortest paths between the source and destination nodes by coalescing the first and second explicit routes. Beneficially, the step of introducing conditional link costs comprises 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. Corresponding method for determining “N” maximally disjoint paths in a network, wherein “N” is equal or greater than two, is also provided.
1. A method for selecting two maximally disjoint shortest paths between a source node and destination node in a network, comprising the steps of:
determining a first explicit route between the source and destination nodes by using an original link cost for each link in the network;
transforming the network by introducing conditional link costs;
wherein 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.
determining a second explicit route between the source and destination nodes in the transformed network taking into account the conditional link costs; and
determining the two maximally disjoint shortest paths between the source and destination nodes by coalescing the first and second explicit routes.
2. A method as described in claim 1 , wherein the step of adding the additional parameters comprises adding a first conditional link cost (LC 1 ), a second conditional link cost (LC 2 ), and a router list parameter.
3. A method as described in claim 2 , wherein the step of adding the first conditional link cost comprises adding the first conditional link cost, which is equal to one of the following:
original link cost;
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.
4. A method as described in claim 2 , wherein the step of adding the second conditional link cost comprises adding the second conditional link cost, which is equal to one of the following:
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.
5. A method as described in claim 3 , wherein 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 1 equal to one of the following:
the original link cost plus the large cost, if the link is a link belonging to the first explicit route; and
the original link cost otherwise.
6. A method as described in claim 5 , wherein 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 1 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.
7. A method as described in claim 4 , wherein 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 2 equal to:
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
zero otherwise.
8. A method as described in claim 2 , wherein 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.
9. A method as described in claim 1 , wherein 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:
LC 1 ;
LC 2 ; and
the original link cost.
10. A method as described in claim 9 , wherein 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:
LC is equal to the original link cost if both LC 1 and LC 2 equal to zero;
LC=LC 2 if LC 2 is not zero, and if the router list parameter of the link is not indicating the previous node of the second explicit route; and
LC=LC 1 otherwise.
11. 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:
(a) determining a first explicit route between the source and destination nodes by using an original link cost for each link in the network;
(b) for each explicit route found so far, transforming the network by introducing conditional link costs; wherein 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 each explicit route found so far;
(c) determining the next explicit route between the source and destination nodes in the transformed network taking into account the conditional link costs;
(d) removing conditional link costs;
(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
(f) repeating the steps (b) to (e) “i” number of times, wherein “i”=N−1.
12. A method as described in claim 11 , wherein the step of adding the additional parameters comprises adding a first conditional link cost (LC 1 ), a second conditional link cost (LC 2 ), and a router list parameter.
13. A method as described in claim 12 , wherein the step of adding the first conditional link cost comprises adding the first conditional link cost, which is equal to one of the following:
the original link cost;
the link cost assigned so far;
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;
the link cost assigned so far plus the large cost; and
zero.
14. A method as described in claim 12 , wherein the step of adding the second conditional link cost comprises adding the second conditional link cost, which is equal to one of the following:
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;
the link cost assigned so far plus the large cost; and
zero.
15. A method as described in claim 13 , wherein 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 1 equal to one of the following, the step being performed for each of the explicit routes found so far:
the original link cost plus the large cost, if the link is a link belonging to the explicit route and LC 1 =0 before the step of assigning LC 1 is performed;
the link cost assigned so far plus the large cost, if the link is a link belonging to the explicit route and LC 1 is not zero before the step of assigning LC 1 is performed; and
the original link cost otherwise.
16. A method as described in claim 15 , wherein the step of assigning LC 1 comprises the step of assigning LC 1 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.
17. A method as described in claim 14 , wherein 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 2 equal to one of the following, the step being performed for each of the explicit routes found so far:
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 2 =0 before performing the step of assigning LC 2 ;
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 2 is not zero before performing the step of assigning LC 2 ; and
zero otherwise.
18. A method as described in claim 12 , wherein 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.
19. A method as described in claim 12 , wherein 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:
LC 1 ;
LC 2 ; and
the original link cost.
20. A method as described in claim 19 , wherein 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:
LC is equal to the original link cost if both LC 1 and LC 2 equal to zero;
LC=LC 2 if LC 2 is not zero, and if the router list parameter of the link is not indicating the previous node of the second explicit route;
LC=LC 1 otherwise.
21. 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 described in claim 1 .
22. A communications networks 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 described in claim 11 .
23. 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 described in claim 1 .
24. 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 described in claim 11 .