Methods and systems for a receiver to allocate bandwidth among incoming communications flows

• US 7,039,715 B2
• Filed: 05/21/2002
• Issued: 05/02/2006
• Est. Priority Date: 05/21/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: England, Paul, Herley, Cormac E.
• Primary Examiner(s): Thompson, Marc D.
• Application Number:
  US10/152,112
• Publication Number:
  US 20030221008A1
• Time in Patent Office: 1,442 Days
• Field of Search: 709/206, 709/207, 709/223, 709/224, 709/225, 709/226, 709/228, 709/232, 709/233, 709/234, 709/235, 370/235
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/2475 for supporting traffic characterised by the type of applications
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/765 triggered by the end-points
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/803 Application aware
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data

Abstract

Disclosed are methods and systems for a receiver to autonomously allocate bandwidth among its incoming communications flows. The incoming flows are assigned priorities. When it becomes necessary to alter the allocation of bandwidth among the flows, the receiver selects one of the lower priority flows. The receiver then causes the selected flow to delay sending acknowledgements of messages received to the senders of the messages. In most modern protocols, senders are sensitive to the time it takes to receive acknowledgements of the messages they send. When the acknowledgement time increases, the sender assumes that the receiver is becoming overloaded. The sender then slows down the rate at which it sends messages to the receiver. This lowered sending rate in turn reduces the amount of bandwidth used by the flow as it comes into the receiver. This frees up bandwidth which can then be used by higher priority flows.

Claims

1. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a method for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the method comprising:

assigning a priority to each incoming communications flow;

deciding whether to re-allocate the incoming bandwidth of the common communications link among the incoming communications flows; and

if a decision is made to re-allocate the incoming bandwidth, then;

selecting an incoming communications flow with an assigned priority lower than the assigned priority of another incoming communications flow; and

increasing an average response time for messages received over the selected incoming communications flow,

wherein increasing an average response time for messages received over the selected incoming communications flow comprises utilizing a method selected from the group consisting of;

delaying presentation of messages received over the selected incoming communications flow to an application associated with the selected incoming communications flow,

delaying transmission of message acknowledgements over an outgoing communications flow associated with the selected incoming communications flow, and decreasing a size of a receiver buffer pool associated with the selected incoming communications flow.

2. The method of claim 1 wherein at least one incoming communications flow is associated with an application running on a computing device other than the receiver computing device.

3. The method of claim 1 wherein assigning a priority comprises choosing a priority selected from the group consisting of:

high priority, medium priority, and low priority.

4. The method of claim 1 wherein assigning a priority comprises choosing a priority selected from the group consisting of:

always real-time priority, real-time priority, always interactive priority, interactive priority, always back-off priority, and back-off priority.

5. The method of claim 1 wherein assigning a priority to an incoming communications flow comprises analyzing a name of an application associated with the incoming communications flow.

6. The method of claim 1 wherein assigning a priority to an incoming communications flow comprises analyzing dataflow patterns of the incoming communications flow.

7. The method of claim 6 wherein analyzing dataflow patterns reveals that the incoming communications flow is a real-time-type communications flow and wherein assigning a priority comprises choosing a priority selected from the group consisting of:

high priority, always real-time priority, and real-time priority.

8. The method of claim 6 wherein analyzing dataflow patterns reveals that the incoming communications flow is a browser-type communications flow and wherein assigning a priority comprises choosing a priority selected from the group consisting of:

medium priority, always interactive priority, and interactive priority.

9. The method of claim 6 wherein analyzing dataflow patterns reveals that the incoming communications flow is a file-transfer-type communications flow and wherein assigning a priority comprises choosing a priority selected from the group consisting of:

low priority, always back-off priority, and back-off priority.

10. The method of claim 1 wherein assigning a priority to an incoming communications flow comprises:

analyzing input from a user of the receiver associating a priority with an application associated with the incoming communications flow; and

deriving a priority for the incoming communications flow from the priority associated with the application associated with the incoming communications flow.

11. The method of claim 10 wherein the incoming communications flow is associated with an application running on a computing device other than the receiver computing device.

12. The method of claim 10 wherein analyzing input from a user of the receiver comprises:

for a plurality of incoming communications flows, associating an application with each incoming communications flow;

for each of the associated applications, measuring an amount of incoming bandwidth of the common communications link used by the associated application;

creating a list of the associated applications and the measured amounts of incoming bandwidth used by the associated applications;

displaying the list to the user; and

receiving from the user input associating a priority with an associated application on the list.

13. The method of claim 12 wherein analyzing input from a user further comprises:

associating an application with a potential, but non-current, incoming communications flow; and

adding to the created list the application associated with the potential incoming communications flow.

14. The method of claim 1 wherein assigning a priority to an incoming communications flow comprises analyzing information selected from the group consisting of:

an amount of time that an application associated with the incoming communications flow has been active, an amount of bandwidth used by the incoming communications flow, and input from a user of the receiver associated a priority with a sender computing device associated with the incoming communications flow.

15. The method of claim 1 wherein deciding whether to re-allocate the incoming bandwidth of the common communications link comprises:

if a first incoming communications flow has an assigned priority higher than an assigned priority of a second incoming communications flow, then choosing to re-allocate.

16. The method of claim 1 wherein deciding whether to re-allocate the incoming bandwidth of the common communications link comprises:

setting a threshold value for an amount of the incoming bandwidth of the common communications link;

measuring an amount of the incoming bandwidth of the common communications link that is used;

comparing the measured amount with the threshold value;

and if the measured amount exceeds the threshold value, and if a first incoming communications flow has an assigned priority higher than an assigned priority of a second incoming communications flow, then choosing to re-allocate.

17. The method of claim 1 wherein deciding whether to re-allocate the incoming bandwidth of the common communications link comprises:

monitoring an outgoing communications flow associated with a first incoming communications flow; and

if an indication is seen on the monitored outgoing communications flow that the first incoming communications flow will soon need more bandwidth, and if the first incoming communications flow has an assigned priority higher than an assigned priority of a second incoming communications flow, then choosing to re-allocate.

18. The method of claim 17 wherein monitoring an outgoing communications flow comprises watching for a Hyper Text Transfer Protocol GET( ) command.

19. The method of claim 1 wherein deciding whether to re-allocate the incoming bandwidth of the common communications link comprises:

setting a desired value range for a Quality of Service (QOS) parameter of a first incoming, communications flow;

measuring the QOS parameter of the first incoming communications flow;

comparing the measured QOS parameter with the QOS desired value range; and

if the measured QOS parameter does not lie within the QOS desired value range, and if the first incoming communications flow has an assigned priority higher than an assigned priority of a second incoming communications flow, then choosing to reallocate.

20. The method of claim 19 wherein measuring the QOS parameter comprises measuring a parameter selected from the group consisting of:

latency and amount of incoming bandwidth of the common communications link that is used.

21. The method of claim 1 wherein increasing an average response time for messages received over the selected incoming communications flow comprises utilizing a method selected from the group consisting of:

delaying presentation of messages received over the selected incoming communications flow to an application associated with the selected incoming communications flow, delaying transmission of message acknowledgements over an outgoing communications flow associated with the selected incoming communications flow, and decreasing a size of a receiver buffer pool associated with the selected incoming communications flow.

22. The method of claim 1 further comprising:

deciding whether to decrease an average response time for messages received over the selected incoming communications flow; and

if a decision is made to decrease the average response time, then decreasing the average response time for messages received over the selected incoming communications flow.

23. The method of claim 22 wherein deciding whether to decrease an average response time comprises:

setting a threshold value for an amount of the incoming bandwidth of the common communications link;

measuring an amount of the incoming bandwidth of the common communications link that is used;

comparing the measured amount with the threshold value; and

if the measured amount is below the threshold value, then choosing to decrease the average response time.

24. The method of claim 22 wherein deciding whether to decrease an average response time comprises:

setting a repose value;

monitoring an outgoing communications flow associated with a first incoming communications flow; and

if for a period of time equal to the repose value, no indication is seen on the monitored outgoing communications flow that the first incoming communications flow will soon need more bandwidth, then choosing to decrease the average response time.

25. The method of claim 24 wherein monitoring an outgoing communications flow comprises watching for a Hyper Text Transfer Protocol GET( ) command.

26. The method of claim 22 wherein deciding whether to decrease an average response time comprises:

setting a desired value range for a Quality of Service (QOS) parameter of a first incoming communications flow;

measuring the QOS parameter of the first incoming communications flow;

comparing the measured QOS parameter with the QOS desired value range; and

if the measured QOS parameter lies within the QOS desired value range, then choosing to decrease the average response time.

27. The method of claim 26 wherein measuring the QOS parameter comprises measuring a parameter selected from the group consisting of:

latency and amount of incoming bandwidth of the common communications link that is used.

28. The method of claim 22 wherein decreasing an average response time comprises utilizing a method selected from the group consisting of:

removing a delay in presentation of messages received over the selected incoming communications flow to an application associated with the selected incoming communications flow, removing a delay in transmission of message acknowledgements over an outgoing communications flow associated with the selected incoming communications flow, and increasing a size of a receiver buffer pool associated with the selected incoming communications flow.

29. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a system for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the system comprising:

communications hardware supporting the common communications link;

a first protocol stack coordinating messaging of a first incoming communications flow over the common communications link;

a second protocol stack coordinating messaging of a second incoming communications flow over the common communications link;

a first application receiving messages from the first incoming communications flow;

a second application receiving messages from the second incoming communications flow;

a first layered service provider communicating with the first application and with the first incoming communications flow;

a second layered service provider communicating with the second application and with the second incoming communications flow; and

a comparator for comparing a priority assigned to the first incoming communications flow with a priority assigned to the second incoming communications flow.

30. The system of claim 29 wherein the first protocol stack and the second protocol stack are the same.

31. The system of claim 29 wherein the first application is part of an operating system.

32. The system of claim 29 wherein the first layered server provider and the second layered service provider are the same.

33. The system of claim 29 wherein the first layered server provider increases an average response time for messages received over the first incoming communications flow by utilizing a method selected from the group consisting of:

delaying presentation of messages received over the first incoming communications flow to the first application, delaying transmission of message acknowledgements over an outgoing communications flow associated with the first incoming communications flow, and decreasing a size of a receiver buffer pool associated with the first incoming communications flow.

34. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a method for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the method comprising:

assigning a priority to each incoming communications flow;

deciding whether to re-allocate the incoming bandwidth of the common communications link among the incoming communications flows; and

if a decision is made to re-allocate the incoming bandwidth, then;

selecting an incoming communications flow with an assigned priority lower than the assigned priority of another incoming communications flow; and

increasing an average response time for messages received over the selected incoming communications flow, wherein analyzing input from a user of the receiver comprises;

for a plurality of incoming communications flows, associating an application with each incoming communications flow;

for each of the associated applications, measuring an amount of incoming bandwidth of the common communications link used by the associated application;

creating a list of the associated applications and the measured amounts of incoming bandwidth used by the associated applications;

displaying the list to the user; and

receiving from the user input associating a priority with an associated application on the list.

35. The method of claim 34, wherein analyzing input from a user further comprises:

associating an application with a potential, but non-current, incoming communications flow; and

adding to the created list the application associated with the potential incoming communications flow.

36. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a method for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the method comprising:

assigning a priority to each incoming communications flow;

deciding whether to re-allocate the incoming bandwidth of the common communications link among the incoming communications flows; and

if a decision is made to re-allocate the incoming bandwidth, then;

selecting an incoming communications flow with an assigned priority lower than the assigned priority of another incoming communications flow; and

increasing an average response time for messages received over the selected incoming communications flow,

wherein deciding whether to re-allocate the incoming bandwidth of the common communications link comprises;

monitoring an outgoing communications flow associated with a first incoming communications flow; and

if an indication is seen on the monitored outgoing communications flow that the first incoming communications flow will soon need more bandwidth, and if the first incoming communications flow has an assigned priority higher than an assigned priority of a second incoming communications flow, then choosing to re-allocate.

37. The method of claim 36 wherein monitoring an outgoing communications flow comprises watching for a Hyper Text Transfer Protocol GET() command.

38. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a method for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the method comprising:

assigning a priority to each incoming communications flow;

deciding whether to re-allocate the incoming bandwidth of the common communications link among the incoming communications flows; and

if a decision is made to re-allocate the incoming bandwidth, then;

selecting an incoming communications flow with an assigned priority lower than the assigned priority of another incoming communications flow; and

increasing an average response time for messages received over the selected incoming communications flow,

wherein selecting an incoming communications flow comprises;

selecting a priority such that the selected priority is assigned to at least one incoming communications flow and such that the selected priority is at least as low as a priority assigned to any other incoming communications flow;

for each incoming communications flow with the selected priority, measuring an amount of incoming bandwidth of the common communications link used; and

of the incoming communications flows with the selected priority, selecting an incoming communications flow such that the measured amount of incoming bandwidth used by the selected incoming communications flow is at least as high as the measured amount of incoming bandwidth used by any other incoming communications flow with the selected priority.

39. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a method for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the method comprising:

assigning a priority to each incoming communications flow;

deciding whether to re-allocate the incoming bandwidth of the common communications link among the incoming communications flows;

if a decision is made to re-allocate the incoming bandwidth, then;

selecting an incoming communications flow with an assigned priority lower than the assigned priority of another incoming communications flow; and

increasing an average response time for messages received over the selected incoming communications flow;

deciding whether to decrease an average response time for messages received over the selected incoming communications flow; and

if a decision is made to decrease the average response time, then decreasing the average response time for messages received over the selected incoming communications flow,

wherein deciding whether to decrease an average response time comprises;

setting a repose value;

monitoring an outgoing communications flow associated with a first incoming communications flow; and

if for a period of time equal to the repose value, no indication is seen on the monitored outgoing communications flow that the first incoming communications flow will soon need more bandwidth, then choosing to decrease the average response time.

40. The method of claim 39, wherein monitoring an outgoing communications flow comprises watching for a Hyper Text Transfer Protocol GET() command.

41. In a communications environment with a receiver computing device receiving a plurality of incoming communications flows over a common communications link, a method for allocating incoming bandwidth of the common communications link among the plurality of incoming communications flows, the method comprising:

assigning a priority to each incoming communications flow;

deciding whether to re-allocate the incoming bandwidth of the common communications link among the incoming communications flows;

if a decision is made to re-allocate the incoming bandwidth, then;

selecting an incoming communications flow with an assigned priority lower than the assigned priority of another incoming communications flow; and

increasing an average response time for messages received over the selected incoming communications flow;

deciding whether to decrease an average response time for messages received over the selected incoming communications flow; and

if a decision is made to decrease the average response time, then decreasing the average response time for messages received over the selected incoming communications flow,

wherein decreasing an average response time comprises utilizing a method selected from the group consisting of;

removing a delay in presentation of messages received over the selected incoming communications flow to an application associated with the selected incoming communications flow, removing a delay in transmission of message acknowledgements over an outgoing communications flow associated with the selected incoming communications flow, and increasing a size of a receiver buffer pool associated with the selected incoming communications flow.