Nonblocking minimal spanning switch
A nonblocking minimal spanning switch is a device that can connect N inputs to N outputs in any combination.
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.
One early, successful mathematical analysis was performed by Charles Clos (French pronunciation: [ʃaʁl klo]), and a switched fabric constructed of smaller switches is called a Clos network.
Being nonblocking it could always complete a call (to a non-busy receiver), which would maximize service availability.
Engineers also noticed that at any time, each bar of a crossbar switch was only making a single connection.
The smaller switches are less massive, more reliable, and generally easier to build, and therefore less expensive.
This is called a "minimal spanning switch," and managing it was the holy grail of the Bell Labs' investigations.
For example, a 10,000 line exchange would need 100 million contacts to implement a full crossbar.
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.
Eventually one of two things must happen: 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.
As soon as the algorithm was discovered, Bell system engineers and managers began discussing it.
After several years, Bell engineers began designing electromechanical switches that could be controlled by it.
Therefore, in a busy switch, when a particular PCB lacks any connections, it is an excellent candidate for testing.
To test or remove a particular printed circuit card from service, there is a well-known algorithm.
If a test fails, the software isolates the exact circuit board by reading the failure from several external switches.
Shortly after replacement, the next test succeeds, the connections to the repaired subswitch are marked "not busy," and the switch returns to full operation.
When they disagreed, they would diagnose themselves, and the correctly running computer would take up switch operation while the other would disqualify itself and request repair.
The 1ESS switch was still in limited use as of 2012, and had a verified reliability of less than one unscheduled hour of failure in each thirty years of operation, validating its design.
Initially it was installed on long-distance trunks in major cities, the most heavily used parts of each telephone exchange.
A practical implementation of a switch can be created from an odd number of layers of smaller subswitches.
Although each subswitch has limited multiplexing capability, working together they synthesize the effect of a larger N×N crossbar switch.
First, it is typical to "fold" the switch, so that both the input and output connections to a subscriber-line are handled by the same control logic.
The outer layer is implemented in subscriber-line interface cards (SLICs) in the local presence street-side boxes.
The control logic has to allocate these connections, and the basic method is the algorithm already discussed.
Multiplexer lines are allocated in a first-in-first out way, so that new connections find new switch elements.
