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

162 CHAPTER 8 Routing Basics
of the traffic routes in the clockwise direction around the ring, leaving all of the
counterclockwise channels idle and loading the clockwise channels with 3 units of
traffic 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 traffic traverses 5 links in the counterclockwise direction.
This gives a throughput of 2b/5. Weighting the random decision sends 5/8ofthe
traffic over 3 links and 3/8 of the traffic 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 significantly
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
paths R
xy
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
xy
| > 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 traffic across all of the paths
in R
xy
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
load information.
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 definitions, we described each type of routing algorithm over the set of
routes in R
xy
the minimal, or shortest path, routes from source to destination.

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