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

CHAPTER 6
Non-Blocking Networks
Until this point, we have focused on packet-switched networks, but for this chapter,
we shift our attention to circuit-switched networks. In circuit-switched networks,
connections between a particular source and destination are first set up, then held
as data flows continuously through the connection, and then finally torn down.
1
Historically, non-blocking, circuit-switched networks were first associated with the
telephone system. A call placed from one person to another represented a single con-
nection request. For the call to go through, an unused path through the network had
to be found and then allocated for that call. If the telephone system was non-blocking,
then the call would always succeed as long as the recipient’s phone was not in use.
More precisely, a network is said to be non-blocking if it can handle all circuit re-
quests that are a permutation of the inputs and outputs. That is, a dedicated path can
be formed from each input to its selected output without any conflicts (shared chan-
nels). Conversely, a network is blocking if it cannot handle all such circuit requests
without conflicts.
2
In this chapter, we examine two types of non-blocking networks. First, a network
is strictly non-blocking if any permutation can be set up incrementally, one circuit at
a time, without the need to reroute (or rearrange) any of the circuits that are already
set up. If any unused input can be connected to any unused output without altering
the path taken by any other traffic, then the network is strictly non-blocking.
In contrast, a network is rearrangeably non-blocking (or simply rearrangeable)
if it can route circuits for arbitrary permutations, but incremental construction of
1. Chapter 12 includes a detailed description of both packet and circuit switching.
2. The U.S. phone system is obviously blocking to any person who has ever received the “all circuits are busy”
recording.
111

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