Integrated low complexity broadband multi-channel switch

Abstract

A multi-channel, multicasting switch for an ATM network utilizes a particular nonblocking condition of the Flip Network, which is exploited to realize a multi-channel switching architecture that supports an arbitrary number of channel groups. Using a single Flip Network recursively, the resulting architecture becomes efficient in the sense that the crosspoint complexity is O(N log 2 N) for N inputs. The number of times the Flip Network is used recursively is a function of the number of channel groups only. The architecture is internally nonblocking and bufferless. Distinguishing features are the abilities to provide multicasting, super-rate switching (i.e., rates that exceed the capacity of a single channel are accommodated), multi-rate switching (i.e., bit pipes of different rates are supported simultaneously), multiple performance requirements (i.e., services with different performance requirements are treated accordingly), and fairness (i.e., cells originating from different input channels and/or destined for different output channels are treated fairly). In multi-channel switching, cells belonging to a single session can traverse over multiple channels and the architecture maintains cells in order by assigning a specific Gray code to each data cell in each group.

What is claimed is: 
     
       1. A non-blocking switch for an ATM network having: a plurality of inputs for connection to a plurality of input channels over which a plurality of data cells arrive in a sequence;   a plurality of outputs over which said data cells are routed to i+1 output channels, where i is a nonnegative integer, said i+1 output channels being grouped into a plurality of channel groups; and   a processor for processing said data cells from said inputs to at least one of said channel groups, said processor assigning a first plurality of said data cells to outputs in a first channel group starting with output channel i, assigning a second plurality of said data cells to outputs in a second channel group starting with output channel i-1, and maintaining the sequence of said data cells as they are processed.   
     
     
       2. The switch of claim 1 wherein said processor sorts said data cells into said channel groups. 
     
     
       3. The switch of claim 2 wherein said processor comprises at least one NBGN. 
     
     
       4. The switch of claim 3 wherein said processor comprises a plurality of NBGN's. 
     
     
       5. The switch of claim 3 wherein said processor recycles said data cells through said NBGN to thereby sort said data cells into a greater number of channel groups. 
     
     
       6. The switch of claim 5 wherein said NBGN sorts said data cells into two channel groups so that said data cells are sorted into 2 r  channel groups by being recycled through said NBGN, where r equals the number of cycles required to separate said channel groups. 
     
     
       7. The switch of claim 6 wherein said NBGN has an output and further comprising a buffer at said NBGN output to separate in time each cycle of data cells through said NBGN. 
     
     
       8. The switch of claim 7 wherein the number of switch inputs equals a factor C times the number of input channels, where C equals a positive integer, and further comprising a buffer at the input of said NBGN. 
     
     
       9. The switch of claim 2 wherein said processor assigns said outputs in a Gray code order. 
     
     
       10. The switch of claim 1 wherein said processor maintains the sequence of the data cells according to their input channel and according to their time period. 
     
     
       11. A non-blocking switch for an ATM network having: a plurality of inputs for connection to a plurality of input channels over which a plurality of data cells arrive in a sequence;   a plurality of outputs over which said data cells are routed to a plurality of output channels, said plurality of output channels being grouped into a plurality of channel groups; and   a processor for processing said data cells from said inputs to at least one of said channel groups, said processor maintaining the sequence of said data cells as they are processed, said processor including a multicaster for multicasting at least a selected one of said input channels to a selected plurality of said output channel groups, said multicaster including an upstream broadcast network.   
     
     
       12. The switch of claim 11 wherein said data cells are processed such that their sequence is the same as they leave said switch through said outputs. 
     
     
       13. The switch of claim 11 wherein said multicaster recycles data cells. 
     
     
       14. The switch of claim 13 wherein said multicaster includes an NBGN, said NBGN having two groups of inputs, one of said input groups being reserved for recycled data cells. 
     
     
       15. The switch of claim 14 wherein said processor maintains the sequence of said data cells according to their input channel and according to their time period. 
     
     
       16. The switch of claim 15 wherein said NBGN processes the data cells appearing at said recycled data cell input group before the other of said group of inputs to said NBGN. 
     
     
       17. The switch of claim 16 wherein said multicaster sorts the data cells into a plurality of service classes, said service classes determining the priority for processing of said data cells through said switch. 
     
     
       18. The switch of claim 17 wherein said multicaster includes an RNBGN for sorting said data cells into the plurality of service classes. 
     
     
       19. The switch of claim 11 wherein said multicaster includes a plurality of NBGNs. 
     
     
       20. The switch of claim 19 wherein said multicaster includes a sum check. 
     
     
       21. A non-blocking switch for an ATM network having: a plurality of inputs for connection to a plurality of input channels over which a plurality of data cells arrive in a sequence;   a plurality of outputs over which said data cells are routed to a plurality of output channels, said plurality of output channels being grouped into a plurality of channel groups; and   a processor for processing said data cells from said inputs to at least one of said channel groups, said processor including an NBGN and a RNBGN, said NBGN sorting said data cells into a first group and a second group, said first group of data cells being recycled through said NBGN, said second group of data cells being channel grouped by said RNBGN.   
     
     
       22. The switch of claim 21 wherein said data cells are processed such that their sequence is the same as they leave said switch through said outputs. 
     
     
       23. The switch of claim 21 wherein said NBGN sorts said data cells according to whether said data cells are subject to contention. 
     
     
       24. The switch of claim 21 wherein said NBGN has two groups of inputs, one of said input groups being reserved for recycled data cells.