Design and optimization of switching fabrics for ATM networks and parallel computer systems

Concentration operations play a central role in the construction of high performance ATM switching networks, and multiprocessor systems. The main objective of this dissertation is to optimize the design of concentrators, strong concentrators, and superconcentrators. We extend the probabilistic constructions of Pinsker, Bassalygo and Pippenger to obtain semi-explicit constructions with fewer crosspoints. More specifically, we show that, for n inputs, concentrators can be constructed with 19n crosspoints, superconcentrators can be constructed with 33n crosspoints, and generalizers can be constructed with 76.2...