Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1997-10-02
2001-03-06
Patel, Ajit (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S412000
Reexamination Certificate
active
06198724
ABSTRACT:
NOTICE OF COPYRIGHTS AND TRADE DRESS
A portion of the disclosure of this patent document contains material which is subject to copyright protection. This patent document may show and/or describe matter which is or may become trade dress of the owner. The copyright and trade dress owner has no objection to the facsimile reproduction by any one of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright and trade dress rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method for processing packets in packet switched networks for efficient transmission, and more particularly to processing cells in Asynchronous Transfer Mode (ATM) networks.
2. Description of Related Art
In packet oriented networks, e.g., ATM (Asynchronous Transfer Mode) networks, data packets, also called cells, are forward between different stations and in particular they may pass through numerous switch or other units where arrived packets are forwarded. These transferring stations (most often switches) contain memories or buffers which store the packets before they are forwarded. However, transfers of packets through the network may have time criticality. Thus, the ability of the transferring stations to process packets efficiently is critical.
One problem that arises when performance is low that the buffers, which have limited capacities, may overflow. This results in the need to resend packets at a later time, thus shifting congestion.
ATM networks use time division multiplexing (TDM) to allow multiple data streams to be sent concurrently. These data streams are called Virtual Channels or Virtual Circuits (VCs), and there might be thousands of VCs converging into a single connection. While there might be numerous sources of data (VCs), only one cell at a time can be transmitted.
When a VC is established, a number of parameters are also set. These parameters include: a minimum cell transmission rate called the “sustainable cell rate” (SCR), a peak cell transmission rate (PCR), a cell delay variation time (CDVT) and a burst tolerance (BT). While the SCR and PCR relate to the average throughput of the VC, the CDVT and BT limit the variation in the throughput. The maximum average time between cells is 1/SCR. The minimum average time between cells is 1/PCR. CDVT is the maximum amount of time that a cell may be sent early within 1/PCR. BT is the amount of time that a cell may be sent at 1/PCR without violating the SCR limitation.
According to ATM standards, VCs are set up (“contracted”) with different types of service (known as Quality of Service, QoS). Some VCs are set up (“subscribed”) with a set transmission rate. These are known as Constant Bit Rate (CBR) VCs. Other VCs are called Variable Bit Rate (VBR), Available Bit Rate (ABR) and Unspecified Bit Rate (UBR). Normally, CBR VCs have the highest priority, and UBR VCs have the lowest priority.
In ATM devices, two critical processes are the segmentation of data into cells for transmission and the reassembly of received cells. Typically, an ATM device includes a component called the “SAR” which performs segmentation and reassembly. Considerable effort has been expended in making segmentation as efficient as possible.
Another key and critical task for the SAR is scheduling cells from various VCs for transmission. A typical first step in pre-transmission processing is selection of a VC to service. Typical prior art methods employ link-list tables which store cells or pointers to cells and information about the priority of each cell. However, this technique requires multiple memory access cycles to complete a single entry scanning. Furthermore, it requires double link-list pointers to add and delete entries. This technique also uses considerable amount of memory.
In other systems, a token is associated with each VC, and there are multiple queues having varied priorities. The tokens are moved from queue to queue during a cyclical scanning process, and the VCs in the highest priority queue are serviced. Movement of the tokens is based upon the relevant VC's subscription rate.
After the order of servicing of VCs is selected, the cells themselves are scheduled for transmission. Two methods are described in the ATM Forum UNI Specification 3.1, in Section 3.6.2.4.1: a virtual scheduling algorithm and a continuous-state leaky bucket algorithm, also known as the generic cell rate algorithm (GCRA). According to the prior art leaky bucket method, cells accumulate in a buffer in the order in which they are to be sent. The leaky buffer fills and empties at a set rate. Cells typically are placed into the buffer in advance of their scheduled departure time. Thus, before the cell at the bottom of the bucket can be sent, the system must ensure that it is time to send the cell. On the next processing cycle, the cell's scheduled departure time is calculated and compared to the present time. If the cell departure time is before or equal to the present time, then the cell is transmitted. If the cell is too early, then the computed departure time is discarded. This process continues until the cell's departure time is met or passed and the cell is transmitted, after which the next cell in the buffer is processed.
Referring now to
FIG. 7A
, another perspective of the GCRA is appreciated. Normally, cells for a given VC are scheduled to be sent at set intervals T
s
. T
s
is a function of internal cell scheduling resolution. For example, a first cell is transmitted at t
0
, a second cell transmitted at t
0
+T
s
, and a third cell is transmitted at t
0
+2T
s
. When the VC is established, a subscribed cell time is established also as T
c
. Thus, the first cell is subscribed to be sent at t
0
, the second cell is subscribed to be sent at t
0
+T
c
, and the third cell is subscribed to be sent at t
0
+2T
c
. Ideally, T
s
is identical to T
c
. However, due to limited scheduling resolution T
s
is less than or equal to T
c
.
The GCRA necessarily results in increasing differences between the subscribed cell time and the scheduled cell time. T
s
is always shorter than T
c
, so cells are scheduled to be sent earlier and earlier than the subscription time. Eventually, a cell will be scheduled too soon before the subscribed time. This limit &tgr; is also established when the VC is established. This limit is also known as the cell delay variation time (CDVT). If a cell is scheduled to be sent within this limit, then the cell is said to be “conforming.”
The GCRA necessarily results periodically in some cells being non-con the prior art, non-conforming cells are typically rescheduled T
s
later. For example, in
FIG. 7A
, the fourth cell was initially scheduled for transmission at t
0
+3T
s
. However, this time would have been more than &tgr; before t
0
+3T
c
. Therefore, the cell was rescheduled to be sent at t
0
+4T
s
and the subscribed time was reset to t
1
, the new scheduled transmission time. As a result, there is a loss of bandwidth or failure to keep up with the subscribed cell rate.
There has been a suggestion to include a final traffic shaping step in ATM transmission systems. According to this suggestion, in the traffic shaping step, the flow of cells is smoothed to reduce the chance of traffic congestion which might occur inside an ATM device due to the burstiness of incoming traffic. A parallel sequencing scheme was suggested to achieve this. However, the parallel sequencing scheme requires multiple copies of hardware logic—one for each cell; it has a very high cost rendering it impractical for medium and low costs implementations, and requires reordering of every arrival or departure of cells.
It is therefore the object of the invention to efficiently schedule cells for transmission in a packet switched network. It is an object to select VCs for servicing. It is also an object to produce service requests in a constant time interval with minimum jitter. It is an object to provide for selection of
Chen Martin
Fuh Eric
Huang Frank
Lam John
Arter & Hadden LLP
Nguyen Brian
Patel Ajit
Vertex Networks, Inc.
LandOfFree
ATM cell scheduling method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with ATM cell scheduling method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ATM cell scheduling method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2498924