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 trafﬁc to make
All of the above deﬁnitions apply to unicast trafﬁc, where each input is connected
to at most one output. We also consider multicast trafﬁc, where a connection from
a single input may fan out to several outputs. A network is strictly non-blocking for
multicast trafﬁc if any unconnected output can be connected to any input (connected
or unconnected) without affecting other trafﬁc. Also, a network is rearrangeable for
multicast trafﬁc if it can connect any unconnected output to any input but may have
to reroute other trafﬁc to make the connection.
Crossbar switches and Clos networks with an expansion of 2:1 are examples of
strictly non-blocking networks for unicast trafﬁc. Crossbar switches and Clos net-
works with larger expansion are also strictly non-blocking for multicast trafﬁc. Beneˇs
networks and Clos networks without expansion are examples of rearrangeable net-
works for unicast trafﬁc.
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 ﬂows 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 trafﬁc sharing the channel. This bandwidth
constraint is met if the channel load γ
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 ﬂow denies service to another ﬂow for more than a short,
predetermined amount of time. This resource allocation constraint can be realized
by a suitable ﬂow 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 trafﬁc with a guaranteed bound
on packet delay. The trafﬁc neither exceeds the bandwidth capacity of any network
channel, nor does it result in coupled resource allocation between ﬂows.
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