Switch preservation under two-stage interconnection: An algebraic theory for recursive construction of distributors and other types of switches

A switch is a device with multiple choices of configurations for I/O connections. Because of various constraints on the scale, a switch is often recursively constructed from a network of smaller ones. The 2-stage interconnection network is conceivably the most compact design for interconnecting small switches into a large switch. Switch preservation under 2-stage interconnection means that, when every node in a 2-stage interconnection network is filled with a small switch of a certain type with a certain property, the network constructs a large switch of the same type with the same property. Starting with small switches, recursive application of 2-stage interconnection then leads to indefinitely large switches.; Theorems on switch preservation under 2-stage interconnection are not just of theoretical interest, they are also timely for industrial implementations of high-speed switching fabrics with distributed control. The thesis considers various switches that are preserved under 2-stage interconnection. These switches can be categorized into two classes: control-independent switches and in-band controlled switches. A control-independent switch stipulates all possible configurations of concurrent I/O connections without specifying the switching control mechanism in the selection and activation of the configuration. Meanwhile, an in-band controlled switch activates concurrent I/O connections by control signals that are stored on the data packets.; The second half of the thesis deals with merge-style recursive construction of distributors. A distributor is a time-multiplexed switch that routes active input signals to output ports in the round-robin fashion. The Merge-Distribute algorithm proposed in the thesis for the recursive construction of distributors is analogous to the Mergesort algorithm for the recursive construction of sorting networks. The key component in the Merge-Distribute algorithm is a merge-distributor (MD), which is the counterpart to the merger in Mergesort. A large MD is constructed from a 2-stage interconnection network of small MDs and circular-unimodal distributors ( CUDs), which are preserved under 2-stage interconnection. Thus, CUDs are recursively constructed through 2-stage interconnection and used in the construction of MDs through 2-stage interconnection. MDs in turn are used in the Merge-Distribute algorithm for recursive construction of distributors. In the special case when N = 2n, this triply recursive procedure yields N x N distributors in the form of n(n+1)/2-stage networks.; Compared to the proposed constructions of distributors up to date, the Merge-Distribute algorithm achieves the best known depths for distributors of all sizes within the practical range. The rigorous algebraic formulation not only keeps the algorithmic construction transparent but also affords many variations in the construction so as to flexibly cope with ad hoc engineering constraints in implementation.