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

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 trafﬁc 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 deﬁnitions, 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.

Start Free Trial

No credit card required