Drangonfly网络拓扑结构
http://www.redsheeran.top/?p=76
Dragonfly Topology是由John Kim等人于2008年提出的一种网络拓扑结构(Technology-Driven, Highly-Scalable Dragonfly Topology)，被广泛地应用在高性能计算网结构上。
一份比较详细的参考ppt：From Hypercubes to Dragonflies a short history of interconnect
拓扑结构
Dragonfly的结构有三个层级：路由器(Router)、组(Group)、系统(system)，它的拓扑结构一般由以下这些参数描述：
| 参数 | 描述 | 参数 | 描述 |
|---|---|---|---|
| N | 网络中的终端（主机）数 | p | 每个路由器连接的终端数 |
| a | 每个组的路由器数 | k | 路由器的接口数 |
| k' | 每一组的有效接口数 | h | 每个路由器用于与其他组连接的频道个数 |
| g | 系统内组个数 | q | 输出端口队列长度 |
| qvc | Queue depth of an individual output VC(并不知道怎么翻译) | H | 跳数 |
| Outi | 路由i号输出端口 |
如上图所示，最底层的每个路由器与p个终端链接，并拥有a-1个与组内路由器通信的本地频道(Local Channel)，以及h个与其他组路由连接的全局频道(Global Channel)，由此可以计算出每个路由器的接口数k=p+h+a-1。在组(Group)的层面上，每组连接着ap个终端，并拥有ah条全局频道的连接(ah connections to global channels)，可以将一个组抽象为拥有k'=a(p+h)个端口的虚拟路由器(virtual router)，由于其拥有非常高的路由数因此在系统层面的网络上可以拥有很短的全局网络直径(global diameter)。
在最大规模( N=ap(ah+1) )的Dragonfly网络中没对组之间只能由一条连接，而在更小的网络中可以存在更多的连接。
a、p、h是描述一个Dragonfly网络主要的三个参数，它们可以取任意值，不过要是链路分在均衡这三项参数需要满足a=2p=2h，因为一个包在传输过程中会经过两条本地频道和一个全局频道，这样的比率可以维持平衡。网络保持平衡的条件：a与2p均大于等于2h。下图为一个a=4，p=h=2的网络：
在Dragonfly拓扑中组内路由的连接方式可以根据实际需求进行调节，下图是一个各项参数与上图相同的Dragonfly拓扑，不过为了让邻居路由器之间带宽更大改变了组内路由器之间的连接方式。组内的路由方式可以是任意的，如在Dragonfly+拓扑中组内使用胖树的结构。
路由算法
Dragonfly的路由算法主要有两类，最小路由算法与由Valiant提出的可以在系统层面上应用的算法。此外作者在论文中还提出了UGAL(Universal Globally-Adaptive Load-balanced)算法。
Minimal算法
将包直接发送到目的路由所在的组
Valiant的算法
先随机选一个组发送过去，如果不是目的路由所在的组则再由该组接收到的路由将其按最短路径发送给目的路由
UGAL算法
UGAL对每一个包在MIN与VAL算法之间选择，根据队列长度与跳数估算网络延时并选择最低延迟的道路，UGAL有本地与组内两种实现，UGAL-L使用当前路由节点的队列信息，而UGAL-G使用组内所有队列信息实现，可以在全局频道上负载均衡。