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

112 CHAPTER 6 Non-Blocking Networks
a permutation may require rearranging some of the early circuits to permit later
circuits to be set up. A rearrangeble network can connect any unconnected input to
any unconnected output, but it may need to reroute some unrelated traffic to make
this connection.
All of the above definitions apply to unicast traffic, where each input is connected
to at most one output. We also consider multicast traffic, where a connection from
a single input may fan out to several outputs. A network is strictly non-blocking for
multicast traffic if any unconnected output can be connected to any input (connected
or unconnected) without affecting other traffic. Also, a network is rearrangeable for
multicast traffic if it can connect any unconnected output to any input but may have
to reroute other traffic to make the connection.
Crossbar switches and Clos networks with an expansion of 2:1 are examples of
strictly non-blocking networks for unicast traffic. Crossbar switches and Clos net-
works with larger expansion are also strictly non-blocking for multicast traffic. Beneˇs
networks and Clos networks without expansion are examples of rearrangeable net-
works for unicast traffic.
6.1 Non-Blocking vs. Non-Interfering Networks
For packet switching applications, the notion of a non-blocking network is largely
irrelevant, or at least overkill. Because packet switches do not tie down a circuit
for the duration of a connection or session, they can share channels between con-
nections and packet flows without interference as long as two constraints having to
do with bandwidth and resource allocation are met. First, there must be adequate
channel bandwidth to support all of the traffic sharing the channel. This bandwidth
constraint is met if the channel load γ
max
is less than the channel bandwidth. Sec-
ond, the allocation of resources (buffers and channel bandwidth) must be done in a
manner such that no single flow denies service to another flow for more than a short,
predetermined amount of time. This resource allocation constraint can be realized
by a suitable flow control mechanism as described in Chapter 12.
We will call a packet-switched network that meets these criteria non-interfering.
Such a network is able to handle arbitrary packet traffic with a guaranteed bound
on packet delay. The traffic neither exceeds the bandwidth capacity of any network
channel, nor does it result in coupled resource allocation between flows.
For almost all applications today, when people say they want a non-blocking
network, what they really require is a non-interfering network, which can usually
be realized with considerably less expense. For the sake of history, however, and for
those cases in which true non-blocking is needed to support circuit switching, we
give a brief survey of non-blocking networks in the remainder of this chapter.
6.2 Crossbar Networks
A n × m crossbar or crosspoint switch directly connects n inputs to m outputs with
no intermediate stages. In effect, such a switch consists of mn:1 multiplexers, one for
6.2 Crossbar Networks 113
each output. Many crossbar networks are square in that m = n. Others are rectangular
with m>nor m<n.
Figure 6.1 shows a conceptual model of a 4 ×5 crossbar. There are 4 input lines
and 5 output lines. At each point where an input line crosses an output line that is,
at each crosspoint a switch optionally connects the input line to the output line.
For correct operation, each output must be connected to at most one input. Inputs,
however, may be connected to more than one output.
3
In Figure 6.1, for example,
input 1 drives outputs 0 and 3.
At one point in time, much of the telephone network was implemented using
crossbar switches composed of mechanical relays that did in fact have the structure
of Figure 6.1. With such switch-based crossbars, there is no real distinction between
inputs and outputs. The connections made by the switches are bidirectional.
Today, however, most crossbars are implemented using digital logic and have the
structure shown in Figure 6.2. Each of the n input lines connect to one input of
mn:1 multiplexers. The outputs of the multiplexers drive the m output ports. The
multiplexers may be implemented with tri-state gates or wired-OR gates driving an
output line, mimicking the structure in Figure 6.1, or with a tree of logic gates to
realize a more conventional multiplexer.
in0
in1
in2
in3
out0
out1
out2
out3
out4
Crosspoint
Input line
Output line
Figure 6.1 A4×5 crossbar switch consists of 4 input lines, 5 output lines, and 20 crosspoints. Each output
may be connected to at most one input, while each input, may be connected to any number
of outputs. This switch has inputs 1,0,3,1,2 connected to outputs 0,1,2,3,4, respectively.
3. This is true of most, but not all, crossbar implementations. Some have limited fanout.

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