前言
A. Singh. Load-Balanced Routing in Interconnection Networks.PhD thesis, Stanford University, 2005.
总结自 A. Singh 的博士毕业论文 —— Load-Balanced Routing in Interconnection Networks
Oblivious Load Balancing 不经意路由负载平衡
文章提出了用于 torus 网络的随机、非最小、不经意路由算法——RLB和RLBth
1. oblivious routing 不经意/无关路由的背景知识
不经意算法仅使用源节点和目标节点的身份来选择从源到目标的路径。换句话说，路由决策是“忽略”网络状态的。不经意的算法可能会使用随机化来在可能的路径之间进行选择。根据路线的长度，它们也可以被分类为最小或非最小。
1. oblivious routing, adaptive routing & minimal/non-minimal routing algorithms
不经意路由算法(oblivious routing algorithms)仅根据消息源和目的地的身份在这些路径之间进行选择，而自适应算法(adaptive algorithms)则可以根据网络状态(拥塞信息)做出决策。
不经意的算法和自适应算法都可以使用**随机化(Randomization)**来在替代路径中进行选择。
最小算法(Minimal algorithms)沿着从源到目的地的最短路径路由所有数据包，而非最小算法(non-minimal)可能沿着更长的路径路由数据包，即进行了绕远如 VAL 路由算法。
常见的不经意算法 oblivious routing 包括——DOR、VAL 和 ROMM。
- 维序路由(DOR)，有时称为 e-cube routing，首先由 Sullivan 和 Bashkow 在A LARGE SCALE, HOMOGENOUS, FULLY DISTRIBUTED PARALLEL MACHINE, II 一文中首次提出[1]。**在 DOR 算法中，每个数据包首先只在一个维度上传递，只有当该维度的坐标一致后，再进入下一个维度进行传输。**由于其简单性，它已被大量用于互连网络中。但 DOR 在对抗性流量(adversarial traffic)模式上的糟糕表现引出了自适应路由方面的大量工作。
- Valiant 首先提出了如何使用随机化为任意流量模式提供有保证的吞吐量[2]。即将**路由分为两个阶段，第一阶段从源节点路由至全局中随机选择的中间节点(intermediate node)，第二阶段从中间节点路由至目标节点。两个阶段的具体路由算法都使用 DOR。**虽然 VAL 路由算法能够进行负载的平衡，在最坏模式下保证一定的性能，但是其破坏了局部性(locality)，在本地流量甚至平均流量上性能较差。
- 为了在获得随机化优势的同时保留局部性，Nesson 和 Johnson 提出了 ROMM 路由算法[3]，即随机、不经意、多阶段最小路由(Randomized, Oblivious, Multi-phase Minimal routing)。**与 VAL 一样需要两个阶段，但 ROMM 通过从最小象限(minimal quadrant)(即源节点和目标节点坐标所构成的象限)中随机选择的中间节点路由每个数据包，确保生成的路径严格最小。**虽然[3]报告了一些排列的良好结果，但 ROMM 实际上比 DOR 具有更低的最坏情况吞吐量。问题在于使用最小路由(minimal routing)，不可能在对抗模式上实现良好的负载平衡。
2. RLB and RLBth
1. Motivation of Balancing load 平衡负载的动机
下图 1.4 显示了8 node的 ring 的简化版本。对于良性流量模式，如最近邻居 (NN)，来自节点的所有流量均等分配到其相邻节点之间（一半到节点 i+1，一半到节点 i-1，模8/模k）。由于每个单向通道具有带宽b，因此如果流量只是沿着最小路径路由，则每个节点都可以以最佳速率2b (吞吐量, 2b) 注入流量。我们称这种流量为良性(benign)，因为如果使用最小路由来路由数据包，所有通道自然会实现负载平衡。
而对于对抗流量模式，我们考虑 ring 的 MR 的最坏情况流量(worst-case traffic)、龙卷风(TOR)流量。在 TOR 中，来自节点 i 的所有流量几乎绕环的一半发送到节点 i+3(i + k/2 - 1)。图 1.5 显示了最小路由 TOR 导致顺时针通道上的高负载，保持逆时针通道完全空闲。这会导致相当大的负载不平衡，吞吐量较差(单向通道带宽为b，每个顺时针通道需要维持3条不同数据流，故吞吐量为b/3)。
如果要在 TOR 等对抗模式上获得良好的性能，需要非最小路由(绕环的长距离)路由一些流量以平衡负载。先按照 Valiant 的建议，通过完全随机化路由 (VAL) 来平衡 TOR 流量，从节点 i 发送到随机中间节点 j，然后从 j 发送到 i+3。这两个阶段中的每一个阶段都是完全随机的路由，因此每个阶段平均使用 2 个 links，故整个路由使用 4 个 links。而最小路由是 3 个 links。即使 VAL 平均比最小路由多遍历一个链路 link，VAL 的每节点吞吐量在 TOR 上更高，为b/2(其使用了双向的channels，且每条 link 上平均有两条数据流)。纯随机路由的问题在于它破坏了局部性。对于 NN 流量模式，吞吐量仍然为 b/2，而 MR 为 2b。文章提出的路由算法，努力在不牺牲良性流量固有的局部性的情况下实现良好的最坏情况性能。
2. 一维 ring 的 RLB and RLBth
**在对抗性流量中，最小路由算 MIN 无法均衡负载，使得一个 8 node ring 的吞吐量降低至 b/3。**任何 k-ary n-cube 的网络容量为 2B/N = 8b/k(用 UR 流量的理想吞吐量作为网络容量，将吞吐量和提供的负载归一化为网络容量，Bw 为对分带宽，一般为双向带宽，B/N 为一个单向通道的带宽，故网络容量为 2B/N)。
所以一个 8 node ring 在最小路由和 TOR 流量模式下的吞吐量为 b/3 即 0.33b，33.3%的网络容量。一般而言，最小路由 MIN 的吞吐量会逐渐降低到 25% 的容量，这意味着最坏情况下的性能非常差。即 b/(k/2-1) / (8b/k) = k/8 / (k/2-1)，当对于较大的 k 时，吞吐量小于 0.25。
定理 3. 对于具有大基数 radix 的 torus，最小路由 MIN 的最坏情况(worst-cast)吞吐量最多为容量的 25%。
MIN 在最坏情况下表现差的原因是硬流量模式(hard traffic)可能会导致网络链路中的严重负载不平衡。为了平衡所有链路上的负载，路由算法必须沿着非最小路径(non-minimal)发送一些流量以应对对抗性流量。考虑节点环上的龙卷风流量模式，使用非最小路由算法，将所有消息的 5/8 沿环的短方向(short direction)顺时针(clockwise)发送三跳，并将其余所有消息即 3/8 沿长、逆时针方向发送(见图 3.1)。
顺时针方向的每个 link 承载 5a/8 x 3 = 15a/8的流量负荷，因为每个link承载三条短数据流。类似地，逆时针方向的每个链接都承载 3a/8 x 5 = 15a/8 的流量负载。因此，流量是完美平衡的——每个链路都有相同的负载。由于这种负载平衡。吞吐量为 b / (15a/8) = 8b/15，与最小路由的 b/3 相比，每个节点的吞吐量增加了 60% 的容量。由于该方案基于目的地的位置进行非最小路由，因此我们将其称为随机本地平衡路由(Randomized Local Balanced routing (RLB))[4]。
更一般地，若源节点 s 发送流量到目标节点 d，那么 s 和 d 之间的短距离是△ = min(|s-d|, k - |s-d|)，如果短路径为顺时针则 r = +1，否则为 -1。为了平衡负载，在发送每个数据包时上以概率 P+r = k-△/k 在短路径上传输，以 P-r = △/k 的概率在长路径方向上传输。因此每个方向上 channels 的负载均为(k-△)△/k。
对于最近邻居流量(NN)，每个node分别发送一半流量到i+1,i-1的节点上。即△ = 1，P+r = k-△/k = 7/8，P-r = 1/8，故每个方向上channel的负载为 (a/2) x 7/8 + (a/2) x 1/8 x 7 = 7/8 a，所以吞吐量为 b/(7/8 a) = 8/7b。
简单的一维比较表明，RLB 能够在对抗性流量模式上提供良好的性能，而无需牺牲良性流量中的所有局部性。它在龙卷风流量上实现了 0.53 的吞吐量，比最小算法的吞吐量有了巨大的改进，但在最近邻居流量上实现的吞吐量不如最小算法，但比完全随机路由 (VAL) 的 0.5 的吞吐量好得多。事实上，我们可以证明，对于 1 维环面，RLB 与 VAL 一样，可以提供最佳的最坏情况性能，同时在良性流量上的执行效率更高：
定理 4. RLB 可以在 ring 上提供最佳的 worst-case 吞吐量。
同时为了提高 RLB 在本地流量上的性能(例如最近邻居)，我们可以修改选择短路径或长路径的概率函数 P，以便对于非常本地的流量，RLB 始终最小化路由。具体来说，如果 △ < k/4 (k node ring 的平均跳数)，则必须对消息进行最小路由(短路径)。因此，如果△ < k/4，P+r = 1 and P-r = 0，否则 Pr 与 RLB 中的相同。将此修改后的版本称为 RLB threshold 或 RLBth。通过此修改，RLBth 实现了最近邻居流量的吞吐量为2，同时保留了龙卷风流量模式的吞吐量。
3. 高维 tori 的 RLB
1. 为了将 RLB 扩展到高维的 tori，首先选择不同的象限
例如 n dimensions in a k-ary n-cube，假设源节点为{s1,s2,…,sn}，目标节点为{d1,d2,…,d3}，xi是node x在维度i的坐标。然后计算最小距离向量△ = {△1,△2,…,△n}，其中△i = min(|si-di|, k-|si-di|)，从而可以得出最小方向向量r = {r1,r2,…,rn}，如果最短距离顺时针则方向为+1，否则为-1。最终可以计算出每个维度的r’，对于+1方向概率为Pri = (k-△i)/k，-1方向概率为1 - Pri = △i/k。
举例来说，对于s = (0,0)，d = (2,3) 在8x8 的2D torus。距离向量为△=(2,3)，最小方向向量为(+1,+1)，概率P为(0.75,0.625)。故每个数据包都有四个象限的选择，包括(+1,+1),(+1,-1),(-1,+1),(-1,-1)，概率分别为0.469,0.281,0.156和0.094。每一个方向是 2D-torus 中的一个象限(quadrant)，如图3.2。由概率可得，r’=(+1,+1)发送最多的流量，(-1,-1)发送的最少。并且这样的每个方向的权重会平衡任何流量模式的负载。
2. 选择象限之后，需要利用象限中丰富的路径，随机选择中间节点
为了平衡通道间的负载，需在象限内随机选择一个中间节点q，先从s-q，再从q-d进行路由。每个路由阶段随机选择维度的顺序，o，oi是第i个选择传输的维度。为两个路由阶段独立选择维度顺序。这类似于 VAL，但随机化仅限于选定的象限范围内。每个路由阶段需要随机选择维度的顺序，不然会导致不同链路的负载的不平衡。
重要的是，数据包在路由的过程中可能会回溯(backtrack)。**如果每个阶段的路由算法为最小路由MIN，则短路径可能不在由选定的象限所指定的方向上。**为了避免回溯(负载分布不均匀)，限制路由在两个路由阶段期间沿指定的方向行进：从 s 到 q 和从 q 到 d。这些方向是根据中间节点 q 所在的象限而固定的，如图 3.2 所示。
假设在上面的示例中，在 8-ary 2-cube 中从 (0,0) 路由到 (2,3)，我们选择象限(-1,+1)。因此，我们正朝着 x 的负方向前进，并在 y 的正方向上前进。然后我们从x=[3,4,5,6,7,0] 和y=[1,2,3] 中随机选择。假设此选择产生中间点(7,1) 。最后，我们随机选择维度顺序，第一阶段(0,1)，第二阶段(0,1)(请注意，这两个顺序可能不同)，这意味着我们将在两个阶段中先路由x，然后再路由y。**结合我们选择的方向、中间节点和维度顺序，得到如图 3.4 所示的最终路线。请注意，如果允许回溯，则最小路由器将在第一阶段后选择方向，因为它在+x的方向上只有三跳，-x的方向上有五跳。**图 3.5 显示了如果两个阶段的方向都是固定的如何避免回溯。虚线路径表示从 s 到 q 到 d 的每个阶段，如果遵循维序路由(并贪婪地遍历维度，即选择该维度中的最短路径，然后贪婪地遍历维度)所采取的路径。根据 q 所在象限固定方向集，如粗体路径所示。
4. 高维 tori 的 RLBth
和1维 tori 类似，对于选择象限的概率函数进行了修改。具体如下：
- 如果△i < k/4，即最短距离小于 torus 在每维度的平均跳数，那么设置 Pri = 1 and P-ri = 0；
- 否则仍旧按照概率 Pri = (k-△i)/k and P-ri = △i/k 传输数据包；
- k/4 这个阈值是一个 k node ring 在每维度的平均跳数。
References
[1] L. G. Valiant and G. J. Brebner, “Universal schemes for parallel communication,” in Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC ’81, Milwaukee, Wisconsin, United States: ACM Press, 1981, pp. 263–277. doi: 10.1145/800076.802479.
[2] H. Sullivan, S. Associates, T. R. Bashkow, and D. Klappholz, “A LARGE SCALE, HOMOGENOUS, FULLY DISTRIBUTED PARALLEL MACHINE, II”.
[3] T. Nesson and S. L. Johnsson, “ROMM routing on mesh and torus networks,” in Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures - SPAA ’95, Santa Barbara, California, United States: ACM Press, 1995, pp. 275–287. doi: 10.1145/215399.215455.
[4] A. Singh, W. J. Dally, B. Towles, and A. K. Gupta, “Locality-preserving randomized oblivious routing on torus networks,” in Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, Winnipeg Manitoba Canada: ACM, Aug. 2002, pp. 9–13. doi: 10.1145/564870.564873.