Adaptive allocation of last-hop bandwidth based on monitoring of end-to-end throughput

• US 20030212787A1
• Filed: 05/13/2002
• Published: 11/13/2003
• Est. Priority Date: 05/13/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Adya, Atul, Qiu, Lili
• Granted Patent: US 7,363,375 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals

Abstract

An improved method and system for optimizing the allocation of bandwidth within a network system is presented. When a client device is engaged in communication with a remote computing device, an access point measures the throughput of the connection between the client device and the network. If the throughput is less than the amount of bandwidth reserved for usage by the client device, the access point adjusts the amount of bandwidth allocated for the client device to an amount equivalent to the measured throughput multiplied by an error variance factor. This process is then repeated periodically for the duration of the communication between the client device and the remote computing device in order to continually adapt the bandwidth allocation of the client device. Optionally, the method and system can be also deployed in client devices instead of the access point

Claims

1. A method for optimizing the allocation of bandwidth within a network system communicably linked with a network, the network system having one or more client devices and one or more intermediate computing devices that act as an interface between the network and the one or more client devices, the method comprising:

measuring throughput of a connection established between at least one of the client devices and the network;

determining whether the measured throughput is less than an amount of bandwidth allocated to the at least one client device; and

setting an amount of bandwidth to be allocated to the at least one client device to an amount equivalent to the measured throughput multiplied by an error variance factor if the measured throughput is less than an amount of bandwidth allocated to the at least one client device.

2. The method of claim 1 further comprising:

informing the at least one client of the adjustment made to the bandwidth; and

assigning an amount of bandwidth equivalent to the set amount of bandwidth to the at least one client device.

3. The method of claim 1 wherein the step of measuring further comprises performing active throughput measurement.

4. The method of claim 1 wherein the step of measuring further comprises performing passive throughput measurement.

5. The method of claim 1 wherein the step of determining is performed by the at least one client device.

6. The method of claim 5 wherein the at least one client device exchanges the measured throughput value with at least one of the intermediate computing devices.

7. The method of claim 1 wherein the step of determining is performed by the at least one intermediate computing device.

8. The method of claim 1 wherein the error variance factor is equal to one.

9. The method of claim 1 wherein the error variance factor is greater than one.

10. The method of claim 2 wherein the step of assigning further comprises modifying the amount of bandwidth allocated to the at least one client device to an amount equivalent to the minimum of the bandwidth reserved initially by the client and the set amount of bandwidth.

11. A computer-readable medium for performing the computer-executable steps recited in claim 1.

12. A system for optimizing the allocation of bandwidth within a network system communicably linked with a network, the network system having one or more client devices and one or more intermediate computing devices that act as an interface between the network and the one or more client devices, the system comprising:

means for measuring the throughput associated with a connection established between at least one of the client devices and the network;

means for determining whether the measured throughput is less than an amount of bandwidth allocated to the at least one client device; and

means for adjusting the amount of bandwidth allocated to the at least one client device to an amount equivalent to the measured throughput multiplied by an error variance factor.

13. The system of claim 12 further comprising means for informing the at least one client of the adjustment made to the bandwidth.

14. A method for preventing the under utilization of reserved bandwidth by one or more client devices capable of communicating over a network by establishing a communicable link with an intermediate computing device that is communicably linked to the network, the method comprising:

receiving a bandwidth reservation request from a first client device;

determining whether the first client device has similar bandwidth affecting criteria as at least one of the client devices having an existing bandwidth allocation; and

assigning the first client device an amount of bandwidth equivalent to the existing bandwidth allocation if the first device has similar bandwidth affecting criteria as at least one of the client devices having an existing bandwidth allocation.

15. The method of claim 14 further comprising establishing a link between the intermediate computing device and the first client device.

16. The method of claim 14 further comprising informing the first client device of the amount of bandwidth it is assigned.

17. The method of claim 14 wherein the step of determining further comprises comparing state information related to the first client device with state information related to the at least one client device having an existing bandwidth allocation.

18. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 14.

19. A system for preventing the wasting of reserved bandwidth by one or more client devices capable of communicating over a network by establishing a connection with an intermediate computing device that is communicably linked to the network, the system comprising:

means for receiving a bandwidth reservation request from a first client device having no current bandwidth allocation;

means for determining whether the first client device shares comparable bandwidth affecting criteria with a second client device having a current bandwidth allocation; and

means for assigning the first client device an amount of bandwidth equivalent to the amount of bandwidth allocated to the second client device.

20. The system of claim 19 further comprising means for establishing a connection with the intermediate computing device by the first client device.

21. The system of claim 19 further comprising means for informing the first client device of the amount of bandwidth it is assigned.

22. A method for adjusting the amount of bandwidth allocated within a network system having one or more nodes and one or more intermediary nodes that act as an interface between the network and the one or more nodes, the method comprising:

measuring throughput associated with a connection established between at least one of the nodes and the network;

determining whether the measured throughput is less than an amount of bandwidth allocated to the at least one node;

setting an amount of bandwidth to be allocated to the at least one node to an amount equivalent to the measured throughput multiplied by an error variance factor if the measured throughput is less than an amount of bandwidth allocated to the at least one node;

repeating the steps of measuring, determining and setting for the duration of the connection established between at least one of the nodes and the network.

23. The method of claim 22 further comprising:

informing the at least one node of the adjustment made to the bandwidth; and

assigning an amount of bandwidth equivalent to the set amount of bandwidth to the at least one node.

24. The method of claim 23 wherein the step of assigning further comprises modifying the amount of bandwidth allocated to the at least one node to an amount equivalent to the minimum of the bandwidth reserved initially by the node and the set amount of bandwidth.

25. The method of claim 22 wherein the error variance factor is equal to one.

26. The method of claim 22 wherein the error variance factor is greater than one.

27. A computer-readable medium for performing the computer-executable steps recited in claim 22.

28. A system for preventing the over allocation of bandwidth by one or more computers capable of communicating over a network by establishing a connection with an intermediate computing device that is linked to the network, the system comprising:

means for receiving a bandwidth reservation request from a first computer having no current bandwidth allocation;

means for determining whether the first computer shares comparable bandwidth affecting criteria with a second computer having a current bandwidth allocation; and

means for assigning the first computer an amount of bandwidth equivalent to the amount of bandwidth allocated to the second computer.

29. The system of claim 28 further comprising means for establishing a connection with the intermediate computing device by the first client device.

30. The system of claim 28 further comprising means for informing the first client device of the amount of bandwidth it is assigned.

31. A method for adjusting the amount of bandwidth allocated within a network system having one or more nodes and one or more intermediary nodes that act as an interface between the network and the one or more nodes, the method comprising:

receiving a throughput measurement associated with a connection established between at least one of the nodes and the network;

determining whether the throughput measurement indicates a throughput of less than an amount of bandwidth allocated to the at least one node;

setting an amount of bandwidth to be allocated to the at least one node to an amount equivalent to the throughput multiplied by an error variance factor if the throughput is less than an amount of bandwidth allocated to the at least one node;

repeating the steps of receiving, determining and setting for the duration of the connection established between at least one of the nodes and the network.

32. The method of claim 31 further comprising:

informing the at least one node of the adjustment made to the bandwidth; and

assigning an amount of bandwidth equivalent to the set amount of bandwidth to the at least one node.

33. The method of claim 32 wherein the step of assigning further comprises modifying the amount of bandwidth allocated to the at least one node to an amount equivalent to the minimum of the bandwidth reserved initially by the node and the set amount of bandwidth.

34. The method of claim 32 wherein the error variance factor is equal to one.

35. The method of claim 32 wherein the error variance factor is greater than one.

36. A computer-readable medium for performing the computer-executable steps recited in claim 31.