Switching system for telecommunication networks

The present invention is directed to a high performance broadband ATM switching system comprised of concentrator, non-recirculating sort-trap and queuing stages. The concentrator stage concentrates cells entering the switch by discarding idle inputs thereto. Cells arriving at the non-recirculating sort-trap stage during a time slot are sorted based upon destination address and priority. Cells having a unique address for the time slot are placed in a corresponding output queue while cells having non-unique destination addresses are re-routed to a trap buffer which ages the cell until a subsequent time slot in which the destination address is unique.

CROSS-REFERENCE TO RELATED APPLICATIONS

Not applicable.

Not applicable.

REFERENCE TO A MICROFICHE APPENDIX

Not applicable.

FIELD OF THE INVENTION

The invention is directed to a switching system for telecommunication networks. The switching system achieves enhanced throughput by incorporating a three-stage, non-recirculating configuration thereinto.

BACKGROUND OF THE INVENTION

Over the years, switching systems having a wide variety of architectures have been developed for use in telecommunication networks. A “crossbar” switch is a single-stage, single-path, non-blocking switch. Broadly speaking, an N by N crossbar switch consists of a square array of N2individually operated crosspoints, one for each input-output pair, having two possible states—cross (default) and bar. For such an N by N crossbar switch, a connection between input port i and output port j is established by setting the (i, j) crosspoint switch to the bar state.

Crossbar switches have always been attractive to switch designers because they are non-blocking, relatively simple in architecture and modular in nature. Originally developed for circuit switching, many asynchronous transfer mode (“ATM”) switching systems are either based on the crossbar switch or use it as their basic building block. Crossbar switches do, however, have several drawbacks. First and foremost, crossbar switches have a square growth of complexity. As a result, they do not scale well to large sizes. Additionally, different input-output pairs of a crossbar switch may have different transit delays. As a result, a fairness problem arises when the crossbar switch is operated in a self-routing mode. Finally, despite being non-blocking, crossbar switches suffer from output blocking. As a result, buffers are oftentimes necessary to reduce cell losses in ATM switching systems based upon crossbar switch technology.

Other ATM switching systems are based upon a network architecture commonly referred to as a “Banyan” network. Besides being self-routing, Banyan network-based switching systems are modular, generally have the same latency for all input-output pairs, support synchronous and asynchronous modes of operation, are suitable for very large scale implementation (“VLSI”) implementations, and enjoy reduced complexity in comparison to the crossbar switch. However, while the Banyan network's path-uniqueness characteristic preserves cell sequencing in Banyan network-based switching systems, it results in the switching systems being internally blocking. Thus, while the Banyan network-based switching systems and the crossbar switch-based switching systems both suffer from degraded performance when the size of the switching system is increased, the degradation is more significant for the Banyan network-based switching systems because the crossbar switching system suffers only from output blocking while the Banyan network-based switching system suffers from both output blocking and an internal blocking which increases in severity with the number of stages therein.

A Banyan network-based switching system may become non-blocking if incoming cells are ordered according to their output port addresses and concentrated to remove any gaps between active inputs if output conflicts do not exist. A network architecture which, if incorporated into a Banyan network-based switching system, that can perform distributed parallel sorting is generally referred to as a “Batcher” sorter network. An N by N Batcher sorter network can be constructed using log2(log2N+1)/2 stages, each with N/2 sorting elements, for example, binary comparators. A Batcher sorter network can sort an arbitrary set of active cells based upon their output port addresses and group them consecutively at either the bottom or top of its output ports.

An ATM switching system150which combine the aforedescribed Batcher sorter and Banyan networks is illustrated inFIG. 1a.The ATM switching system150, commonly referred to as a “Sunshine” switching system, is comprised of a Batcher sorter network152, trap network154, a concentrator156, a selector158, a recirculating buffer160, a parallel array of Banyan networks162-1through162-N and a parallel array of output buffers164-1through164-N. Cells input the ATM switching system150first enter the Batcher sorter network152. The Batcher sorter network152arranges the cells in order of destination address and priority. The sorted cells proceed to the trap network154for resolution of output port contention. More specifically, the trap network154resolves output port contention by selecting the k highest priority cells present for each destination address within a time slot for routing to the parallel array of Banyan networks162-1through162-N. Any excess cells for each destination address are selected for routing to the recirculation buffer160from those to be routed to the parallel array of Banyan networks162-1through162-N and the selector158selectively directs the separated cells to either the recirculation buffer160or the parallel array of Banyan networks162-1through162-N as appropriate.

The parallel array of k Banyan networks162-1through162-N provides k independent paths for cells to access the output buffers164-1through164-N. Thus, as many as k cells may request a single destination address in a single time slot. If more than k cells request the same destination address, the excess cells are instead directed into the recirculating buffer160. There, the excess cells are held until the next time slot and then resubmitted to the Batcher sorter network152. Thus, ATM switching system150recirculates excess cells requesting the same address and must dedicate a number of input ports for recirculating cells. Accordingly, while the ATM switching system150can handle k cells requesting the same destination address, once the number of cells requesting that destination address exceeds k, performance of the ATM switching system150begins to suffer. Finally, because the ATM switching system150cannot be readily partitioned into integrated circuits, its commercial applicability is relatively limited.

Another ATM switching system166which incorporates a Batcher sorter network, here, without an associated parallel array of Banyan networks, is illustrated inFIG. 1b.The ATM switching system166, commonly referred to as a “Starlite” switching system, includes a concentrator168, a Batcher sorter network170, a trap network172, a recirculation buffer174and an expander176. For the ATM switching system166, cells arriving at the Batcher sorter network170within a time slot are sorted based upon destination address. The outputs of the Batcher sorter network170are fed into the trap network172in ascending order. The trap network172detects plural cells having the same destination address and allows only one of the plural cells destined to the same output port to be admitted to the expander176. The remaining cells destined to that output port are recycled back to the Batcher sorter network170through the recirculation buffer174. While the ATM switching system166suffers from a number of deficiencies, one of the more glaring of such deficiencies is that, in order to reduce cell loss within the recirculation buffer174a substantial fraction of the input ports of the Batcher sorter network170must be dedicated for cells being recirculated from the trap network172via the recirculating buffer174. In the absence of such a need, these input ports would instead be dedicated to the concentrator168. Thus, because of the need to dedicate a substantial number of ports to the recirculation buffer174, the probability of cell loss within the concentrator168increases and the overall utilization rate of the ATM switching system166decreases substantially.

This invention improves on current switching systems such as the aforementioned Starlite and Sunshine switching systems by providing the advantages of a higher performance switching system without need of relatively complex hardware configurations therefor.

SUMMARY OF THE INVENTION

The present invention is directed to a multi-stage switching system for a telecommunications network. In various embodiments thereof, the multi-stage switching system may include concentrator, non-recirculating sort-trap, and/or queuing stages and, if multi-casting is desired, a broadcast network. The concentrator stage concentrates cells entering the switching system by discarding idle inputs. The non-recirculating sort-trap stage, which may include a Batcher sorter as a component thereof, places each cell having a unique destination address and arriving, at the non-recirculating sort-trap stage, in a first time slot, onto a selected output while aging those arriving cells having a non-unique destination address. The queuing stage buffers cells having a common destination address to be output the switching system via output ports thereof. Finally, the broadcast network, which is typically placed on the input side of the no-recirculating sort-trap stage copies data from selected ones of a plurality of source cells to selected ones of a plurality of empty copy cells to produce copies of the source cells for broadcast to multiple destination addresses.

In one aspect thereof, the non-recirculating sort-trap stage includes sort and non-recirculating trap substages. Within the sort substage, cells arriving in a time slot are sorted based upon destination address and, for common destination addresses, priority. Next, within the non-recirculating trap substage, the cells having a unique destination address are placed on a selected one of the outputs thereof while the cells having a non-unique destination address are aged until a subsequent time slot during which the destination address for that cell becomes unique. The aged cell is then placed on a selected output of the non-recirculating trap substage. In various further aspects thereof, a “unique” destination address may be, for plural cells having a common destination address, that cell which has the highest priority among the plural cells.

DETAILED DESCRIPTION OF THE INVENTION

Referring now toFIG. 2, a telecommunications network178incorporating a switching system180constructed in accordance with the teachings of the present invention will now be described in greater detail. As disclosed herein, the telecommunications network178is a broadband integrated data services network (“BIDSN”), a telecommunications network having a network architecture which utilizes asynchronous transfer mode (“ATM”) as its communication protocol. Of course, the present disclosure of the telecommunications network178as a BIDSN is purely by way of example and it is fully contemplated that the telecommunications network may be any broadband or other telecommunication network utilizing the ATM communication protocol. For example, the telecommunication network may be a private ATM network. Furthermore, the ATM telecommunication network may be configured as either a connection-oriented network service (“CONS”) packet switched network or a connectionless network service (“CLNS”) packet switched network. In turn, the CONS ATM telecommunication network may be operated using either permanent virtual connections (“PVCs”) or switched virtual connections (“SVCs”).

First and second ATM switching systems180and182are coupled to the telecommunication network178by an ATM switching fabric184. Each of the first and second ATM switching systems180and182provide telecommunication services to plural end terminals. For example, the first ATM switching system180provides telecommunication services to end terminals186-1through186-X while the second ATM switching system184provides telecommunication services to end terminals188-1through188-Y. Of course, the disclosure of the first and second switching systems178and180as ATM switching systems is purely exemplary and it is fully contemplated that, in alternate embodiments thereof, the first and second switching systems178and180may instead be configured to employ any one of a multitude of other packet switching protocols currently in use. Furthermore, while in the embodiment of the invention disclosed inFIG. 1, the end terminals186-1through186-X and188-1through188-Y are all configured as voice terminals, it should be clearly understood that the end terminals186-1through186-X and188-1through188-Y may instead all be configured as voice, data, video, or multimedia terminals and/or some combination thereof. Finally, it should be fully understood that, as illustrated inFIG. 1, the telecommunications network178has been greatly simplified and that various components thereof, for example, a router to which the first ATM switching system180would direct internet protocol (“IP”) traffic, a frame switch to which the first ATM switching system180would direct frame-relay traffic and a voice/data gateway to which the first ATM switching system180would direct voice-over-ATM traffic, have all been omitted for ease of description.

Referring next toFIG. 3a,the first ATM switching system180will now be described in greater detail. As may now be seen, the first ATM switching system180is comprised of a concentrator stage200, a non-recirculating sort-trap stage202and a queuing stage204. ATM cells entering the first ATM switching system180at input ports201-1through201-N first enter the concentrator stage200. A typical ATM cell similarly structured to those entering the concentrator stage200is set forth in Table I, below.

TABLE ICONTROL HEADER (5 BYTES)DATA PAYLOAD (48 BYTES)
For an ATM cell, control information is maintained in a header portion of the cell while data is maintained in a payload portion thereof. The control information maintained in the header includes a destination address to which the data payload is to be directed and a priority field which identifies the priority of a data payload destined to a particular destination address relative to other data payloads destined to the same destination address.

Within the concentrator stage200, an N input to L output concentration is performed on the entering ATM cells. More specifically, if there are k cells arriving in a time slot for a given output, after passing through the concentrator stage200, all k cells will emerge on outputs 1 to k, if, of course, k≦L. In this manner, the concentrator stage200can reduce the size of the stages that follow, here, the non-recirculating sort-trap stage208and the queuing stage202by compacting all of the active input ports. If k>L, however, then all L outputs of the concentrator stage200will have cell thereon and k L cells will be dropped within the concentrator stage200.

Referring next, in combination toFIGS. 3aand3b,the cells exiting the concentrator stage200enter the non-recirculating sort-trap stage202for resolution of potential output port contentions. More specifically, cells entering the non-recirculating sort-trap network202in a time slot pass through, in sequence, a sort substage206and a non-recirculating trap substage208. Within the sort substage206, which, for example, may be a Batcher-type sorter network, the entering cells are sorted based upon their respective control headers and then arranged in ascending order of destination address. For cells having the same destination address, the priority field is used to sort cells destined to a common address. More specifically, a lower numerical value in the priority field is represented as a higher priority level. Thus, for an output line i, of the sort substage206, cell addresses in the sorted list increase as i increases, and for identically addressed cells, cell priority decreases as i increases.

Once the cells are sorted based upon destination address and, for cells sharing a common destination address, priority, the cells continue to the non-recirculating trap substage208. Within the non-recirculating trap substage208, unique addresses are spotted by the trap circuitry (which typically includes a comparator array for spotting unique and non-unique addresses) and routed towards one side of the output lines, for example, towards output line211-L while non-unique addresses are routed towards the other side of the output lines, for example, towards output line211-1. As used herein, a cell is deemed to have a “unique” destination address if, for a given time slot, no other cell has the same destination address. If, for that same given time slot, plural cells share a common destination address, the cell having the common destination address and the highest priority among the plural cells is also deemed to have a “unique” destination address while those of the plural cells having the common destination address and a lower priority are deemed to have a “non-unique” destination address.

Accordingly, to separate the cells in accordance with the aforementioned definition of “unique” and “non-unique”, the comparator array of the non-recirculating trap substage208are configured to pass each cell if the cell has a previously unencountered destination address but will flag each cell having a previously encountered destination address. While various techniques may be used to “flag” a cell, one suitable technique would be to select an unused control bit within the control header of the data cell and designate the selected bit as the non-unique destination address bit. Cells exiting the comparator array may then be separated into unique and non-unique groups by routing the cells having the selected control bit set towards one side of the non-recirculating trap substage208while routing the cells having the selected control bit unset towards the other side.

While the non-recirculating trap substage208separates cells having unique and non-unique destination addresses by identifying those cells having non-unique addresses and routing the identified cells towards one side of the non-recirculating trap substage208, to minimize re-routing of cells within the non-recirculating trap substage208, the prior sort of cells based upon destination address and priority is maintained within the separated groups of cells. If desired, the cells identified as having non-unique addresses may be discarded. Preferably, however, the cells identified as having non-unique addresses are temporarily stored in trap buffer210until a subsequent time slot and then released back onto the lines211-1through211-L of the non-recirculating trap substage208. Of course, to preserve sequencing of the trapped cells, cells are released according to their age. Thus, it is contemplated that one suitable configuration of the trap buffer211would be as a first-in-first-out (“FIFO”) buffer. It is further contemplated that, to enhance throughput of the switching system180under various load conditions, the depth of the trap buffer210may be increased. However, it should be noted that, by increasing the depth of the trap buffer210, the construction cost of the switching system180is also increased. As a result, in selecting the depth of the trap buffer210, the enhanced performance of the switching system180should be weighed against the resultant increase in construction cost. Accordingly, hereinafter, the depth of the trap buffer210shall be identified as “M”.

Finally, in various configurations thereof, the width of the trap buffer210may be varied between I and N. Widths less than L are generally less preferred since such configurations would require arbitration circuitry to handle time slots where L cells attempt to enter a lesser number of buffers. Thus, a more suitable width would be L. In such a configuration, each line211-1through211-L would be coupled to a corresponding FIFO or other type of buffer. Again, however, since the L lines of the non-recirculating sort trap stage202were concentrated from the N input ports201-1through201-N of the switching system180, a drawback to configuring the trap buffer210to have a width of L is that, for a given line i, in a first time slot, the cell on that line may have a first destination address while, in a subsequent time slot, the cell on that line may have a second destination address. If so, various ones of the FIFOs or other buffers forming the trap buffer210may simultaneously hold cells having different destination addresses. As a result, the return of the trapped cells to the non-recirculating trap substage210would be much more complicated since the destination address of each returning cells may need to be determined to ensure proper routing thereof. Thus, in another alternate configuration, it is contemplated that the trap buffer210may have a width of N. For such a configuration, each cell re-routed to the trap buffer210would be placed in a selected one of the N FIFO or other type of buffers based upon the destination address for that cell. If multiple cells re-routed to the trap buffer210have the same destination address, the cells may all be placed in the same buffer, if desired, in order of priority.

It is contemplated that a variety of techniques may be used to release the trapped cells held in the trap buffer210back onto the lines211-1through211-L of the non-recirculating trap substage210. For example, if the trap buffer210is a FIFO buffer, the non-unique cells having a first destination address which are routed to the trap buffer210in a first time slot may simply be released onto the same lines211-1through211-1from which they were rerouted in a subsequent time slot related to the depth of the trap buffer. For example, if the depth of the trap buffer is 2, the non-unique cells having the first destination address would be released after two additional time slots have elapsed. While a non-recirculating trap substage208utilizing such a release technique would be quite easy to construct, it is generally considered less desirable because the released cells would still have to contend with the subsequent cells passing through the non-recirculating trap substage210for output ports of the switching system180and, while, in contrast to when the trap cells first entered the non-recirculating sort-trap stage, the likelihood of conflicting cells has been reduced, the likelihood of a conflicting cell being dropped within the non-recirculating trap substage208may still be too great.

In an alternate, generally more preferred, configuration thereof, a cell held in the trap buffer210may be released whenever it is determined, for a subsequent time slot, no cell shares the destination address with the cell to be released. Thus, a cell is placed into the trap buffer210if, for a first time slot, it has a non-unique destination address. That cell is then released in a subsequent time slot in which its destination address has become unique. Thus, cells having conflicting addresses are held in the trap buffer210until they are no longer conflicting. It is contemplated that a non-recirculating trap substage208utilizing such a release technique would likely require additional logic circuitry not shown inFIG. 3b.For example, logic circuitry which monitors: (1) which destination addresses are on the lines211-1through211-N in each time slot and (2) for which destination addresses, are cells being held in the trap buffer210. If the logic circuitry determines that a cell being held in the trap buffer210has a destination address that is not shared by any of the cells passing through the non-recirculating trap substage208in a subsequent time slot, the logic circuitry would then release, from the trap buffer210, the cell having a unique destination address for the subsequent time slot.

In still another alternate configuration thereof, the cells held in the trap buffer210may simply be recycled, i.e., returned to a front end of the non-recirculating trap substage208to compete with cells in a subsequent time slot in the manner previously set forth. To enhance cell sequencing, the aged cells released from the buffer may have their priority reset to the highest possible priority so that, in the event that the released cell shares a destination address with a cell entering the non-recirculating trap substage208in a subsequent time slot, the aged cell will have a unique destination address and the younger cell will have a non-unique destination address and will be re-routed to the trap buffer210. While such a configuration is suitable for the uses contemplated herein, one drawback to such a technique is that, by returning the released cells to the front end of the non-recirculating trap substage208for recycling, the speed of the non-recirculating trap substage208may be reduced.

Coupled to each output of the non-recirculating sort-trap network202is a corresponding output queue204-1through204-N. As disclosed herein, each output queue204-1through204-N is configured as a FIFO buffer. However, it is fully contemplated that various other buffer configurations not disclosed herein would be equally suitable for the uses contemplated herein. Cells exiting respective outputs of the non-recirculating trap substage208of the non-recirculating sort-trap network202enter a corresponding output queue204-1through204-N. Thus, all of the cells entering a selected one of the output queues204-1through204-N share the same destination address. The cells in each one of the output queues204-1through204-N await their turn to access a corresponding output port213-1through213-N coupled thereto from which the cells propagate to their destination address.

Referring toFIG. 4, an alternate embodiment of the switching system180, hereafter referred to as switching system180′ will now be described in greater detail. As will be more fully described below, the switching system180has been modified, relative to the switching system180, so that the switching system180′ may perform multi-casting functions. The switching system180′ differs from the switching system180in that the concentrator stage200has been removed and a broadcasting network212added. The broadcasting network212has an input side coupled to the input ports201-1through201-N and an output side coupled to the input side of the non-recirculating sort-trap stage202. If desired, however, a concentrator stage configured similarly to the concentrator stage200could be place between the input ports201-1through201-N and the broadcasting network212. By adding a concentrator stage in this manner, it is contemplated that idle sources and unused copy packet inputs may be eliminated before entering the broadcasting network212.

As may be further seen inFIG. 4, the broadcasting network212is comprised of a source sort stage214and a copy stage216. The source sort stage214has an input side coupled to the input ports201-1through201-N and an output side coupled to an input side of the copy stage216. The output side of the copy stage216, on the other hand, is coupled to the input side of the non-recirculating sort-trap stage202. Unlike the switching system180, two types of data cells may arrive at the source sort stage214of the broadcasting network212—source data cells and empty copy cells. Unlike the data cell illustrated in Table I, in addition to a destination address, the control header of the source data cells include a source address which indicates where the data cell originated. The control header of a source data cell also includes a copy bit which is set to “0” to indicate that the source data cell is an original cell.

Empty copy cells are automatically input the source sort stage by an empty copy cell generator (not shown). Typically, the empty copy cell generators are controlled by either users transmitting data to be multi-cast to multiple destinations or by a receiver interested in getting copies of data deemed suitable, by the source, for transmission to the receiver. Using a low bandwidth link to the input side of the source sort network214, the empty copy cell generator generates empty copy cells having an empty data payload and a control header which contains the source address where the original data cell originated, a destination address for a recipient of a copy cell, and a copy bit set to “1” to indicate that the cell is a copy.

The source sort stage214sorts the data cells and empty copy cells based upon source address and, for plural cells sharing a common source address, copy bit, to order the entering cells such that their source addresses increase from left to right. Thusly, empty copy cells are grouped together with the corresponding data source cell on physical adjacent lines. For example, inFIG. 4, the cells entering on line201-2and201-3are source cells having respective source addresses. The cells on line201-5is an empty copy cell which shares a source address with the source cell on line201-2while the cells on lines201-4and201-6are empty copy cells which share a source address with the source cell on line201-3.

Following the source sort stage214is an N by (log2N) copy stage216which takes the information contained in the data payload for each entering source cell and copies that information into each entering empty copy cell sharing the source address. To perform this operation, the copy stage216searches the incoming cells for source cells. More specifically, starting on the leftmost input line thereinto, the copy stage examines the contents of the copy bit for each incoming cell. If the copy bit indicates that the incoming data cell is a source cell, the contents of the data payload is copied into the payload for the adjacent cell to the right of the source cell if the copy bit for the adjacent cell indicates that it is a copy cell. The copy stage216repeats this copy operation for each cell to the right of the source cell until a next source cell is encountered. The contents of the data payload for the next source cell is then copied into all copy cells adjacent thereto. Having filled all of the empty copy cells with data from the appropriate source cell, all of the data cells now contain the desired data. Accordingly, the data cells exit the broadcast network212and proceed to the non-recirculating sort-trap stage202for further handling in the manner previously described.

Thus, there has been described and illustrated herein, a relatively simple and inexpensive three-stage, non-recirculating switching system which enjoys enhanced throughput in contrast to other switching systems. However, those skilled in the art will recognize that numerous changes and modifications may be made in the switching system disclosed herein without departing from the spirit of the invention. Accordingly, the scope of the invention should be defined only be the appended claims.