Adaptively changing weights for fair scheduling in broadcast environments

Abstract

Adaptively changing weights for fair scheduling in broadcast environments is disclosed. In one embodiment, a computer-implemented method for allocating bandwidth among a plurality of flows, such as nodes, sharing an output link, such as a network, is disclosed. The method includes adaptively determining a weight for each flow, based on a predetermined criteria, and allocating a portion of bandwidth to each flow proportionally to the weight for the flow. In one embodiment, the predetermined criteria takes into account an input rate of data packets for each flow, while in another embodiment, the predetermined criteria takes into account an queue size for each flow.

1 . A computer-implemented method for allocating bandwidth in a broadcast environment comprising a plurality of end nodes among a plurality of flows associated with respective end nodes and sharing an output link comprising: 
 adaptively determining at each end node a weight for each flow associated with that end node based on a predetermined criteria; and    allocating at each end node a portion of bandwidth to each flow associated with that end node based on the determined weight for the flow.    
   
   
       2 . The method of  claim 1 , wherein the predetermined criteria comprises an input rate for each flow.  
   
   
       3 . The method of  claim 2 , wherein adaptively determining a weight for each flow comprises: 
 determining the input rate for the flow; and    adaptively determining the weight for the flow as the input rate multiplied by a normalizing constant.    
   
   
       4 . (Cancelled)  
   
   
       5 . (Cancelled)  
   
   
       6 . The method of  claim 1 , wherein the predetermined criteria comprises the queue size for each flow.  
   
   
       7 . The method of  claim 6 , wherein adaptively determining a weight for each flow comprises: 
 determining a number of packets in the flow at a given time;    adapatively determining the weight for the flow as the number of packets in the flow divided by a maximum number of packets allowed in the flow.    
   
   
       8 . A computer-implemented method for allocating bandwidth among a plurality of flows sharing an output link comprising: 
 adaptively determining a weight for each flow based on a predetermined criterion as                w   ⁡     (   τ   )       =       Avg   ⁢           ⁢   queue   ⁢           ⁢     size   ⁡     (   τ   )           Max   ⁢           ⁢   allowed   ⁢           ⁢   queue   ⁢           ⁢   size         ,           where Avg queue size(τ) is the queue size at time τ, and Max allowed queue size specifies a maximum allowed size of a queue; and    allocating a portion of bandwidth to each flow at an end node associated with that flow based on the weight for the flow.    
   
   
       9 . The method of  claim 1 , wherein each flow corresponds to a queue over at least one node.  
   
   
       10 . The method of  claim 1 , wherein the output link comprises a local-area network (LAN).  
   
   
       11 . The method of  claim 1 , wherein the output link comprises a wireless network.  
   
   
       12 . A machine-readable medium having instructions stored thereon for execution by a processor to perform a method for allocating bandwidth in a broadcast environment comprising a plurality of end nodes among a plurality of flows associated with respective end nodes and sharing an output link comprising: 
 adaptively determining at each end node a weight for each flow associated with that end node based on an input rate for each flow; and    allocating at each end node a portion of bandwidth to each flow associated with that end node based on the determined weight for the flow.    
   
   
       13 . The medium of  claim 12 , wherein adaptively determining a weight for each flow comprises: 
 determining the input rate for the flow; and    adaptively determining the weight for the flow as the input rate multiplied by a normalizingconstant.    
   
   
       14 . (Cancelled)  
   
   
       15 . (Cancelled)  
   
   
       16 . A machine-readable medium having instructions stored thereon for execution by a processor of a particular one of a plurality of end nodes of a broadcast environment to perform a method for allocating bandwidth in the broadcast environment among a plurality of flows sharing an output link comprising: 
 adaptively determining a weight at the particular end node for each flow associated with that end node based on the queue size for each flow; and    allocating a portion of bandwidth to each flow associated with that end node based on the determined weight for the flow.    
   
   
       17 . The medium of  claim 16 , wherein adaptively determining a weight for each flow comprises: 
 estimating a number of packets in the flow at a given time;    adaptively determining the weight for the flow as the number of packets in the flow divided by a maximum number of packets allowed in the flow.    
   
   
       18 . A machine-readable medium having instructions stored thereon for execution by a processor to perform a method for allocating bandwidth among a plurality of flows sharing an output link comprising: 
 adaptively determining a weight for each flow based on the queue size for each flow, wherein adaptively determining a weight for each flow comprises determining the weight as                w   ⁡     (   τ   )       =       Avg   ⁢           ⁢   queue   ⁢           ⁢     size   ⁡     (   τ   )           Max   ⁢           ⁢   allowed   ⁢           ⁢   queue   ⁢           ⁢   size         ,           where Avg queue size(τ) is the queue size at time τ, and Max allowed queue size specifies a maximum allowed size of a queue; and    allocating a portion of bandwidth to each flow based on the weight for the flow.    
   
   
       19 . A computerized system comprising: 
 a broadcast environment output link having a bandwidth, the broadcast environmentcomprising a plurality of end nodes; and    a plurality of flows, each flow being associated with one end node, each flow sharing the bandwidth of the output link proportional in a proportion based on a corresponding adaptive weight based on a predetermined criteria applied at the end node associated with the flow.    
   
   
       20 . The system of  claim 19 , wherein the predetermined criteria comprises an input rate for each flow.  
   
   
       21 . The system of  claim 19 , wherein the predetermined criteria comprises the queue size for each flow.  
   
   
       22 . The system of  claim 19 , wherein the output link comprises a wireless network (LAN) communicatively coupling the plurality of flows.  
   
   
       23 . The system of  claim 19 , wherein the output link comprises a wireless network communicatively coupling the plurality of flows.  
   
   
       24 . The system of  claim 19 , further comprising at least one node, such that at least one of the plurality of flows is located at each node.  
   
   
       25 . The method of  claim 8  wherein the adaptively determining the weight for each flow based on the predetermined criterion comprises adaptively determining the weight for each flow based on the queue size and an input rate.  
   
   
       26 . The method of  claim 8  wherein the output link comprises a local area network.  
   
   
       27 . The method of  claim 8  wherein the output link comprises a wireless network.  
   
   
       28 . The medium of  claim 18  wherein the adaptively determining the weight for each flow based on the predetermined criterion comprises adaptively determining the weight for each flow based on the queue size and an input rate.  
   
   
       29 . The medium of  claim 18  wherein the output link comprises a local area network.  
   
   
       30 . The medium of  claim 18  wherein the output link comprises a wireless network.