Slow-start adaptive mechanisms to improve efficiency of bandwidth allocation
First Claim
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 comprisingestimating 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 comprisesestimating 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.
12 Assignments
0 Petitions
Accused Products
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.
-
Citations
26 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 comprisesestimating 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26)
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.
Specification