Iterative max-min fairness algorithms

Abstract

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 - 10 . (canceled) 
     
     
         11 . A method for allocating resources of a network among a plurality of traffic demands being routed from a respective source to a respective destination along one or more respective paths connecting the respective source to the respective destination, the method comprising:
 determining initial splits for each traffic demand over said one or more respective paths, wherein each split corresponds to one of the one or more respective paths;   generating updated flow values for each traffic demand based on the determined splits; and   computing updated splits based on the generated updated flow values.   
     
     
         12 . The method of  claim 11  further comprising:
 increasing flow values of respective ones of the traffic demands at a single rate to generate the updated flows, wherein the increased flow values are split over the one or more respective paths according to the determined splits. 
 
     
     
         13 . The method of  claim 12  further comprising:
 determining whether a link of the one or more respective paths is saturated; and 
 in response to determining that the link is saturated, discarding at least one from the one or more respective paths, wherein the at least one discarded path includes the saturated link. 
 
     
     
         14 . The method of  claim 13 , wherein computing the updated splits comprises re-scaling splits of non-saturated ones of the one or more respective paths. 
     
     
         15 . The method of  claim 14  further comprising:
 determining whether each one of the one or more respective paths is saturated; 
 in response to determining that each one of the one or more respective paths is saturated, outputting the generated flow values. 
 
     
     
         16 . The method of  claim 11  further comprising:
 outputting the generated flow values in response to determining at least one of a convergence of the updated splits and performance of a maximum number of updating iterations. 
 
     
     
         17 . The method of  claim 11 , wherein determining the initial splits comprises:
 assigning equal splits to the one or more respective paths, wherein each split is equal to a reciprocal of a number of the one or more respective paths.   
     
     
         18 . The method of  claim 11 , wherein determining the initial splits comprises:
 assigning a random split to each one of the one or more respective paths.   
     
     
         19 . The method of  claim 11 , wherein determining the initial splits comprises:
 assigning splits to the one or more respective paths, wherein each split is proportional to 1/10 l , wherein l is a number of nodes in the associated path.   
     
     
         20 . The method of  claim 11 , wherein the one or more respective paths comprise at least two paths, and wherein determining the initial splits comprises:
 sorting the respective paths based on length;   arbitrarily ranking any two from the respective paths, wherein the two paths have the same length; and   assigning splits to the respective paths, wherein each split is proportional to 1/10 x , wherein x is a rank of the associated path among the respective paths.