Editing Nonblocking minimal spanning switch (section)

== Background: switching topologies ==

===The crossbar switch===
The [[crossbar switch]] has the property of being able to connect N inputs to N outputs in any [[bijection|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 N<sup>2</sup> (N squared) simple [[Switch#Contact terminology|SPST switches]].  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.

The obvious way to emulate a crossbar switch was to find some way to build it from smaller crossbar switches.  If a crossbar switch could be emulated by some arrangement of smaller crossbar switches, then 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.  This is called a [[Clos network]].

===Completely connected 3-layer switches===

The next approach was to break apart the crossbar switch into three layers of smaller crossbar switches. There would be 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.

A telephone system only has to make a one-to-one connection.  Intuitively this seems to mean that the number of inputs and the number of outputs can always be equal in each subswitch, but intuition does not prove this can be done nor does it tell us how to do so.  Suppose we want to synthesize a 16 by 16 crossbar switch.  The design could have 4 subswitches on the input side, each with 4 inputs, for 16 total inputs.  Further, on the output side, we could also have 4 output subswitches, each with 4 outputs, for a total of 16 outputs.  It is desirable that the design use as few wires as possible, because wires cost real money.  The least possible number of wires that can connect two subswitches is a single wire.  So, each input subswitch will have a single wire to each middle subswitch.  Also, each middle subswitch will have a single wire to each output subswitch.

The question is how many middle subswitches are needed, and therefore how many total wires should connect the input layer to the middle layer.  Since telephone switches are symmetric (callers and callees are interchangeable), the same logic will apply to the output layer, and the middle subswitches will be "square", having the same number of inputs as outputs.

The number of middle subswitches depends on the algorithm used to allocate connection to them.  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.

Theoretically, in the example, only four central switches are needed, each with exactly one connection to each input switch and one connection to each output switch.  This is called a "minimal spanning switch,"  and managing it was the holy grail of the Bell Labs' investigations.

However, a bit of work with a pencil and paper will show that it is easy to get such a minimal switch into conditions in which no single middle switch has a connection to both the needed input switch and the needed output switch.   It only takes four calls to partially block the switch.  If an input switch is half-full, it has connections via two middle switches.  If an output switch is also half full with connections from the other two middle switches, then there is no remaining middle switch which can provide a path between that input and output.

For this reason, a "simply connected nonblocking switch" 16x16 switch with four input subswitches and four output switches was thought to require 7  middle switches; in the worst case an almost-full input subswitch would use three middle switches, an almost-full output subswitch would use three different ones, and the seventh would be guaranteed to be free to make the last connection.  For this reason, sometimes this switch arrangement is called a "2''n''&minus;1 switch", where ''n'' is the number of input ports of the input subswitches.

The example is intentionally small, and in such a small example, the reorganization does not save many switches.  A 16×16 crossbar has 256 contacts, while a 16×16 minimal spanning switch has 4×4×4×3 = 192 contacts.

As the numbers get larger, the savings increase.  For example, a 10,000 line exchange would need 100 million contacts to implement a full crossbar.  But three layers of 100 100×100 subswitches would use only 300 10,000 contact subswitches, or 3 million contacts.

Those subswitches could in turn each be made of 3×10 10×10 crossbars, a total of 3000 contacts, making 900,000 for the whole exchange; that is a far smaller number than 100 million.

===Managing a minimal spanning switch===

The crucial discovery was a way to reorganize connections in the middle switches to "trade wires" so that a new connection could be completed.

The first step is to find an unused link from the input subswitch to a middle-layer subswitch (which we shall call A), and an unused link from a middle-layer subswitch (which we shall call B) to the desired output subswitch.  Since, prior to the arrival of the new connection, the input and output subswitches each had at least one unused connection, both of these unused links must exist.

If A and B happen to be the ''same'' middle-layer switch, then the connection can be made immediately just as in the "2''n''−1" switch case.  However, if A and B are ''different'' middle-layer subswitches, more work is required.  The algorithm finds a new arrangement of the connections through the middle subswitches A and B which includes all of the existing connections, ''plus'' the desired new connection.

Make a list of all of the desired connections that pass through A or B.  That is, all of the existing connections to be maintained ''and'' the new connection.  The algorithm proper only cares about the internal connections from input to output switch, although a practical implementation also has to keep track of the correct input and output switch connections.

In this list, each input subswitch can appear in at most two connections: one to subswitch A, and one to subswitch B.  The options are zero, one, or two.  Likewise, each output subswitch appears in at most two connections.

Each connection is linked to at most two others by a shared input or output subswitch, forming one link in a "chain" of connections.

Next, begin with the new connection.  Assign it the path from its input subswitch, through middle subswitch A, to its output subswitch.  If this first connection's output subswitch has a second connection, assign that second connection a path from its input subswitch through subswitch B.  If that input subswitch has another connection, assign that third connection a path through subswitch A.  Continue back and forth in this manner, alternating between middle subswitches A and B.  Eventually one of two things must happen:
# the chain terminates in a subswitch with only one connection, or
# the chain loops back to the originally chosen connection.
In the first case, go back to the new connection's input subswitch and follow its chain backward, assigning connections to paths through middle subswitches B and A in the same alternating pattern.

When this is done, each input or output subswitch in the chain has at most two connections passing through it, and they are assigned to different middle switches.  Thus, all the required links are available.

There may be additional connections through subswitches A and B which are not part of the chain including the new connection; those connections may be left as-is.

After the new connection pattern is designed in the software, then the electronics of the switch can actually be reprogrammed, physically moving the connections.  The electronic switches are designed internally so that the new configuration can be written into the electronics without disturbing the existing connection, and then take effect with a single logic pulse.  The result is that the connection moves instantaneously, with an imperceptible interruption to the conversation.  In older electromechanical switches, one occasionally heard a clank of "switching noise."

This algorithm is a form of [[topological sort]], and is the heart of the algorithm that controls a minimal spanning switch.