Granted Patent B2

US 6,928,052 · App. 10/790,272 · Granted Aug 9, 2005

Abstract

Claims (78)

1. A method for allocating bandwidth on a communication link in an operating network, comprising:

receiving a flow of data packets at a receiving system from a sending system on the network via the link;

determining at the receiving system a target rate for the flow on the link;

transmitting data from the receiving system to the sending system in response to the flow of data packets received, the transmitted data providing feedback to the sending system such that when the sending system transmits subsequent data packets to the receiving system, such subsequent data packets are transmitted at a rate approximating the target rate determined by the receiving system; and

calculating a period of time for which the receiving system does not transmit data to the sending system.

2. The method of claim 1 wherein a rate at which the transmitted data from the receiving system arrive at the sending system determines the rate at which the sending system transmits the subsequent data packets.

3. The method of claim 1 , further comprising:

applying the calculated period of time for which the receiving system does not transmit data to a plurality of flows of a class.

4. The method of claim 1 , wherein the data transmitted from the receiving system to the sending system indicates a maximum amount of data that the receiving system will accept from the sending system in a subsequent data transmission.

5. The method of claim 1 , wherein the step of calculating the period of time includes using a model of the network.

6. The method of claim 1 , further comprising the steps of measuring a bandwidth of the link being used by a class of flows, and using the measured bandwidth as feedback for calculating the period of time.

7. The method of claim 1 , wherein the data transmitted by the receiving system to the sending system includes acknowledgment of receipt of a particular data packet in the flow of data packets.

8. The method of claim 1 , wherein the target rate is determined by a network protocol process.

9. The method of claim 1 , wherein when the link is idle, the target rate equals a full bandwidth of the link.

10. A method for allocating bandwidth on a communication link in an operating network, comprising:

receiving flows of data packets at a receiving system from sending systems on the network via the link;

determining at the receiving system a target rate for the flows on the link;

transmitting data to the sending systems that will cause the sending systems to transmit subsequent data packets to the receiving system at a rate approximating the target rate for the flows of data packets from the sending systems; and

for each flow of at least a subset of the flows, calculating a period of time for which the receiving system does not transmit data to the sending system.

11. A computer system for allocating bandwidth on a communication link in an operating network, comprising:

a network interface for receiving a flow of data packets from a sending system on the network via the link; and

a processor coupled to the network interface for determining a target rate for the flow on the link, the network interface transmitting data to the sending system in response to the flow of data packets received, the transmitted data providing feedback to the sending system such that the sending system transmits subsequent data packets at a rate approximating the target rate for the flow when responding to the transmitted data;

wherein the processor is configured to calculate a period of time for which the receiving system does not transmit data to the sending system.

12. The computer system of claim 11 , further comprising:

memory, coupled to the processor, configured to store a model of a behavior of the network that is used when calculating a period of time for which the receiving system does not transmit data to the sending system.

13. The computer system of claim 11 , wherein the processor is configured to assign the flow to a class of flows; and wherein a calculated period of time for which the receiving system does not transmit data to the sending system applies to the flows in said class.

14. The computer system of claim 11 , wherein the system is configured to measure a bandwidth of the link being used by a class of flows and to calculate, based on the measured bandwidth, a period of time for which the receiving system does not transmit data to the sending system.

15. The computer system of claim 11 , wherein the data transmitted from the receiving system to the sending system include a maximum amount of data that the receiving system will accept from the sending system in a subsequent data transmission.

16. The computer system of claim 11 , wherein the target rate is determined by an application program that receives the flow of data packets.

17. A method for allocating bandwidth on a communication link in an operating network, comprising:

receiving a flow of data packets at a receiving system from a sending system on the network via the link;

determining at the receiving system a target rate for the flow on the link; and

transmitting data from the receiving system to the sending system in response to the flow of data packets received, the transmitted data providing feedback to the sending system such that when the sending system transmits subsequent data packets to the receiving system, such subsequent data packets are transmitted at a rate approximating the target rate determined by the receiving system; and

calculating and applying a period of time for which the receiving system does not transmit data to a plurality of flows of a class;

wherein the target rate is determined by an application program that receives the flow of data packets.

18. The method of claim 17 , wherein the step of calculating the period of time includes using a model of the network.

19. The method of claim 17 , further comprising the steps of measuring a bandwidth of the link being used by a class of flows, and using the measured bandwidth as feedback for calculating the period of time.

20. A method for allocating bandwidth on a communication link in an operating network, comprising:

receiving a flow of data packets at a receiving system from a sending system on the network via the link;

determining at the receiving system a target rate for the flow on the link; and

transmitting data from the receiving system to the sending system in response to the flow of data packets received, the transmitted data providing feedback to the sending system such that when the sending system transmits subsequent data packets to the receiving system, such subsequent data packets are transmitted at a rate approximating the target rate determined by the receiving system;

wherein the target rate is determined by an application program that receives the flow of data packets; and the data transmitted by the receiving system to the sending system includes acknowledgment of receipt of a particular data packet in the flow of data packets.

21. In a data flow control device operative to control the rate of data packets transmitted between first and second transmission stations in a packet communications environment, wherein the first transmission station is operative to transmit at least one packet associated with a data flow to the second transmission station, wait for acknowledgment of at least one transmitted packet before transmitting subsequent packets associated with the flow, and retransmit the at least one packet if an acknowledgment is not received with a period of time, a method comprising

delaying transmission acknowledgment packets, corresponding to a first data flow transmitted from the first transmission station to the second transmission station, by a computed delay, wherein the computed delay associated with the delayed acknowledgment packet provides feedback to the first transmission station such that when the first transmission station transmits subsequent packets corresponding to the flow, such subsequent packets are transmitted at a rate approximating a target rate;

receiving a second data flow from the first transmission station, wherein the data flow comprises at least one packet;

storing the data flow in a memory;

if the second data flow is a retransmission of the first data flow, determining whether an acknowledgement packet corresponding to the first data flow is in the memory; and

if so, deleting the second data flow from the memory; otherwise, forwarding the second data flow to the second transmission station.

22. The method of claim 21 further comprising classifying the first data flow into one of a plurality of classes to determine the target rate for the first data flow.

23. A method for controlling the rate of data packets transmitted between first and second nodes in a packet communication environment, wherein the first node is operative to transmit at least one packet associated with a flow to the second node, and wait for acknowledgment of at least one transmitted packet before transmitting subsequent packets associated with the flow, said method comprising:

forwarding at least one packet corresponding to a flow from a first node to a second node;

receiving an acknowledgment packet from the second node to the first node, the acknowledgment packet acknowledging at least one packet in the flow transmitted from the first node, wherein the acknowledgment packet received from the second node includes a window size indicator that specifies an allowable range of transmission of data beyond a range of data acknowledged as a window size to be advertised from said second node to said first node;

selecting a substitute window size indicator for said window size indicator to modify the rate of transmission of packets from the first node;

inserting said substitute window size indicator into said acknowledgment packet; and

forwarding the acknowledgment packet to the first node.

24. The method of claim 23 wherein the substitute window size indicator is computed based on a target rate for the flow.

25. The method of claim 23 wherein the first and second nodes implement the TCP protocol and wherein the flow is a TCP flow.

26. The method of claim 23 further comprising

computing a delay for transmission of the acknowledgment packet to control the rate of transmission of packets from the first node; and

delaying the forwarding step by the computed delay.

27. The method of claim 23 wherein the substitute window size indicator is computed based on a metric characterizing an attribute of the communications path between the first and second node.

28. The method of claim 27 wherein the metric is a measured data rate between the first node and the second node.

29. The method of claim 27 wherein the metric is a round trip time between the first node and the second node.

30. A method for controlling the rate of data packets transmitted between first and second nodes in a packet communication environment, wherein the first node is operative to transmit at least one packet associated with a flow to the second node, and wait for acknowledgment of at least one transmitted packet before transmitting subsequent packets associated with the flow, said method comprising:

forwarding packets corresponding to a flow from a first node to a second node;

receiving acknowledgment packets from the second node to the first node, the acknowledgment packets acknowledging at least one packet in the flow transmitted from the first node, wherein the acknowledgment packets received from the second node includes a window size indicator that specifies an allowable range of transmission of data beyond a range of data acknowledged as a window size to be advertised from said second node to said first node;

computing, for at least one acknowledgement packet, a substitute window size indicator for said window size indicator to control the rate of transmission of packets from the first node;

inserting said substitute window size indicator into said acknowledgment packet; and

forwarding the acknowledgment packet, modified in the inserting step, to the first node.

31. In a network device disposed in a communications path between at least a first and second node, a method for controlling the rate of data packets transmitted between first and second nodes in a packet communication environment employing the TCP/IP protocol, wherein the nodes in the packet communications environment are operative to transmit at least one packet associated with a flow to the second node, and wait for acknowledgment of at least one transmitted packet before transmitting subsequent packets associated with the flow, said method comprising:

receiving, at the network device, a TCP packet associated with a flow from a first node, wherein the TCP packet includes a window size indicator that specifies an allowable range of transmission of data beyond a range of data acknowledged as a window size to be advertised from said first node to said second node;

selecting a substitute window size indicator for said window size indicator to control the rate of transmission of packets from the second node;

inserting said substitute window size indicator into said TCP packet; and

transmitting the TCP packet to the second node.

32. The method of claim 31 wherein the substitute window size indicator is computed based on a target rate for the flow.

33. The method of claim 32 wherein the substitute window size indicator is computed based on a metric characterizing an attribute of the communications path between the first and second node.

34. The method of claim 33 wherein the metric is a measured data rate between the first node and the second node.

35. The method of claim 33 wherein the metric is a round trip time between the first node and the second node.

Assignments (13)