• Universal Globally Adaptive Load-Balancing 通用全局自适应负载平衡
  • 1. Motivation 动机
  • 2. 任意对称拓扑上的 UGAL
  • 3. 总结

Universal Globally Adaptive Load-Balancing 通用全局自适应负载平衡

之前的工作都是基于 torus 网络的负载平衡路由，而这篇文章的内容提出了一种适用于任意对称拓扑(arbitrary symmetric)的通用负载平衡算法。用有向图(directed graph)G(V,E)来表示拓扑，V是网络中的节点，E是边(通道)。因为图是对称的，因此每个节点的度是相同的。

最小自适应路由(MIN AD)在所有可能的最小路径中，根据输出队列长度自适应地选择每一跳的维度。然而严格的最小路由会在最坏情况流量模式下获得次优的性能，因为其无法利用非最小路由进行负载平衡；VAL 路由算法可以提供最佳的最坏情况吞吐量，然而这是以牺牲良性流量的性能为代价的。

为了保证任意对称拓扑上的最佳的最坏情况和最好情况(best-case)性能，提出一种在良性流量上进行最小路由，并在对抗流量模式下像 VAL 路由算法一样进行负载平衡。

1. Motivation 动机

考虑图6.1 的一个四节点的网络，理解 MIN AD 和 VAL 路由算法为什么不能在最坏情况或最佳情况获得最优性能。网络的容量为 2B/N = 4b bits/s。对于良性模式考虑均匀随机流量(UR)，其中每个节点均匀且随机地将流量发送到每个可能的目的地。良性模式如果要取得最佳性能，需要将每个数据包以最小路由方式发送，沿着连接源节点到目标节点的直接连接通道。因此MIN AD展示出UR上的最佳性能，吞吐量为4b bits/s，或到达100%的容量。

而对于排列流量(permutaiton)，如node0(2)发送所有的流量到node1(3)，反之亦然。最小路由会导致网络中通道上的负载分布不均匀。图6.1中的黑色箭头说明MIN AD仅使用的链路，而其他通道处于空闲状态。产生了 b bits/s 的吞吐量，或1/4的容量。

VAL 路由算法对任意的排列流量提供最佳性能。VAL 路由算法通过随机选择中间节点i路由数据包，如图6.2所示，首先从s-i，其次i-d。中间节点i可以选择为s/d，因此VAL选择一跳的概率为1/2(即选择目标节点或者源节点)，选择两条的路径概率也为1/2。因此每个链路有一个 0.5a的负载，吞吐量为 2b bits/s。

为了在这两种情况(worst-case, best-case)下都能获得最佳性能，利用了这样一个事实：对于 UR 上的最小路由，所有通道有均等负载，而在排列流量情况下，沿最短路径通道的队列被填满，而其他队列完全为空。队列占用率的这种不平衡表明这种不均衡的流量模式对于最小路由是不利的，并且数据包应该被非最小路由以平衡负载。为了对任何对抗性流量进行负载平衡，引入路由 VAL 路由方法，通过随机选择的中间节点 q 来进行从 s 到 d 的路由。s-q 和 q-d 的路径都是是最小路径。将此方法称为通用全局自适应负载平衡路由(UGAL)。

在数据包的源节点，UGAL 记录从 s-d 的最短路径的输出通道的队列长度qm。选中随机中间目的地 q，并记录沿着从 s-q 开始的最短路径的队列长度 qnm。当q=s或q=d时，qnm=qm。Hm 和 Hnm 分别表示路径 s-d 和 s-q-d 的跳数。为了平衡沿最小路径和非最小路径的负载，如果 $q_m{H}_m\le q_{nm}{H}_{nm}$，UGAL 按最小路由发送数据包，否则它沿s-q-d进行非最小路径路由。

图 6.3 显示，在 UR 流量上，UGAL 几乎始终以最少的方式进行路由。

然而，在排列流量上情况有所不同，UGAL 在非常低的负载下采用最小路由，但在中到高负载时部分采用非最小路由(图 6.4)。最后接近饱和时，它会最小化路由一半的数据包，并沿着中间节点按非最小路径路由另一半一半的数据包。由于这种misroute的自适应决策，UGAL 在 UR 和排列流量上都产生了最佳吞吐量。

图 6.5 显示了这两种流量模式的延迟-负载图。UGAL 在排列流量上达到50%饱和，在 UR 上达到100%饱和。

2. 任意对称拓扑上的 UGAL

UGAL 可以轻松扩展到任意对称拓扑。一旦在其源节点 s 处从源队列接收到发往目的地 d 的数据包，UGAL 将根据通道队列的拥塞情况决定是否以最小方式路由或以 VAL 的方式以非最小方式路由。$qm$ 表示为所有最短路径通道中最短的输出队列长度，即沿最短路径s-d的输出通道。然后 UGAL 选择一个随机中间目标节点 q。$q_{n}m$ 表示为来自 s-q 的所有最短路径通道中的最短输出队列长度。令s-d路径的跳数为Hm ，s-q-d 路径的跳数为 Hnm。如果 $q_m{H}_m\le q_{nm}{H}_{nm}$，UGAL 按最小路由发送数据包，否则它沿s-q-d进行非最小路径路由，其中每个阶段为最小的自适应的。

之后文章将 UGAL 应用于三种不同的节点对称拓扑：全连接图、2-D torus 和立方体连接环。我们使用以 C 语言编写的周期精确模拟器来评估每种拓扑上的 UGAL。所有拓扑中的总缓冲区资源保持恒定，即 VC 数量和 VC 通道缓冲区深度的乘积保持恒定。

其中全连接图需要2VC保证无死锁，而torus仍以3VC来保证无死锁，正如CQR GAL 和GOAL所实现的那样。

3. 总结

UGAL 是一种自适应路由算法，可保证最坏情况下的最佳性能，而不会牺牲良性（最佳情况）流量的任何局部性。 UGAL 通过根据通道队列的拥塞情况自适应地决定何时最小化或非最小化路由数据包来实现此属性。UGAL 是通用的，因为它可以应用于任意对称拓扑。我们将 UGAL 应用于三种对称拓扑 - 全连接图、环面网络和立方体连接循环，并通过广泛的模拟证明了其对每种拓扑的有效性。