Iterative max-min fairness algorithms

摘要

Systems and methods are provided for allocating resources of a network among a plurality of traffic demands to optimize fairness and network utilization. Methods based on flow-increase dynamics converge toward an upward max-min fair (UMMF) allocation, in which the value of each traffic demand cannot be increased, along any of its paths, even if larger traffic demands are removed from the network. An efficient iterative algorithm that converges to a UMMF solution is also provided. The described methods and systems can be implemented efficiently, distributively, and asynchronously.

主权项

1. A method for allocating resources of a network among a plurality of traffic demands, the method comprising:
selecting a first traffic demand from the plurality of traffic demands, wherein the first traffic demand has a first total flow value along one or more first paths in the network; identifying, from the plurality of traffic demands, a second traffic demand having a second total flow value along one or more second paths in the network, wherein the second total flow value is higher than the first total flow value; iteratively increasing, using routing circuitry associated with the first traffic demand, the first total flow value of the first traffic demand by an amount Δ along at least one of said one or more first paths until a convergence condition is met, the convergence condition being that the first and second total flow values converge to an upward max-min fair (UMMF) allocation where a total flow value of each traffic demand cannot increase, along any of its paths, even if traffic demands with a flow value strictly larger than the total flow value are removed and the amount Δ is constant across iterations and a fraction of a possible maximum increase; and decreasing, using routing circuitry associated with the second traffic demand, the second total flow value of the second traffic demand along at least one of said one or more second paths, wherein the increased first total flow value of the first traffic demand is upper bounded by the decreased second total flow value of the second traffic demand.