Routing Implementation: Regardless of the routing decision mechanism, a route computation is
needed to determine the output port at each router.The route computation can be implemented
using either algorithmic logic or a table-based structure.
- Algorithmic: Based on the current node and destination information, a fixed logic can
be used to determine the output port. This can result in simple logic but inflexible routing
- Table-based routing: A lookup table can be implemented whose inputs are either the
source (or current node) and destination, and the table returns the appropriate output
5.1.1 OBJECTIVES OF A ROUTING ALGORITHM
In designing a routing algorithm for a given topology, the objective of the algorithm should include
path diversity : Exploit the path diversity of the topology, which can include both minimal
and non-minimal paths.
load balancing : Proper load-balancing of the channels across both benign and adversarial
traffic pattern is needed to achieve high throughput.
complexity effective : To minimize the impact of the routing algorithm on packet latency,
and load imbalance that may result from a fault in the network, the routing algorithm must be
able to be implemented efficiently. For example, it is not practical for a routing algorithm to
perform a simulated-annealing process to find the optimal load balance each time a network
In the rest of this chapter, we describe various routing algorithms that try to achieve these character-
istics on both conventional topologies (Chapter 3 ) as well as recently proposed high-radix topologies
(Chapter 4 ).
5.2 MINIMAL ROUTING
With minimal routing, all packets traverse the minimal hop count from source to its destination.
Minimal routing can be done either deterministically, obliviously, or adaptively.
5.2.1 DETERMINISTIC ROUTING
The simplest form of minimal routing is using dimension-ordered routing (DOR) where the routing
is restricted to traverse in a pre-determined order. For example, XY routing can be used on a 2D
mesh network where all packets first traverse in the X dimension and then, traverse the Y dimension
to reach its destination. This is the simplest form of routing in a given topology but does not exploit
any possible path diversity and can not load-balance channels on adversarial traffic patterns.