Other routing algorithms such as Globally Oblivious Adaptive Local (GOAL) [ 59 ] routing or
Channel-Queue Routing (CQR) [ 60 ] implement similar source-based adaptive routing algorithm
in a torus network such that minimal or nonminimal routing decision is made at the source router.
5.3.3 PROGRESSIVE ADAPTIVE ROUTING (PAR)
Unlike UGAL where adaptive routing decision is made only once at the source router, incremental
adaptive routing can be done using Progressive Adaptive Routing (PAR) [ 34 ] where the adaptive
routing decision is revisited at each hop. By incrementally adapting, a better sense of congestion
can be obtained - i.e., a congestion might not be observed at the source router but as the packet
traverses the network, congestion can be encountered. PAR attempts to avoid this limitation of
source adaptive routing by progressively re-evaluating the adaptive routing decision. However, to
ensure forward progress and prevent livelock, restrictions in the amount of adaptivity are needed.
In PAR routing, once a packet decides to route nonminimally (i.e., congestion is encountered), the
packet is routed non-minimally without revisiting the adaptive routing decision.
5.3.4 DIMENSIONALLY-ADAPTIVE, LOAD-BALANCED (DAL) ROUTING
Similar to PAR, DAL [ 6 ] routing also attempts to adapt to congestion that is not visible at the
source router and adapt en route to the destination. At each hop, all minimal and nonminimal paths
are compared using only local congestion information. By revisiting the routing decision at each
hop, a more accurate view of network congestion can be obtained and packets in-flight can switch
from minimal to nonminimal as well as from nonminimal to minimal routing. To avoid livelock,
restriction is applied such that packets can only be misrouted once per dimension. In addition, once
a packet becomes aligned 1 with the destination in a given dimension, no misrouting is allowed for
that particular dimension. Thus, DAL is able to incrementally select its nonminimal intermediate
node based on congestion - instead of randomly selecting an intermediate node in the network as
done with VAL implementation in adaptive routing algorithms such as UGAL.
INDIRECT ADAPTIVE ROUTING
Another class of adaptive routing that has been recently proposed is indirect adaptive routing [ 34 , 39 ].
When congestion information used to make adaptive routing is not directly available at the source
router, it becomes difficult to accurately estimate the congestion of the network. Congestion is often
measured using queue lengths which relies on backpressure. However, if congestion information
needs to propagate through multiple intermediate routers, backpressure needs to propagate through
the intermediate routers which increases the propagation delay of the congestion information. Con-
sider the dragonfly topology shown in Figure 5.1 . Assume a packet in R1 is making its global adaptive
routing decision of routing either minimally through gc 0 or non-minimally through gc 7 . The rout-
1 For a packet originating from source (x s ,y s , ..) to destination (x d ,y d , ..) , for dimension i ,if i s == i d , the packet is defined to
be aligned with the destination in dimension i .