Background transport service

• US 7,516,238 B2
• Filed: 09/30/2003
• Issued: 04/07/2009
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Bing, Key, Peter B., Massoulie, Laurent
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): LAZARO, DAVID R
• Application Number:
  US10/676,772
• Publication Number:
  US 20050071451A1
• Time in Patent Office: 2,016 Days
• Field of Search: 709230-237, 709/224, 370229-235
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets

Abstract

In an application-level background transport service, a receiver node infers the available network capacity between itself and a sender node over a control interval. Based on the inferred available network capacity, the receiver node adjusts its receive window size accordingly in order to conservatively optimize the bandwidth used by a background transfer without degrading performance of other foreground transfers on the network. The adjusted receive window size is communicated to the sender node, which is likely to adjust its send window size based on the adjusted receive window size.

Claims

1. A method comprising:

evaluating network capacity available for communications between a first node and a second node based on transfer data received by the second node from the first node within a specified receive window during a specified control interval; and

generating an adjusted receive window size for a subsequent control interval based on evaluated availability of the network capacity in the specified control interval, by adjusting a receive buffer size at the second node at an application level to generate the adjusted window size in the subsequent control interval,

wherein the operation of generating further comprises evaluating a measured amount of the transfer data received by the second node during the specified control interval relative to the specified received window size to determine a slope for the specified control interval; and

comparing the slope for the specified control interval against an estimate of a constant slope associated with additional available network capacity in at least one previous control interval and adjusting the receive window size for the subsequent control interval based on a result of the comparing.

2. The method of claim 1 further comprising:

communicating the adjusted receive window size to the first node to instruct the first node to transmit to the second node in accordance with the adjusted receive window size in the subsequent control interval.

3. The method of claim 1 wherein the operation of generating comprises:

applying the adjusted receive window size to a transport level of the second node in the subsequent control interval.

4. The method of claim 1 further comprising:

communicating the adjusted receive window size to the first node to instruct the first node to adjust a send window size in accordance with the receive window and to transmit to the second node in accordance with the adjusted receive window size in the subsequent control interval.

5. The method of claim 1 wherein the operation of evaluating comprises:

detecting a loss of the transfer data received by the second node during the specified control interval, relative to the specified receive window.

6. The method of claim 1 wherein the operation of evaluating comprises:

measuring an amount of the transfer data received by the second node during the specified control interval.

7. The method of claim 1 wherein the operation of generating comprises:

determining whether to increase or decrease the receive window to obtain the adjusted receive window size; and

determining an amount by which to adjust the receive window to obtain the adjusted receive window size.

8. The method of claim 1 wherein the operation of generating comprises:

determining an amount by which to adjust the receive window using a binary search to obtain the adjusted receive window size.

9. The method of claim 1 wherein the operation of generating comprises:

determining an amount by which to adjust the receive window using a stochastic approximation to obtain the adjusted receive window size.

10. The method of claim 1 wherein

the comparing of the slope for the specified control interval against an estimate of a constant slope associated with additional available network capacity in the at least one previous control interval is performed in the presence of a measurement noise threshold.

11. The method of claim 1 wherein

the estimate of the constant slope represents a weighted average of at least one previous slopes associated with at least one previous control interval in which the previous slope exceeds or equals a previous estimate of the constant slope.

12. The method of claim 1 wherein the operations of evaluating and generating are performed at the application level.

13. A computer program product including a computer readable medium having encoded thereon a computer program for executing on a computer system a computer process, the computer process comprising:

evaluating network capacity available for communications between a first node and a second node based on transfer data received by the second node from the first node within a specified receive window during a specified control interval; and

generating an adjusted receive window size for a subsequent control interval based on evaluated availability of the network capacity in the specified control interval,

wherein the operation of generating further comprises evaluating a measured amount of the transfer data received by the second node during the specified control interval relative to the specified received window size to determine a slope for the specified control interval, and

comparing the slope for the specified control interval against an estimate of a constant slope associated with additional available network capacity in at least one previous control interval and adjusting the receive window size based on a result of the comparing.

14. The computer program product of claim 13 wherein the computer process further comprises:

communicating the adjusted receive window size to the first node to instruct the first node to transmit to the second node in accordance with the adjusted receive window size in the subsequent control interval.

15. The computer program product of claim 13 wherein the operation of generating comprises:

adjusting a receive buffer size at the second node at an application level to generate the adjusted receive window size in the subsequent control interval.

16. The computer program product of claim 13 wherein the operation of generating comprises:

applying the adjusted receive window size to a transport level of the receive node in the subsequent control interval.

17. The computer program product of claim 13 the computer process further comprises:

communicating the adjusted receive window size to the first node to instruct the first node to adjust a send window size in accordance with the receive window and to transmit to the second node in accordance with the adjusted receive window size in the subsequent control interval.

18. The computer program product of claim 13 wherein the operation of evaluating comprises:

detecting a loss of the transfer data received by the second node during the specified control interval, relative to the specified receive window.

19. The computer program product of claim 13 wherein the operation of evaluating comprises:

measuring an amount of the transfer data received by the second node during the specified control interval.

20. The computer program product of claim 13 wherein the operation of generating comprises:

determining whether to increase or decrease the receive window to obtain the adjusted receive window size; and

determining an amount by which to adjust the receive window to obtain the adjusted receive window size.

21. The computer program product of claim 13 wherein the operation of generating comprises:

determining an amount by which to adjust the receive window using a binary search to obtain the adjusted receive window size.

22. The computer program product of claim 13 wherein the operation of generating comprises:

determining an amount by which to adjust the receive window using a stochastic approximation to obtain the adjusted receive window size.

23. The computer program product of claim 13 wherein

the comparing of the slope for the specified control interval against an estimate of a constant slope associated with additional available network capacity in at least one previous control interval is performed in the presence of a measurement noise threshold.

24. The computer program product of claim 13 wherein

wherein the estimate of the constant slope represents a weighted average of at least one previous slopes associated with at least one previous control interval in which the previous slope exceeds or equals a previous estimate of the constant slope.

25. The computer program product of claim 13 wherein the operations of evaluating and generating are performed at the application level.

26. A system comprising:

an estimating module evaluating network capacity available for communications between a first node and a second node based on transfer data received by the second node from the first node within a specified receive window during a specified control interval; and

an adjusting module generating an adjusted receive window size for a subsequent control interval based on evaluated availability of the network capacity in the specified control interval,

wherein the adjusting module generates the adjusted receive window size by evaluating a measured amount of the transfer data received by the second node during the specified control interval relative to the specified received window size to determine a slope for the specified control interval; and

comparing the slope for the specified control interval against an estimate of a constant slope associated with additional available network capacity in at least one previous control interval and adjusting the receive window size for the subsequent control interval based on a result of the comparing.

27. The system of claim 26 further comprising:

a communication module communicating the adjusted receive window size to the first node to instruct the first node to transmit to the second node in accordance with the adjusted receive window size in the subsequent control interval.

28. The system of claim 26 wherein the adjusting module adjusts a receive buffer size at the second node at an application level to generate the adjusted receive window size in the subsequent control interval.

29. The system of claim 26 wherein the adjusting module applies the adjusted receive window size to a transport level of the second node in the subsequent control interval.

30. The system of claim 26 further comprising:

a communications module communicates the adjusted receive window size to the first node to instruct the first node to adjust a send window size in accordance with the receive window and transmits to the second node in accordance with the adjusted receive window size in the subsequent control interval.

31. The system of claim 26 wherein the estimating module detects a loss of the transfer data received by the second node during the specified control interval, relative to the specified receive window.

32. The system of claim 26 wherein the estimating module measures an amount of the transfer data received by the second node during the specified control interval.

33. The system of claim 26 wherein the adjusting module determines whether to increase or decrease the receive window to obtain the adjusted receive window size and determines an amount by which to adjust the receive window to obtain the adjusted receive window size.

34. The system of claim 26 wherein adjusting module determines an amount by which to adjust the receive window using a binary search to obtain the adjusted receive window size.

35. The system of claim 26 wherein the adjusting module determines an amount by which to adjust the receive window using a stochastic approximation to obtain the adjusted receive window size.

36. The system of claim 26 wherein the adjusting module compares the slope for the specified control interval against an estimate of a constant slope associated with additional available network capacity in at least one previous control interval in the presence of a measurement noise threshold.

37. The system of claim 26 wherein the estimate of the constant slope represents a weighted average of at least one previous slopes associated with at least one previous control interval in which the previous slope exceeds or equals a previous estimate of the constant slope.

38. The system of claim 26 wherein the estimating module and the adjusting module operate at the application level.