Patent ID: 7136380

Claim:
A method for implementing a class of N×N compressors each serving a connection request to route m incoming signals, m≦N and for enabling the service of any connection request in a nonblocking way on the condition that the connection request is compliant to certain constraints, where each compressor in the class has a set of connection states and has an array of N input ports with N distinct input addresses and an array of N output ports with N distinct output addresses wherein the m incoming signals arrive at m distinct ones of the input ports determining m active input addresses and are destined for corresponding m distinct ones of the output ports determining m active output addresses, the method for each of the compressors comprising: configuring an N×N k-stage interconnection network comprises (i) k stages of nodes, (ii) an interstage exchange between any succeeding two of the k stages, (iii) an input exchange, and (iv) an output exchange, and each node is filled with a switch of N−1 or fewer input ports and output ports, and routing the incoming signals from the m distinct input ports to the corresponding m distinct output ports by activating one of the connection states such that the activated one of the connection states accommodates the connection request subject to said certain constraints on the connection request, wherein said certain constraints on the connection request are that: (1) the m active output addresses are consecutive upon a rotation of the ordering of the N output addresses, and (2) the correspondence between the m active input addresses and the m active output addresses is order preserving after the rotation, said class excluding (i) those having a switch constructed from the reverse banyan network of switching cells appended with the inverse shuffle exchange and (ii) those having a switch constructed from the reverse shuffle-exchange network of switching cells appended with the inverse shuffle exchange.