Patent ID: 7042878

Claim:
A method for self-routing a plurality of packets through a 2 n ×2 n switch, the switch having 2 n external input ports and 2 n external output ports labeled with 2 n distinct binary output addresses in the form of b 1 b 2 . . . b n , and composed of a plurality of switching cells interconnected into a k-stage bit-permuting network which is characterized by a guide γ(1), γ(2), . . . , γ(k) where γ is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, each of the packets destined for a rectangular set of output addresses represented by a quaternary sequence Q 1 , Q 2 , . . . , Q n , where each Q j is a quaternary symbol in any one of the three values: ‘0-bound’, ‘1-bound’, and ‘bicast’, wherein each of the switching cells is a sorting cell associated with the partial order “‘0-bound’ ‘bicast’ ‘1-bound’”, the method comprising: generating a routing tag Q γ(1) Q γ(2) . . . Q γ(k) for each of the packets based on the guide of the bit-permuting network and the destination output addresses of the packet, and routing each of the packets through the network by using Q γ(j) in the routing tag of the packet in the j-th stage cell, 1≦j≦k, to select an output or both outputs from the j-th stage cell to emit the packet.