Clos network and STS/TST blocking

Clos network

A Clos network is a three-stage (multi-stage) switching network, proposed by Charles Clos (1953), in which $N$ inputs are divided into $N/n$ first-stage arrays of size $n \times k$, connected to $k$ middle arrays of size $\frac{N}{n} \times \frac{N}{n}$, which connect to $N/n$ third-stage arrays of size $k \times n$. Every array of one stage has exactly one link to every array of the next stage.

$$\begin{aligned} N_x &= \underbrace{\tfrac{N}{n}(nk)}_{\text{stage 1}} + \underbrace{k\left(\tfrac{N}{n}\right)^2}_{\text{stage 2}} + \underbrace{\tfrac{N}{n}(kn)}_{\text{stage 3}} \\ &= 2Nk + k\left(\frac{N}{n}\right)^2 \end{aligned}$$

Clos showed that the network is strictly non-blocking when $k = 2n - 1$ (worst case: $n-1$ other inputs of the calling array and $n-1$ outputs of the called array use different middle arrays, so one more is needed). With the best choice $n \approx \sqrt{N/2}$, the minimum is $N_x \approx 4N(\sqrt{2N} - 1)$, much less than $N^2$.

Blocking probability of STS

 STS:     S (N x k) -> T (k TSI modules) -> S (k x N)
 Lee graph: k parallel paths, each = 2 links in series

In STS, a call from input highway A to output highway B in given slots can go through any of the $k$ time-switch modules. Each path uses a link from the first space stage to a module and a link from the module to the second space stage. With link occupancy $p' = p/\beta$ ($\beta = k/N$ space expansion):

• Probability a link is free $= 1 - p'$; both links of a path free $= (1-p')^2$.
• Path blocked $= 1 - (1-p')^2$; all $k$ paths blocked:

$$\begin{aligned} p' &= \frac{p}{\beta},\quad \beta = \frac{k}{N} \\ P_B(\text{STS}) &= \left[1 - (1-p')^2\right]^{k} \end{aligned}$$

Blocking probability of TST

 TST:     T (c -> l slots) -> S (N x N) -> T (l -> c)
 Lee graph: l parallel paths (internal time slots)

In TST, the path from A to B passes through the space stage in any of the $l$ internal time slots. Each path uses one internal slot on A's highway and the same slot on B's highway. With time expansion $\alpha = l/c$, $p' = p/\alpha$, and by the same argument:

$$\begin{aligned} p' &= \frac{p}{\alpha},\quad \alpha = \frac{l}{c} \\ P_B(\text{TST}) &= \left[1 - (1-p')^2\right]^{l} \end{aligned}$$

Comparison

Since the number of paths in TST equals the number of internal time slots $l$ (32 to several hundred), while in STS it equals the number of time-switch modules $k$ (usually small), TST blocking is far lower for the same hardware. Example with $p' = 0.2$:

$$\begin{aligned} \text{STS},\ k = 8 &: \ (1-0.8^2)^{8} = 0.36^{8} \approx 2.8 \times 10^{-4} \\ \text{TST},\ l = 32 &: \ (1-0.8^2)^{32} = 0.36^{32} \approx 6.3 \times 10^{-15} \end{aligned}$$