Editing Nonblocking minimal spanning switch (section)

===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.