Nonblocking minimal spanning switch

A nonblocking minimal spanning switch is a concept developed in the 1950s to reduce the costs of telephone exchanges in the Bell System by reducing the number of the most expensive components of a telephone switch.

This reflects a key problem in the AT&T Bell System prior to divestiture in 1984, which was

providing satisfactory (from the customer point of view) end-to-end service at the lowest possible cost.

Historically, in telephone switches, connections between callers were arranged with Strowger switches, which were large, expensive banks of electromechanical relays. Later the Strowger switches were replaced by crossbar switches, which used a matrix of connections (called crosspoints) to set up calls.

The Operations Research Department at Bell Labs and other technical staff focused on developing mathematics and computer tools to minimize costs subject to constraints. In the context of making telephone connections, this was taken to mean minimizing the number of the most expensive switch components -- the crosspoints -- subject to the constraint of still being able to connect any two idle telephones on request.

In the 1940s and 1950s, engineers in Bell Lab began an extended series of mathematical investigations into methods for reducing the size and expense of the "switched fabric" needed to implement a telephone exchange. For this purpose a minimal non-blocking network of crossbar switches would be any device that can connect N inputs to N outputs in any sequence while using as few crosspoints as possible. The term "non-blocking" means that if the switch is not defective, it can always make the connection. The term "minimal" means that it has the fewest possible crosspoints, and therefore the minimal expense.

The mathematical analysis that establishes the conditions under which a switching network is minimal non-blocking was performed by Charles Clos, and a switched fabric constructed of smaller switches is called a Clos network.