Path computation systems and methods for concurrent bi-directional k-optimal paths
Systems and methods include, responsive to defining a routing graph that includes vertices for each node of a plurality of nodes in a network and edges for links interconnecting the plurality of nodes, receiving a request for k shortest paths, where k is an integer>0, between a source node and a destination node of the plurality of nodes; and determining the k shortest paths utilizing a k-shortest path algorithm that utilizes two threads in parallel for each shortest path query, wherein the two threads include i) a shortest path query from the source node to the destination node and ii) a shortest path query from the destination node to the source node. The determining further includes, responsive to a first thread in each shortest path query obtaining a result, utilizing the result from the first thread and terminating a second thread.
1. A non-transitory computer-readable medium having instructions stored thereon for programming a processing device to perform steps of:
responsive to defining a routing graph that includes vertices for each node of a plurality of nodes in a network and edges for links interconnecting the plurality of nodes, receiving a request for k shortest paths, where k is an integer>0, between a source node and a destination node of the plurality of nodes, wherein the k shortest paths are for route determination in the network between the source node and the destination node; and
performing path computation by determining the k shortest paths utilizing a k-shortest path algorithm that utilizes two threads in parallel for each shortest path query, wherein the two threads include i) a shortest path query from the source node to the destination node and ii) a shortest path query from the destination node to the source node, and wherein the determining further comprises performing an early exit of the path computation whenever there is any of a no-connectivity case in either of the two threads and failure of a constraint associated with the request, and, responsive to a first thread of the two threads in each shortest path query obtaining a result, utilizing the result from the first thread and terminating a second thread of the two threads.
2. The non-transitory computer-readable medium of claim 1 , wherein the result includes any of i) no connectivity between the source node and the destination node and ii) a path between two nodes that are used in each shortest path query.
3. The non-transitory computer-readable medium of claim 1 , wherein the result includes any of i) no connectivity between the source node and the destination node, ii) a failure to find a path due to failure of a constraint associated with the request, and iii) a path between two nodes that are used in each shortest path query.
4. The non-transitory computer-readable medium of claim 1 , wherein each shortest path query only uses a result from one of the two threads.
5. The non-transitory computer-readable medium of claim 1 , wherein the k-shortest path algorithm is Yen's algorithm and each shortest path query utilizes Dijkstra algorithm.
6. The non-transitory computer-readable medium of claim 1 , wherein the steps further include
obtaining data from the network, wherein the data includes a topology that describes how a plurality of network elements in the network are connected via the links and additional data defining any of bandwidth availability and spectrum availability on the links; and
defining the routing graph based on the topology.
7. A method comprising:
responsive to defining a routing graph that includes vertices for each node of a plurality of nodes in a network and edges for links interconnecting the plurality of nodes, receiving a request for k shortest paths, where k is an integer>0, between a source node and a destination node of the plurality of nodes, wherein the k shortest paths are for route determination in the network between the source node and the destination node; and
performing path computation by determining the k shortest paths utilizing a k-shortest path algorithm that utilizes two threads in parallel for each shortest path query, wherein the two threads include i) a shortest path query from the source node to the destination node and ii) a shortest path query from the destination node to the source node, and wherein the determining further comprises performing an early exit of the path computation whenever there is any of a no-connectivity case in either of the two threads and failure of a constraint associated with the request, and, responsive to a first thread of the two threads in each shortest path query obtaining a result, utilizing the result from the first thread and terminating a second thread of the two threads.
8. The method of claim 7 , wherein the result includes any of i) no connectivity between the source node and the destination node and ii) a path between two nodes that are used in each shortest path query.
9. The method of claim 7 , wherein the result includes any of i) no connectivity between the source node and the destination node, ii) a failure to find a path due to failure of a constraint associated with the request, and iii) a path between two nodes that are used in each shortest path query.
10. The method of claim 7 , wherein each shortest path query only uses a result from one of the two threads.
11. The method of claim 7 , wherein the k-shortest path algorithm is Yen's algorithm and each shortest path query utilizes Dijkstra algorithm.
12. The method of claim 7 , further comprising
obtaining data from the network, wherein the data includes a topology that describes how a plurality of network elements in the network are connected via the links and additional data defining any of bandwidth availability and spectrum availability on the links; and
defining the routing graph based on the topology.
13. An apparatus comprising:
one or more processors and memory comprising instructions that, when executed, cause the one or more processors to
responsive to defining a routing graph that includes vertices for each node of a plurality of nodes in a network and edges for links interconnecting the plurality of nodes, receive a request for k shortest paths, where k is an integer>0, between a source node and a destination node of the plurality of nodes, wherein the k shortest paths are for route determination in the network between the source node and the destination node, and
performing path computation by determine the k shortest paths utilizing a k-shortest path algorithm that utilizes two threads in parallel for each shortest path query, wherein the two threads include i) a shortest path query from the source node to the destination node and ii) a shortest path query from the destination node to the source node, and wherein there is an early exit of the path computation from the determine when there is any of a no-connectivity case in either of the two threads and failure of a constraint associated with the request, and wherein the k shortest paths are determined through, responsive to a first thread of the two threads in each shortest path query obtaining a result, utilization of the result from the first thread and termination of a second thread of the two threads.
14. The apparatus of claim 13 , wherein the result includes any of i) no connectivity between the source node and the destination node and ii) a path between two nodes that are used in each shortest path query.
15. The apparatus of claim 13 , wherein the result includes any of i) no connectivity between the source node and the destination node, ii) a failure to find a path due to failure of a constraint associated with the request, and iii) a path between two nodes that are used in each shortest path query.
16. The apparatus of claim 13 , wherein each shortest path query only uses a result from one of the two threads.
17. The apparatus of claim 13 , wherein the k-shortest path algorithm is Yen's algorithm and each shortest path query utilizes Dijkstra algorithm.