142 CHAPTER 6 Non-Blocking Networks
network. However, we can ignore all but the outermost TSIs and view the network
as a TSSST network with a 48 × 48 TSI followed by a 24 × 48 space switch, then a
72 ×72 space switch, a 48 ×24 space switch, and a 48 ×48 TSI. The other four TSIs
along each path are left in the straight-through conﬁguration. Exercise 6.6 examines
the possibilities of treating the network as a seven-stage TSTSTST.
To schedule our logical ﬁve-stage network, we start by considering the middle
three space-switch stages as 48 3,456 × 3,456 space switches, one for each time
slot. We assign each call to one of the 48 time slots by scheduling this (m, n, r) =
(48, 24, 3456) Clos. This solution then leaves 48 subproblems, one per time slot, of
assigning each call in that time slot to one of the 48 physical middle-stage switches.
For each subproblem, we schedule all calls in that middle-stage time slot on the
(m, n, r) = (48, 24, 72) Clos formed by the three space switches for a single time
6.7 Bibliographic Notes
The seminal paper on non-blocking networks was published by Clos in 1953 .
This paper introduced Clos networks and described the requirements for them to
be strictly non-blocking. Beneˇs, Slepian, and Duguid discovered that much smaller
Clos networks were rearrangeably non-blocking [17, 171, 64]. The looping algorithm
presented to ﬁnd these arrangements can be traced back to K ¨onig, who proved a
bipartite graph of maximum degree can be edge-colored using colors .
Several more efﬁcient algorithms for edge-coloring are due to Cole [39, 40] and
matrix decomposition is addressed by Waksman . Beneˇs’s classic 1965 book
 derives a bound for the number of crosspoints required to realize a rearrangeable
non-blocking network and introduces the Beneˇs network, a special form of a Clos
network, to realize this bound. Batcher’s 1968 paper introduced the bitonic sort and
the Batcher sorting network . A detailed treatment of sorting networks can be
found in Knuth . Multicast in Clos networks was ﬁrst considered by Masson and
Jordan  and has since been studied by many researchers. More recent results
include the near-optimal multicast scheduling algorithm of Yang and Masson .
6.1 A 27-port Clos. Sketch a rearrangeable Clos network using 3 × 3 crossbar switches
that has exactly 27 ports.
6.2 Maximum size Clos networks. Using n ×n crossbar switches as a building block, how
large a Clos can you build with k stages (k odd)? Assume that your Clos need only
be rearrangeable for unicast trafﬁc.
6.3 Performance of the looping algorithm. Implement the looping algorithm described in
Figure 6.11. Run the algorithm for a (5,5,5) Clos network: start with an empty