Dragonfly 拓扑的路由算法
John Kim, William J. Dally 等人在 2008 年的 ISCA 中提出技术驱动、高度可扩展的 Dragonfly 拓扑。而文章中也提到了 针对 Dragonfly 拓扑的路由算法。本文对其中提到的路由算法进行汇总归纳。主要是讨论蜻蜓拓扑的最小和非最小路由算法。
1. Dragonfly 上的路由
图 7 显示了如何使用虚拟通道 (VC) 来避免路由死锁。为了防止路由死锁，最小路由需要两个VC，非最小路由需要三个VC。此分配消除了由于路由而产生的所有通道依赖性。对于某些应用程序，可能需要额外的虚拟通道来避免协议死锁 - 例如，对于共享内存系统，请求和回复消息需要单独的虚拟通道集。
(1)最小路由
Dragonfly 中位于组Gs中的路由器Rs，连接着源节点s，到组Gd中的路由器Rd的目标节点d的最小路由经过单个全局通道，由三步组成：
- 步骤 1：如果 Gs != Gd，并且 Rs 没有到 Gd 的连接，在 Gs 内从 Rs 路由到 Ra，Ra 路由器具有到 Gd 的全局通道。
- 步骤 2：如果 Gs != Gd，则从 Ra 经过全局信道到达 Gd 中的路由器 Rb。
- 步骤 3：如果 Rb != Rd，则在 Gd 内从 Rb 到 Rd 路由。
这种最小路由非常适合负载平衡流量(load-balanced traffic)，但会导致对抗性流量模式的性能非常差。
(2)非最小路由
为了对对抗性流量模式进行负载平衡，Valiant 的算法可以应用于系统级别 - 首先将每个数据包路由到随机选择的中间组 Gi，然后路由到其最终目的地 d。将 Valiant 的算法应用于组足以平衡全局和本地通道上的负载。这种随机非最小路由最多遍历两个全局通道，需要五个步骤：
- 步骤 1：如果 Gs != Gi 并且 Rs 没有到 Gi 的连接，则在 Gs 内从 Rs 路由到 Ra，一个具有到 Gi 的全局通道的路由器。
- 步骤 2：如果 Gs != Gi 从 Ra 经过全局信道到达 Gi 中的路由器 Rx。
- 步骤 3：如果 Gi != Gd 并且 Rx 没有到 Gd 的连接，则在 Gi 内从 Rx 路由到 Ry(具有到Gd 的全局通道的路由器)。
- 步骤 4：如果 Gi != Gd，则遍历从 Ry 到 Gd 中的路由器 Rb 的全局通道。
- 步骤 5：如果 Rb != Rd，则在 Gd 内从 Rb 到 Rd 路由。
2. 评估
实验评估最小路由算法 (MIN)，Valiant (VAL)路由，UGAL 通用全局自适应负载平衡(UGAL-G，UGAL-L)。UGAL逐个数据包在 MIN 和 VAL 之间进行选择以平衡网络负载。通过使用队列长度和跳数来估计网络延迟并选择延迟最小的路径来做出选择。实验实现了两个版本的 UGAL：
- UGAL-L —— 使用当前路由器节点的本地队列信息。
- UGAL-G —— 使用 Gs 中所有全局通道的队列信息(原文中是使用 Gs 中所有全局通道的队列信息，但应该是具有全局信息)。假设了解其他路由器上的队列长度。虽然难以实现，但这代表了 UGAL 的理想实现，因为负载平衡需要全局通道，而不是本地通道。
理想的 UGAL 路由称为 UGAL-G(具有全局信息的 UGAL)，假设精确的全局网络状态信息可用，并使用路径上所有链路上的总队列长度来估计路径上最小的数据包延迟。令 T Q M I N TQ_{MIN} TQMIN 为 M I N MIN MIN 路径的总队列长度， T Q V L B TQ_{VLB} TQVLB 为 V L B VLB VLB 路径的总队列长度。若
T Q M I N ≤ T Q V L B + T TQ_{MIN} \leq TQ_{VLB} + T TQMIN≤TQVLB+T
否则为 VLB 路径。这里的 T 是一个偏移常数，可以调整它来决定路径选择将在多大程度上偏向 MIN 路径(T 的较大值优先考虑 MIN 路径)。
使用良性和对抗性合成流量模式来评估不同的路由算法。对于均匀随机 (UR) 等良性流量，MIN 足以提供低延迟和高吞吐量，如图 8(a)。 VAL 实现了大约一半的网络容量，因为它的负载均衡使全局通道上的负载加倍。UGAL-G 和 UGAL-L 都接近 MIN 的吞吐量，但在接近饱和时延迟稍高。较高的延迟是由使用并行或贪婪分配引起的，其中每个端口的路由决策是并行做出的。使用顺序分配将减少延迟，但代价是分配器更复杂。
为了测试路由算法的负载平衡能力，使用最坏情况 (WC) 流量模式，其中组 Gi 中的每个节点将流量发送到组 Gi+1 中随机选择的节点。通过最小路由，此模式将导致每个组 Gi 中的所有节点通过单个全局通道将其所有流量发送到组 Gi+1，需要非最小路由通过将大部分流量分散到其他全局通道来平衡此流量模式的负载。此 WC 流量的评估如图 8(b) 所示。由于 MIN 通过单个通道转发来自每个组的所有流量，因此其吞吐量限制为 1/ah。VAL 实现略低于 50% 的吞吐量，这是该流量的最大可能吞吐量。UGAL-G 实现了与 VAL 相似的吞吐量，但 UGAL-L 导致吞吐量有限，并且在中间负载时平均数据包延迟较高。
未完待续…