Slow-start adaptive mechanisms to improve efficiency of bandwidth allocation

• US 7,426,181 B1
• Filed: 03/26/2004
• Issued: 09/16/2008
• Est. Priority Date: 03/26/2004
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Feroz, Azeem, Stabile, James J., Lai, Wei-Lung
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): PATEL, CHANDRAHAS B
• Application Number:
  US10/810,785
• Time in Patent Office: 1,635 Days
• Field of Search: 370/231, 370/229, 370/230, 370/232, 370/234, 370/235, 370/236
• US Class Current: 370/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/37 Slow start

Abstract

Methods, apparatuses and systems directed to improving the efficiency of bandwidth allocation schemes by adapting to slow-start mechanisms associated with network communications protocols, such as the TCP/IP protocol suite. In one implementation, the present invention scales down the initial target rate assigned to a data flow to a fraction of an initial estimate of the effective rate capacity of the communications path between two hosts. As packets are received, the target rate is gradually increased, eventually up to the detected rate capacity of the communications path. Implementations of the present invention improve the efficiency of bandwidth allocation by reducing the over-allocation of bandwidth to data flows during the slow-start phase, leaving more bandwidth available to other data flows.

Claims

1. In a network device operative to control data flows transmitted between hosts connected to a computer network, wherein at least some of the hosts employ slow-start mechanisms, a method comprising

estimating the initial rate demand for a data flow between a first host and a second host;

estimating the number of packets that the first host will transmit before achieving the initial rate demand;

setting at least one threshold based on the number of packets in the second estimating step;

allocating bandwidth for the flow, wherein the allocated bandwidth is a fraction of the initial rate demand for the flow;

maintaining a count of the packets associated with the flow; and

increasing the bandwidth allocated to the flow as the count crosses at least one threshold;

wherein the estimating the number of packets that the first host will transmit before achieving the initial rate demand comprises

estimating the round trip time between the first and second host;

multiplying the initial demand rate associated with the data flow by the round trip time; and

dividing the product of the multiplying step by an average packet size.

2. The method of claim 1 further comprising

estimating the number of bytes that the first host will transmit before achieving the initial rate demand;

and

setting the at least one threshold based on the number of bytes in the second estimating step.

3. The method of claim 2 wherein the second estimating step comprises

estimating the round trip time between the first and second host;

and

multiplying the initial demand rate associated with the data flow by the round trip time.

4. The method of claim 3 wherein the round trip time is based on an analysis of the arrival times of the handshake packets corresponding to the data flow.

5. The method of claim 1 wherein the initial rate demand is based on an analysis of the arrival times of at least one of the handshake packets corresponding to the data flow.

6. The method of claim 5 wherein the initial rate demand is based on an analysis of at least one data packet corresponding to the data flow.

7. The method of claim 1 wherein the initial rate demand is based on an analysis of at least one data packet corresponding to the data flow.

8. The method of claim 1 wherein the average packet size is a dynamic parameter that changes based on observations of the packets traversing the network device.

9. The method of claim 1 wherein the round trip time is based on an analysis of the arrival times of the handshake packets corresponding to the data flow.

10. The method of claim 1 wherein the average packet size is a static parameter.

11. The method of claim 10 wherein the average packet size is a configurable parameter.

12. The method of claim 1 wherein the initial rate demand is based on an analysis of at least one data packet corresponding to the data flow.

13. The method of claim 1 wherein the initial rate demand is based on an analysis of the arrival times of at least one of the handshake packets corresponding to the data flow.

14. The method of claim 13 wherein the initial rate demand is based on an analysis of at least one data packet corresponding to the data flow.

15. The method of claim 1 further comprising

monitoring for at least one indication that the sending host has re-initiated the slow start mechanism for the data flow;

upon detection of at least one of the indications,

resetting the count of the packets for the flow; and

repeating the allocating, maintaining and increasing steps.

16. The method of claim 15 wherein the monitoring step comprises

determining whether the packet arrived a threshold period of time after the last packet corresponding to the data flow.

17. The method of claim 15 wherein the monitoring step comprises

determining whether at least one data packet corresponding to the data flow is a re-transmission of a previous packet.

18. The method of claim 17 wherein the monitoring step further comprises

determining whether the re-transmitted packet arrived a threshold period of time after the last packet corresponding to the data flow.

19. An apparatus facilitating control data flows transmitted between hosts connected to a computer network, wherein at least some of the hosts employ slow-start mechanisms, comprising

a packet processor operative to

detect a data flow in network traffic traversing a communications path;

maintain a count of the packets associated with the data flow;

a path rate detection module operative to

estimate the initial rate demand for a data flow;

estimate, for the data flow, the number of packets that a sending host will transmit before achieving the initial rate demand by estimating the round trip time between the sending and receiving host;

multiplying the initial demand rate associated with the data flow by the round trip time; and

dividing the product of the multiplying step by an average packet size;

a bandwidth allocation module operative to

allocate bandwidth to the data flow based in part on a target rate associated with the data flow; and

wherein the apparatus is operative to

set the initial target rate for the data flow as a fraction of the initial rate demand for the flow; and

increase the target rate associated with the data flow as the count of packets crosses a threshold value, wherein the threshold value is based at least in part on the estimated number of packets the sending host will transmit before achieving the initial rate demand.

20. The apparatus of claim 19 wherein the apparatus is further operative to

monitor for at least one indication that the sending host has re-initiated the slow start mechanism for the data flow;

and

upon detection of at least one of the indications,

reset the count of packets for the flow; and

reset the target rate for the data flow to the initial target rate.

21. The apparatus of claim 19 wherein the average packet size is a static parameter.

22. The apparatus of claim 19 wherein the average packet size is a configurable parameter.

23. The apparatus of claim 19 wherein the average packet size is a dynamic parameter that changes based on observations of the packets traversing the network device.

24. The apparatus of claim 19 wherein the round trip time is based on an analysis of the arrival times of the handshake packets corresponding to the data flow.

25. The apparatus of claim 19 wherein the initial rate demand is based on an analysis of the arrival times of at least one of the handshake packets corresponding to the data flow.

26. The apparatus of claim 25 wherein the initial rate demand is based on an analysis of at least one data packet corresponding to the data flow.