Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-04-10
2003-12-02
Pham, Chi (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
Reexamination Certificate
active
06657962
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer networks and more particularly to a method and system for managing congestion in a processing system.
BACKGROUND OF THE INVENTION
In communications systems, it is common to reserve bandwidth for high priority traffic that is then transmitted in preference to lower priority traffic. Such lower priority traffic therefore must be managed to take advantage of the bandwidth remaining after higher priority traffic that is conformant to a contract has been served. This remaining bandwidth can vary widely depending on the activity of the high priority traffic. It is therefore of considerable importance to manage the low priority traffic so as to optimize the use of the widely varying available bandwidth in the network, and, at the same time, avoid congestion in the network which reduces network throughput.
It has become common to utilize window-based flow control mechanisms to avoid congestion in a TCP/IP packet communications network. Such window-based mechanisms pre-allocate receiver buffer credits to sources and notify the corresponding sender how much data can be sent. Upon detection of congestion, either at an egress port (if the receiver is an intermediate node) or within a node, the receiver withholds buffer credits, forcing the sending partner to slow down the launching of packets or to stop transmission altogether. This process, also known as “back pressure” congestion control, is repeated hop by hop, eventually reaching the sources of traffic causing the congestion and forcing those sources to slow down.
Such window-based, backpressure mechanisms perform efficiently with low speed networks with reasonably high bit error rates. As networks move toward higher transmission speeds and more reliable transmission media such as optical fibers, the window-based mechanisms no longer perform adequately. The cost of such hop-by-hop mechanisms becomes prohibitively expensive and inefficient due to the fact that a sender can send an entire window's worth of data and be required to wait for the receipt of new buffer credits from the receiver before continuing. The resulting silent period is at least as long as two propagation delays and results in a direct loss of throughput during this silent interval. Furthermore, the window-based flow control does not smooth the transmission of data into the network and hence causes large oscillations in loading due to the clustering of packets, further degrading network performance. Using larger windows merely worsens the silent period throughput degradation.
In order to better accommodate modern high-speed and reliable packet communications networks, it has been proposed to use an end-to-end congestion control mechanism which relies on the regular transmission of sample packets having time stamps included therein. One such mechanism is disclosed in, “Adaptive Admission Congestion Control,” by Z. Haas, ACM SIG-COMM Computer Communications Review, Vol. 21(5), pages 58-76, October 1991. In the Haas article, successive time-stamped sample packets are used to calculate changes in network delays that are averaged to: represent the state of the network. The averaged network delay is then used to control the admission of packets to the network by controlling the admission of packets to the network. That is, the admission rate becomes a function of congestion measurements, either by controlling the inter-packet gap directly, or by adjusting the token rate in a standard leaky bucket scheme at the admission point.
One disadvantage of the Haas end-to-end congestion control mechanism is that Haas sends sampling packets at regular intervals regardless of the traffic load from a sender. Sending such sampling packets when the sender is idle is wasted effort and reduces the good throughput of the system. Furthermore, Haas must await the arrival of a plurality of sampling packets before initiating congestion control, thus providing too slow a response time to permit flow control as well as congestion control.
Another disadvantage of the Haas scheme is the so-called “accumulation effect”. If the length of queues along the congestion path is built up gradually by small amounts, the overall delay can exceed the threshold allowed for the overall connection without being detected by the Haas endpoint detection scheme. The network can therefore become congested without timely correction when using the Haas congestion control scheme.
Yet another disadvantage of the Haas congestion control scheme is the fact that the inter-packet control gap is used to control the input packet rate. Sources of short packets are therefore penalized unfairly compared to sources of long packets when the inter-packet gap control technique of Haas is used to control congestion. Finally, and most importantly, the Haas congestion control scheme requires relatively frequent transmission of sampling packets to provide timely control information. Indeed, the overhead for such sampling packets can reach up to twenty percent of the entire throughput of the network, making the Haas congestion control scheme provide a lower throughput than an uncontrolled network when the traffic load is less than eighty percent. If the transmission rate of Haas' sampling packets were to be reduced to approximate the round trip delay period, on the other hand, the scheme simply would not work at all due to the paucity of control information available at the sender. That is, the averaging step used to reduce the noise in the control signal would make the scheme so unresponsive to the congestion to be controlled that the low sampling rate would be unable to control the congestion.
U.S. Pat. No. 5,367,523 issued to Chong, et al; to the assignee of the present application addresses some of the problems associated with Haas. This patent discloses an end-to-end, closed loop flow and congestion control system for packet communications networks. It exchanges rate request and rate response messages between data senders and receivers to allow the'sender to adjust the data rate to avoid congestion and to control the data flow. Requests and responses are piggybacked on data packets and result in changes in the input data rate to optimize data throughput. GREEN, YELLOW and RED operating modes are defined to increase data input, reduce data input and reduce data input drastically, respectively. Incremental changes in data input are altered non-linearly to change more quickly when further away from the optimum operating point that when closer to the optimum operating point.
Although this system operates effectively for its stated purpose, it allows neither for prioritizing of packets nor for viewing congestion at various levels of granularity. Accordingly, what is needed is a system and method that control congestion in a network in a manner that enables a response to congestion in each part of the system both locally and in the context of the overall system performance. The method and system should be easily implemented in existing networks and should be cost effective. The present invention addresses such a need.
SUMMARY OF THE INVENTION
A system for minimizing congestion in a communication system is disclosed. The system comprises at least one ingress system for providing data. The ingress system includes a first free queue and a first flow queue. The system also includes a first congestion adjustment module for receiving congestion indications from the free queue and the flow queue. The first congestion adjustment module generates and stores transmit probabilities and performs per packet flow control actions. The system further includes a switch fabric for receiving data from the ingress system and for providing a congestion indication to the ingress system. The system further includes at least one egress system for receiving the data from the switch fabric. The egress system includes a second free queue and a second flow queue. The system also includes a second congestion adjustment module for receiving congestion indications from the second free. queue
Barri Peter Irma August
Bass Brian Mitchell
Calvignac Jean Louis
Clemminck Ivan Oscar
Heddes Marco C.
Ly Anh-Vu
Pham Chi
Sawyer Law Group
LandOfFree
Method and system for managing congestion in a network 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 and system for managing congestion in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for managing congestion in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3112701