Congestion management system and method

Details Congestion management system and method Congestion management system and method

2000-01-06

2004-01-13

Ho, Duc (Department: 2665)

Multiplex communications

Data flow congestion prevention or control

C370S400000, C370S408000, C370S412000

Reexamination Certificate

active

06678244

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates generally to congestion management in computer networks, and more particularly, to a congestion management system which utilizes downstream congestion notification.
A network is generally a data communication system which links two or more computers and peripheral devices to allow a user on a computer to access resources and exchange messages with users on other computers. Internetworking is the process of establishing and maintaining communications between and transferring data among multiple local networks in a distributed network system. The network allows users to share resources on their own systems with other network users and to access information on centrally located systems or on systems which are located at remote offices.
Networks transfer vast quantities of information in both local and wide area networks. Networks comprised of high performance switching elements are important for the high-speed transport of information which may include text, voice, and video information. For example, the information may consist of signals (electronic or optical) representing digitized or digital voice, video, or data that is transferred between endpoints in the network. In order for information to be transmitted in the network, a communication path must be established within the network between a sender and a receiver of the information. The communication path may be established by packet switching, for example.
Once connections are established, the connections must be regulated to prevent congestion in the network. When too many packets are present within a portion of the network, performance degrades due to congestion. As traffic increases above the load capacity of the network, routers and system modules are no longer able to support the traffic and they begin to queue and then lose packets. A quality of service (QOS) of a connection is provided by the network if the connection stays within specified traffic parameters such as the rate at which data bits are transmitted through the network and the variations in bit rate. Different classes of traffic may require different levels of QOS and have different traffic parameters.
Congestion may be brought about by several factors. If streams of packets suddenly begin arriving on three or four input lines and all need the same output line, a queue will build up. If there is insufficient memory to hold all of the packets, some packets will be lost. Adding more memory may help up to a point, but if routers have a large amount of memory, congestion may get worse, because by the time packets get to the front of the queue, they have already timed out and duplicate packets have been sent. Slow processors may also cause congestion. If the routers' Central Processing Units (CPUs) are slow at performing tasks (e.g., queuing buffers, updating tables), packets may build up within a queue, even though there is excess line capacity. Similarly, low-bandwidth lines can also cause congestion. Various measurements may be used to monitor network congestion such as the percentage of all packets discarded for lack of buffer space, average queue length, number of packets that time out and are retransmitted, average packet delay, and the standard deviation of packet delay, for example. Another approach is to have hosts or routers send probe packets out periodically to explicitly ask about congestion.
FIG. 1
illustrates a prior art method for identifying congestion within a communication path located in a network element. A number of software and hardware modules M are located within the communication path between a sender and a receiver. Packets D
1
, D
2
, D
3
, D
4
have been sent in a stream along the communication path and are located at various positions along the path as indicated in a phantom box shown below the modules M in FIG.
1
. One or more of the modules M may receive packets faster than it can dispose of them. As a result, the packets build up in a local buffered memory associated with the module, causing an overflow situation. When a module begins to receive packets faster than it can transmit the packets, it notifies the sender that the path is congested. The sender will hold the packets until the path is clear. As shown in
FIG. 1
, packets D
1
, D
2
, D
3
, D
4
are held within the communication path which forms a distributed first in first out (FIFO) queue due to the delay in congestion notification. When the congestion is cleared, the packets D
1
, D
2
, D
3
, D
4
held within the queue are sent along the path. One problem with this arrangement is that a high priority packet D
0
(e.g., voice over IP packet) contained within the sender's queue cannot be immediately sent through the communication path. Instead, it must wait until the other packets within the queue (D
1
, D
2
, D
3
, D
4
) are transmitted to the receiver. Furthermore, the sender cannot reorder packets within its queue to transmit a high priority packet since it does not know which packet will have the highest priority when the path is finally cleared and D
0
is received at the receiver.
There is, therefore, a need for a congestion management system that provides up to date congestion notification of all downstream modules to a queuing element within the communication path to prevent a buildup of packets within the path and allows for transmittal of high priority packets directly through the communication path once the path is cleared.
SUMMARY OF THE INVENTION
A congestion management system and method are disclosed. A method of the present invention is for monitoring congestion on a data path. The data path includes a queuing node located therein and a plurality of downstream nodes positioned downstream of the queuing node. The method generally includes monitoring congestion at the plurality of downstream nodes and setting a bit within a congestion notification flag by one of the downstream nodes when the node is congested. The transmission of data packets from the queuing node is then stopped and packets received at the queuing node are queued. Packets are transmitted from the queuing node when the congestion notification flag is cleared.
In another aspect of the invention, a system for managing congestion on a data path having a plurality of modules positioned therein generally comprises a queuing node positioned within the data path upstream of the modules and a downstream congestion notification device operable to receive input from the modules indicative of their congestion state and flag the queuing node when one of the modules is congested. The queuing node is operable to determine the state of the downstream congestion notification device prior to transmitting a packet and stop the transmission of packets therefrom and queue new packets received when the downstream congestion notification device indicates that one of the modules is congested.
A computer program product for monitoring congestion with the data communication path generally includes computer code that monitors congestion at the downstream nodes, computer code that sets a congestion notification flag when one of the downstream nodes is congested, and computer code that stops the transmission of data packets from the queuing node and queues packets received at the queuing node when the congestion notification flag is set. The product further includes computer code that transmits packets from the queuing node when the congestion notification flag is cleared and a computer readable medium that stores the computer codes.


REFERENCES:
patent: 5115429 (1992-05-01), Hluchyj et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5406556 (1995-04-01), Widjaja et al.
patent: 5426640 (1995-06-01), Hluchyj et al.
patent: 5638359 (1997-06-01), Peltola et al.
patent: 5822300 (1998-10-01), Johnson et al.
patent: 6463035 (2002-10-01), Moore

Affiliated with

Also associated with

Rating

Congestion management system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Congestion management system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Congestion management system and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3223821