Network to network priority frame dequeuing

Details Network to network priority frame dequeuing Network to network priority frame dequeuing

1999-10-26

2001-07-03

Olms, Douglas (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000

Reexamination Certificate

active

06256315

ABSTRACT:

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
N/A
BACKGROUND OF THE INVENTION
The invention relates generally to queuing of received data units in networking devices, and more specifically to a system for temporarily storing and dequeuing received data units for subsequent transmission based on their relative priorities and the availability of transmit credits.
A network switch is one example of the many types of networking devices used to interconnect computer and/or communications networks (“networks”). These devices receive and forward data units such as cells, packets, messages or frames from other devices located within one or more networks to which they are connected. For example, a network switch may be used to forward data units between networks employing a variety of communications protocols, such as Asynchronous Transfer Mode (ATM) or Frame Relay. Such devices typically include some amount of buffer memory to store data units as they are received, together with some combination of hardware circuits and/or software-implemented functionality.
During operation of a network switch, conditions may arise which require it to store received data units for some period of time before they can be transmitted from the device. For example, one or more output links of the device may become congested due to a lack of available transmission bandwidth. In such situations, the stored data units should be organized and forwarded to their respective output links in such a way that their relative priorities are maintained. For example, the priority of a data unit associated with a virtual connection may be indicated by a specific Quality of Service (QoS) indicating levels of delay and loss sensitivity associated with the connection. QoS parameters for a connection may include a guaranteed level of bandwidth, sometimes referred to as a Committed Information Rate (CIR), and an available bandwidth level, sometimes referred to as an Excess Information Rate (EIR). A data unit associated with the CIR of a connection is considered to have priority over a data unit associated with the EIR of that connection or another connection. This relative priority between received data units should be maintained in the way data units are temporarily stored in a device as a result of output link congestion, and in any protocol used to forward such stored data units for subsequent transmission.
The originator of a frame in a frame relay network may expressly indicate a frame's priority by selecting a value of a “discard enabled” (DE) bit contained in the frame. Network switches receiving a frame with the DE bit set are permitted to discard the frame in the face of congestion at an outbound link. Accordingly, a frame with the DE bit set may have a lower priority with respect to other frames with the DE bit clear. This type of relative priority between received data units should also be maintained in the way they are temporarily stored in a network switch as a result of output link congestion, and in any protocol used to subsequently forward such data units for transmission.
Virtual connections passing through a network switch typically employ a flow control protocol, which controls when data units buffered at each node traversed by the virtual connection may be forwarded downstream. An example of a credit based flow control protocol providing QoS guarantees in an ATM environment is described in
Quantum Flow Control,
Version 2.0, published Jul. 25, 1995, available on the World Wide Web at http://www.qfc.org. The Quantum Flow Control (QFC) protocol requires a transmitting device to have received sufficient transmit credits from the next downstream node to transmit a complete frame before it can begin transmitting the frame to the downstream node. As frames are transmitted, the transmitting device logically decrements a transmit credit count. As the downstream node frees up buffers which can be used to receive more frames, it sends transmit credits upstream to the transmitter. By requiring a transmitter to accumulate sufficient credits to transmit a complete frame before it can begin transmitting that frame, QFC ensures that downstream buffers are available to store the frame. However, this requirement may also introduce undesirable or unacceptable delay to a frame.
For the reasons stated above it would be desirable to have a system for temporarily storing data units in a network device which maintains the relative priorities of the data units, for example as determined by their QoS levels and/or DE bit values. Such relative priorities should be maintained both in the manner in which the data units are stored, as well as in the manner in which they are forwarded to their respective output links. In addition, the system should provide flow control in a way that is consistent with the relative priorities of received data units.
BRIEF SUMMARY OF THE INVENTION
In accordance with the invention, a system for storing a received data unit is disclosed which maintains the relative priority of the data unit with respect to other received data units, in terms of any QoS associated with the data unit, any DE bit value included in the data unit, and/or other types of priority with which the data unit may be associated. The disclosed system further maintains relative priorities between received data units as they are dequeued and forwarded to their respective output links.
During operation of the disclosed system, a determination is made as to whether a data unit is part of either a guaranteed bandwidth or an available bandwidth associated with a virtual connection on which the data unit was received. A data unit is considered to be part of the guaranteed bandwidth for a connection on which it is received if the total amount of data received on that connection, including the data unit, over a predetermined time period, is less than or equal to a predetermined value reflecting the negotiated guaranteed bandwidth for the connection. Otherwise, the system considers the data unit to be part of the available bandwidth associated with the connection. Additionally, if the frame includes a set DE bit, then the frame is considered part of the available bandwidth for the associated connection. Further, in an illustrative embodiment, if the system determines that a received frame is part of the available bandwidth for a connection, and it has a DE bit that is clear, the system may set the DE bit in the frame. Frames associated with guaranteed bandwidth are considered by the disclosed system to be higher priority than frames associated with available bandwidth.
The disclosed system includes a prioritized list of queues. Each queue in the list includes a number of entries, and each entry is associated with one or more buffers for storing portions of a received data unit. A received data unit, having a length equal to some number of transmission credits, is associated with a virtual connection and a flow control mode. A number of transmission credits are maintained in association with the prioritized queue list, and may be used to transmit data units stored within it. Received data units are stored within specific queues in the queue list based on their relative priorities, for example, as indicated by the QoS levels of their associated connections, whether they are part of guaranteed or available bandwidth, and the DE bit values they contain.
The disclosed system provides both “cut through” and “store and forward” flow control modes. Data units and/or queues having a relatively high priority are associated with the cut through flow control mode. When store and forward flow control is employed, transmission of a data unit cannot begin until there are sufficient transmit credits available to transmit the whole data unit. When cut through flow control is employed, portions of a data unit may be transmitted as applicable transmit credits become available.
Further during operation of the disclosed system, the prioritized queue list is traversed by searching for a highest priority data unit that is part of the guarantee

Affiliated with

Also associated with

Rating

Network to network priority frame dequeuing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Network to network priority frame dequeuing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network to network priority frame dequeuing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2493548