Crosspoints and three-stage switching

Crosspoint and switching array

A crosspoint is the basic switching element at the intersection of an input line and an output line; when it is closed (a relay contact, reed or electronic gate) it connects that input to that output. A switching array (matrix) is a rectangular arrangement of crosspoints with $N$ inputs and $M$ outputs ($N \times M$ crosspoints); any input can be connected to any free output. A single-stage $N \times N$ array needs $N^2$ crosspoints (or $N(N-1)/2$ if folded), which grows too quickly for large exchanges.

        out1 out2 out3
 in1 ----x----x----x---
 in2 ----x----x----x---    x = crosspoint
 in3 ----x----x----x---

Three-stage switching

The $N$ inputs are divided into groups of $n$.

  first stage      middle stage     third stage
 (N/n arrays,     (k arrays,       (N/n arrays,
   n x k)        N/n x N/n)          k x n)
 n -->[n x k]--+->[N/n x N/n]--+-->[k x n]--> n
 n -->[n x k]--+->[N/n x N/n]--+-->[k x n]--> n
   ...         +->   ...       +-->   ...
 n -->[n x k]--+->[N/n x N/n]--+-->[k x n]--> n
  (every first-stage array has one link to
   every middle array, and so on)

• Stage 1: $N/n$ arrays, each $n \times k$.
• Stage 2: $k$ arrays, each $\frac{N}{n} \times \frac{N}{n}$.
• Stage 3: $N/n$ arrays, each $k \times n$.

Each input reaches any output through any one of the $k$ middle arrays, so there are $k$ alternative paths. Total crosspoints:

$$\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}$$

If $k = 2n - 1$ the network is strictly non-blocking (Clos); if $k < 2n-1$ some blocking occurs but the cost is lower.

Example calculation

Take $N = 128$ lines, $n = 8$ (so $N/n = 16$), non-blocking $k = 2n - 1 = 15$:

$$\begin{aligned} \text{Stage 1} &= 16 \times (8 \times 15) = 1920 \\ \text{Stage 2} &= 15 \times (16 \times 16) = 3840 \\ \text{Stage 3} &= 16 \times (15 \times 8) = 1920 \\ N_x &= 2(128)(15) + 15(16)^2 = 7680 \end{aligned}$$

A single-stage $128 \times 128$ switch would need $128^2 = 16\,384$ crosspoints. The three-stage switch saves about 53 % while still being non-blocking. Here $n = 8 = \sqrt{N/2}$ is the optimum, and the result equals $4N(\sqrt{2N} - 1) = 4(128)(15) = 7680$.

Answer: 7680 crosspoints for a 128-line non-blocking three-stage switch (vs 16 384 single-stage).