Slow-start adaptive mechanisms to improve efficiency of bandwidth allocation
View Patent ↗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.
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.