--- title: "Strictly non-blocking 3-stage condition" subject: "Telecommunications" chapter: 4 key: "semester_8/telecommunications:strictly-nonblocking-3-stage" source: https://www.bctengineer.com/q/semester_8/telecommunications/strictly-nonblocking-3-stage site: BCT Engineering --- # Strictly non-blocking 3-stage condition Telecommunications · Chapter 4: Digital Switching - Asked in: 2076 Asoj, 7 marks - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/telecommunications/strictly-nonblocking-3-stage - Whole chapter: https://www.bctengineer.com/md/semester_8/telecommunications/chapter-4 ## Question Derive the necessary conditions for a 3-stage network to be strictly non-blocking. ## Short answer A 3-stage network is strictly non-blocking if k >= 2n-1, derived from worst-case n-1 busy inputs and n-1 busy outputs occupying different middle arrays, plus one free middle array. Minimum crosspoints occur near n = sqrt(N/2), giving Nx,min = 4N(sqrt(2N)-1). ## Answer 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. ```text 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$. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the worst case for a new call from array A to array B, how many middle arrays are already unusable? A. n - 1 B. 2(n - 1) C. 2n D. n Answer: B. n-1 are used by A's other calls and n-1 different ones by B's, giving 2(n-1). (Key point: Worst-case blocked middle arrays) 2. The strictly non-blocking condition for a three-stage network is A. k >= n B. k >= 2n - 1 C. k >= n^2 D. k >= N/n Answer: B. k >= (n-1) + (n-1) + 1 = 2n - 1. (Key point: Condition) 3. Minimising crosspoints Nx = (2n-1)[2N + N^2/n^2] gives n_opt = A. sqrt(2N) B. sqrt(N/2) C. N/2 D. 2N Answer: B. Setting dNx/dn = 0 with 2n-1 about 2n gives 4N = 2N^2/n^2, so n = sqrt(N/2). (Key point: Optimum n) 4. The minimum crosspoints for a Clos network are A. 4N(sqrt(2N) - 1) B. N^2 C. 2N sqrt(N) D. 4N^2 Answer: A. Substituting n = sqrt(N/2) gives 4N(sqrt(2N) - 1), 15200 for N = 200. (Key point: Minimum crosspoints) ## Related in Telecommunications - [Digital exchange principles; non-blocking 3-stage](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adigital-exchange-nonblocking-3-stage) — Telecommunications, chapter 4 - [TST time slots for non-blocking operation](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Atst-time-slots-numerical) — Telecommunications, chapter 4 - [Blocking and non-blocking switching](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Ablocking-nonblocking-switching) — Telecommunications, chapter 4 - [Clos network and STS/TST blocking](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aclos-network-sts-tst-blocking) — Telecommunications, chapter 4 - [Derive STS and TST blocking probabilities](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Asts-tst-blocking-derivation) — Telecommunications, chapter 4 - [Time switch and two-stage T-S network](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Atime-switch-two-stage-ts) — Telecommunications, chapter 4 ## Related in other subjects - [Deadlock; necessary conditions with examples](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-necessary-conditions-examples) — Operating System, chapter 7 - [Deadlock conditions and why all necessary](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-why-necessary) — Operating System, chapter 7 - [Necessary conditions; deadlock prevention](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-prevention-necessary-conditions) — Operating System, chapter 7 - [Derive magnetic boundary conditions](https://www.bctengineer.com/question.md?key=semester_3%2Felectromagnetism%3Amagnetic-boundary-conditions-derive) — Electromagnetism, chapter 3