第 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 relation）R 和一个选择函数（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) 展示了高基数蝶形中的一个路由例子。图中粗线是四进制（基数 4）2 蝶网络中从节点 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
Δi=mi−{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若 di>si−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（立方体连接环）拓扑设计一种近似最小的路由算法。宁可求简单而不必在所有情况下都找到精确的最小路由，但要保证算法产生的路径都不超过直径Hmax=2n+⌊n/2⌋−2H_{max} = 2n + \lfloor n/2 \rfloor - 2Hmax=2n+⌊n/2⌋−2（见 [128]）。评述你的路由算法在均匀流量下的负载均衡情况。
