Minimal Deterministic : The minimal deterministic algorithm chooses the next hop in a
deterministic order - similar to dimension-ordered routing (DOR). An example of DOR on flattened
butterfly includes routing packets along increasing dimension order. This routing algorithm does
not require additional virtual channels (VCs) [ 21 ] for routing deadlock but no path diversity exists
and results in a performance similar to a conventional butterfly.
Minimal Adaptive : The minimal adaptive algorithm operates by choosing for the next hop
the productive channel with the shortest queue. To prevent deadlock, n VC are used with the VC
channel selected based on the number of hops remaining to the destination.
188.8.131.52 Non-minimal Routing
Routing non-minimally in a flattened butterfly provides additional path diversity and can achieve
load-balanced routing for arbitrary traffic patterns. Consider, for example, Figure 4.7 (b) and suppose
that all of the traffic from nodes 0-3 (attached to router R0 ) was destined for nodes 4-7 (attached
to R1 ). With minimal routing, all of this traffic would overload channel (R0 ,R1 ). By misrouting a
fraction of this traffic to R2 and R3 , which then forward the traffic on to R1 , load is balanced. With
non-minimal routing, a flattened butterfly is able to match the load-balancing (and non-blocking)
properties of a Clos network - in effect acting as a flattened Clos .
We consider routing in a k -ary n -flat where the source node s , destination node d , and current
node c are represented as n -digit radix- k numbers, e.g., s n − 1 ,...,s 0 . At a given step of the route, a
channel is productive if it is part of a minimal route; that is, a channel in dimension j is productive
if c j
d j after traversing the channel.
Valiant (VAL) [ 66 ]: Valiant's algorithm load balances traffic by converting any traffic pattern
into two phases of random traffic. It operates by picking a random intermediate node b , routing
minimally from s to b , and then routing minimally from b to d . Routing through b perfectly balances
load (on average) but at the cost of doubling the worst-case hop count, from n to 2 n . While any
minimal algorithm can be used for each phase, our evaluation uses dimension order routing. Two
VCs, one for each phase, are needed to avoid deadlock with this algorithm.
Universal Globally-Adaptive Load-balanced (UGAL [ 58 ], UGAL-S) : UGAL chooses between
MIN AD and VAL on a packet-by-packet basis to minimize the estimated delay for each packet as
described earlier in Section 5.3.2 . With UGAL, traffic is routed minimally on benign traffic patterns
and at low loads, matching the performance of MIN AD, and non-minimally on adversarial patterns
at high loads, matching the performance of VAL. UGAL-S is identical to UGAL but with a sequential
allocator while UGAL uses greedy allocator [ 40 ].
Adaptive Clos (CLOS AD): Like UGAL, the router chooses between minimal and non-
minimal on a packet-by-packet basis using queue lengths to estimate delays. If the router chooses
to route a packet non-minimally, however, the packet is routed as if it were adaptively routing to
the middle stage of a Clos network. A non-minimal packet arrives at the intermediate node b by
traversing each dimension using the channel with the shortest queue for that dimension (including
a “dummy queue” for staying at the current coordinate in that dimension). Like UGAL-S, CLOS
d j before traversing the channel, and c j