Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1999-04-13
2004-07-13
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
C370S230000, C370S232000
Reexamination Certificate
active
06762994
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to high speed digital switching systems such as asynchronous transfer mode (ATM) networks for servicing multiple categories of traffic and more particularly to a lookup table approach for making complex decisions and/or variable updates at high speed in such systems.
BACKGROUND
The use of Asynchronous Transfer Mode (ATM) by a continuously widening set of applications is driving a requirement for efficient dynamic allocation of bandwidth. The ATM Forum has specified (Traffic Management Specification, Version 4.0) two best effort service categories that provide flexible access to bandwidth: the Available Bit Rate (ABR) category; and the Unspecified Bit Rate (UBR) category.
In general an ATM switch can be viewed as a system with two or more physically separate ingress ports which bring ATM cells to the switch, and an equal number of physically separate egress ports to which ATM cells are sent. ATM is inherently a connection oriented system and individual connections on ingress and egress links are identified by using the virtual path identifier (VPI) and virtual channel identifier (VCI) fields of the standard ATM cell. Within an ATM switch it is convenient to identify connections with a more compact identifier. A Connection Identifier (CI) is used for this purpose. Connections of different types may be configured on a single port—for example a connection may belong to the ABR or UBR categories mentioned above.
Since it is possible that all ingress ports may transmit cells to a given egress port simultaneously, buffers are required at each egress port to absorb transient periods in which the ATM cell service rate is less than the arrival rate. A queuing function is required at each port to manage the buffers for that port. A conventional queuing function consists of one or more queues, and an arbitration function that decides which queue to service at each cell departure time. Typical queuing function implementations queue ABR cells separately from UBR cells.
The ABR category of service employs a rate-based flow control scheme where sources only send data at a rate that the network elements along the path of the connection can handle without overflowing their queues. The ABR protocol allows many options and leaves many details to be implementation specific. Achieving high link utilization demands that the network elements accurately indicate the data rates that they can accept. Furthermore, it is important that bandwidth contending for a congested queuing resource be allocated ‘fairly’ to each connection.
Explicit Rate (ER) ABR is a scheme whereby each switch in the data path of an ABR connection calculates an explicit cell rate at which the source is allowed to transmit and sends that information to the source in a special resource management (RM) cell.
UBR is a service category that is specified to allow the sustained mean aggregate arrival rate of connections into a queue to exceed the service rate. As a result, it is probable that a queue containing UBR connections will overflow and cells will be discarded. It is desirable to implement cell discard mechanisms that ensure that connections are treated fairly when cells are discarded. In addition, it is desirable to provide a UBR service that can, in a configurable manner, give better service to some connections than others. This is called a differentiated service.
A large number of data applications use the standard ATM Adaptation Layer 5 (AAL5) method of segmenting data packets into ATM cells. For these applications it is desirable to discard entire AAL5 packets instead of individual cells that may only be a portion of a packet. Early Packet Discard (EPD) is a scheme that discards entire packets, e.g. AAL5 packets. EPD is also useful for ABR and UBR connections.
In general, as the rate at which telecommunication systems operate increases, it becomes increasingly difficult to update important variables in sophisticated flow control schemes (such as ABR ER) or to arrive at a decision whether to apply EPD or not. While the time allowed to do calculations shrinks, efforts to increase the efficiency of the network demands that more and more complex equations be implemented. The current state of the art is to use either specialized RISC (Reduced Instruction Set Computer)-based compute engines (such as the ATMizer from LSI Logic) or to design application specific integrated circuits (ASICs) to do the necessary calculations. A major problem with these current approaches is the expense in dollar cost, power and area. Another problem is the complexity of current implementations and the difficulty in easily making modifications, i.e. either ASICs need to be changed or complex low level RISC code must be modified.
SUMMARY OF THE INVENTION
This invention solves the problem of doing complex real-time calculations to update variables in flow control systems by using Lookup tables. The memory based lookup table is low cost, low power, fast, real-estate efficient and flexible. Not only can arbitrarily complex functions be implemented but tools can be provided to make the programming of the table straight-forward, thereby offering a means for the customer (the network provider) to differentiate service offerings.
Therefore, in accordance with a first aspect of the invention there is provided in a connection oriented digital switching network having statistical multiplexing a system for implementing congestion control between multiple connection queues comprising: means to obtain statistical information respecting each queue; a lookup table containing threshold information; comparison means to compare the statistical information with the threshold information; and means to discard data if the statistical information exceeds a threshold.
In accordance with a second aspect of the invention there is provided a lookup table for use in a congestion control scheme for an asynchronous transfer mode (ATM) network servicing multiple connection categories, said lookup table comprising a programmable memory for storing queue related threshold information.
In accordance with a further aspect of the invention there is provided a method of managing traffic through a high speed, digital switching network having multiple :connections, each with queuing means to buffer statistical traffic, said method comprising: monitoring traffic in each queue; providing a lookup table with queue threshold information; and marking traffic eligible for early packet discard (EPD) in accordance with threshold information specified in the lookup table.
In a preferred embodiment the lookup table includes information for use in implementing an early packet discard (EPD) algorithm.
In a further preferred embodiment the lookup table also includes information for use in marking resource management cells of ABR traffic with explicit rate information.
REFERENCES:
patent: 5694390 (1997-12-01), Yamato et al.
patent: 5777984 (1998-07-01), Gun et al.
patent: 5812527 (1998-09-01), Kline et al.
patent: 5936939 (1999-08-01), Des Jardins et al.
patent: 5940368 (1999-08-01), Takamichi et al.
patent: 5940375 (1999-08-01), Soumiya et al.
patent: 6034945 (2000-03-01), Hughes et al.
patent: 6044079 (2000-03-01), Calvignac et al.
patent: 6345037 (2002-02-01), St-Denis et al.
The ATM Forum Technical Committee, Traffic Management Specification Version 4.0, Apr. 1996.
Davis Tom
Giroux Natalie
Mitchell Charles
(Marks & Clerk)
Alcatel Canada Inc.
Chin Wellington
Schultz William
LandOfFree
High speed traffic management control using lookup tables does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed traffic management control using lookup tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed traffic management control using lookup tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211471