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 8
Routing Basics
Routing involves selecting a path from a source node to a destination node in a
particular topology. Once we have a topology, or road map for our network, routing
is the next logical step: picking a route on the map that gets us to our destination.
Whereas a topology determines the ideal performance of a network, routing is one
of the two key factors that determine how much of this potential is realized. We
discuss the other key factor, flow control, in Chapters 12 and 13.
The routing algorithm used for a network is critical for several reasons. A good
routing algorithm balances load across the network channels even in the presence
of non-uniform traffic patterns such as permutation traffic. The more balanced the
channel load, the closer the throughput of the network is to ideal. Surprisingly, many
routers that have been built and are in use today do a poor job of balancing load.
Rather, the traffic between each pair of nodes follows a single, predetermined path.
As you would expect, non-uniform traffic patterns can induce large load misbalances
with this type of routing algorithm, giving suboptimal throughput. However, these
routing choices can be at least partially explained because most of these routers have
been designed to optimize a second important aspect of any routing algorithm: short
path lengths.
A well-designed routing algorithm also keeps path lengths as short as possible,
reducing the number of hops and the overall latency of a message. What might not
be immediately obvious is that, often, routing minimally (always choosing a shortest
path) is at odds with balancing load and maximizing throughput. In fact, for oblivious
routing algorithms, to improve load balance over all traffic patterns, we are forced to
increase the average path length of all messages. The converse is also true. This
tradeoff exists for oblivious algorithms because they do not factor the current traffic
pattern into the routing algorithm. We explore these algorithms in more detail in
Chapter 9.
159
160 CHAPTER 8 Routing Basics
On the other hand, a clever designer might suggest an approach to offer the “best
of both worlds.” Instead of picking an algorithm independent of the traffic pattern,
as in oblivious algorithms, why not adapt to the current traffic conditions? Then we
could send traffic minimally for an “easy” traffic pattern such as uniform traffic, but
then could resort to non-minimal routing for “hard” non-uniform traffic patterns.
This simple idea forms the basis of adaptive routing algorithms, which we explore
in Chapter 10. The potential advantage of these algorithms is realizing both load
balance and locality (short path lengths). However, we will see that practical design
issues make achieving this goal challenging.
Another important aspect of a routing algorithm is its ability to work in the
presence of faults in the network. If a particular algorithm is hardwired into the
routers and a link or node fails, the entire system fails. However, if an algorithm can
be reprogrammed or adapt to the failure, the system can continue to operate with only
a slight loss in performance. Obviously, this is critical for systems with high-reliability
demands. Finally, routing interacts with the flow control of the network and careful
design of both is often required to avoid deadlocks and/or livelocks (Chapter 14).
Our discussion of routing begins below with a short example and a discussion of
routing taxonomy and an introduction to deterministic routing algorithms. We con-
tinue in Chapter 9 with a discussion of deterministic and oblivious routing, and then
adaptive routing in Chapter 10. We conclude with a discussion of routing mechanics
in Chapter 11.
8.1 A Routing Example
Consider the problem of routing on the 8-node ring network shown in Figure 8.1.
If we rule out backtracking, or revisiting a node in the network, the routing decision
here is binary. For each packet being sent from s to d, we can either send the packet
clockwise or counterclockwise around the ring starting at s and ending at d. Even
with this simple topology and only a binary decision to make, there are many possible
routing algorithms. Here are a few:
Greedy: Always send the packet in the shortest direction around the ring. For
example, always route from 0 to 3 in the clockwise direction and from 0 to 5 in
the counterclockwise direction. If the distance is the same in both directions, pick a
direction randomly.
Uniform random: Randomly pick a direction for each packet, with equal probability
of picking either direction.
1 2 3 4 5 6 70
Figure 8.1 An 8-node ring network.

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