Scalable 2-stage interconnections

A switching network constructed from recursive 2-stage construction, one of the recursive steps constructing a modified 2-stage interconnection network, the modified 2-stage interconnection network comprising

• N/D P×M input nodes having output ports,
• M/D N×Q output nodes having input ports, and
• an interstage exchange interconnecting each one of the input nodes to each one of the output nodes with D lines, each of the lines interconnecting a distinct one of the output ports and a distinct one of the input ports, where D>1, and D is a common factor of M and N.

A switch based upon a plurality of opto-electrical-physical implementation levels comprising

• N/D first switching elements, each having P input ports and M output ports and having a configuration based on a first one of the implementation levels,
• M/D second switching elements, each having N input ports and Q output ports and having a configuration based on a second one of the implementation levels, and
• an interface circuit, which is compatible with both the first implementation level and the second implementation level, interconnecting each of the first switching elements to each of the second switching elements with D lines, each line interconnecting a distinct one of the output ports of the first switching elements and a distinct one of the input ports of the second switching elements, where D>1, and D is a common factor of M and N.

A method for routing a packet through a 2n−d×2n−d k-stage bit-permuting network constructed from modified 2-stage interconnection, the packet having a destination address expressed as D1D2. . . Dn−d, the network including 2r−d2n−r×2n−r input nodes, 2n−r−d2r×2r output nodes, and an interstage exchange induced by a permutation π on integers from 1 to n−d such that the images of the numbers r−d+1, r−d+2, . . . , n−d cover the numbers 1, 2, . . . , n−r−d, or equivalently, the images of the numbers 1, 2, . . . , r−d are covered by the numbers n−r−d+1, n−r−d+2, . . . , n−d, for 1<r<n and 1≦d<min(r, n−r), k>n−d, the method comprising

• generating a routing tag for the packet from the destination address D1D2 . . . Dn−d and the guide of the network expressed as γ(1), γ(2), . . . , γ(k), the routing tag being a k-symbol string Dγ(1)Dγ(2) . . . Dγ(k), and
• routing the packet at the j-th stage using Dγ(j) in the routing tag.