Patent ID: 7065073

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 address in the form of b 1 b 2 . . . b n with b indistinguishable output ports, and (b) k super-stages of concentrators wherein each of the concentrators is a 2b×2b partial sorting network of interconnected routing cells and b of its 2b output ports are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, the network being characterized by the guide γ(1), γ(2), . . . , γ(k), where y 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 the output group at the binary destination address d 1 d 2 . . . d n , or an idle packet having no pre-determined destination, generating a routing tag 1 d γ(1) d γ(2) . . . d γ(k) for the real data packet with reference to the guide of the network and the destination address of the packet, and routing the real data packet through the network by using 1 d γ(j) in the routing tag in the j-th super-stage concentrator, 1≦j≦k, to select between the 0-output group or the 1-output group of the j-th super-stage concentrator to emit the real data packet.