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

164 CHAPTER 8 Routing Basics
Relation 8.3, the third relation, is also incremental and is used in a similar way. The
only difference is that the inputs to the function are the previous channel used by
the packet and its destination.
Compared to all-at-once routing, there is no overhead associated with carrying
the route along with a packet, but the routing relation may have to be evaluated many
times, which potentially increases the latency of a packet. Another important point is
that incremental algorithms cannot implement every routing strategy possible with
all-at-once routing. This is because we are using little or no history from a packet to
compute its next hop. For example, with an all-at-once algorithm, we could design
a routing algorithm for a 2-D mesh where packets are only routed vertically or
horizontal through a particular node. (No packets turn from a horizontal to vertical
dimension at this node.) However, this would be impossible with the second routing
relation (Relation 8.2) because there is no way to distinguish a packet that has arrived
from a vertical channel from one that arrived from a horizontal channel. Of course,
the third relation could alleviate this problem, but it still does not cover many all-
at-once algorithms. (See Exercise 8.2.)
The third form of the routing relation (Relation 8.3) is also incremental, but bases
the routing decision on a packet’s current channel c rather than its current node, w.
In this case, the routing relation takes the current channel c and the destination node
y and returns a set of channels D = R(c, y). Basing this decision on the channel c
over which a packet arrived at node w rather than on w itself provides just enough
history to decouple dependencies between channels, which is important for avoiding
deadlock (Chapter 14).
Whichever form of R we use, unless the routing is deterministic, it returns a set
of possible paths or channels. The selection function ρ is used to choose the element
of this set that will be used. If ρ uses no information about the network state in
making this choice, the routing will be oblivious. If, on the other hand, ρ bases the
choice on output channel availability, the routing will be adaptive.
8.4 Deterministic Routing
The simplest routing algorithms are deterministic they send every packet from
source x to destination y over exactly the same route. The routing relation for a
deterministic routing algorithm is a function R : N ×N → P , for example. As we
saw in Section 8.1, this lack of path diversity can create large load imbalances in the
network. In fact, there is a traffic pattern that causes large load imbalance for every
deterministic routing algorithm. So, for a designer interested in the worst case, these
algorithms would not be a first choice. However, deterministic algorithms still have
their merits.
Many early networks adopted deterministic routing because it was so simple
and inexpensive to implement. What may be surprising is that deterministic routing
continues to appear in networks today. This is especially true for irregular topolo-
gies, where designing good randomized or adaptive algorithms is more difficult. For

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