Satisfying demands in data communications networks

1. A non-transitory, computer-readable medium containing first instructions that, when executed by at least one processor of a system, cause the system to perform operations comprising:

selecting a cycle of a communication network, the communication network including network nodes configured to communicate using communication links, the cycle including a subset of the network nodes and communication links in the communication network, and identifying demands for the communication network that originate and terminate on network nodes in the subset;

generating a representation of the communication network and the demands, the representation including:

vertices corresponding to network nodes of the communication network on the cycle,

external edges corresponding to communication links of the communication network on the cycle, the external edges connecting the vertices,

internal edges, each internal edge connecting two of the vertices, and

a set of flows corresponding to the identified demands, each flow having a source vertex and a target vertex;

identifying a subset of the internal edges based on the set of flows;

determining, using a stream graph generated based on a one of the set of flows and the identified subset of the internal edges, a set of graph paths that satisfy the one of the flows, comprising:

obtaining an indication of a set of functional external edges and a set of functional internal edges; and

determining a graph path from a source vertex of the one of the flows to a target vertex of the one of the flows, the determination restricted to:

the set of functional external edges; and

an intersection of the set of functional internal edges and the identified subset of the first internal edges; and

providing second instructions for configuring the communication network to satisfy a one of the demands that corresponds to the one of the set of flows, the second instructions indicating a set of network paths that corresponds to the set of graph paths.

2. The non-transitory, computer-readable medium of claim 1 , wherein:

identifying the subset of the internal edges based on the set of flows comprises:

selecting a flow from the set of flows;

determining at least one graph path from a source vertex to a target vertex of the flow; and

updating the subset of the internal edges based on the determined at least one graph path.

3. The non-transitory, computer-readable medium of claim 1 , wherein:

identifying the subset of the internal edges based on the set of flows comprises:

identifying disjoint cliques of the internal edges;

building a graph using the identified disjoint cliques and the set of flows;

identifying sub-cliques in a tree of the graph; and

converting the identified sub-cliques into the identified subset of the internal edges.

4. The non-transitory, computer-readable medium of claim 3 , wherein:

converting the identified sub-cliques into the identified subset of the internal edges comprises:

converting the identified sub-cliques into star sets of internal edges; and

generating the identified subset of the internal edges, the identified subset of the internal edges being the union of the star sets.

5. The non-transitory, computer-readable medium of claim 3 , wherein:

building the graph using the identified disjoint cliques and the set of flows comprises:

creating terminal vertex sets based on the set of flows;

creating extended vertex sets; and

connecting vertex sets satisfying connection criteria to form the graph.

6. The non-transitory, computer-readable medium of claim 1 , wherein:

determining the set of graph paths that satisfy the one of the set of flows comprises:

generating the stream graph, the stream graph including:

graph elements corresponding to the vertices, the graph elements including a starting graph element corresponding to the source vertex and a finishing graph element corresponding to the target vertex,

graph arcs corresponding to the external edges, each graph arc directed away from the finishing graph element and towards the starting graph element, and

graph edges corresponding to the internal edges; and

identifying a first directed path from the starting graph element to the finishing graph element.

7. The non-transitory, computer-readable medium of claim 6 , wherein:

determining the set of graph paths that satisfy the one of the flows further comprises:

generating an updated first directed path by replacing a set of intersecting graph edges in the first directed path with an express graph edge corresponding to an internal edge; and

determining three graph paths from the source vertex to the target vertex, the determination restricted to:

the external edges; and

internal edges corresponding to the graph edges in the updated first directed path.

8. The non-transitory, computer-readable medium of claim 7 , wherein:

the three graph paths are pairwise edge-disjoint.

9. The non-transitory, computer-readable medium of claim 7 , wherein:

identifying the subset of the internal edges based on the set of flows comprises:

identifying connected components in the representation;

associating sub-flows with each of the connected components based on a one of the set of flows; and

generating a clique graph using the sub-demands.

10. A non-transitory, computer-readable medium containing first instructions that, when executed by at least one processor of a system, cause the system to perform operations comprising:

obtaining a first representation of a cycle of a communication network, the communication network including network nodes configured to communicate using communication links, the cycle including a subset of the network nodes and communication links in the communication network, and a first demand on the communication network that originates and terminates on network nodes in the subset, the first representation including:

vertices corresponding to network nodes of the communication network on the cycle,

external edges corresponding to communication links of the communication network on the cycle, the external edges connecting the vertices,

first internal edges, each first internal edge connecting two of the vertices, and

a first flow corresponding to the first demand on the communication network;

identifying a subset of the first internal edges using a graph corresponding to the first flow, the graph including graph arcs corresponding to the external edges and graph edges corresponding to the first internal edges;

determining a set of graph paths that satisfy the first flow using the identified subset of the first internal edges, comprising:

obtaining an indication of a set of functional external edges and a set of functional internal edges; and

determining a graph path from a source vertex of the first flow to a target vertex of the first flow, the determination restricted to:

the set of functional external edges; and

an intersection of the set of functional internal edges and the identified subset of the first internal edges; and

providing second instructions for configuring the communication network to satisfy the first demand, the second instructions indicating a set of network paths that corresponds to the set of graph paths.

11. The non-transitory, computer-readable medium of claim 10 , wherein:

determining the set of graph paths that satisfy the first flow using the identified subset of the first internal edges comprises:

generating a Steiner graph including Steiner graph elements corresponding to the vertices and Steiner graph elements corresponding to the internal edges; and

identifying a first Steiner graph path from the Steiner graph element corresponding to the source vertex of the flow to the Steiner graph element corresponding to the target vertex of the flow.

12. The non-transitory, computer-readable medium of claim 10 , wherein:

the first flow further specifies a protection type; and

the set of graph paths is determined based on the protection type and using the identified subset of the first internal edges.

13. The non-transitory, computer-readable medium of claim 10 , wherein:

identifying the subset of the first internal edges using the graph comprises:

generating the graph, the graph including:

graph elements corresponding to the vertices, the graph elements including a starting graph element corresponding to a source vertex of the first flow and a finishing graph element corresponding to a target vertex of the first flow, and

wherein each graph arc is directed away from the finishing graph element and towards the starting graph element; and

determining a first directed path from the starting graph element to the finishing graph element, the identified subset of the first internal edges being the first internal edges corresponding to the graph edges included in the first directed path.

14. The non-transitory, computer-readable medium of claim 10 , wherein:

determining the set of graph paths comprises:

replacing ones of the identified subset of the first internal edges with an express internal edge; and

determining three pairwise internal edge-disjoint paths from a source vertex of the first flow to a target vertex of the first flow, the determination restricted to:

the external edges; and

the identified subset of the first internal edges.

15. The non-transitory, computer-readable medium of claim 10 , wherein:

obtaining the first representation of the communication network comprises:

selecting the cycle of the communication network and identifying demands that originate and terminate on the cycle, the identified demands including the first demand;

generating a second representation based on the cycle, the second representation including the vertices, the external edges, and second internal edges;

selecting the first internal edges from among the second internal edges, selecting comprising:

constructing a clique graph using the demands;

determining a tree of the clique graph; and

selecting the first internal edges based on the tree.

16. A non-transitory, computer-readable medium containing first instructions that, when executed by at least one processor of a system, cause the system to perform operations comprising:

obtaining a first representation of a cycle of a communication network, the communication network including network nodes configured to communicate using communication links, the cycle including a subset of the network nodes and communication links in the communication network, and demands on the communication network that originate and terminate on network nodes in the subset, the first representation including:

vertices corresponding to network nodes of the network on the cycle,

external edges corresponding to communication links of the communication network on the cycle, the external edges connecting the vertices,

first internal edges, each first internal edge connecting two of the vertices, and

flows corresponding to the demands;

identifying a subset of the first internal edges based on the flows, identification comprising:

building a clique graph using the flows;

identifying sub-cliques on a tree of the clique graph; and

converting the identified sub-cliques into the identified subset of the first internal edges;

determining a set of graph paths that satisfy a one of the flows using the identified subset of the first internal edges, comprising:

obtaining an indication of a set of functional external edges and a set of functional internal edges; and

determining a graph path from a source vertex of the one of the flows to a target vertex of the one of the flows, the determination restricted to:

the set of functional external edges; and

an intersection of the set of functional internal edges and the identified subset of the first internal edges; and

providing second instructions for configuring the communication network to satisfy a one of the demands that corresponds to the one of the flows, the second instructions indicating a set of network paths that corresponds to the set of graph paths.

17. The non-transitory, computer-readable medium of claim 16 , wherein:

converting the identified sub-cliques into the identified subset of the first internal edges comprises:

converting the identified sub-cliques into star sets of the first internal edges; and

generating the identified subset of the first internal edges, the identified subset of the first internal edges being the union of the star sets.

18. The non-transitory, computer-readable medium of claim 16 , wherein:

building the clique graph using the flows comprises:

creating terminal vertex sets based on the flows;

creating extended vertex sets, each extended vertex set connected to a corresponding terminal vertex set; and

connecting intersecting extended vertex sets.