Congestion management

Details Congestion management Congestion management

1999-10-26

2003-12-09

Ton, Dang (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S229000

Reexamination Certificate

active

06661802

ABSTRACT:

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
N/A
BACKGROUND OF THE INVENTION
The present invention relates generally to communication systems, and more specifically to a system and method for providing congestion management while supporting quality of service levels for multiple connections.
In existing network devices, such as network switches, received data units, such as Asynchronous Transfer Mode (ATM) cells and/or frame relay frames, arrive and are stored in one or more receive buffers. Rate policing of some form may then be performed, and the receive buffers storing the data units may be enqueued to a receive queue. Subsequently, the data units are typically dequeued and transmitted from the device at an output port of the device.
As it is generally known, when a data unit is received at a network device, it must contend for resources needed to process the data unit, including bandwidth on the output link on which it is to be transmitted. Accordingly, when enough received data units contend for a single output link, the queue on which they are stored may overflow, causing one or more arriving data units to be dropped. At such a point, the network device is said to be “congested”. Many existing network devices provide a mechanism to deal with such situations as they occur. These mechanisms are commonly referred to as “congestion control” mechanisms. In addition, end nodes in some networks sometimes take a proactive role in allocating resources on an end to end basis, in an attempt to prevent congestion from happening at intermediate network devices. Such techniques are referred to as “congestion avoidance” mechanisms.
Contemporary network protocols, such as Asynchronous Transfer Mode (ATM), enable a virtual connection to be associated with a Quality of Service (QoS) that defines the loss and/or delay sensitivity of traffic on that connection. In addition, data units using the frame relay frame formats permit a data unit originator to specify a value of a “Discard Enabled” (DE) bit in the data unit. When the DE bit is set, a network device receiving the data unit is permitted to discard the frame in order to control or avoid congestion. Virtual connections may further be allocated some amount of guaranteed bandwidth, sometimes referred to as the Committed Information Rate (CIR) of the connection. Bandwidth defined in addition to the CIR of a connection is referred to as the Excess Information Rate (EIR) of the connection. Data units associated with the EIR of a connection are processed using available resources, and may be discarded in the event that no resources are available to process them.
It would be desirable to have a system for managing congestion in a network device which also contributes to providing better Quality of Service (QoS) for received data units which do not contain a discard enabling indicator, such as a set DE bit in a frame relay frame. Additionally, it would be desirable for the system to provide control over the delay experienced by a frame in a receive queue in a network device under congestion conditions, in order to support defined QoS delay levels. Generally, the system should operate in such a way that data units received on connections associated with higher QoS assurances are provided resources before data units received on connections associated with relatively lower QoS assurances.
BRIEF SUMMARY OF THE INVENTION
In accordance with the invention, there is disclosed a system and method for congestion management including one or more receive queues organized into a queue list, in which each queue is associated with a high water mark and a low water mark. The high water mark indicates a length at which the queue is considered congested. The low water mark is a length at which a congested queue is considered no longer congested. When the size of a queue reaches or exceeds its high water mark, data unit enqueuing with regard to that queue is performed in a more restrictive manner. For example, newly arriving frames destined for that queue which are eligible for discard based on an asserted DE bit may be dropped. However, frames arriving without an asserted DE bit are still enqueued at the tail of the queue.
The queues in the queue list are organized by relative priority, such that the queue list may be traversed in order of descending priority, from the highest priority queue to the lowest priority queue. When a single queue above a predetermined priority is determined to be congested, all queues in the queue list are treated as congested. Congestion in lower priority queues results in only the individual congested queue being treated as congested.
Additionally, a maximum allowed queue length is associated with each queue in the queue list, in order to control the delay experienced by data units stored in the queue. When the size of a queue reaches its maximum length, a data unit dropping mechanism is triggered. The data unit dropping mechanism drops newly arriving data units that are eligible for discard, for example because they contain an asserted DE bit. However, an arriving data unit that is not eligible for discard is enqueued at the tail of the queue, and one or more data units at the head of the queue are dropped to provide sufficient room in the queue for the newly arrived data unit.
In this way, a system for managing congestion in a network device is disclosed which also contributes to providing better Quality of Service (QoS) for received data units which do not contain a discard enabling indicator. The disclosed system further provides control over the delay experienced by a frame in a receive queue in a network device under congestion conditions, in order to support defined QoS delay levels. The disclosed system advantageously operates such that data units received on connections associated with higher QoS assurances are provided resources before data units received on connections associated with relatively lower QoS assurances.


REFERENCES:
patent: 5218456 (1993-06-01), Stegbauer et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5315591 (1994-05-01), Brent et al.
patent: 5408472 (1995-04-01), Hluchyj et al.
patent: 5425029 (1995-06-01), Hluchyj et al.
patent: 5461611 (1995-10-01), Drake, Jr. et al.
patent: 5485455 (1996-01-01), Dobbins et al.
patent: 5490141 (1996-02-01), Lai et al.
patent: 5497375 (1996-03-01), Hluchyj et al.
patent: 5524006 (1996-06-01), Hluchyj et al.
patent: 5541913 (1996-07-01), Witters et al.
patent: 5553073 (1996-09-01), Barraclough et al.
patent: 5666353 (1997-09-01), Klausmeier et al.
patent: 5689500 (1997-11-01), Chiussi et al.
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5771234 (1998-06-01), Wu et al.
patent: 5781801 (1998-07-01), Flanagan et al.
patent: 5802278 (1998-09-01), Isfeld et al.
patent: 5812774 (1998-09-01), Kempf et al.
patent: 5828653 (1998-10-01), Goss
patent: 5852601 (1998-12-01), Newman et al.
patent: 5872769 (1999-02-01), Caldara et al.
patent: 5901147 (1999-05-01), Joffe

Affiliated with

Also associated with

Rating

Congestion management 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Congestion management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3184492