Multiplex communications – Channel assignment techniques – Arbitration for access to a channel
Reexamination Certificate
1999-03-05
2001-03-20
Olms, Douglas W. (Department: 2732)
Multiplex communications
Channel assignment techniques
Arbitration for access to a channel
C370S235000, C370S412000, C370S428000, C370S462000
Reexamination Certificate
active
06205155
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to telecommunications apparatus and methods. More particularly, the present invention relates to ATM switch arbitration apparatus and methods for limiting data bursts in the switch, and thereby permitting simplified output port electronics.
2. State of the Art
Asynchronous transfer mode (ATM) is perhaps the fastest growing segment of the telecommunications backbone. The purpose of ATM is to provide a high-speed, low-delay multiplexing and switching network which supports all types of user traffic, including voice, data, and video. ATM data is transported in fixed-length “cells” which are fifty-three bytes in length, including a five byte header and a forty-eight byte data packet. The header includes virtual path and virtual circuit identifiers (VPI and VCI) which are used by the ATM network in relaying the traffic through switches of the network and to its customer premise equipment (CPE) destinations.
Many different ATM switches are known in the art. Generally, the switches have a plurality of input ports with input queue buffers, a plurality of output ports with associated queue buffers, and a source traffic control system which includes a switch fabric or bus mechanism and a switch controller which controls the transfer of data among the ports. A well-accepted source traffic control system for accomplishing switching is known in the art as CELLBUS® (a registered trademark of the assignee hereof TranSwitch, Corp.) which is described in detail in the previously incorporated patent application Ser. Nos. 08/960,499 and 08/961,932. The CELLBUS® mechanism is an asynchronous data transfer and source traffic control system which includes a bus master (switch controller) and a plurality of bus users (ports) coupled to a bidirectional data bus. The bus master preferably provides two clock signals to each bus user, a system clock and a frame clock. The frame clock designates the start of a frame. A frame format preferably includes fifteen or sixteen system clock cycles, the first of which is designated the request field and the last of which includes a grant field. One or more other cycles may be assigned control and/or routing information and the remainder of the cycles comprise a data field of fixed length. During the request field, any number of bus users may request access which is received by the bus master. During the grant field, the bus master grants access to a selected bus user for the entire data portion of the next frame. Which user is granted access to the next frame is determined according to an arbitration algorithm in the bus master which may be unknown to the bus users.
In the CELLBUS® system, as well as in other source traffic control systems, arbitration for access to the shared bus in order to accomplish switching is based on knowledge of the sender's identity. As described in the previously incorporated patent applications, simple arbitration algorithms, such as round-robin, may be used, resulting in the utilization of simple arbiters of low complexity and cost. While round-robin and other simple arbitration algorithms generally reduce the cost and complexity of the arbiters, additional cost is generated in the input buffers, as each input buffer must be long enough to allow for the time the port waits for bus access. More complex arbitration systems are known which reduce input buffer costs. However, regardless of the complexity of the arbitration system, no mechanisms are presently available in ATM switches which employ shared buses to reduce output port buffers. Indeed, in the systems of the art, it is not uncommon that long bursts from a single input port which are intended for a single output port are broken only by short bursts to other ports. This bursty traffic necessitates a worst case design of output port electronics at both a hardware and software level, as each port must be capable of accepting data at the speed of the bus for an indeterminate amount of time. The result is an expensive design with large high speed memories (buffers).
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide an ATM switch with an arbitration system which reduces output port buffer requirements.
It is another object of the invention to provide an ATM switch with means for tracking the internal destination of packets within the switch, and for limiting bursts destined for any particular output port.
It is an additional object of the invention to provide methods of controlling traffic within an ATM switch in order to reduce output port buffer requirements.
In accord with the objects of the invention, an ATM switch system is provided and generally includes a plurality of input ports with associated input buffer memories, a plurality of output ports with associated buffer memories, and a source traffic control system which preferably includes a shared bus which couples the input ports and the output ports, and a switch controller or arbiter which controls the transfer of data among the ports via the shared bus. In the preferred embodiment of the invention, each ATM cell which is placed on the shared bus includes the usual forty-eight bytes of data payload, several (e.g., four) bytes of predefined overhead (VPI, VCI, etc.), and several bytes of switch-specific information including an internal destination address (also called an internal routing field). The internal destination address designates the output port within the switch to which the ATM cell is destined.
According to the invention, means associated with the arbiter are provided to track the destinations of the ATM cells and prevent any particular output port from being overloaded by ongoing bursts of traffic. More particularly, in the preferred embodiment, the arbiter is coupled to the shared bus and monitors the destination address of each cell placed on the shared bus. The arbiter utilizes two or more counters, each having associated with it an address register containing the address of the output port which has most recently received or is presently receiving the traffic burst. The counter is incremented (preferably by one) each time a packet is sent to the specific destination associated with the counter. When a packet is sent to a destination other than the one for which the counter is tracking, the counter is decremented; preferably by a value greater than or equal to one). Accordingly, as a burst destined for a particular output port continues, the count of the counter grows large; whereas as breaks occur more frequently or for a long period of time, the count drops.
According to a preferred aspect of the invention, two thresholds are defined for the counters. A first (high) threshold is utilized to alert the arbiter that the buffer of the output port being tracked by the counter is in danger of overflowing. Upon receiving the alert, the arbiter either stalls the bus by refusing to grant access to the bus until the counter decrements below the first threshold, or alternatively grants bus access to the input port associated with the output port on the theory that the input port will not be sending data to its own output. A second (low) threshold is utilized to declare that a burst is over and to free the counter for tracking a new burst to the same or a different output port.
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: 4149144 (1979-04-01), Diefenderfer
patent: 4156798 (1979-05-01), Doelz
patent: 4375681 (1983-03-01), Abbott et al.
patent: 4460993 (1984-07-01), Hampton et al.
patent: 4488293 (1984-12-01), Haussmann et al.
patent: 4660169 (1987-04-01), Norgren et al.
patent: 4685101 (1987-08-01), Segal et al.
patent: 4727536 (1988-02-01), Reeves et al.
patent: 4750168 (1988-06-01), Trevitt
patent: 4763320 (1988-08-01), Rudolph
patent: 4789926 (1988-12-01), Clarke
patent: 4815074 (1989-03-01), Jacobsen
patent: 4817037 (1989-03-0
Parrella Eugene L.
Roy Subhash C.
Gallagher Thomas A
Gordon David P.
Hom Shick
Jacobson David S.
Olms Douglas W.
LandOfFree
Apparatus and method for limiting data bursts in ATM switch... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for limiting data bursts in ATM switch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for limiting data bursts in ATM switch... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497450