Method of optimizing a routing in a communications network
A computer-implemented method optimizes a routing of data traffic in a communications network by using a quantum concept processor. A set of potential short communication paths among possible communication paths between respective origin nodes and respective destination nodes of captured traffic demands is specified. The edges within the set of potential short communication paths are assigned a respective usage capacity limit. Fractional capacity usages of the edges are calculated based on respective usage capacity limits of the edges. The calculated fractional capacity usages are formulated as terms of a quadratic stress function. An optimized routing is determined by using a quantum concept processor, thereby selecting for each traffic demand one short communication path from the set of potential short communication paths such that the quadratic stress function is minimized.
1. A computer-implemented method of optimizing a routing of data traffic in a communications network with a plurality of communication nodes connectable over edges of communication paths for a routing of the data traffic, wherein the method comprises:
capturing a set of traffic demands, each traffic demand specifying a transfer of a determined data volume from an origin node to a destination node among the plurality of communication nodes,
specifying a set of potential short communication paths among possible communication paths between the respective origin nodes and the respective destination nodes specified in the set of traffic demands, wherein edges within the set of potential short communication paths are assigned a respective usage capacity limit,
specifying a set of potential segment nodes among the plurality of communication nodes, wherein each of the potential segment nodes defines as intermediate node a potential short communication path as member of the set of potential short communication paths between an origin node and a destination node;
calculating for the set of traffic demands, fractional capacity usages of the edges within the set of potential short communication paths, the fractional capacity usages being calculated based on the respective usage capacity limit,
formulating the calculated fractional capacity usages as terms of a quadratic stress function,
formulating in the quadratic stress function, segment node terms that connect the calculated fractional capacity usages of the edges of a respective potential short communication path with those segment nodes within the set of potential segment nodes that lead to the respective potential short communication path, and
determining by using a quantum concept processor, an optimized routing by selecting for each traffic demand of the set of traffic demands one short communication path from the set of potential short communication paths, such that the quadratic stress function is minimized, and
calculating the segment node terms, by using the quantum concept processor, to choose segment nodes within the set of potential segment nodes such that the quadratic stress function is minimized for the determination of the optimized routing.
2. The method according to claim 1 , wherein the segment node terms are calculated under consideration of a path condition that each traffic demand of the set of traffic demands is routed along a shortest path or via exactly one segment node between the respective origin node and the respective destination node.
3. The method according to claim 2 , wherein the quadratic stress function and at least one of the path condition and the cost condition each are weighted and combined into a global QUBO function.
4. The method according to claim 1 , wherein the segment node terms are calculated under consideration of a path condition that each traffic demand of the set of traffic demands is routed along a shortest path or via multiple segment nodes between the respective origin node and the respective destination node.
5. The method according to claim 4 , wherein the quadratic stress function and at least one of the path condition and the cost condition each are weighted and combined into a global QUBO function.
6. The method according to claim 1 , wherein the segment node terms are calculated under consideration of a cost condition such that a number of chosen segment nodes is minimized.
7. The method according to claim 6 , wherein the quadratic stress function and at least one of the path condition and the cost condition each are weighted and combined into a global QUBO function.
8. The method according to claim 1 , further comprising:
selecting a subset of potential segment nodes from the set of potential segment nodes, and
performing the method for the subset of potential segment nodes.
9. The method according to claim 1 , wherein the quadratic stress function is formulated as a quadratic unconstrained binary optimization function.
10. The method according to claim 9 , wherein the quadratic stress function and at least one of the path condition and the cost condition each are weighted and combined into a global QUBO function.
11. The method according to claim 1 , further comprising:
selecting a subset of traffic demands from the set of traffic demands,
performing the method for the subset of traffic demands,
storing the determined optimized routing for the subset of traffic demands, and
updating a respectively remaining usage capacity limit of the edges within the set of potential short communication paths under consideration of the determined optimized routing for the subset of traffic demands.
12. The method according to claim 11 , wherein the method is iteratively performed for the remaining traffic demands until all traffic demands of the set of traffic demands are processed.
13. A quantum concept processor configured to perform the method according to claim 1 .
14. The quantum concept processor according to claim 13 , wherein the quantum concept processor is a digital annealing processing unit.
15. The quantum concept processor according to claim 13 , wherein the quantum concept processor is a quantum annealing processing unit.
16. A computer program, the computer program comprising instructions that, when the program is executed by one or more processors, cause each of the one or more processors to perform the method according to claim 1 .
17. A non-transitory computer-readable storage medium on which the computer program of claim 16 is stored.
18. An interface arrangement comprising one or more interfaces to a plurality of communication nodes of a communications network in which data traffic is routed, wherein the interface arrangement is configured to automatically deploy an optimized routing determined by the method according to claim 1 to the communication nodes of the communications network.