162 CHAPTER 8 Routing Basics
of the trafﬁc routes in the clockwise direction around the ring, leaving all of the
counterclockwise channels idle and loading the clockwise channels with 3 units of
trafﬁc — that is, γ = 3 — , which gives every terminal a throughput of = b/3. With
random routing, the counterclockwise links become the bottleneck with a load of
γ = 5/2, since half of the trafﬁc traverses 5 links in the counterclockwise direction.
This gives a throughput of 2b/5. Weighting the random decision sends 5/8ofthe
trafﬁc over 3 links and 3/8 of the trafﬁc over 5 links for a load of γ = 15/8 in both
directions giving a throughput of 8b/15. Adaptive routing, with some assumptions
on how the adaptivity is implemented, will match this perfect load balance in the
steady state, giving the same throughput as weighted random routing.
This example has shown how the choice of routing function can signiﬁcantly
affect load balance. However, worst-case throughput is only one of several possible
metrics a designer may wish to optimize. And as one would expect, different metrics
can lead to different conclusions about which of these four algorithms would be the
most appropriate. We explore some of these in Exercise 8.1.
8.2 Taxonomy of Routing Algorithms
We classify routing algorithms in terms of how they select between the set of possible
from source node x to destination node y.
Deterministic routing algorithms always choose the same path between x and y,
even if there are multiple possible paths (|R
| > 1). These algorithms ignore path
diversity of the underlying topology and hence do a very poor job of balancing load.
Despite this, they are quite common in practice because they are easy to implement
and easy to make deadlock-free.
Oblivious algorithms, which include deterministic algorithms as a subset, choose a
route without considering any information about the network’s present state. For
example, a random algorithm that uniformly distributes trafﬁc across all of the paths
is an oblivious algorithm.
Adaptive algorithms, adapt to the state of the network, using this state information
in making routing decisions. This information may include the status of a node or
link (up or down), the length of queues for network resources, and historical channel
The tornado example from the previous section includes examples of all three of
these types of routing.The greedy algorithm on the ring is an example of deterministic
routing. All packets between s and d travel in the same direction around the ring. The
uniform and weighted random routing schemes are examples of oblivious routing.
They choose between directions around the ring without taking into account the
state of the network. Finally, the adaptive algorithm makes its decision based on
channel load of the initial hop.
In these deﬁnitions, we described each type of routing algorithm over the set of
routes in R
— the minimal, or shortest path, routes from source to destination.