On non‐blocking switching networks

Abstract

A switching network may be informally described as a collection of single‐pole, single‐throw switches arranged so as to connect a set of terminals called inputs to another set of terminals called outputs. It is non‐blocking if, given any set of connections from some of the inputs to some of the outputs, and an idle input terminal x and idle output terminal y, then it is possible to connect x to y without disturbing any of the existing connections. Denote by σ(a, b) the minimal number of switches necessary to connect a inputs to b outputs using a non‐blocking network. We are interested in studying the growth of σ(a, a) as a → ∞. Results of C. Clos show that σ(a, a) ⩽ C ae^{2√log a·log 2}. We show that σ(a, a) ⩽ 8a(log₂a)².