Theory on switch preservation under 2-stage interconnection

The most compact pattern for interconnecting small switches into a large switch is conceivably the 2-stage interconnection network A certain version of a 2-stage interconnection network is said to preserve switches with a certain attribute when the network constructs such a switch from smaller ones at nodes. Recursive application of this version of 2-stage interconnection then leads to the construction of indefinitely large switches with the same attribute. The present paper studies a few new classes of switches that are preserved under 2-stage interconnection and also identifies their applications. Different switch preservation theorems presented in the paper offer the advantages of both the algorithmic flexibility and the theoretic insight.