Ciena Corporation
Path computation systems and methods for concurrent bi-directional k-optimal paths

Abstract:

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.