5.2.2 OBLIVIOUS ROUTING
If path diversity exists in the topology (i.e., there is more than one minimal path between a source
and a destination), oblivious minimal routing can be used and take advantage of path diversity. All
routing paths consist of minimal hop count but different paths can be used according to the routing
algorithm. Examples of minimal oblivious routing include ROMM [ 50 ], O1turn [ 57 ], and CDR [ 3 ].
ROMM (Randomized, Oblivious Multi-phase Minimal) routing consists of p phases and
1 randomly selected intermediate nodes. The packets are routed to an intermediate node in each
of the first p − 1 phases and routed to its destination in the final phase. The intermediate nodes
are selected such that the routing is still minimal - i.e., within each phase, the routing output at
each route is productive as the packet moves closer to the destination. To avoid routing deadlock, p
virtual channels (VC) [ 21 ] are needed. While ROMM provides very high path diversity, randomized
DOR or O1turn routing [ 57 ] on a 2D mesh network limits path diversity to 2. For each packet,
O1turn routing algorithm randomly select either XY or YX routing - with a probability of 1 / 2,
packets are routed using XY DOR while the other packets are routed using YX DOR. This routing
algorithm maintains the simplicity of a DOR algorithm except for the need for an extra VC. Packets
routed using XY use one VC while packets routed using YX use another VC to avoid routing
deadlock. Despite providing only a path diversity of 2, it has been shown to be near-optimal in its
performance [ 57 ].
A variation of O1turn routing algorithm is the class-based deterministic routing (CDR) [ 3 ]
algorithm. Similar to O1turn, both XY and YX routing is used but instead of randomly selecting a
packet for either XY or YX routing, the routing path is determined by the packet class. For example,
if there are request and reply traffic class in the network, packets in the request class use one routing
algorithm (i.e., XY ) while the other class (reply traffic) uses YX routing. CDR exploits path diversity
of the topology while all packets still traverse minimal hop count. Compared to O1turn, this routing
algorithm has the additional benefit of reducing the number of VCs needed since another separate
set of VC are not need to avoid protocol deadlock as the same VCs can be used for both routing and
protocol deadlock avoidance.
Minimal routing minimizes the hop count but when network congestion occurs, taking a non-
minimal route can sometimes reduce the network latency. In addition, for adversarial traffic patterns,
better load-balancing of the channels can be achieved with non-minimal routing and result in
higher network throughput. In this section, we describe an oblivious non-minimal routing algorithm
(Valiant's algorithm [ 66 ]) and several different adaptive non-minimal routing algorithm including
Universal Globally Adaptive routing algorithm (UGAL) [ 58 ].