第 8 章 路由基础路由routing是在给定拓扑中为分组选择从源节点到目的节点路径的过程。有了拓扑——网络的道路地图——之后路由是顺理成章的下一步在地图上选一条能到达目的地的路线。拓扑决定网络的理想性能而路由是决定这一潜力有多少能实现的两个关键因素之一。另一个关键因素是流量控制在第 12、13 章讨论。网络采用的路由算法至关重要原因有几点。好的路由算法即使在非均匀流量模式如置换流量下也能在网络通道间平衡负载。通道负载越均衡网络的吞吐率就越接近理想值。令人惊讶的是今天已建造并使用的许多路由器在负载均衡方面做得很差每对节点之间的流量只走一条预先确定的单一路径。如你所料非均匀流量模式会在这类路由算法下引起严重的负载失衡导致吞吐率欠佳。不过这些路由选择至少可以部分解释——这些路由器大多是为了优化路由算法的另一个重要方面而设计的短路径长度。设计良好的路由算法还要让路径尽可能短减少跳数和消息的总延迟。可能不那么显而易见的是最小路由总是选择最短路径往往与平衡负载、最大化吞吐率相矛盾。事实上对无意oblivious路由算法而言为了在所有流量模式下改善负载均衡我们被迫增加所有消息的平均路径长度——反之亦然。这种折衷之所以存在于无意算法是因为它们不把当前流量模式纳入路由决策。第 9 章将更详细地探讨这类算法。另一方面聪明的设计者可能提出一种两全其美的方法不像无意算法那样独立于流量模式来选择算法而是适应当前的流量状况——对均匀流量这类容易的流量模式走最小路由对困难的非均匀流量模式则改用非最小路由。这个简单的想法构成了自适应路由算法adaptive routing algorithm的基础第 10 章将探讨这类算法。这类算法的潜在优势是同时实现负载均衡和局部性短路径然而我们将看到实际的设计问题使这一目标难以实现。路由算法的另一个重要方面是它在网络存在故障时仍能工作的能力。如果某个算法被硬连线进路由器而一条链路或一个节点失效整个系统就失效了。但如果算法可以重新编程或适应故障系统就能继续运行只损失少量性能。显然这对高可靠性要求的系统至关重要。最后路由与网络的流量控制相互影响两者的精心设计往往是避免死锁和/或活锁所必需的第 14 章。我们对路由的讨论从下面的简短例子开始随后讨论路由分类法并介绍确定性路由算法。第 9 章继续讨论确定性与无意路由第 10 章讨论自适应路由最后第 11 章讨论路由机制。8.1 一个路由示例考虑在图 8.1 所示 8 节点环网上路由的问题。如果排除折返backtracking即重访网络中的节点这里的路由决策是二元的对每个从 s 发往 d 的分组要么沿顺时针方向、要么沿逆时针方向绕环发送。即使拓扑如此简单、只有二元决策也有许多种可能的路由算法。下面是其中几种贪心Greedy总是沿环上最短的方向发送分组。例如从 0 到 3 总是顺时针路由从 0 到 5 总是逆时针路由。如果两个方向距离相同随机选一个方向。均匀随机Uniform random为每个分组随机选择方向两个方向概率相等。加权随机Weighted random为每个分组随机选择方向但短方向加权概率 1 − Δ/8长方向加权概率 Δ/8其中 Δ 是源与目的之间的最小距离。自适应Adaptive沿本地通道负载最低的方向发送分组。负载可以用该通道的队列长度、或它在最近 T 个时隙内发送的分组数来近似。注意由于我们不允许折返这个决策只在源端做一次。图 8.18 节点环网。哪种算法给出最好的最坏情形吞吐率绝大多数人会选择贪心算法。¹ 然而结果表明贪心算法在这个拓扑上并不能给出最好的最坏情形吞吐率。¹ 环上路由这个问题曾作为 2002 年博士资格考试题出现超过 90% 的考生一开始都选了贪心算法。图 8.28 节点环网上的龙卷风流量。采用贪心路由时全部流量沿顺时针方向绕环流动逆时针通道全部闲置。要看出贪心路由如何惹上麻烦考虑龙卷风流量模式每个节点 i 向 i 3 (mod 8) 发送分组如图 8.2 所示。上述 4 种路由算法在 8 节点环上跑龙卷风流量的性能汇总于表 8.1。贪心路由算法下全部流量沿顺时针方向绕环逆时针通道全部闲置顺时针通道承载 3 个单位的流量——即 γ 3——每个终端的吞吐率为 Θ b/3。随机路由下逆时针链路成为瓶颈负载 γ 5/2一半流量沿逆时针穿越 5 条链路吞吐率为 2b/5。加权随机把 5/8 的流量送到 3 条链路上、3/8 的流量送到 5 条链路上两个方向的负载均为 γ 15/8吞吐率为 8b/15。自适应路由在对自适应实现方式的一些假设下稳态时能达到同样的完美负载均衡给出与加权随机路由相同的吞吐率。表 8.1若干示例路由算法在 8 节点环上、龙卷风流量模式下的吞吐率占容量的比例。算法龙卷风流量下的吞吐率贪心0.33随机0.40加权随机0.53自适应0.53这个例子说明路由函数的选择能显著影响负载均衡。然而最坏情形吞吐率只是设计者可能希望优化的若干指标之一。不出所料不同的指标会对这四种算法中哪种最合适得出不同的结论。习题 8.1 将探讨其中一些。8.2 路由算法的分类我们按路由算法如何在源节点 x 到目的节点 y 的可能路径集合RxyR_{xy}Rxy​中进行选择来对路由算法分类。确定性deterministic路由算法总是在 x 和 y 之间选择同一条路径即使存在多条可能路径∣Rxy∣1|R_{xy}| 1∣Rxy​∣1。这类算法无视底层拓扑的路径多样性因此负载均衡做得很差。尽管如此它们在实践中很常见因为容易实现也容易做到无死锁。无意oblivious算法——确定性算法是其子集——在选择路由时不考虑网络当前状态的任何信息。例如把流量均匀分布到RxyR_{xy}Rxy​中所有路径上的随机算法就是无意算法。自适应adaptive算法适应网络的状态在做路由决策时使用状态信息。这些信息可以包括节点或链路的状态正常或失效、网络资源的队列长度以及历史通道负载信息。上一节的龙卷风例子涵盖了全部三类路由环上的贪心算法是确定性路由的例子——s 与 d 之间的所有分组都沿环的同一方向行进均匀随机和加权随机路由是无意路由的例子——它们在环的两个方向之间选择时不考虑网络状态自适应算法则根据第一跳的通道负载来做决策。在上述定义中我们描述各类路由算法时使用的路径集合是RxyR_{xy}Rxy​——从源到目的的最小最短路径路由。因此这些算法称为最小minimal路由算法。如我们已经看到的纳入非最小路由往往很重要此时路由函数从所有最小与非最小路由的集合Rxy′R_{xy}Rxy′​中选择路径这类算法称为非最小non-minimal路由算法。仍以环上的简单例子来看贪心算法是最小的而随机和自适应算法是非最小的。8.3 路由关系把路由算法表示为一个路由关系routing relationR 和一个选择函数selection functionρ 是很有用的R 返回一个路径集合对增量式路由算法则是通道集合ρ 在这些路径或通道中选择要走的路线。这样划分之后与通道依赖和死锁有关的问题涉及关系 R而与自适应性有关的问题涉及选择函数 ρ。死锁将在第 14 章详细讨论。根据算法是否增量式、以及是基于节点还是基于通道R 有三种不同的定义方式R:N×N↦P(P)(8.1)R : N \times N \mapsto \mathcal{P}(P) \tag{8.1}R:N×N↦P(P)(8.1)R:N×N↦P(C)(8.2)R : N \times N \mapsto \mathcal{P}(C) \tag{8.2}R:N×N↦P(C)(8.2)R:C×N↦P(C)(8.3)R : C \times N \mapsto \mathcal{P}(C) \tag{8.3}R:C×N↦P(C)(8.3)其中P(X)\mathcal{P}(X)P(X)表示集合 X 的幂集所有子集的集合。这种记号反映了路由关系可能返回多条路径或多条通道、由选择函数从中择一的事实。当路由关系的输出是整条路径时如关系 8.1——三个路由关系中的第一个路由算法称为整体式all-at-once路由。这个名字准确反映了算法的使用方式当分组在源节点 x 注入网络、发往节点 y 时对路由关系求值 U R(x, y)由于 U 可能是路由的集合从中选择一条指派给该分组。当然U 不必包含全部可能路由Rxy′R_{xy}Rxy′​甚至不必包含全部最小路由RxyR_{xy}Rxy​——确定性路由算法就只返回一条|U| 1。路由选定后与分组一同保存。我们将在第 11 章看到整体式路由使每个分组求值路由关系的时间最小但这一优点伴随着在分组内部携带路由的开销。另一种方法是增量式incremental路由关系返回一个可能通道的集合。路由关系不再一次性返回整条路径而是在分组的每一跳求值一次其输出用于选择分组下一条要走的通道。例如在第二种形式的路由关系关系 8.2中关系的输入是分组当前所在节点 w 和目的地 y求值得到通道集合 D R(w, y)其中 D 的每个元素都是从 w 出发的通道即D⊆COwD \subseteq C_{Ow}D⊆COw​。然后由选择函数从 D 中选择分组使用的下一条通道。这个增量过程不断重复直到分组到达最终目的地。第三个关系关系 8.3也是增量式的用法类似唯一区别是函数的输入为分组刚刚经过的通道和目的地。与整体式路由相比增量式路由没有随分组携带路由的开销但路由关系可能要被求值多次可能增加分组的延迟。另一个要点是增量式算法无法实现整体式路由能实现的每一种路由策略。这是因为在计算下一跳时我们几乎没有使用分组的历史信息。例如用整体式算法我们可以为二维网格设计这样一种路由算法分组在某个特定节点只能沿竖直或水平方向直行不允许分组在该节点从水平维转向竖直维。然而用第二种路由关系关系 8.2就无法做到这一点因为没有办法区分从竖直通道到达的分组和从水平通道到达的分组。当然第三种关系可以缓解这个问题但它仍然不能涵盖许多整体式算法见习题 8.2。第三种形式的路由关系关系 8.3也是增量式的但把路由决策建立在分组当前所处通道 c而非当前节点 w之上。此时路由关系接受当前通道 c 和目的节点 y返回通道集合 D R(c, y)。把决策建立在分组到达节点 w 所经过的通道 c而非 w 本身之上恰好提供了足够的历史信息来解耦通道之间的依赖关系——这对避免死锁很重要第 14 章。无论使用哪种形式的 R除非路由是确定性的它都会返回一个可能路径或通道的集合由选择函数 ρ 选取将要使用的元素。如果 ρ 在做选择时不使用网络状态的任何信息路由就是无意的反之如果 ρ 根据输出通道的可用性来做选择路由就是自适应的。8.4 确定性路由最简单的路由算法是确定性的——它把从源 x 到目的 y 的每个分组都沿完全相同的路由发送。确定性路由算法的路由关系是一个函数例如 R : N × N ↦ P。如 8.1 节所见缺乏路径多样性会在网络中造成很大的负载失衡。事实上对每一种确定性路由算法都存在一种能造成大负载失衡的流量模式。因此关心最坏情形的设计者不会首选这类算法。不过确定性算法仍有其优点。许多早期网络采用确定性路由因为它实现起来简单、便宜。可能令人惊讶的是确定性路由今天仍出现在网络中——尤其在不规则拓扑中那里设计好的随机化或自适应算法更加困难。对几乎任何²拓扑选择最小化的确定性路由函数才是合理的这样至少路径长度是短的。对某些拓扑简单的确定性方法在负载均衡上实际上与任何其他最小路由算法包括自适应算法一样好习题 9.2。最后对特定源—目的对之间消息顺序很重要的网络确定性路由常常是提供这种顺序的简单方法——这对某些缓存一致性协议等场景很重要。² 一个例外是均匀流量下最小路由并非最优的那一类奇特拓扑如习题 3.3。本节介绍两种最流行的确定性路由算法蝶形网络上的目的标签路由以及环面和网格上的维序路由。8.4.1 蝶形网络中的目的标签路由在 k 元 n 蝶网络中见 4.1 节把目的地址解释为 n 位 k 进制数直接用于路由分组地址的每一位数字依次用于在路由的每一步选择输出端口就好像地址本身就是从源路由表查得的路由头部一样。这正是第 2 章简单路由器所采用的路由。图 8.3 展示了两个目的标签路由的例子。图 8.3(a) 的 2 元 3 蝶中从源 3 到目的 5 的路由用粗线标出。从左到右网络的每一级使用二进制目的地址 101 中的一位来选择输出最高位的 1 在第一级选择下方输出0 在第二级选择上方输出最低位的 1 在最后一级选择下方输出。图 8.3目的标签路由的两个例子(a) 在 2 元 3 蝶中从源 3 路由到目的 5。二进制目的地址 5 101₂ 下、上、下选定路由。(b) 在 4 元 2 蝶中从 7 路由到 11。目的地址按四进制数字解释11 23₄选定路由。回顾我们从 3 到 5 的路由过程会发现实际上根本没有用到源节点的地址。事实上从任何源出发、使用同样的 101 开关端口模式无论源节点是谁都会路由到目的地 5。不难相信同样的事实对所有可能的目的地都成立。因此k 元 n 蝶网络中的目的标签路由只依赖目的地址与起始位置无关。图 8.3(b) 展示了高基数蝶形中的一个路由例子。图中粗线是四进制基数 42 蝶网络中从节点 7 到节点 11 的路由。与二进制网络一样从左到右目的地址的各位数字决定网络每一级的输出端口不同的是四进制网络中目的地址按四进制数解释11 1011₂ 23₄。每台路由器的输出端口从顶部开始从 0 编号。目的地址 23₄ 选择第一台路由器的端口 2从上数第三个和第二台路由器的端口 3最底部。与上例一样无论起点在哪里这组端口选择都到达目的 11。8.4.2 立方体网络中的维序路由维序路由dimension-order routing又称 e-cube 路由是直接 k 元 n 立方体网络环面和网格上目的标签路由的对应物。与目的标签路由一样把目的地址解释为 k 进制数各位数字一次一个地引导路由不同的是每位数字不是用来选择某级的输出端口而是用来在某一维中选择节点。与蝶形网络不同立方体网络在转到下一位数字之前可能需要若干跳才能解析当前地址位。作为维序路由的例子考虑分组在图 8.4 所示的 6 元 2 立方体中从节点 s 03 旅行到节点 d 22。由于环面的每一维都可以沿顺时针或逆时针方向穿越e-cube 路由的第一步是计算每一维中的最短首选方向。为求首选方向先对源地址和目的地址的每一位数字 i 计算相对地址Δi\Delta_iΔi​mi(di−si) mod km_i (d_i - s_i) \bmod kmi​(di​−si​)modkΔimi−{0若 mi≤k/2k否则\Delta_i m_i - \begin{cases} 0 \text{若 } m_i \le k/2 \\ k \text{否则} \end{cases}Δi​mi​−{0k​若mi​≤k/2否则​然后即可计算首选方向DT,i{0若 ∣Δi∣k/2sign⁡(Δi)否则(8.4)D_{T,i} \begin{cases} 0 \text{若 } |\Delta_i| k/2 \\ \operatorname{sign}(\Delta_i) \text{否则} \end{cases} \tag{8.4}DT,i​{0sign(Δi​)​若∣Δi​∣k/2否则​(8.4)其中下标 T 表示该函数用于环面。在讨论首选方向为零的情形之前先回到我们的例子。按上述公式相对地址为m(2,2)−(0,3) mod 6(2,5)m (2, 2) - (0, 3) \bmod 6 (2, 5)m(2,2)−(0,3)mod6(2,5)Δ(2,5)−(0,6)(2,−1)\Delta (2, 5) - (0, 6) (2, -1)Δ(2,5)−(0,6)(2,−1)于是首选方向为D(1,−1)D (1, -1)D(1,−1)算出首选方向向量之后分组一次只在一个维中路由。在每一维内分组沿首选方向行进直到在该维中到达与目的地相同的坐标。在图 8.4 的例子中分组从节点 s 03 出发在 x 维中沿负方向地址递减移动一跳之后到达节点 02已在 x 维到达正确坐标于是开始在 y 维沿正方向路由再走两跳到达目的节点 22。图 8.46 元 2 立方体中维序路由的例子。分组从节点 s 03 路由到节点 d 22先在 x 维路由再在 y 维路由。现在考虑同样的问题但目的地稍微移动到 d 32。按同样过程求得 D (0, −1)。x 维的路由不变但 y 维的首选方向为DyD_yDy​ 0。这种情况下如何路由分组把目的节点移到 32 之后y 维沿正方向或负方向都需要 3 跳。因此为了平衡负载重要的是让流量均匀分布到两个方向上。做到这一点的简单方法是放弃确定性算法把流量随机均分到 y 的正、负两个方向上。³ 凭直觉或由式 (8.4) 都容易验证首选方向为零只在 k 为偶数时发生。³ 在习题 8.9 中我们将探讨不平衡这部分负载的代价以及用确定性方法实现这种平衡的做法。到目前为止我们聚焦于环面但维序路由在网格中的工作方式类似。缺少回绕通道简化了首选方向的选择——此时首选方向也是唯一合法的方向DM,i{1若 disi−1否则D_{M,i} \begin{cases} 1 \text{若 } d_i s_i \\ -1 \text{否则} \end{cases}DM,i​{1−1​若di​si​否则​尽管负载均衡性质普遍较差维序路由仍被广泛用于网格和环面网络原因有二。第一它实现起来非常简单——特别是它允许路由器做维切片跨维划分。第二它防止维与维之间出现任何通道依赖环从而简化了死锁避免问题。不过维内部仍可能发生死锁见第 14 章。8.5 案例研究Cray T3D 中的维序路由图 8.5 所示的 Cray T3D [95, 161] 把多达 2,048 个 DEC Alpha 处理单元连接成三维环面。T3D 是共享存储器多处理机每个处理单元有自己的本地存储器但可以通过环面网络转发 load 和 store 操作来访问所有其他处理单元的本地存储器。每对处理单元经一个网络接口共享一台路由器。图 8.5Cray T3D 把多达 2,048 个 DEC Alpha 处理器连接成共享存储器的三维环面。T3D 网络采用维序路由并用维切片7.2.2 节路由器实现如图 8.6 所示。路由器由三片相同的 ECL 门阵列实现分别在 x、y、z 维路由。整体设计沿袭了 J-Machine 路由器5.5 节的组织方式。这种划分之所以可行正是因为采用了维序路由。习题 8.6 将考虑一种不同的划分方式。当分组从网络接口到达时x 路由器检查分组确定它需要在 x 维路由、在 −x 维路由还是若已到达目的 x 坐标交给 y 路由器。假设分组沿 x 方向转发经 xpOut 通道在其后的每台 x 路由器处路由器检查分组是否已到达正确的 x 坐标到达正确坐标后分组被交给 y 路由器否则继续沿 x 方向前进。图 8.6T3D 路由器划分在三片相同的 ECL 门阵列芯片上x、y、z 维各一片。T3D 路由器的每条通道带宽为 300 Mbytes/s由模块之间的线毯wire mat承载。每条通道有 16 个数据位和 8 个控制位工作在 150 MHz——与最初的 Alpha 21064 处理器同频。线毯是一束手工连接到板边连接器、用以实现环面拓扑的导线因形似不规则编织的织物而得名。每个数据和控制信号都作为差分 ECL 信号在线毯中的一对双绞线上传输。Cray T3D 还包含一组只在 x 维和 z 维连入网络的 I/O 节点这使环面网络略显不规则。由于消息总是从 x 维开始、在 z 维结束这看上去行得通但如果发送消息的节点与 I/O 节点的地址只在 y 维上不同会发生什么为了让维序路由仍能工作这些节点被赋予两个地址。习题 8.8 将考察这个问题。8.6 文献注记龙卷风流量的路由问题和加权随机解法由 Singh 等人描述 [168]。路由关系的不同形式及其在死锁分析中的重要性由 Dally [57] 和 Duato [60, 61, 62] 阐述。蝶形网络中的目的标签路由最早由 Lawrie 描述 [110]环面网络中的 e-cube 路由归功于 Sullivan 和 Bashkow [179]。对度为 δ 的网络Borodin 和 Hopcroft [28] 以及 Kaklamanis 等人 [91] 证明对任何确定性路由算法都存在某种流量模式能引起至少Ω(N/δ)\Omega(\sqrt{N}/\delta)Ω(N​/δ)的通道负载。8.7 习题8.1 路由算法之间的折衷。重新考虑 8.1 节的路由算法和网络。针对下列目标你会选择哪种算法(a) 最小消息延迟。(b) 均匀流量下的最佳吞吐率。© 在许多种置换流量模式上的最高平均吞吐率。每项准则限选一种算法并论证你的选择。8.2 增量式路由的局限。描述一种可以用关系 8.1 的基于路径的关系来表达、但无法用关系 8.2 和关系 8.3 的两种增量形式中任何一种来表达的路由算法。8.3 增量式与整体式路由的头部比特。目的标签路由既可以实现为增量式算法也可以实现为整体式算法。计算实现每种方法需要随分组存储的比特数。哪种方法需要的比特更少这种关系对一般拓扑中的最小路由成立吗它与拓扑的路径多样性有何关系8.4 环中的折返。假设在 8.1 节的路由例子中允许折返。能否设计出一种最坏情形吞吐率优于加权随机算法的算法如果能给出这样的算法否则解释为什么不存在这样的算法。8.5 带额外级的蝶形中的路由。描述一种对目的标签路由的确定性扩展使之能处理带一个或多个额外级的 k 元 n 蝶。给出一种把随机化引入该算法以改善负载均衡的简单方法。8.6 Cray T3D 中的方向序路由。假设重新安排图 8.6 中 Cray T3D 路由器各通道的标号使第一片路由器处理 x 和 y第二片处理 z 和 −x第三片处理 −y 和 −z。描述一种能在这种划分下工作的路由算法。记住分组一旦到达三片路由器中的每一片就再也不能回到前面的路由器。8.7 方向序路由的优点。考虑你在习题 8.6 中导出的路由算法。与维序路由相比这种算法有什么优点8.8 T3D 中往返 I/O 节点的路由。T3D 网络中I/O 节点只沿 x 维和 z 维加入——方法是给一个 3 立方体增加额外的 x 和/或 z 坐标。例如假设你有一个 64 节点的 4 元 3 立方体节点地址从 (0,0,0) 到 (3,3,3)一个 I/O 节点可能以地址 (4,0,0) 或 (0,0,4) 加入。解释如何给每个 I/O 节点分配一对地址使得用维序路由总能够从机器内部的任何节点路由到该 I/O 节点也能从该 I/O 节点路由到任何内部节点。8.9 环面中半程流量的平衡。在讨论维序路由时我们谈到了节点恰好位于环面某一环的半程处时出现的负载均衡问题。如果在半程情形下总是选择正方向而不做负载均衡对 k 为偶数的 k 元 n 立方体均匀流量的吞吐率会受到什么影响此时的最坏情形吞吐率是多少用占容量的比例表示结果。给出一种在保持确定性算法的同时改善半程情形负载均衡的方法并重新计算均匀和最坏情形吞吐率。8.10 CCC 中的最小路由。为习题 5.8 所述的一般 CCC立方体连接环拓扑设计一种近似最小的路由算法。宁可求简单而不必在所有情况下都找到精确的最小路由但要保证算法产生的路径都不超过直径Hmax2n⌊n/2⌋−2H_{max} 2n \lfloor n/2 \rfloor - 2Hmax​2n⌊n/2⌋−2见 [128]。评述你的路由算法在均匀流量下的负载均衡情况。