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

slot.

6.7 Bibliographic Notes

The seminal paper on non-blocking networks was published by Clos in 1953 [37].

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 [103].

Several more efﬁcient algorithms for edge-coloring are due to Cole [39, 40] and

matrix decomposition is addressed by Waksman [190]. Beneˇs’s classic 1965 book

[18] 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 [14]. A detailed treatment of sorting networks can be

found in Knuth [102]. Multicast in Clos networks was ﬁrst considered by Masson and

Jordan [120] and has since been studied by many researchers. More recent results

include the near-optimal multicast scheduling algorithm of Yang and Masson [196].

6.8 Exercises

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

Start Free Trial

No credit card required