Shaping algorithm

Details Shaping algorithm Shaping algorithm

1999-07-26

2003-03-04

Nguyen, Chau (Department: 2663)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S395400

Reexamination Certificate

active

06529474

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to traffic shaping in an Asynchronous Transfer Mode (ATM) application and more particularly to an algorithm that can be implemented in ATM queuing systems where cells need to be shaped in order to be conformant to downstream Usage Parameter Control (UPC) traffic descriptors.
BACKGROUND OF THE INVENTION
Asynchronous Transfer Mode (ATM) is a packet based communications system well suited to the delivery of high-speed traffic including data, voice and video. In ATM a packet is a fixed length cell including a 5 byte header and a 48 byte payload. In order to accommodate the different types of service, i.e. voice, video, file transfer etc, delivered by an ATM network, the ATM Forum Traffic Management working group has defined five service categories, namely constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR), and unspecified bit rate (UBR) which are distinguished by the parameter sets which describe source behavior and quality of service (QoS) guarantees. The ATM Forum Traffic Management working group has also identified a mechanism to ensure conformance of a stream of cells. This mechanism is called traffic shaping and is defined as “a mechanism that alters the traffic characteristics of a stream of cells on a connection to achieve better network efficiency while meeting the QoS objectives, or to ensure conformance at a subsequent interface”. Conformance is defined based on an algorithm known as the Generic Cell Rate Algorithm (GCRA). Conformance for an ABR connection is network specific while conformance for a CBR and UBR connection is characterized by a Peak Cell Rate (PCR) parameter with a corresponding Cell Delay Variation Tolerance (CDVT) to account for delays at queuing points within the network. Additionally, the ability of the cell stream to withstand end to end cell loss depends on the type of communication carried by connection. Categories having low tolerance for cell loss are marked CLP=0 while categories having higher cell loss tolerance are marked CLP=1 where CLP is Cell Loss Priority. CLP=1 cells may be dropped or discarded in the event of network congestion. Aggregate traffic carrying different cell loss priorities are designated CLP=0+1.
Conformance for a rt-VBR or nrt-VBR connection is characterized by a Sustainable Cell Rate (SCR) parameter and a corresponding Maximum Burst Size (MBS) parameter, in addition to a PCR and a corresponding CDVT for the CLP=0+1 flow. A traffic shaping algorithm must thus yield a conformant cell stream and must maintain the sustained cell rate or peak cell rate requested.
The shaping algorithms known in the prior art, (see for example, J. Rexford et al “Scalable Architectures for Integrated Traffic Shaping and Link Scheduling in High-Speed ATM Switches”, IEEE Journal on Selected Areas in Communications, Vol. 15, No. 15, June 1997) ensure that a VBR connection is conformant to GCRA(1/PCR, CDVT) and GCRA(1/SCR, BT+CDVT), and ensure that a CBR or UBR connection is conformant to GCRA(1/PCR, CDVT) on queuing systems where a clock wrap around can be identified and where the state of each connection can be updated independent of cell arrivals. In this description wrap around is the action of a counter (clock in this case) that starts over at zero or at minus infinity after its maximum value has been reached, and continues to increment, either because it is programmed to do so or because of an overflow.
On current queuing systems with a single processor, it is not possible to identify clock wrap around. The algorithm described in the above identified prior art uses a maximum function to determine the schedule time of a cell. When a wrap around occurs and it is not detected, the maximum function will return erroneous values. The shaping algorithm described in the Rexford et al article then fails to maintain the requested sustain cell rate or peak cell rate.
Although the above example is not an exhaustive list of prior art, all known shaping algorithms do not simultaneously yield a conformant cell stream and maintain the sustained cell rate or peak cell rate requested in queuing systems where a clock wrap around cannot be identified.
SUMMARY OF THE INVENTION
The present invention is applicable to queuing systems where clock wrap around occurs and there is no background process to detect clock wrap around. The algorithm is described in its application to Constant Bit Rate (CBR), Real and non-real time Variable Bit Rate (VBR), Available Bit Rate (ABR) and Unspecified Bit Rate (UBR) service categories.
With this invention, the algorithm described in Rexford et al is modified such that a cell stream is conformant to GCRA and its SCR or PCR is maintained even on queuing systems where a clock wrap around may be encountered and is not detected.
Therefore in accordance with a first aspect of the present invention there is provided a method of shaping cell traffic at a queuing system for conformance with downstream traffic descriptors comprising: providing a calendar system having a register with a plurality of time slots for indicating emission times of cells awaiting service; limiting the register to positive values; dividing the positive time slot register into quadrants; comparing quadrant location of a theoretical emission time of a cell on the register with quadrant location of a next cell service time slot; and determining a scheduled emission time based on the comparison.
The algorithm according to the invention is capable of shaping traffic in a queuing system without means to detect clock wrap around.
According to a second aspect of the invention there is provided a queuing system having a shaper for conforming Asynchronous Transfer Mode (ATM) cell traffic to traffic descriptors comprising: a calendar register in said shaper having a plurality of time slots for indicating servicing sequences of cell traffic awaiting service; means to constrain the calendar register to positive time values; means to divide the positive time values into quadrants; means to calculate a Theoretical Emission Time (TET) of a cell based on Peak Cell Rate (PCR) and Cell Delay Variation Tolerance (CDVT) parameters; and means to compare the TET_PCR with a next time slot location on the register to determine the scheduled service time of a cell.
The system according to the second aspect of the invention implements an algorithm known as a single leaky bucket and is used to conform CBR and UBR categories of service. A dual leaky bucket algorithm can also be implemented by this system and includes means to calculate a theoretical emission time (TET) of a cell based on peak cell rate (PCR) and cell delay variation tolerance (CDVT) parameters and sustainable cell rate (SCR) as well as burst tolerance (BT) and cell delay variation tolerance (CDVT) parameters.


REFERENCES:
patent: 5926459 (1999-07-01), Lyles et al.
patent: 6058114 (2000-05-01), Sethuram et al.
patent: 6320845 (2001-11-01), Davie
patent: 6343076 (2002-01-01), Ha-Doung et al.
patent: 6396843 (2002-05-01), Chiussi et al.
patent: 6438134 (2002-08-01), Chow et al.
Jennifer Rexford, et al. document entitled “Scalable Architectures for Integrated Traffic Shaping and Link Scheduling in High-Speed ATM Switches”; IEEE Journal on Selected Areas in Communications, vol. 15 dated Jun. 1997.
The ATM Forum document entitled “Traffic Management Specification Version 4.0” dated Apr. 1996.

Affiliated with

Also associated with

Rating

Shaping algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3005626