Systems and methods for quality of service (QoS) based management of bottlenecks and flows in networks

1. A method for improving network utilization by configuring processing of flows therein, the method comprising:

in a network comprising a plurality of links and having a plurality of flows that are processed according to P policies, P being greater than 1,

evaluating a plurality of candidate partitionings of the plurality of flows into P groups, using a QoS function that, using network topology, determines network performance for each candidate partitioning, wherein:

according to a candidate partitioning, a first flow belongs to a first group of the P groups and one or more flows belong to a second group of the P groups; and

to determine the network performance, the QoS function accounts for effect of rate drift in a rate of the first flow on respective rates of all other flows in the plurality of flows; and

designating a candidate partitioning that maximizes the network performance as best partitioning, wherein the plurality of flows are allocated to P groups according to the best partitioning and one or more flows in each group are processed according to a respective one of the P policies.

2. The method of claim 1 , wherein the QoS function comprises a generalized P-partitioned set function receiving (P−1) sets as inputs.

3. The method of claim 1 , wherein the QoS function comprises a max-min-max-flow (m3f) function.

4. The method of claim 3 , wherein the max-min-max-flow (m3f) function comprises: (i) a weighted max-min-max-flow function, (ii) a max-min-weighted-max-flow function, or (iii) a weighted max-min-weighted-max-flow function.

5. The method of claim 1 , wherein the QoS function guarantees for at least one flow from the plurality of flows a specified minimum flow rate.

6. The method of claim 1 , wherein the QoS function is inclusive.

7. The method of claim 6 , wherein:

the plurality of candidate partitionings comprises one or more sets of partitionings, one or more partitionings in each set corresponding to a respective value of a parameter (λ); and

evaluating the plurality of candidate partitionings comprises:

selecting a plurality of parameter values in order and, for each parameter value:

evaluating from a corresponding set one or more candidate partitionings using the QoS function; and

designating a candidate partitioning that maximizes the network performance as optimal partitioning for that parameter value,

yielding a plurality of optimal partitionings corresponding to the plurality of parameter values; and

designating as the best partitioning from the plurality of optimal partitionings, a partitioning for which the network performance according to the QoS function is maximum.

8. The method of claim 7 , wherein evaluating the one or more candidate partitionings for a current parameter value comprises identifying a nested neighborhood of the optimal partitioning for a preceding parameter value.

9. The method of claim 8 , wherein:

in the optimal partitioning for the preceding parameter value, each flow belonging to a first group in the P groups is larger in size than any flow in a second group in the P groups;

each partitioning is encoded using P symbols; and

identifying the nested neighborhood comprises selecting a candidate partitioning such that:

Manhattan distance between an encoding of the candidate partitioning and an encoding of the optimal partitioning for the preceding parameter value is less than or equal to a specified threshold; and

each flow designated to the first group in the optimal partitioning for the preceding parameter value is designated to a corresponding first group in the candidate partitioning.

10. The method of claim 1 , wherein evaluating a particular candidate partitioning comprises:

constructing a flow gradient graph for the network;

decrementing a respective flow rate of each flow in at least one partition according to the candidate partitioning, by a unit rate (δ);

propagating reduction in the flow rates through the flow gradient graph to obtain a flow rate drift at each flow in the network; and

aggregating the flow rate drifts using a function based on the QoS function to obtain the network performance.

11. The method of claim 10 , wherein constructing the flow gradient graph comprises:

creating a link vertex for each bottleneck link in the network and a flow vertex for each flow in the network;

for each link in the network:

identifying one or more flows bottlenecked by that link, and adding a respective directed edge from a link vertex corresponding to that link to the respective flow vertices corresponding to each of the one or more bottlenecked flows; and

identifying non-bottlenecked flows passing through the link, and adding a respective directed edge from a flow vertex corresponding to each non-bottlenecked flow to the link vertex corresponding to the link.

12. The method of claim 11 , wherein the one or more bottlenecked flows and the one or more non-bottlenecked flows are identified by constructing a bottleneck precedence graph.

13. The method of claim 1 , wherein the network is selected from the group consisting of a data network, an energy-distribution network, a cellular network, and a goods-distribution network.

14. The method of claim 1 , wherein:

P is equal to two; and

according to the best partitioning, one or more flows from the plurality of flows belong to a first group and are designated elephant flows, and remaining flow or flows belong to a second group and are designated mouse flows.

15. The method of claim 1 , wherein each of the P policies defines a respective processing priority for flows belonging to the corresponding one of the P groups.

16. A system for improving network utilization by configuring processing of flows therein, the system comprising:

a first processor;

a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to:

in a network comprising a plurality of links and having a plurality of flows that are processed according to P policies, P being greater than 1,

evaluate a plurality of candidate partitionings of the plurality of flows into P groups, using a QoS function that, using network topology, determines network performance for each candidate partitioning, wherein:

according to a candidate partitioning, a first flow belongs to a first group of the P groups and one or more flows belong to a second group of the P groups; and

to determine the network performance, the QoS function accounts for effect of rate drift in a rate of the first flow on respective rates of all other flows in the plurality of flows; and

designate a candidate partitioning that maximizes the network performance as best partitioning, wherein the plurality of flows are allocated to P groups according to the best partitioning and one or more flows in each group are processed according to a respective one of the P policies.

17. The system of claim 16 , wherein the QoS function comprises a generalized P-partitioned set function receiving (P−1) sets as inputs.

18. The system of claim 16 , wherein the QoS function comprises a max-min-max-flow (m3f) function.

19. The system of claim 18 , wherein the max-min-max-flow (m3f) function comprises: (i) a weighted max-min-max-flow function, (ii) a max-min-weighted-max-flow function, or (iii) a weighted max-min-weighted-max-flow function.

20. The system of claim 16 , wherein the QoS function guarantees for at least one flow from the plurality of flows a specified minimum flow rate.

21. The system of claim 16 , wherein the QoS function is inclusive.

22. The system of claim 21 , wherein:

the plurality of candidate partitionings comprises one or more sets of partitionings, one or more partitionings in each set corresponding to a respective value of a parameter (λ); and

to evaluate the plurality of candidate partitionings, the instructions program the processing unit to:

select a plurality of parameter values in order and, for each parameter value:

evaluate from a corresponding set one or more candidate partitionings using the QoS function; and

designate a candidate partitioning that maximizes the network performance as optimal partitioning for that parameter value,

yielding a plurality of optimal partitionings corresponding to the plurality of parameter values; and

designate as the best partitioning from the plurality of optimal partitionings, a partitioning for which the network performance according to the QoS function is maximum.

23. The system of claim 22 , wherein to evaluate the one or more candidate partitionings for a current parameter value, the instructions program the processing unit to:

identify a nested neighborhood of the optimal partitioning for a preceding parameter value.

24. The system of claim 23 , wherein:

in the optimal partitioning for the preceding parameter value, each flow belonging to a first group in the P groups is larger in size than any flow in a second group in the P groups;

each partitioning is encoded using P symbols; and

to identify the nested neighborhood the instructions program the processing unit to select a candidate partitioning such that:

Manhattan distance between an encoding of the candidate partitioning and an encoding of the optimal partitioning for the preceding parameter value is less than or equal to a specified threshold; and

each flow designated to the first group in the optimal partitioning for the preceding parameter value is designated to a corresponding first group in the candidate partitioning.

25. The system of claim 16 , wherein to evaluate a particular candidate partitioning, the instructions program the processing unit to:

construct a flow gradient graph for the network;

decrement a respective flow rate of each flow in at least one partition according to the candidate partitioning, by a unit rate (δ);

propagate reduction in the flow rates through the flow gradient graph to obtain a flow rate drift at each flow in the network; and

aggregate the flow rate drifts using a function based on the QoS function to obtain the network performance.

26. The system of claim 25 , wherein to construct the flow gradient graph the instructions program the processing unit to:

create a link vertex for each bottleneck link in the network and a flow vertex for each flow in the network;

for each link in the network:

identify one or more flows bottlenecked by that link, and add a respective directed edge from a link vertex corresponding to that link to the respective flow vertices corresponding to each of the one or more bottlenecked flows; and

identify non-bottlenecked flows passing through the link, and add a respective directed edge from a flow vertex corresponding to each non-bottlenecked flow to the link vertex corresponding to the link.

27. The system of claim 26 , wherein to identify the one or more bottlenecked flows and the one or more non-bottlenecked flows, the instructions program the processing unit to:

construct a bottleneck precedence graph.

28. The system of claim 16 , wherein the network is selected from the group consisting of a data network, an energy-distribution network, a cellular network, and a goods-distribution network.

29. The system of claim 16 , wherein:

P is equal to two; and

according to the best partitioning, one or more flows from the plurality of flows belong to a first group and are designated elephant flows, and remaining flow or flows belong to a second group and are designated mouse flows.

30. The system of claim 16 , wherein each of the P policies defines a respective processing priority for flows belonging to the corresponding one of the P groups.