Networking Reference
In-Depth Information
G d
G s
R s
R a
R b
R d
G i
minimal route
non-minimal route
R x
R y
Figure 5.4: Routing and virtual channel assignment on the dragonfly topology.
AD uses a sequential allocator. The routing is identical to adaptive routing in a folded-Clos[ 40 ]
where the folded-Clos is flattened into the routers of the flattened butterfly. Thus, the intermediate
node is chosen from the closest common ancestors and not among all nodes. As a result, even though
CLOS AD is non-minimal routing, the hop count is always equal or less than that of a corresponding
folded-Clos network.
The dragonfly topology routing differs as the routing consists of an intra-group and inter-group
routing. Because the inter-group or the global channels are more expensive, the main objective is to
load-balance these global channels with adaptive routing.
Minimal routing in a dragonfly from source node s attached to router R s in group G s to
destination node d attached to router R d
in group G d
traverses a single global channel and is
accomplished in three steps:
Step 1 :If G s = G d and R s does not have a connection to G d , route within G s from R s to
R a , a router that has a global channel to G d .
Step 2 :If G s = G d , traverse the global channel from R a
to reach router R b
in G d .
Step 3 :If R b =
R d , route within G d from R b to R d .
Step 1 and Step 3 are intra-group routing while Step 2 is the inter-group routing. This minimal
routing works well for load-balanced traffic, but results in very poor performance on adversarial
traffic patterns.
To load-balance adversarial traffic patterns, Valiant's algorithm [ 66 ] can be applied at the
system level — routing each packet first to a randomly-selected intermediate group G i and then
to its final destination d . Applying Valiant's algorithm to groups suffices to balance load on both
Search MirCeyron ::

Custom Search