前言
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)(即源节点和目标节点坐标所构成的象限)中随机选择的中间节点路由每个数据包，确保生成的路径严格最小。**虽然[31]报告了一些排列的良好结果，但 ROMM 实际上比 DOR 具有更低的最坏情况吞吐量。问题在于使用最小路由(minimal routing)，不可能在对抗模式上实现良好的负载平衡。
2. Balancing a 1-Dimensional ring: RLB and RLBth 一维 ring 的 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。
未完待续…
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.