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 trafﬁc pattern,
as in oblivious algorithms, why not adapt to the current trafﬁc conditions? Then we
could send trafﬁc minimally for an “easy” trafﬁc pattern such as uniform trafﬁc, but
then could resort to non-minimal routing for “hard” non-uniform trafﬁc 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 ﬂow 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
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.