O'Reilly logo

Principles and Practices of Interconnection Networks by Brian Patrick Towles, William James Dally

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 configuration. Exercise 6.6 examines
the possibilities of treating the network as a seven-stage TSTSTST.
To schedule our logical five-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 find 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 efficient 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 first 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 traffic.
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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required