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.
Background: switching topologies
The crossbar switch The crossbar switch has the property of being able to connect N inputs to N outputs in any one-to-one combination, so it can connect any caller to any non-busy receiver, a property given the technical term "nonblocking". Being nonblocking it could always complete a call (to a non-busy receiver), which would maximize service availability.
However, the crossbar switch does so at the expense of using N2 (N squared) electrical connections, or crosspoints, implemented by simple SPST switches. The diagram shows a crossbar switch with N=4. The crosspoints are represented by filled circles. There are 16 crosspoints, one for each combination of input and output. When a crosspoint is activated, the corresponding input and output are connected. For large N (and the practical requirements of a phone switch are considered large) this growth was too expensive. Further, large crossbar switches had physical problems. Not only did the switch require too much space, but the metal bars containing the switch contacts would become so long that they would sag and become unreliable. Engineers also noticed that at any time, each bar of a crossbar switch was only making a single connection. The other contacts on the two bars were unused. This seemed to imply that most of the switching fabric of a crossbar switch was wasted.
Completely connected 3-layer switches One way to reduce the cost of a crossbar switch is to emulate it with smaller crossbar switches. These smaller crossbar switches could also, in turn be emulated by even smaller crossbar switches. The switching fabric could become very efficient, and possibly even be created from standardized parts. A Clos network does this. The approach is to break apart the crossbar switch into three layers of smaller crossbar switches. There is an "input layer", a "middle layer" and an "output layer." The smaller switches are less massive, more reliable, and generally easier to build, and therefore less expensive. In addition, compared to large crossbar switches, the multi-layer switching fabric uses fewer crosspoints.
Suppose we want to synthesize a 9 by 9 crossbar switch. The design could have 3 switches on the input side, each with 3 inputs, for 9 total inputs. Further, on the output side, we could also have 3 output switches, each with 3 outputs, for a total of 9 outputs. Every input and output switch will be connected to every middle switch. The goal is to use as few crosspoints as possible, because crosspoints are an expensive component of a switch. The questions are how many middle switches are needed to provide a nonblocking fabric, thus emulating a crossbar switch, and will the number of crosspoints be reduced? Charles Clos showed in his 1953 paper that the number of middle switches required for this example is 5, and in general, is 2N−1 for N input and output switches. The basic algorithm for managing a three-layer switch is to search the middle subswitches for a middle subswitch that has unused wires to the needed input and output switches. Once a connectible middle subswitch is found, connecting to the correct inputs and outputs in the input and output switches is trivial. The example is intentionally small, and in such a small example, the reorganization does not save crosspoints. A 9x9 crossbar has 81 crosspoints, while a 9x9 minimal spanning switch has 3x3x5×3 = 135 contacts, providing no savings. As the numbers get larger, the savings appear. For example, a 10,000 line exchange would need 100 million crosspoints to implement a full crossbar. Input and output layers of 100 100×199 switches and a middle layer of 199 100x100 switches would use only 3x199x100x100 crosspoints, or about 6 million crosspoints, a savings of 94% of the crosspoints.
… excerpt ends here. Continue reading the full article.
