Strictly non-blocking 3-stage condition

A three-stage network is strictly non-blocking if a free input can always be connected to a free output, however the existing calls are routed. The condition was derived by C. Clos (1953).

Network

• $N$ inputs and $N$ outputs; groups of $n$ lines.
• Stage 1: $N/n$ arrays of $n \times k$; Stage 2: $k$ arrays of $(N/n) \times (N/n)$; Stage 3: $N/n$ arrays of $k \times n$.
• Each first-stage array has one link to every middle array; each middle array has one link to every third-stage array.

  input array A          output array B
  (n inputs)             (n outputs)
  n-1 busy -> use        n-1 busy -> use
  n-1 middle arrays      n-1 other middle
       \                      /
        \  need 1 more free  /
         +-- middle array --+
     total k >= (n-1)+(n-1)+1

Derivation of $k \ge 2n - 1$

Consider a new call from a free input of first-stage array A to a free output of third-stage array B. Take the worst case:

1. Array A has $n$ inputs; apart from the calling input, the other $n - 1$ are busy. Each of those calls uses a different link from A, so they occupy $n - 1$ middle arrays.
2. Array B has $n$ outputs; apart from the called output, the other $n - 1$ are busy, using $n - 1$ middle arrays.
3. In the worst case, these two sets of middle arrays are all different, so $2(n - 1)$ middle arrays cannot be used.
4. To connect A to B, at least one more middle array must be free:

$$k \ge (n - 1) + (n - 1) + 1 = 2n - 1$$

This is the necessary and sufficient condition for strict non-blocking.

Crosspoints and optimum $n$

$$N_x = 2Nk + k\left(\frac{N}{n}\right)^2 = (2n-1)\left[2N + \frac{N^2}{n^2}\right]$$

Differentiating, and dropping the small $1/n^3$ term for large $n$:

$$\begin{aligned} \frac{dN_x}{dn} &= 4N + N^2\frac{2 - 2n}{n^3} \approx 4N - \frac{2N^2}{n^2} = 0 \\ n_{opt} &= \sqrt{\frac{N}{2}} \end{aligned}$$

Substituting:

$$N_{x,min} = 4N\left(\sqrt{2N} - 1\right)$$

Example

$N = 200$: $n = 10$, $k = 19$, $N_{x,min} = 4(200)(20 - 1) = 15\,200$, compared with $N^2 = 40\,000$ for a single-stage switch.

The same idea applies to digital switches: a TST switch is strictly non-blocking when the internal time slots satisfy $l \ge 2c - 1$, and an STS switch when the centre TSIs satisfy $k \ge 2N - 1$.