Patent ID: 7079532

Claim:
A method for self-routing a packet through a b2 n ×b2 n switching network comprising configuring the switching network with (a) 2 n output groups, each of the output groups having a distinct binary output group address in the form of b 1 b 2 . . . b n with b indistinguishable output ports, and (b) k super-stages of 2b-to-b multicast concentrators wherein each of the multicast concentrators is a 2b×2b partial sorting network of interconnected bicast cells and b of its 2b output ports are grouped into a 0-output group with the remaining b output ports being grouped into a 1-output group, the network being characterized by the guide γ (1), γ(2), . . . , γ(k), where γis a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and wherein the packet is either a real data packet destined for a rectangular set of output group addresses represented by a quaternary sequence Q 1 , Q 2 , . . . , Q n , where each Q j is a quaternary symbol in any of the three values representing ‘0-bound’, ‘1-bound’ or ‘bicast’, or an idle packet having no pre-determined destination, generating a routing tag Q γ(1) Q γ(2) . . . Q γ(k) for the packet with reference to the guide of the network and the destination output group addresses of the packet, wherein each Q γ(j) , 1≦j≦k, has a value representing ‘idle’ if the packet is an idle packet or has one of the three values representing ‘0-bound’, ‘1-bound’ or ‘bicast’ if the packet is a real data packet, and routing the packet through the network by using Q γ(j) in the routing tag of the packet in the j-th super-stage multicast concentrator, 1≦j≦k, to select an output group or both output groups from the j-th super-stage multicast concentrator to emit the packet.