Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-03-27
2001-06-26
Ngo, Ricky (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395430, C370S414000, C370S428000
Reexamination Certificate
active
06252851
ABSTRACT:
BACKGROUND OF THE INVENTION
Most Internet data applications today use transmission control protocol (TCP) as the transport layer protocol. Since the Internet is becoming increasingly heterogeneous, most TCP traffic traverses a wide range of networks with different bandwidth characteristics. TCP traffic is typically generated from a source connected to a local area network (LAN) e.g. Ethernet, and is aggregated through an Internet protocol (IP) edge router to an access network that uses a different link layer technology such as Asynchronous Transfer Mode (ATM). Congestion at the edge router occurs when the bandwidth available in the access network cannot support the aggregated traffic generated from the LAN.
TCP is a connection-oriented transport protocol which is designed to work with any underlying network technology. TCP makes no assumption as to how the network processes the data it sends, and perform its own data recovery and flow control.
TCP packets can contain thousands of bytes, while ATM transmits cells of 53 bytes, of which only 48 contain data. Thus, TCP packets must be broken up at the network edge into tens or hundreds of cells in order to be transmitted over an ATM network. If any one of these cells is dropped for any reason, congestion in the network being one of the main causes, the entire packet is lost, even though all of the remaining cells may arrive at the destination intact. Valuable bandwidth is therefore wasted transporting these cells once one has been dropped. Compounding this problem, the entire packet must be re-transmitted, consuming even more bandwidth.
The TCP acknowledgment-based flow control mechanism is designed to slow down the source rate when the network becomes congested. TCP has no direct way of knowing when the network is congested. It can only indirectly detect congestion by keeping track of how many packets are lost. Packet loss is indicated by a failure to receive the appropriate acknowledgments, depending on the TCP version. When packets do get lost, the loss indicates that some queue in the network might have experienced overflow. Every time TCP detects a packet loss, it reduces its source rate to alleviate the congestion that could have caused the packet loss.
TCP's congestion control and error recovery, based on acknowledgments, are implemented by a dynamic window at the source. Every packet that is sent must be acknowledged by the destination. A congestion window size determines the number of unacknowledged packets that can be present in the network at any given time, and is initially set to one. Each packet includes a sequence number, so that packets arriving at the destination out of order can be reordered. A destination responds to an incoming packet by sending an acknowledgment back to the source. If a sequence number is skipped, the destination continues to return the same sequence number, resulting in duplicate acknowledgments.
In general, when a packet is acknowledged, the congestion window size increases, and when a packet is lost, the window size decreases, forcing the rate to decrease. Specifically, during the “slow-start” phase, the window is incremented by one for each acknowledgment received, so that during this phase, two packets are transmitted for each acknowledgment received, resulting in an exponential increase in the packet transmission rate.
After the window reaches some threshold, the “congestion-avoidance” phase is entered, in which the window is incremented by one for every w acknowledgments received, where w is the window size. Thus, in this phase, usually one packet is transmitted for each acknowledgment received, but occasionally (when w is incremented), two packets will be transmitted.
Finally, when a maximum limit is reached, the window size does not change, and one packet is released for every acknowledgment received. This is the “saturation” phase.
When a packet is lost, the congestion-avoidance threshold is set to one half the window size, and the window is reduced to one.
The available bit rate (ABR) service provided by ATM has been developed with the goal of minimizing switch buffer requirement and cell loss in transporting data and allowing users to have fair access to the available bandwidth in ATM networks. To achieve such service requirements, the ABR service uses congestion control at the ATM layer. Network switches must constantly monitor the traffic load and feed the information back to the sources. The sources are expected to adjust their input to the network dynamically, based on the congestion status of the network.
However, while ABR assumes that the end systems comply with the ABR source behavior, most current applications are only connected to ATM via legacy networks such as Ethernet and employ TCP which provides flow control at the transport layer.
While TCP handles network congestion and resulting packet loss quite effectively with its end-to-end window flow control mechanism, its throughput could be improved if intermediate routers of the access network could detect incipient congestion and explicitly inform the TCP source to throttle its data rate before any packet loss occurs. Such throughput improvement is particularly significant in a high latency access network environment such as an ATM-based network. However, while the ATM access network may have its own traffic control mechanism, its effect terminates at edge routers, e.g., at the interface between two networks, and consequently, the end-to-end performance is not improved. In fact, when different flow control mechanisms are employed simultaneously, in some cases TCP throughput can actually be reduced.
When transmitting TCP traffic over a network service such as ATM ABR, TCP's own flow control mechanism does not have direct knowledge of the network's flow control dynamics. Though an effective ABR rate control mechanism can determine the desired source rate into the ATM network, a TCP source not directly connected to an ATM network will send data at different rates according to its own dynamics. Thus, even if ABR's flow control can relieve congestion inside an ATM network, congestion can still occur at the network edges when TCP sources are sending data at a faster rate than the available bandwidth in the ATM network, requiring very large buffers at the network edges to avoid packet loss.
SUMMARY OF THE INVENTION
The present invention is a new efficient method for regulating TCP traffic over ATM and other networks with the objective of maximizing TCP throughput while minimizing the network-interface buffer requirement.
Accordingly, in 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. From the packet buffer, they are later forwarded to their destinations. Acknowledgments arriving from the destinations are withheld in an acknowledgment bucket, and are released to the sources such that the sources respond by transmitting new packets at a rate which avoids overflow of the buffer. As a result, successive data packets are effectively buffered in the sources to avoid overflow of the packet buffer due to bandwidth limitations toward the destinations.
In a preferred embodiment, the destination is in a bandwidth constrained network (BCN) while the source is in a local area network (LAN), preferably 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. The known transmission rate of the BCN is then translated to a timed sequence of acknowledgment releases based on the predicted behavior.
In particular, the TCP source rate is matched to the ATM ABR explicit rate by controlling the flow of TCP acknowledgments at network interfaces. This embodiment h
Narvaez Paolo L.
Siu Kai-Yeung S.
Hamilton Brook Smith & Reynolds P.C.
Massachusetts Institute of Technology
Ngo Ricky
LandOfFree
Method for regulating TCP flow over heterogeneous networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for regulating TCP flow over heterogeneous networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for regulating TCP flow over heterogeneous networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2540417