Manipulating bottlenecks in systems modeled as networks
A technique is described for quantifying the effect of a perturbation on a property of a network link or flow, and to add a new flow, reroute an existing flow, or to reshape a flow, based on a quantitative estimation of the perturbation.
1. A method for jointly performing routing and congestion control in a system modeled as a network, the method comprising performing by a processor the steps of:
receiving, for a system modeled as a network, a network topology, the network topology comprising a plurality of nodes, a plurality of links between respective pairs of nodes, and a plurality of flows via the plurality of links;
receiving a request for routing a flow between a source node and a destination node;
selecting a path for the flow based on a maximum achievable flow rate therefor, wherein the maximum achievable flow rate is derived by generating a bottleneck structure of the network modified to have the network topology and the flow.
2. The method of claim 1 , wherein the flow comprises a new flow.
3. The method of claim 1 , wherein the flow comprises an existing flow, the method further comprising:
before the selecting step, removing the existing flow from the plurality of flows in the network topology.
4. The method of claim 1 , wherein:
each link in the plurality of links represents a respective availability of a system resource; and
a respective flow rate associated with each flow in the plurality of flows represents a respective utilization of one or more system resources.
5. The method of claim 1 , wherein the selected path is different from a shortest hop path between the source node and the destination node.
6. The method of claim 1 , wherein the bottleneck structure comprises a plurality of link elements and a plurality of flow elements, wherein:
a dependence from a first link element to a first flow element indicates that a first flow corresponding to the first flow element is bottlenecked at a first link corresponding to the first link element; and
a dependance from a second flow element to a second link element indicates that a second flow corresponding to the second flow element traverses a second link corresponding to the second link element.
7. The method of claim 1 , further comprising:
selecting, from the plurality of flows, a flow to be accelerated;
determining, by traversing the bottleneck structure, a target flow associated with a positive flow gradient;
computing a leap and a fold for the target flow, the leap representing a maximum perturbation of flow rate of the target flow while maintaining the relative order of the plurality of links according to their respective fair shares;
reducing flow rate of the target flow using a traffic shaper by a factor up to the leap; and
increasing flow rate of the flow to be accelerated up to a product of the leap and a gradient of the flow to be accelerated.
8. The method of claim 7 , wherein the factor is selected to preserve completion time of slowest of the plurality of flows.
9. The method of claim 7 , further comprising repeating the determining, computing, reducing, and increasing steps with respect to a different target flow.
10. The method of claim 1 , wherein the system modeled as a network comprises system modeled as: a data network, a transportation network, an energy distribution network, a fluidic network, or a biological network.
11. An apparatus for jointly performing routing and congestion control in a system modeled as a network, the apparatus comprising:
a first processor; and
a first memory in electrical communication with the first processor, and comprising instructions that, when executed by a processing unit that comprises one or more computing units, wherein one of the one or more computing units comprises the first processor or a second processor, and wherein the processing unit is in electronic communication with a memory module that comprises the first memory or a second memory, program the processing unit to:
receive, for a system modeled as a network, a network topology, the network topology comprising a plurality of nodes, a plurality of links between respective pairs of nodes, and a plurality of flows via the plurality of links;
receive a request for routing a flow between a source node and a destination node;
select a path for the flow based on a maximum achievable flow rate therefor, wherein the maximum achievable flow rate is derived by generating a bottleneck structure of the network modified to have the network topology and the flow.
12. The apparatus of claim 11 , wherein the flow comprises a new flow.
13. The apparatus of claim 11 , wherein:
the flow comprises an existing flow; and
the instructions further program the processing unit to:
before performing the select operation, remove the existing flow from the plurality of flows in the network topology.
14. The apparatus of claim 11 , wherein:
each link in the plurality of links represents a respective availability of a system resource; and
a respective flow rate associated with each flow in the plurality of flows represents a respective utilization of one or more system resources.
15. The apparatus of claim 11 , wherein the selected path is different from a shortest hop path between the source node and the destination node.
16. The apparatus of claim 11 , wherein the bottleneck structure comprises a plurality of link elements and a plurality of flow elements, wherein:
a dependence from a first link element to a first flow element indicates that a first flow corresponding to the first flow element is bottlenecked at a first link corresponding to the first link element; and
a dependance from a second flow element to a second link element indicates that a second flow corresponding to the second flow element traverses a second link corresponding to the second link element.
17. The apparatus of claim 11 , wherein the instructions further program the processing unit to:
select, from the plurality of flows, a flow to be accelerated;
determine, by traversing the bottleneck structure, a target flow associated with a positive flow gradient;
compute a leap and a fold for the target flow, the leap representing a maximum perturbation of flow rate of the target flow while maintaining the relative order of the plurality of links according to their respective fair shares;
reduce flow rate of the target flow using a traffic shaper by a factor up to the leap; and
increase flow rate of the flow to be accelerated up to a product of the leap and a gradient of the flow to be accelerated.
18. The apparatus of claim 17 , wherein the factor is selected to preserve completion time of slowest of the plurality of flows.
19. The apparatus of claim 17 , wherein the instructions further program the processing unit to repeat the determine, compute, reduce, and increase operations with respect to a different target flow.
20. The apparatus of claim 11 , wherein the system modeled as a network comprises system modeled as: a data network, a transportation network, an energy distribution network, a fluidic network, or a biological network.