Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2002-05-20
2004-11-23
Nguyen, Chau (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236000, C370S395420, C370S412000, C370S468000
Reexamination Certificate
active
06822939
ABSTRACT:
BRIEF DESCRIPTION OF THE APPENDIX
The enclosed CD-ROM appendix is incorporated herein by to reference. The CD-ROM is in ISO 9660 Macintosh® format and includes the following Adobe® Acrobat® files:
List of files
Size (Bytes)
Date of Creation
SCB_FR.pdf
252,958
Apr. 12, 2002
The file SCB_FR.pdf is a document entitled “Aspen Express Scheduler Block (SCB) Requirements Specification” which illustrates in detail a presently preferred embodiment of the invention.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the allocation of bandwidth in an ATM (Asynchronous Transfer Mode) network. More particularly, the invention relates to methods and apparatus for guaranteeing a minimum cell rate (MCR) or a sustained cell rate (SCR) in ATM traffic queues.
2. State of the Art
Perhaps the most awaited, and now fastest growing technology in the field of telecommunications is known as Asynchronous Transfer Mode (ATM) technology. ATM was designed to be a carrier of integrated traffic, e.g. voice, data, and video. ATM utilizes fixed length packets (called “cells”) of 53 octets (5 octets header and 48 octets payload). Current ATM service is offered in different categories according to a user's needs. These categories include, in order of priority: constant bit rate (iCBR), variable bit rate-real time (VBR or VBR-rt), variable bit rate-non-real time (VBR-nrt), guaranteed frame rate (GFR), available bit rate (ABR), unspecified bit rate plus (UBR+), and unspecified bit rate (UBR). CBR and VBR-rt are “real-time” categories suitable for streaming video and voice connections. These categories are given the highest priority in the ATM network. The other five categories are considered “non-real-time”. For GFR, ABR, and UBR+, users pay for a minimum cell rate (or guaranteed frame rate) which is an average rate taken over time during which there may be bursts up to a specified peak cell rate (PCR). For convenience, these three categories are referred to as MCR (minimum cell rate) services. According to ATM Forum standards, both VBR-rt and VBR-nrt require a “sustained cell rate” (SCR) which is substantially the same requirement as MCR. For UBR, no minimum bandwidth is guaranteed. UBR connections are serviced last if there is any available bandwidth after servicing all of the higher categories of service. UBR, is referred to as “best effort” service. Service categories and traffic management issues are specified in the ATM Traffic Management Specification Version 4.1, AF-TM-0121.000, March 1999.
ATM traffic management systems vary in complexity and cost. The simplest method of managing traffic is strict priority queuing. According to strict priority queuing, each traffic flow (virtual circuit or virtual path) is assigned a service category bulk queue. These queues are then serviced in strict priority order. The more complex systems assign a separate queue to each traffic flow and shapes each one according to a specific traffic contract so that it meets a required SCR or MCR and does not exceed a PCR (peak cell rate) and limits the cell delay variation (burstiness).
The strict priority mechanism is quite simple and inexpensive to implement but provides only minimum quality of service (QOS) since there are no individual guarantees for each traffic flow. Also, the lowest categories of service are subject to starvation with no guarantee of any service at all. The shaping mechanisms provide all the necessary guarantees for individual traffic flows but shaping mechanisms are very complex and costly to develop.
SUMMCRY OF THE INVENTION
It is therefore an object of the invention to provide methods and apparatus for guaranteeing MCR or SCR in ATM traffic queues.
It is also an object of the invention to provide methods and apparatus for guaranteeing MCR or SCR in ATM traffic queues which guarantees MCR or SCR in each traffic flow of an ATM device.
It is another object of the invention to provide methods and apparatus for guaranteeing MCR or SCR in ATM traffic queues which prevents starvation of lower service categories.
It is a further object of the invention to provide methods and apparatus for guaranteeing MCR or SCR in ATM traffic queues which are relatively simple and inexpensive to implement as compared to known traffic shaping systems.
In accord with these objects which will be discussed in detail below, the apparatus of the present invention includes at least one queue for each service category, a scheduler for dequeuing cells from the queues, a queue status block for indicating which queues are empty, and an MCR service block. The MCR service block includes a plurality of timers, at least one for each service category. According to the methods of the invention, an MCR value is selected for each queue (or service category) and a timer in the MCR service block is set according to the MCR value. The scheduler dequeues cells in strict priority from non-empty queues as determined by the queue status block until a timer expires. When a timer expires, it is determined whether any queues associated with the timer failed to receive service during the timer interval. If such “starved queues” exist, the scheduler is preempted by the MCR service block so that the starved queues receive service. The arrangement of queues and associated timers is subject to alternate embodiments. As stated above, at least one queue is provided for each service category. However, according to an alternate embodiment, separate queues for each traffic flow are implemented. According to still another embodiment, multiple queues are implemented for some service categories, e.g. three separate priority queues for UBR service so that different classes of IP traffic can be mapped into UBR traffic. As stated above, at least one timer is provided for each service category. When a timer expires, the scheduler is directed to service all of the unserviced queues in the associated service category. According to an alternate embodiment, a separate timer is associated with each queue. The invention may be implemented in either a single port or multi-port device.
Additional objects and advantages of the invention will become apparent to those skilled in the art upon reference to the detailed description taken in conjunction with the provided figures.
REFERENCES:
patent: 5150358 (1992-09-01), Punj et al.
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5280475 (1994-01-01), Yanagi et al.
patent: 5339332 (1994-08-01), Kammerl
patent: 5381407 (1995-01-01), Chao
patent: 5400329 (1995-03-01), Tokura et al.
patent: 5448567 (1995-09-01), Dighe et al.
patent: 5497375 (1996-03-01), Hluchyj
patent: 5499238 (1996-03-01), Shon
patent: 5504744 (1996-04-01), Adams et al.
patent: 5515359 (1996-05-01), Zheng
patent: 5559798 (1996-09-01), Clarkson et al.
patent: 5561791 (1996-10-01), Mendelson et al.
patent: 5787071 (1998-07-01), Basso et al.
patent: 5889761 (1999-03-01), Yamato
patent: 5940370 (1999-08-01), Curtis et al.
patent: 6115358 (2000-09-01), Jones
patent: 6327246 (2001-12-01), Jones
Gordon & Jacobson, PC
Hyun Soon-Dong
Nguyen Chau
Transwitch Corporation
LandOfFree
Method and apparatus for guaranteeing a minimum cell rate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for guaranteeing a minimum cell rate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for guaranteeing a minimum cell rate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3291692