Adaptively changing weights for fair scheduling in broadcast environments

• US 6,795,865 B1
• Filed: 10/08/1999
• Issued: 09/21/2004
• Est. Priority Date: 10/08/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vaidya, Nitin, Bahl, Paramvir
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): WON, MICHAEL YOUNG
• Application Number:
  US09/415,895
• Time in Patent Office: 1,810 Days
• Field of Search: 709/239, 709/240, 709/241, 709/201, 709/243, 709/235, 370/229, 370/431, 370/464
• US Class Current: 709/235
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first

Abstract

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

Claims

1. 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 comprising an input rate for each flow, where the input rate at a given time is derived as $r<br><br>\left(\mathrm{\tau <br><br>}\right)=\frac{\mathrm{tr}<br><br>\left(t\right)+\mathrm{\xi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L}{\mathrm{\tau <br><br>}},$

 

where ξ

is a rate-sensitivity constant, and r(t) is the input rate a previous time t, and L is packet size; and

allocating a portion of bandwidth to each flow based on the weight for the flow.

2. The method of claim 1 wherein the adaptively determining the weight for each flow comprises adaptively determining the weight as the input rate multiplied by a normalizing constant.

3. The method of claim 1 wherein the output link comprises a local area network.

4. The method of claim 1 wherein the output link comprises a wireless network.

5. 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, wherein adaptively determining a weight for each flow comprises determining the weight as $w<br><br>\left(\mathrm{\tau <br><br>}\right)=\frac{r<br><br>\left(\mathrm{\tau <br><br>}\right)}{\mathrm{Normalizing}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{factor}},$

 

where $r<br><br>\left(\mathrm{\tau <br><br>}\right)=\frac{\mathrm{tr}<br><br>\left(t\right)+\mathrm{\xi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L}{\mathrm{\tau <br><br>}},$

 

ξ

is a rate-sensitivity constant, and r(t) is the input rate a previous time t, L is packet size, and Normalizing Factor is a constant; and

allocating a portion of bandwidth to each flow based on the weight for the flow.

6. The method of claim 5 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 input rate and a queue size.

7. The method of claim 5 wherein the output link comprises a local area network.

8. The method of claim 5 wherein the output link comprises a wireless network.

9. 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 determining an input rate for each flow, wherein determining the input rate for the flow comprises determining the input rate at a given time as $r<br><br>\left(\mathrm{\tau <br><br>}\right)=\frac{\mathrm{tr}<br><br>\left(t\right)+\mathrm{\xi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L}{\mathrm{\tau <br><br>}},$

 

where ξ

is a rate-sensitivity constant, and r(t) is the input rate a previous time t, and L is packet size; and

allocating a portion of bandwidth to each flow based on the weight for the flow.

10. The medium of claim 9 wherein the adaptively determining the weight for each flow comprises adaptively determining the weight as the input rate multiplied by a normalizing constant.

11. The medium of claim 9 wherein the output link comprises a local area network.

12. The medium of claim 9 wherein the output link comprises a wireless network.

13. 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 an input rate for each flow wherein adaptively determining a weight for each flow comprises determining the weight as $w<br><br>\left(\mathrm{\tau <br><br>}\right)=\frac{r<br><br>\left(\mathrm{\tau <br><br>}\right)}{\mathrm{Normalizing}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{factor}},$

 

where $r<br><br>\left(\mathrm{\tau <br><br>}\right)=\frac{\mathrm{tr}<br><br>\left(t\right)+\mathrm{\xi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>L}{\mathrm{\tau <br><br>}},$

 

ξ

is a rate-sensitivity constant, and r(t) is the input rate a previous time t, L is packet size, and Normalizing Factor is a constant; and

allocating a portion of bandwidth to each flow based on the weight for the flow.

14. The medium of claim 13 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 input rate and a queue size.

15. The medium of claim 13 wherein the output link comprises a local area network.

16. The medium of claim 13 wherein the output link comprises a wireless network.