Nonblocking Minimal Spanning Switch

Switches have an odd number of layers of multiplexer, that together synthesize a larger NxM multiplexer. In a real telephone switch, alternate layers multiplexers use either space division, or time division.

A space-division multiplexer is similar to a crossbar switch. Any single output can select from any input. In digital switches, this is usually an arrangement of and-gates. 8000 times per second, the connection is reprogrammed to connect particular wires for the duration of a time-slot.

A time division switch has a memroy which is read in a fixed order and written in a programmable order (or vice-versa). It permutes time-slots.

Mathematically, both types can be modelled as nxm multiplexers.

The scarce resources in a telephone switch are the connections between layers of subswitches. The control logic has to allocate these connections.

The connections consist of both time slots and wires. The first thing to try is to search for a subswitch that contains the needed in and out connections. There are two design paths to go if this simple search fails.

One way is to have enough switching fabric to assure that the pairwise allocation will always succeed. This is the method usually used in central office switches, which have low utilization of their resources.

Another way is to have a minimal switching fabric that still can theoretically make all the connections, and reorganize the switch's connections when a new connection won't fit.

If a subswitch with the needed pair of connections can't be found, a pair of subswitchs will still have the necessary in and out, because there has to be at least the same number of connections between each layer of the switch, or else the switch will not be able to complete a full set of connections.

The pair of subswitches' connections can be reorganized with a topological sort, so that all the existing connections continue, though they might migrate between the two different subswitches. This is the method usually used in long distance switches, which have high utilization of their switching fabric.

A topological sort picks two subswitches. One has a needed input connection. The other has a needed output connection. The connections of both subswitches are placed in a list that also includes the desired new connection.

In the list, the basic trick is to trace connections. Starting from some input or output, the software traces a connection to an output, then traces the other connection at that output to an input, and so forth, until it comes to an end. Each time it traces from input to output, the connection is placed in one subswitch, and removed from the list. WHen it traces from output to input, the connection is placed in the other subswitch and removed from the list. To complete correctly, tracing must begin with single connection inputs and outputs, and only then trace double-ended inputs and outputs, which might form loops.

[This algorithm first appeared in the 1953 Bell Systems Journal. Regrettably I have lost it- the reference would be welcome, and the Author deserves credit!]