Slow-start adaptive mechanisms to improve efficiency of bandwidth allocation

• US 8,031,601 B2
• Filed: 08/08/2008
• Issued: 10/04/2011
• 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:
  US12/188,239
• Publication Number:
  US 20080298391A1
• Time in Patent Office: 1,152 Days
• Field of Search: 370229-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. A method comprising

detecting, at a network device operably connected to a link in a network, a first transport layer data flow corresponding to a first host and a second host among a plurality of transport layer data flows transmitted across the link;

estimating, at a start of the first transport layer data flow between the first host and the second host, an initial rate demand for the first transport layer data flow, wherein the first host and the second host implement, relative to the first transport layer data flow, a protocol that utilizes a slow-start phase, wherein the initial rate demand is an estimated rate capacity for the first transport layer data flow of a communications path between the first and second host, wherein the communications path includes the link;

allocating bandwidth of the link to a plurality of data flows including assigning a target rate to the first transport layer data flow wherein the target rate is less than the initial rate demand for the first transport layer data flow;

enforcing, at the network device, the target rate on the first transport layer data flow;

maintaining a count of packets associated with the first transport layer data flow; and

increasing the target rate allocated to the first transport layer data flow, if the count of packets associated with the first transport layer data flow exceeds at least one threshold.

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 first transport layer data flow by the round trip time.

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

5. The method of claim 1 wherein the initial rate demand is based on an analysis of arrival times of at least one handshake packet corresponding to the first transport layer 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 transport layer 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 first transport layer data flow.

8. 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 first transport layer data flow;

upon detection of at least one of the indications,

resetting the count of the packets for the first transport layer data flow; and

repeating the allocating, maintaining and increasing steps.

9. The method of claim 8 wherein the monitoring step comprise

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

10. The method of claim 9 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 first transport layer data flow.

11. The method of claim 8 wherein the monitoring step comprise determining whether the packet arrived a threshold period of time after the last packet corresponding to the first transport layer data flow.

12. A method comprising

detecting, at a network device operably connected to a link in a network, a first transport layer data flow corresponding to a first host and a second host among a plurality of transport layer data flows transmitted across the link;

estimating, at a start of the first transport layer data flow between the first host and the second host, an initial rate demand for the first transport layer data flow, wherein the first host and the second host implement, relative to the first transport layer data flow, a protocol that utilizes a slow-start phase, wherein the initial rate demand is an estimated rate capacity for the data flow of a communications path between the first and second host, wherein the communications path includes the link;

allocating bandwidth of the link to a plurality of data flows including assigning a target rate to the first transport layer data flow wherein the target rate is a fraction of the initial rate demand for the first transport layer data flow;

enforcing, at the network device, the target rate on the first transport layer data flow;

maintaining a count of transmitted bytes associated with the first transport layer data flow; and

increasing the target rate allocated to the first transport layer data flow, if the count of transmitted bytes associated with the first transport layer data flow increases.

13. The method of claim 12 wherein the increasing the target rate comprises increasing the fraction of the initial rate demand allocated to the first transport layer data flow as the count of transmitted bytes crosses at least one threshold.

14. The method of claim 13 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.

15. The method of claim 14 wherein the estimating the number of bytes comprises

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

and

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

16. An apparatus comprising:

a packet processor operative to

detect, among a plurality of transport layer data flows, a first transport layer data flow in network traffic traversing a link in a communications path between a first host and a second host, wherein the first host and the second host implement, relative to the first transport layer data flow, a protocol that utilizes a slow- start phase;

maintain a count of packets or bytes associated with the first transport layer data flow;

a path rate detection module operative to

estimate the initial rate demand for the first transport layer data flow, wherein the initial rate demand is an estimated rate capacity for the first transport layer data flow of a communications path between the first and second host;

a bandwidth allocation module operative to

allocate bandwidth of the link to a plurality of transport layer data flows including allocating bandwidth to the first transport layer data flow based in part on a target rate associated with the first transport layer data flow; and

wherein the apparatus is operative to

set a target rate for the first transport layer data flow wherein the target rate is less than the initial rate demand for the first transport layer data flow; and

increase the target rate associated with the first transport layer data flow, if the count of packets or bytes associated with the first transport layer data flow exceeds a threshold value.

17. The apparatus of claim 16 further comprising

a traffic classification database including at least one traffic class, at least one attribute defining the at least one traffic class, and at least one bandwidth utilization control corresponding to the at least one traffic class, wherein the traffic classification is operative to

compare attributes stored in association with traffic class identifiers to attributes of the first transport layer data flow to identify a traffic class that corresponds to the first transport layer data flow;

associate at least one bandwidth utilization control to the first transport layer data flow based on the identified traffic class; and

wherein the bandwidth allocation module is operative to allocate bandwidth based, at least in part, on the target rate, and the at least one bandwidth utilization control, associated with the first transport layer data flow.

18. The apparatus of claim 16 wherein the packet processor is further operative to parse at least one packet associated with the first transport layer data flow into a flow specification, wherein said flow specification contains at least one instance of any one of the following:

a protocol family designation, a direction of packet flow designation, a protocol type designation, a pair of hosts, a pair of ports, a pointer to a MIME type a pointer to an application-specific attribute.

19. The apparatus of claim 18 wherein the traffic classification database is operative to match the first transport layer data flow specification to a plurality of traffic classes, each of the traffic classes defined by one or more matching attributes;

and thereupon,

having found a matching traffic class in the matching step, associate said transport layer data flow specification with a traffic class from the plurality of traffic classes.

20. The apparatus of claim 16 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 first transport layer data flow;

and

upon detection of at least one of the indications,

reset the count of bytes for the transport layer data flow; and

reset the target rate for the first transport layer data flow to the initial target rate.

21. The apparatus of claim 16 wherein the path rate detection module is further operative to estimate the number of bytes that a sending host will transmit before achieving the initial rate demand.

22. A method comprising

allocating a limited amount of bandwidth to a plurality of transport layer data flows traversing a network between respective first and second hosts based on target rates associated with the transport layer data flows;

and

in response to detection of and for each data flow of at least a subset of the data flows,

estimating an initial rate demand for the transport layer data flow between a first host and a second host, wherein the first host and the second host implement, relative to the transport layer data flow, a protocol that utilizes a slow-start phase, wherein the initial rate demand is an estimated rate capacity for the data flow of a communications path between the first and second host;

setting a target rate to the transport layer data flow wherein the target rate is less than the initial rate demand for the transport layer data flow;

maintaining a count of packets associated with the transport layer data flow; and

increasing the target rate of the transport layer data flow, if the count of packets associated with the transport layer data flow exceeds at least one threshold.