Self-routing control mechanism over multistage interconnection networks of concentrators

A method for self-routing a packet through a b2n×b2n switching network, the network:

• including 2n output groups, each of the output groups having a distinct binary address in the form of b1b2 . . . bn with b indistinguishable output ports, and 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;
• and 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 d1d2 . . . dn, or an idle packet having no pre-determined destination, the method comprising
• generating the routing tag 1dγ(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 1dγ(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.

A method for self-routing a plurality of real data packets through a b2n×b2n switching network, the switching 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 having (a) b2n external input ports, (b) 2n output groups, each of the output groups having a distinct binary address in the form of b1b2 . . . , bn with b indistinguishable output ports, and (c) k super-stages of 2b-to-b concentrators wherein each of the concentrators is a 2b×2b partial sorting network of interconnected routing cells where each of the routing cells is a sorting cell associated with the partial order “10 (‘0-bound’)00 (‘idle’)11 (‘1-bound’)”, b of the 2b output ports of each of the concentrators are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, and extra circuitry arranged at the output end of each of the concentrators wherein the extra circuitry is composed of 2b parallel 1×1 switching elements, one at each of the output ports of the concentrator, and each of the real data packets arriving at a distinct external input port determining an active input port and destined for an output group at the binary destination address d1d2 . . . dn, the method comprising

• generating an idle packet as a stream of ‘0’ bits at each of the non-active external input ports,
• generating a routing tag 1dγ(1)dγ(2) . . . dγ(k) for each of the real data packets with reference to the guide of the network and the destination address of the packet,
• generating a routing tag which is a string of k+1 ‘0’ bits for each of the idle packets,
• routing the real data packets and the idle packets through the network by sorting the packets by the 2b-to-b concentrators of the network, wherein the sorting at each of the concentrators includes the sorting at each of the sorting cells of the concentrator such that the sorting is with respect to the associated partial order and is based upon the leading two bits, which are either ‘10’ or ‘11’ for a real data packet, or ‘00’ for an idle packet, of the routing tag of each of the two packets arrived at each of the sorting cells, and
• processing the routing tag of each of the packets by the extra circuitry at the output end of the concentrator before the said each of the packets exits from the j-th super-stage concentrator by removing the second leading bit from the routing tag or rotating the second leading bit to the end of the routing tag such that the leading two bits of the routing tag of each of the packets at each of the j-th super-stage concentrators, 1≦j≦k, are always ‘1dγ(j)’ or ‘00’.

A system for self-routing a plurality of real data packets comprising

• a b2n×b2n switching network having a plurality of 2b-to-b concentrators interconnected into a k-stage bit-permuting network characterized by guide γ(1), γ(2), . . . , γ(k) where γ is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, and having (a) b2n external input ports, (b) 2n output groups, each of the output groups having a distinct binary address in the form of b1b2 . . . bn with b indistinguishable output ports, and (c) k super-stages of 2b-to-b concentrators wherein each of the concentrators is a 2b×2b partial sorting network of interconnected routing cells where each of the routing cells is a sorting cell associated with the partial order “10 (‘0-bound’)<00 (‘idle’)<11 (‘1-bound’)”, b of the 2b output ports of each of the concentrators are grouped into a 0-output group while the remaining b output ports are grouped into a 1-output group, and extra circuitry arranged at the output end of each of the concentrators wherein the extra circuitry is composed of 2b parallel 1×1 switching elements, one at each of the output ports of the concentrator, and wherein each of the real data packets arrives at a distinct external input port and is destined for an output group at the binary destination address d1d2 . . . dn,
• idle-packet-generating circuitry, coupled to the external input ports, for generating an idle packet as a stream of ‘0’ bits at each of the external input ports of the switching network if no real data packet arrived at that external input port,
• routing tag circuitry, coupled to the external input ports, for generating a routing tag 1dγ(1)dγ(2) . . . dγ(k) for each of the real data packets with reference to the guide of the network and the destination address of the packet, or generating a routing tag which is a string of k+1 ‘0’ bits for each of the idle packets,
• routing control circuitry, coupled to the concentrators, for routing the real data packets and the idle packets through the network by sorting the packets by the 2b-to-b concentrators of the network, wherein the sorting at each of the concentrators includes the sorting at each of the sorting cells of the concentrator where the sorting is with respect to the associated partial order and is based upon the leading two bits, which are either ‘10’ or ‘11’ for a real data packet, or ‘00’ for an idle packet, of the routing tag of each of the two packets arrived at the cell, and
• extra circuitry at the output end of the j-th super-stage concentrator, 1≦j≦k, for processing the routing tag of each of the packets before the said each of the packets exits from the j-th super-stage concentrator by removing the second leading bit from the routing tag or rotating the second leading bit to the end of the routing tag such that the leading two bits of the routing tag of each of the packets at each of the j-th super-stage concentrators, 1≦j≦k, are always ‘1dγ(j)’ or ‘00’.