Multi-stage queuing discipline

Details Multi-stage queuing discipline Multi-stage queuing discipline

1997-06-30

2002-08-06

Nguyen, Chau (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S468000

Reexamination Certificate

active

06430191

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method and apparatus for handling information,sent through a digital network and, more specifically, to a method and apparatus for organizing and servicing cells at a switch within such a network.
BACKGROUND OF THE INVENTION
Asynchronous Transfer Mode (ATM) or “cell switching” is a method of transmitting digital information wherein the information is broken into equal sized units called “cells.” The individual cells of information are transmitted from a source node to a destination node through a “connection”. A connection is a pathway through a digital network. A digital network is constructed of digital switches coupled together by digital communication links.
Each cell originates at a source node and is transmitted across the communication links. The communication links carry the cells of information between the digital switches along the connection pathway. The digital switches route the cells from incoming communication links to outgoing communication links and finally to a destination node.
Each digital switch can be connected to several communication links. Furthermore, each communication link can carry several different connections simultaneously. Typically, a cell memory or buffer is used for temporarily holding cells prior to transmission on a communication link. The cell memory is arranged into logical queues. Several queues may be used for separating different types of services and connections. For example, cells belonging to higher priority connections may be stored in queues that have a higher priority of service. In some cases, a separate queue may be assigned to each connection. Servicing a queue entails removing a cell from the queue and sending the cell out on a communication link or to a destination node coupled to the digital switch. A service algorithm is employed to select a queue for service. To fully utilize the bandwidth of a communication link, a cell should be selected for service during each service time, where a service time is equal to the time required to transmit a cell on the communication link.
Typically, switches are capable of handling different classes of cell traffic, each class having different characteristics and different service requirements. The various classes of cell traffic might include high priority traffic, voice, high speed deterministic traffic, bursty data, etc. Typically, each of these traffic types are buffered at each switch in accordance with their particular sensitivities to network delay and cell loss. Cell loss may occur due to intermittent short term overload of network bandwidth and lack of adequate buffer capacity. Each class of traffic may be placed in a preassigned queue at each switch, each queue having a different service priority. Servicing algorithms are typically employed to discriminate between traffic classes in order to allocate bandwidth. Delay is managed by properly sizing the queue depths and prioritizing transmission within a class.
Even with sophisticated queuing and service algorithms, however, congestion (due to excess arriving traffic at a switch) can occur. This congestion is typically divided into three categories: short term, medium term and long term. Short term congestion management, typically handled by discarding traffic at the queue, may be done haphazardly or, preferably, by selecting cells marked with their “discard eligibility”. Long term congestion is typically controlled by admission policies that allocate resources (e.g., bandwidth and buffers) at the time a connection is established. If no resources are available, the connection is not allowed. Medium congestion control is generally accomplished through open loop or closed loop techniques. Open loop control techniques generally involve no explicit feedback from the network and congestion is controlled by smoothing the flow of input traffic. Closed loop techniques sense a level of congestion on a virtual circuit and control the in-flow of traffic based on feedback of congestion status information to the source terminal.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a method and apparatus for efficiently organizing and servicing cells which flow through a digital switch.
In one embodiment, a method of servicing cells within a switch of a digital network is provided. Incoming cells are placed into a queue in a cell memory until the cell is serviced. The switch maintains various cell queues, including VC queues that correspond to individual connections and QBin queues that correspond to various classes of service. These queues are preferably implemented through the use of linked lists. Cells may arrive to a VC queue or a QBin queue but will depart from a QBin queue. Accordingly, cells may be moved from VC queues to QBin queues at a rate depending upon network bandwidth availability.
Cells may be serviced as follows: First, one of a number of QBin groups (QBGS) is selected. The QBGs contain a number of logical queues (QBins) of cells to be transported in the digital network. Second, one of the logical queues from the selected QBG is selected.
A QBG may be selected by examining each of the QBGs to determine which QBG is most eligible for servicing. That is, the QBG which is selected is the one that is most overdue for service. An individual logical queue from the selected QBG may then be selected by examining the states of each of the logical queues comprising the selected QBG and selecting one of the logical queues for servicing based on its state.
In a further embodiment, a method of allocating bandwidth among a plurality of connections in a cell switched digital network is provided. The method selects a group of logical queues, from among a number of such groups, for servicing. Each queue of the group may have one of a number of connections within the network assigned thereto. The method then selects one of the logical queues of the selected group of queues for servicing. Each of the logical queues may correspond to a class of service within the network, each class of service having an associated service rate. The selection of the group of logical queues may be accomplished by computing a minimum theoretical departure time (TDT) for each of the groups, each TDT representing a time at which a corresponding group of queues may be serviced. Using the TDTs, groups of queues which are eligible for servicing are determined and one of the eligible groups is selected. One of the logical queues of the selected group may be selected for servicing based on its own associated TDT if the queue is in a first state or based on a service delay accumulator value and a priority if the queue is in a second state.
In yet another embodiment, a virtual interface having a number of logical queues corresponding to a plurality of classes of service is provided. The virtual interface may include a scheduler configured to select one of the logical queues for service according to a transmission requirement for a class of service associated with said selected logical queue. The virtual interface may further be configured to limit a number of cells to be stored in a memory associated therewith according to one or more thresholds. Such thresholds may include a cell maximum for the virtual interface, a cell maximum for the memory, a cell loss priority threshold, an early packet discard threshold, an explicit forward congestion indicator threshold, etc.
A further embodiment of the present invention may include a digital switch which includes a number of logical queues of cells stored in a memory, each logical queue having an associated service priority, the logical queues being arranged in a number of groups. The switch may further include selection logic coupled to the memory and configured to select one of the logical queues associated with a first of the groups for servicing.
These and other features and advantages provided by the present invention will be apparent from the detailed description which follows and upon reference to the accompanying figures described therein.


REFERENCES

Affiliated with

Also associated with

Rating

Multi-stage queuing discipline does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-stage queuing discipline, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-stage queuing discipline will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2906901