Method for regulating TCP flow over heterogeneous networks

• US 6,252,851 B1
• Filed: 03/27/1998
• Issued: 06/26/2001
• Est. Priority Date: 03/27/1997
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Narvaez, Paolo L., Siu, Kai-Yeung S.
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US09/049,814
• Time in Patent Office: 1,187 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/252, 370/253, 370/249, 370/395, 370/400, 370/412, 370/428, 370/429, 370/414, 370/413
• US Class Current: 370/236
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/323 Discarding or blocking control packets, e.g. ACK packets
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

A method for regulating flow through a network node where forwarding of successive data packets from sources is dependent on receipt of acknowledgments from the destinations, the packets are buffered in a packet buffer as they arrive from their sources. Acknowledgments are withheld in an acknowledgment bucket, and are released such that successive data packets are buffered in the sources to avoid overflow of the packet buffer due to bandwidth limitations toward the destinations. The destination is typically in a bandwidth constrained network (BCN) while the source is in a local area network (LAN) using transmission control protocol (TCP). In a preferred embodiment the BCN operates in asynchronous transfer mode (ATM), and a transmission rate of the BCN is returned upon request. TCP source states are maintained by observing TCP traffic through the node. The behavior of TCP sources is predicted from traffic observations. Then, the known transmission rate of the BCN is translated to a timed sequence of acknowledgments releases based on the predicted behavior. Alternatively, an estimate is maintained of effective queue size, which includes data buffered in the packet buffer, and residual data packets, i.e., those data packets that have been requested but have not yet been received at the node. An acknowledgment is released if the effective queue size is less than a threshold, which may be dynamic.

Claims

1. A method for regulating flow through a network node in a system adhering to a protocol in which data packets are forwarded from sources to destinations and forwarding of successive data packets from the sources is dependent on receipt of acknowledgments from the destinations, said method comprising the steps of:

receiving data packets from sources, buffering the packets in a packet buffer and forwarding the packets toward destinations;

withholding acknowledgments arriving from the destinations to inhibit the transmission of further packets from the sources; and

releasing the acknowledgments to the sources to allow the transmission of further packets from the sources such that data packets are buffered in the sources to avoid overflow of the packet buffer due to bandwidth limitations toward the destinations.

2. The method of claim 1 wherein the network node is connected between a bandwidth constrained network (BCN) having destinations and a local area network (LAN) having sources.

3. The method of claim 2 wherein the protocol is transmission control protocol (TCP).

4. The method of claim 2 wherein the BCN operates in asynchronous transfer mode (ATM).

5. The method of claim 4 wherein a transmission rate of the BCN is returned upon request.

6. The method of claim 5, further comprising:

maintaining TCP source states by observing TCP traffic through the node;

predicting behavior of TCP sources based on traffic observations; and

translating a known transmission rate of the BCN to a timed sequence of acknowledgments releases based on the predicted behavior.

7. A method claim 2, further comprising:

maintaining an estimate of effective queue size including data buffered between the BCN and LAN and residual data packets where the residual data packets are those data packets that have been requested but have not yet been received at the node;

releasing an acknowledgment if the effective queue size is less than a threshold.

8. A method as claimed in claim 7, wherein TCP versions of sources are known, further comprising:

maintaining TCP source states by observing TCP traffic through the node to keep account of an amount of data requested through acknowledgment releases;

calculating the residual queue size at time t as the amount of data requested up to time t, less an amount of data received from the source by time t; and

calculating the estimate of effective queue size at time t by adding a value based on the actual queue size at time t, to the residual queue size at time t.

9. A method as claimed in claim 7, further comprising:

calculating an estimate of residual queue size at time t by counting acknowledgments released during an interval from (t−

τ

_max) to t, where τ

_max is a maximum round trip delay in the LAN; and

calculating the estimate of effective queue size at time t by adding a value based on the actual queue size at time t, to the estimate of residual queue size at time t.

10. A method as claimed in claim 7, further comprising:

calculating an estimate of residual queue size at time t by counting acknowledgments released during N consecutive intervals of duration τ

_max/N ending at time t for some integer N, and maintaining each of said counts for a duration of τ

_max, where τ

_max is a maximum of round trip delay in the LAN; and

calculating the estimate of effective queue size at time t by adding a value based on the actual queue size at time t, to the estimate of residual queue size at time t.

11. A method as claimed in claim 7, further comprising:

initializing an estimate of residual queue size;

incrementing by one the estimate of residual queue size when an acknowledgment is released;

decrementing by one the estimate of residual queue size when a packet arrives; and

calculating the estimate of effective queue size at time t by adding a value based on the actual queue size at time t, to the estimate of residual queue size at time t.

12. A method as claimed in claim 11, wherein the estimate of residual queue size is not decremented if its value is 0.

13. A method as claimed in claim 7, wherein the threshold changes dynamically and is dependent on the available bandwidth of the BCN.

14. A method as claimed in claim 7 wherein the regulated traffic is aggregated from a plurality of TCP connections, wherein the actual queue size is a count of all packets in a FIFO queue, residual queue size is a count of all packets which have been requested from all sources and which have not yet arrived at the FIFO queue, effective queue size is the sum of the actual queue size and residual queue size, and wherein fairness is ensured among the different connections.

15. A method as claimed in claim 14 wherein the acknowledgments for each TCP connection are kept in separate buckets and are released in a round-robin fashion.

16. The method of claim 1 wherein withholding acknowledgments further comprises storing acknowledgment numbers in an acknowledgment bucket.

17. The method of claim 16 wherein only highest sequence numbers and sequence numbers of last acknowledgments released are stored.

18. A system for regulating flow in a network edge between networks in a system adhering to a protocol in which data packets are forwarded from sources to destinations and forwarding of successive data packets from the sources is dependent on receipt of acknowledgments from the destinations, comprising:

a packet buffer in which data packets received from the sources are stored, and from which the packets are forwarded toward the destinations; and

an acknowledgment bucket in which acknowledgments arriving from the destinations are stored, such that the acknowledgments are withheld from the sources to inhibit the transmission of further packets from the sources and are subsequently released to the sources to allow the transmission of further packets from the sources such that data packets are buffered in the sources to avoid overflow of the packet buffer due to bandwidth limitations toward the destinations.

19. The system of claim 18 wherein the network edge connects a bandwidth constrained network (BCN) having destinations to a local area network (LAN) having sources.

20. The system of claim 19 wherein the protocol is transmission control protocol (TCP).

21. The system of claim 19 wherein the BCN operates in asynchronous transfer mode (ATM).

22. The system of claim 21 wherein a transmission rate of the BCN is returned upon request.

23. The system of claim 22, further comprising:

an observer which maintains TCP source states by observing TCP traffic through the network edge, such that behavior of the TCP sources is predicted based on traffic observations; and

a translator which translates a known transmission rate of the BCN to a timed sequence of acknowledgments releases based on the predicted behavior.

24. The system of claim 19, wherein:

an estimate is maintained of effective queue size including data buffered between the BCN and LAN and residual data packets where the residual data packets are those data packets that have been requested but have not yet been received at the network edge, such that an acknowledgment is released from the acknowledgment bucket if the effective queue size is less than a threshold.

25. The system of claim 24 wherein the regulated traffic is aggregated from a plurality of TCP connections, wherein the actual queue size is a count of all packets in a FIFO queue, residual queue size is a count of all packets which have been requested from all sources and which have not yet arrived at the FIFO queue, effective queue size is the sum of the actual queue size and residual queue size, and wherein fairness is ensured among the different connections.

26. The system of claim 25 further comprising:

a plurality of acknowledgment buckets corresponding to the TCP connections such that the acknowledgments for each TCP connection are kept in separate buckets and are released in a round-robin fashion.

27. The system of claim 18 wherein acknowledgments are stored in the acknowledgment bucket by storing sequence numbers associated with the acknowledgments.

28. The system of claim 27 wherein only highest sequence numbers and sequence numbers of last acknowledgments released are stored.