Path computation with direct enforcement of non-local constraints

1. A non-transitory computer-readable medium comprising instructions that, when executed, cause at least one processor to perform steps of:

creating a graph of a network having i) vertices representing ports, and ii) edges representing possible connections between vertices;

receiving a request for one or more paths in the network;

traversing the graph to determine the one or more paths;

responsive to encountering a non-local constraint in the graph, adding a traversal state based thereon, wherein the traversal state is a label added to the graph to account for the non-local constraint during the traversing; and

responsive to satisfying the non-local constraint in the graph, removing the traversal state based thereon.

2. The non-transitory computer-readable medium of claim 1 , wherein the steps further include

responsive to encountering an edge where the non-local constraint applies, checking the traversal state for the edge and excluding the edge in the traversing if the edge does not satisfy the non-local constraint based on the traversal state.

3. The non-transitory computer-readable medium of claim 1 , wherein the ports include line ports and client ports associated with a network element.

4. The non-transitory computer-readable medium of claim 1 , wherein the graph also includes vertices with associated edges representing connectivity between the line ports and the client ports of a given network element, and vertices with associated edges representing connectivity between the client ports of two different network elements.

5. The non-transitory computer-readable medium of claim 4 , wherein the vertices representing connectivity between the line ports and the client ports of a given network element are internal connections in the given network element, and

wherein the vertices representing connectivity between the client ports of two different network elements are cabled connections.

6. The non-transitory computer-readable medium of claim 1 , wherein the non-local constraint includes a requirement that an exit client port matches an entry client port due to a configuration of a module in the network.

7. The non-transitory computer-readable medium of claim 1 , wherein the traversal state includes nested non-local constraints.

8. The non-transitory computer-readable medium of claim 1 , wherein the traversal state includes multilayer non-local constraints.

9. The non-transitory computer-readable medium of claim 1 , wherein the traversing the graph utilizes Dijkstra's algorithm.

10. A method comprising steps of:

creating a graph of a network having i) vertices representing ports, and ii) edges representing possible connections between vertices;

receiving a request for one or more paths in the network;

traversing the graph to determine the one or more paths;

responsive to encountering a non-local constraint in the graph, adding a traversal state based thereon, wherein the traversal state is a label added to the graph to account for the non-local constraint during the traversing; and

responsive to satisfying the non-local constraint in the graph, removing the traversal state based thereon.

11. The method of claim 10 , wherein the steps further include

responsive to encountering an edge where the non-local constraint applies, checking the traversal state for the edge and excluding the edge in the traversing if the edge does not satisfy the non-local constraint based on the traversal state.

12. The method of claim 10 , wherein the ports include line ports and client ports associated with a network element.

13. The method of claim 10 , wherein the vertices also include vertices representing connectivity between the line ports and the client ports of a given network element, and vertices representing connectivity between the client ports of two different network elements.

14. The method of claim 13 , wherein the graph includes vertices with associated edges representing connectivity between the line ports and the client ports of a given network element are internal connections in the given network element, and

wherein the graph also includes vertices with associated edges representing connectivity between the client ports of two different network elements are cabled connections.

15. The method of claim 10 , wherein the non-local constraint includes a requirement that an exit client port matches an entry client port due to a configuration of a module in the network.

16. The method of claim 10 , wherein the traversal state includes nested non-local constraints.

17. The method of claim 10 , wherein the traversal state includes multilayer non-local constraints.

18. The method of claim 10 , wherein the traversing the graph utilizes Dijkstra's algorithm.

19. A processing device comprising:

at least one processor; and

memory comprising instructions that, when executed, cause the at least one processor to

create a graph of a network having i) vertices representing ports, and ii) edges representing possible connections between vertices;

receive a request for one or more paths in the network;

traverse the graph to determine the one or more paths;

responsive to encountering a non-local constraint in the graph, add a traversal state based thereon, wherein the traversal state is a label added to the graph to account for the non-local constraint during the traversing; and

responsive to satisfying the non-local constraint in the graph, remove the traversal state based thereon.

20. The processing device of claim 19 , wherein the steps further include

responsive to encountering an edge where the non-local constraint applies, check the traversal state for the edge and exclude the edge while the graph is traversed if the edge does not satisfy the non-local constraint.