Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-13
2002-03-19
Yao, Kwang B. (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S458000
Reexamination Certificate
active
06359891
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to asynchronous transfer mode (ATM) communication systems and more particularly to ATM cell processing operations in an ATM communication system.
BACKGROUND OF THE INVENTION
Asynchronous transfer mode (ATM) communication systems are designed to support high-speed, low-delay multiplexing and switching of voice, data, video and other types of user information traffic. 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 a virtual connection (VC) which is established when a user requests a network connection in an ATM system. Additional details regarding these and other aspects of 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, New York, 1993, both of which are incorporated by reference herein. The allocation of available transmission opportunities or slots to user traffic cells is generally referred to as cell scheduling.
One possible ATM cell scheduling technique could involve calculating for a given VC an ideal time at which the VC should be serviced by allocating a cell to that VC. An ATM scheduling system could then mark in a stored table, list or other type of schedule the fact that a given VC X is ready for scheduling at a time Y. Because one or more other active VCs may have previously requested servicing at time Y, such a cell scheduling system would typically require a two-dimensional list of scheduling requests in which one dimension is time and the other dimension is the list of VCs scheduled to be serviced at a given time.
A significant problem with such a two-dimensional cell schedule is that it makes it difficult for a scheduling system to determine when a particular VC should be scheduled for servicing due to the fact that the calculation can no longer be based on time alone. This is because there could be a back-up of arbitrary depth at any given scheduled time. As a result, a servicing processor may arrive late at successive scheduled times. VCs that are scheduled further out in time could have been scheduled earlier in time had the scheduling system been aware of the delays that would be encountered by the servicing processor. For example, the scheduling system could have scheduled a given VC earlier in time while maintaining the necessary elapsed time between successive cell transmission events if it were able to account for the delays. This two-dimensional scheduling technique results in inefficient scheduling and thus reduced system throughput.
Prior art ATM cell processors also suffer from a number of other drawbacks. For example, most available cell processors typically utilize either a hard-wired approach to provide increased throughput speed or a programmable approach which provides a high degree of flexibility but at the cost of reducing throughput speed. Another problem is that prior art cell processor approaches generally do not allow system designers to provide a common, reprogrammable architecture suitable for use in a wide variety of different ATM-based products. Other serious problems with prior art cell processing include the latency associated with accessing control information from static random access memory (SRAM) or other types of control or system memory, the scheduling of constant bit rate (CBR) traffic in the presence of variable bit rate (VBR) traffic, and the failure of the prior art devices to provide support for virtual path (VP) tunneling.
As is apparent from the above, there is a need for improved ATM cell scheduling, servicing and other processing techniques which avoid the above-noted problems of the prior art.
SUMMARY OF THE INVENTION
The present invention provides apparatus and methods for processing asynchronous transfer mode (ATM) cells in an ATM communication system. The invention provides improved cell scheduling and servicing techniques as well as an improved ATM cell processor architecture. An ATM cell processor in accordance with the invention is particularly well-suited for use in high-speed ATM cell processing applications, and can provide cell throughput at speeds typically associated only with fully hard-wired devices, while simultaneously providing the increased flexibility of a programmable device. An ATM communication system based on a cell processor in accordance with the present invention can be readily configured to provide different operating parameters and is therefore relatively insensitive to changes in ATM standards. Many such changes can be implemented in a cell processor of the present invention through relatively simple software and/or firmware modifications.
One aspect of the invention involves a method of allocating cells in an ATM communication system. The method includes the step of generating a first group of bits in the form of a primary scoreboard. Each bit of the primary scoreboard represents a cell time slot on a transmission link in the communication system, and the value of a given primary scoreboard bit indicates whether or not the corresponding cell time slot is available for transmission. In response to a cell scheduling request of a given virtual connection in the ATM system, a processor directs the searching of the primary scoreboard beginning at a bit corresponding to a target time slot and proceeding through the scoreboard until a bit corresponding to an available time slot is identified. The available time slot is then scheduled by setting the identified primary scoreboard bit, and storing a connection identifier (ID) for the virtual connection in a connection ID table at a location corresponding to the identified primary scoreboard bit. The primary scoreboard and connection ID table can both be maintained in an external control memory which the ATM cell processor accesses through a high-speed memory port. Alternatively, the primary scoreboard and/or connection ID table can be maintained in a set of memory locations internal to the ATM cell processor to further reduce scheduling time, thereby allowing for higher rates on the transmission link and efficient implementation of more complex scheduling algorithms.
The scheduled time slots are serviced in response to a servicing instruction specifying an address in the connection ID table. The connection ID at that location is retrieved, as is the primary scoreboard bit corresponding to that location. The primary scoreboard bit is copied to an assigned cell flag register (ACFR) in the processor, and the scoreboard bit is then cleared to free the time slot for subsequent scheduling requests. The processor then directs the construction or retrieval of a cell for the virtual connection identified by the connection ID retrieved in response to the servicing instruction, and queues the cell for transmission over the ATM link in the scheduled time slot.
Another aspect of the invention involves a method for bounding the primary scoreboard search time to an acceptable range. A secondary scoreboard is generated in the form of a group of stored bits, with each secondary scoreboard bit indicating whether a corresponding block of primary scoreboard bits includes a bit indicative of an available cell time slot. When searching the primary scoreboard in response to a scheduling instruction, an ATM cell processor first directs the retrieval and searching of a block of primary scoreboard bits which includes a target slot specified in the scheduling instruction. If there is no available slot in the retrieved block, the ATM cell processor uses the secondary scoreboard to determine the location of a primary scoreboard block which does include an available slot. The ATM cell processor may access the secondary scoreboard in parallel with its access to the current block of primary scoreboard bits, such that if the current bl
Bergantino Paul V.
Lussier Daniel J.
Conexant Systems Inc.
Hale Kelly H.
Kind Keith
Yao Kwang B.
LandOfFree
Asynchronous transfer mode cell processing system with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Asynchronous transfer mode cell processing system with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asynchronous transfer mode cell processing system with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2820723