Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-12-22
2002-08-20
Patel, Ajit (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S233000, C370S234000, C370S395420
Reexamination Certificate
active
06438106
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to inter-class schedulers for digital link systems, including asynchronous transfer mode (ATM) telecommunications systems, and, more particularly, provides novel inter-class schedulers employing statistical priority guaranteed queuing (SPGQ) and generic cell-rate algorithm priority guaranteed queuing (GCRA-PGQ).
The systems and methods disclosed herein are discussed with particular application to ATM systems. However, those skilled in the art will appreciate that the inventive subject matter disclosed herein is equally applicable to other settings in which a plurality of devices transmit and/or receive digital signals over a bandwidth-limited link, such as systems where multiple client or end-user machines communicate with a host.
Information regarding ATM systems can be found in the ATM Forum, “ATM User-Network Interface Specification,” Version 3.1, September, 1994, and in Martin de Prycker, “Asynchronous Transfer Mode: Solution for Broadband ISDN, ” Ellis Horwood, N.Y. 1993, both of which are incorporated by reference herein. Aspects of ATM systems are also discussed in U.S. Pat. Nos. 5,818,815; 5,794,025; and 5,768,259, also incorporated by reference herein.
An advantage of high bandwidth, fixed length cell based transfer mode techniques such as ATM, is the capability of high-speed, low-delay multiplexing and switching of different types of user information traffic—including data, voice, image and video—over the same network, while optimizing bandwidth and resources utilization.
In ATM connection-oriented networks, the end-to-end traffic of data for one user, between the source and the destination, is represented by a Virtual Connection (VC); several Virtual Connections can be grouped in a Virtual Path (VP) that can be switched as a unit.
An ATM system segments user traffic into fixed-length 53-byte cells. A 5-byte header in each cell typically includes a virtual channel identifier (VCI) and a virtual path identifier (VPI) associated with the corresponding cell. The VCI and VPI fields together identify the virtual connection that is established when a user requests a network connection in an ATM system. The allocation of available transmission opportunities or slots to user traffic cells is generally referred to as cell scheduling, and the devices that accomplish this task are schedulers.
As employed in ATM and other digital link systems, an inter-class scheduler is a device that monitors the status of an input queue for each class of service (voice, video, and other digital signals), updates the eligibility data of service of the class, and according to some predefined criteria, makes decisions about the class to be serviced at the next transmit opportunity. The digital switching apparatus utilizes this decision outcome to select a particular class for the next transmit opportunity.
In essence, the inter-class scheduler enables the digital link system to determine which class will next receive a share of limited bandwidth and processor resources. These decisions are vital to the performance of bandwidth-limited digital link systems.
A major problem to be resolved in cell-based networks is congestion control. Since the cells are short, no space is allocated in the header to enable error recovery for the cell payload. If one cell of the block has been lost or discarded by the network in case of network congestion, error recovery is performed at the higher-level by recovery protocols retransmitting the user data block. Since the error rate is normally quite low in the internode links, the loss of cells due to random error is not generally a problem. However, when a node discards cells based upon detection of traffic congestion, it is unlikely that these cells will come from a small number of logical data blocks. Consider, for example, a worst case scenario, in which 1000 messages come from 1000 different connections. Under such a circumstance, the discarding of 1000 cells, where the average user data block length is 2K Bytes (a low estimate) sent as 43 cells, can cause the network to absorb a retransmission of 43,000 cells.
Depending on the type of traffic conveyed over the network, congestion can damage the quality of traffic beyond acceptable limits. For voice applications it is more acceptable to lose data than to excessively delay it. For file applications it is more acceptable to delay the data than to lose any portion of it. That is why the ATM networks provide different Quality of Service (QoS) guarantees for different classes of service. In order to meet the QoS, the network nodes have to control the traffic congestion both at connection admission time and once the connection is established.
A first control on traffic congestion, once the connection is established, is performed by a policing function implemented in a device, referred to as the “policer,” of the network access node adapter. The policer will detect and penalize violations of the peak cell rate of “current” traffic compared to the peak cell rate required at call set-up.
A second control of traffic congestion consists in shaping the output network node traffic by spacing cell departures such that the time between two departures of cells for a same connection is never below the minimal value negotiated at connection setup time. The multiplexing of spaced cells tends to decrease the “burstiness” of the aggregate traffic, permitting a better utilization of the network resources.
The policing function is typically implemented in the network nodes by a “policer”that forms part of the high speed adapter cards in the devices accessing the network. The shaping function is implemented in the network nodes by a “shaper” that controls the sending of the output traffic cells and is also part of the high ed adapter cards.
The policing function proposed as a standard by the ITU (International Telecommunications Union), is the Generic Cell Rate Algorithm (GCRA). Details of the GCRA are given in the ATM Forum, “ATM User-Network Interface Specification”, Version 3.0, 1994, incorporated by reference herein. Those skilled in the art will appreciate that commercially-available, application-specific integrated circuits (ASICs) have been developed to implement GCRA.
The role of the GCRA is, for each connection, to monitor the traffic arriving upstream according to the cell period T (T corresponds to the inverse of the peak cell rate R) and a given tolerance tau on this period. Basically, a cell is assumed to be conforming if the time elapsed between the arrival of two consecutive cells (belonging to the same connection) is greater than or equal to T—tau . If not, the cell is assumed to be nonconforming and is tagged and possibly discarded.
The policer discards cells not only because the source of traffic has violated the parameters negotiated at connection establishment, but also because of a distortion in the cell stream commonly referred to as “jitter” or Cell Delay Variation (CDV). This distortion is due to the queuing of the cells at each intermediate network node and more generally the multiplexing of the cells on the output lines. The magnitude of the “jitter” depends on many parameters, including the connection peak rate; the peak rate of the other connections that share the same link; the link load; and the number of nodes passed through.
The foregoing discussion demonstrates that considerable design and implementation effort has been expended in attempting to control congestion problems in digital link systems. In this regard, it is also clear that inter-class schedulers must be sufficiently efficient to limit adverse effects of congestion. Thus, an effective inter-class scheduler should have several properties. First, it should provide a minimum bandwidth guarantee for each class. Second, it should provide exclusive allocation of unused bandwidth to the highest priority class that requires it. In addition, it should enable provisioning of work-conserving service.
Inter-class schedulers can be categorized into absolute or “static” priority schedulers on the
Marchand Bernard
Pillar John
St-Denis Bernard
Gibbons Del Deo Dolan Griffinger & Vecchione
Nortel Networks Limited
Patel Ajit
Spafford Tim
LandOfFree
Inter-class schedulers utilizing statistical priority... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Inter-class schedulers utilizing statistical priority..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inter-class schedulers utilizing statistical priority... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2968693