Clos network

It was invented by Edson Erwin[1] in 1938 and first formalized by the American [2] engineer Charles Clos[3] in 1952.

By adding stages, a Clos network reduces the number of crosspoints required to compose a large crossbar switch.

When the Clos network was first devised, the number of crosspoints was a good approximation of the total cost of the switching system.

While this was important for electromechanical crossbars, it became less relevant with the advent of VLSI, wherein the interconnects could be implemented either directly in silicon, or within a relatively small cluster of boards.

Upon the advent of complex data centers, with huge interconnect structures, each based on optical fiber links, Clos networks regained importance.

Clos networks are defined by three integers n, m, and r. n represents the number of sources which feed into each of r ingress stage crossbar switches.

Hence in the worst case, 2n−2 of the middle stage switches are unable to carry the new call.

Therefore, to ensure strict-sense nonblocking operation, another middle stage switch is required, making a total of 2n−1.

[6] To prove this, it is sufficient to consider m = n, with the Clos network fully utilised; that is, r×n calls in progress.

The proof shows how any permutation of these r×n input terminals onto r×n output terminals may be broken down into smaller permutations which may each be implemented by the individual crossbar switches in a Clos network with m = n. The proof uses Hall's marriage theorem[7] which is given this name because it is often explained as follows.

Real telephone switching systems are rarely strict-sense nonblocking for reasons of cost, and they have a small probability of blocking, which may be evaluated by the Lee or Jacobaeus approximations,[8] assuming no rearrangements of existing calls.

The probability of blocking, or the probability that no such path is free, is then [1−(1−p)2]m. The Jacobaeus approximation is more accurate, and to see how it is derived, assume that some particular mapping of calls entering the Clos network (input calls) already exists onto middle stage switches.

Let A be the number of ways of assigning the j output calls to the m middle stage switches.

After considerable algebraic manipulation, this may be written as: Clos networks may also be generalised to any odd number of stages.