8.3 The Routing Relation 163

Therefore these algorithms are referred to as minimal. As we have already seen, it’s

often important to include non-minimal routes and in this case, routing functions

choose paths from the set of all minimal and non-minimal routes R

xy

. These algo-

rithms are refered to as non-minimal. Again, from our simple example on the ring,

the greedy algorithm is minimal, while randomized and adaptive algorithms are non-

minimal.

8.3 The Routing Relation

It is useful to represent the routing algorithm as a routing relation R and a selection

function ρ. R returns a set of paths (or channels for an incremental routing algorithm),

and ρ chooses between these paths (or channels) to select the route to be taken. With

this division of the algorithm, issues relating to channel dependencies and deadlock

deal with the relation R while issues relating to adaptivity deal with the selection

function ρ. We address deadlock in detail as part of Chapter 14.

Depending on whether our algorithm is incremental, and whether it is node-

based or channel-based, we deﬁne R in three different ways:

R : N × N → P(P ) (8.1)

R : N × N → P(C) (8.2)

R : C × N → P(C) (8.3)

where P(X) denotes the power set, or the set of all subsets, of the set X. This notation

allows us to reﬂect the fact that a routing relation may return multiple paths or

channels, one of which is chosen by the selection function.

When the output of the routing relation is an entire path, as in Relation 8.1 —

the ﬁrst of our three routing relations, the routing algorithm is referred to as all-

at-once. This name reﬂects exactly how the routing algorithm is used. When a packet

is injected into the network at the source node x destined to node y, the routing

relation is evaluated: U = R(x,y). Since U may be a set of routes, one is selected and

assigned to the packet. Of course, U does not have to include all possible routes R

xy

or even all minimal routes R

xy

, and in the case of a deterministic routing algorithm,

it returns only one (|U |=1). Once the route is chosen, it is stored along with the

packet. As we will see in Chapter 11, all-at-once routing minimizes the time spent

evaluating the routing relation for each packet, but this advantage comes with the

overhead of carrying the routes inside the packets.

An alternate approach is incremental routing, where the relation returns a set of

possible channels. Instead of returning an entire path at once, the routing relation is

evaluated once per hop of the packet. The output of the relation is used to select

the next channel the packet follows. In Relation 8.2, the second form of the routing

relation, for example, the inputs to the relation are the packet’s current node w and

its destination y. Evaluating the relation gives us a set of channels D = R(w, y),

where each element of D is an outgoing channel from w or D ⊆ C

Ow

. The selec-

tion function is then used to choose the next channel used by the packet from D.

This incremental process is repeated until the packet reaches its ﬁnal destination.

Start Free Trial

No credit card required