Table 8.6 Dynamic networks, switching N inputs ´ N outputs using k ´ k switches (each input is one bit).
Network
Other Equivalent Networks
Stages of Delay (in units of k´k switch delay)
Blocking
Approx. Cost (k ´ k switches)
Baseline
Delta, Omega SW Banyan
Yes
Benes
Nonblocking if reconfigured
Clos
Strictly nonblocking
As an example of blocking, consider two source nodes: 110 and 101. Suppose they wish to simultaneously access destination nodes 110 and 111, respectively. The messages share a common channel (labeled X in Figure 8.53), and only one message can go through; the other is blocked.
The baseline network can be expanded into a nonblocking form as shown in Figure 8.54, but at the cost of extending the size of the network. The Benes nonblocking (reconfigurable) network now has distance (diameter) of:
Diameter = # of stages =
and the cost has increased to about:
2 ´ (Baseline cost).
Other dynamic networks provide different tradeoffs on achievable message bandwidth, message delay, and fault tolerance. Table 8.6 summarizes some of the attributes of some common dynamic networks.
