Networking Reference

In-Depth Information

4. HIGH-RADIX TOPOLOGIES

Figure
4.8
(b), if the details of the intra-group is ignored, a group can be viewed as a virtual high-radix

router. This very high radix,
k
>> k
enables the system level network to be realized with very low

global diameter (the maximum number of expensive global channels on the minimum path between

any two nodes). Up to
g
=
ah
+

1 groups (
N
=
ap(ah
+

1
)
terminals) can be connected with a

global diameter of one. In contrast, a system-level network built directly with radix
k
routers would

require a larger global diameter.

In a maximum-size (
N
=
ap(ah
+
1
)
) dragonfly, there is exactly one connection between

each pair of groups. In smaller dragonflies, there are more global connections out of each group

than there are other groups. These excess global connections are distributed over the groups with

each pair of groups connected by at least

ah

+

1

channels. The dragonfly parameters
a
,
p
, and
h

can have any values. However, to balance channel load on load-balanced traffic, the network should

have
a

g

2
h
. Because each packet traverses two local channels along its route (one at each

end of the global channel) for one global channel and one terminal channel, this ratio maintains

balance. Additional details of routing and load-balancing on the dragonfly topology will be discussed

in Chapter
5
. Because global channels are expensive, deviations from this 2:1 ratio should be done

in a manner that overprovisions local and terminal channels, so that the expensive global channels

remain fully utilized. That is, the network should be balanced so that
a
≥

=

2
p

=

2
h
.

The scalability of a balanced dragonfly is shown in Figure
4.9
. By increasing the effective

2
h
, 2
p
≥

1,000,000

100,000

10,000

1,000

100

10

1

0

20

40

60

80

Router radix (k)

Figure 4.9:
Scalability of the dragonfly topology as router radix increases. 1D flattened butterfly is

assumed for both the intra- and the inter-group networks.

radix, the dragonfly topology is highly scalable - with radix-64 routers, the topology scales to over

256k nodes with a network diameter of only three hops. In comparison, a 2D flattened butterfly

using radix-64 routers can scale to approximately 10k nodes while a 3D flattened butterfly can only

scale up to 64k nodes. Arbitrary networks can be used for the intra-group and inter-group networks

in Figure
4.8
. However, to minimize the network cost, a flattened butterfly with the smallest number

of dimensions will be appropriate. A simple example of the dragonfly is shown in Figure
4.10
with