Disjoint path computation systems and methods in optical networks
Systems and methods for computing disjoint paths in a network considering continuity constraints include, responsive to a request for disjoint paths in the network which are subject to the continuity constraints, initializing a plurality of variables associated with a graph defining the network where edges constitute nodes and vertices constitute links; determining a first path through the graph; determining an auxiliary directed graph based on the first path; and determining a second path through the auxiliary directed graph, wherein the second path is determined by considering entry into cut edges, exit from cut edges, and a destination in the auxiliary directed graph and the plurality of variables are adjusted based on the entry, the exit, and the destination to address the continuity constraints. This approach concept applies to not just continuity constraints but to any constraints, which are non-additive in nature; the objective function is still additive for Shortest Path First (SPF).
1. A computer-implemented method for computing disjoint paths in a network considering continuity constraints, the computer-implemented method comprising:
responsive to a request for disjoint paths in the network which are subject to the continuity constraints, initializing a plurality of variables associated with a graph defining the network where edges constitute nodes and vertices constitute links;
determining a first path through the graph using a Non-Viable Segment without the continuity constraints to yield the first path, P 1 , and a tree, T;
determining an auxiliary directed graph based on the first path by applying weight modifications to the tree, T, and reversing edges of the first path, P 1 ;
determining a second path through the auxiliary directed graph, wherein the second path is determined by considering entry into cut edges, exit from cut edges, and a destination in the auxiliary directed graph and the plurality of variables are adjusted based on the entry, the exit, and the destination to address the continuity constraints; and
causing implementation of the determined first path and the determined second path in the network.
2. The computer-implemented method of claim 1 , wherein the continuity constraints comprise one of wavelength and spectrum continuity in the network.
3. The computer-implemented method of claim 1 , further comprising:
returning no solution if the first path does not exist.
4. The computer-implemented method of claim 1 , wherein the determining the first path and determining the second path utilize Shortest Path First (SPF).
5. The computer-implemented method of claim 1 , wherein the plurality of variables comprise a set of Continuity Constraints (CT) for each of paths CT 1 , CT 2 , and wherein the set of CT are modified traversing the auxiliary directed graph during the determining the second path, and subsequent to reaching the destination, if the set of CT are not empty, the set of CT form the disjoint paths.
6. The computer-implemented method of claim 1 , wherein an alternating path and cut edges are used to apply the continuity constraints for both the disjoint paths during the determining the second path.
7. The computer-implemented method of claim 1 , further comprising:
if no solution is found, reiterating the first path using an updated Non-Viable Segment.
8. The computer-implemented method of claim 1 , wherein the continuity constraints are applied only amongst alternating path segments of the first path and the second path.
9. An apparatus adapted to compute disjoint paths in a network considering continuity constraints, the apparatus comprising:
circuitry adapted to initialize a plurality of variables associated with a graph defining the network where edges constitute nodes and vertices constitute links responsive to a request for disjoint paths in the network which are subject to the continuity constraints;
circuitry adapted to determine a first path through the graph using a Non-Viable Segment without the continuity constraints to yield the first path, P 1 , and a tree, T;
circuitry adapted to determine an auxiliary directed graph based on the first path by applying weight modifications to the tree, T, and reversing edges of the first path, P 1 ; and
circuitry adapted to determine a second path through the auxiliary directed graph, wherein the second path is determined by considering entry into cut edges, exit from cut edges, and a destination in the auxiliary directed graph and the plurality of variables are adjusted based on the entry, the exit, and the destination to address the continuity constraints,
wherein each of the circuitry comprises hardware.
10. The apparatus of claim 9 , wherein the continuity constraints comprise one of wavelength and spectrum continuity in the network.
11. The apparatus of claim 9 , wherein the first path and the second path are determined using Shortest Path First (SPF).
12. The apparatus of claim 9 , wherein the plurality of variables comprise a set of Continuity Constraints (CT) for each of paths CT 1 , CT 2 , and wherein the set of CT are modified traversing the auxiliary directed graph during the determining the second path, and subsequent to reaching the destination, if the set of CT are not empty, the set of CT form the disjoint paths.
13. The apparatus of claim 9 , further comprising:
circuitry adapted to reiterate the first path using an updated Non-Viable Segment if no solution is found.
14. A system adapted to compute disjoint paths in a network considering continuity constraints, the system comprising:
a network interface and a processor communicatively coupled to one another; and
memory storing instructions that, when executed, cause the processor to
responsive to a request, via the network interface, for disjoint paths in the network which are subject to the continuity constraints, initialize a plurality of variables associated with a graph defining the network where edges constitute nodes and vertices constitute links,
determine a first path through the graph using a Non-Viable Segment without the continuity constraints to yield the first path, P 1 , and a tree, T,
determine an auxiliary directed graph based on the first path by applying weight modifications to the tree, T, and reversing edges of the first path, P 1 , and
determine a second path through the auxiliary directed graph, wherein the second path is determined by considering entry into cut edges, exit from cut edges, and a destination in the auxiliary directed graph and the plurality of variables are adjusted based on the entry, the exit, and the destination to address the continuity constraints.
15. The system of claim 14 , wherein the continuity constraints comprise one of wavelength and spectrum continuity in the network.
16. The system of claim 14 , wherein the plurality of variables comprise a set of Continuity Constraints (CT) for each of paths CT 1 , CT 2 , and wherein the set of CT are modified traversing the auxiliary directed graph during the determining the second path, and subsequent to reaching the destination, if the set of CT are not empty, the set of CT form the disjoint paths.
17. The system of claim 14 , wherein the memory storing instructions that, when executed, further cause the processor to
if no solution is found, reiterating the first path using an updated Non-Viable Segment.