路由算法：紧凑路由表的探索与实践

### 路由算法：紧凑路由表的探索与实践 #### 1. 路由基础与队列机制 在网络通信中，存在三种重要的队列： - **OQwu**：节点 w 的输出队列。 - **TQwu**：当前正在传输的消息（和数据包）队列。 - **IQwu**：节点 u 的输入队列。 正常情况下，节点 w 向节点 u 发送消息时，会将消息添加到 OQwu 中，消息随后从 OQwu 移动到 TQwu，再从 TQwu 移动到 IQwu，节点 u 通过从 IQwu 中删除消息来接收它们。当通道出现故障时，TQwu 中的消息会被丢弃，OQwu 中的消息也会被丢弃，而不是添加到 TQwu 中。同时，会在 IQwu 的末尾添加 (fail, w) 消息，当恢复正常操作时，(repair, w) 消息也会被添加到 IQwu 的末尾。 #### 2. 最短路径路由 为了计算最短路径而非最小跳数路径，可以为每个通道分配一个权重，并对算法进行修改。在 Netchange 算法的 Recompute 过程中，如果将常数 1 替换为通道 uw 的权重 Wuw，就能在估计通过 w 的最短路径长度时考虑通道权重。同时，算法中的常数 N 需要替换为网络直径的上界。 当修改后的算法达到稳定配置时，路由表是正确的，并且能给出最优路径，但前提是网络中的所有循环都具有正权重。要证明算法最终能达到这种稳定配置，需要更复杂的范数函数。此外，该算法还可以扩展以处理变化的通道权重，节点 u 对通道权重变化的反应是重新计算所有 v 的 Du[v]。不过，这种算法只有在通道成本变化的平均时间远大于收敛时间的情况下才实用，而这在实际中是不太现实的。在这种情况下，像 Merlin - Segall 算法这样能在收敛过程中保证无环的算法更值得推荐。 #### 3. 紧凑路由表的需求与策略 传统的路由算法要求每个节点为每个可能的目的地维护一个单独的路由表项，当数据包在网络中转发时，路径上的每个节点（除目的地外）都需要访问这些表，这会带来较大的存储和表查找开销。为了减少这些开销，我们可以采用一种新的策略，即让路由表为每个通道记录必须通过该通道路由的目的地集合。这样，对于一个具有 deg 个通道的节点，路由表的“长度”变为 deg，实际的存储节省取决于每个通道的目的地集合能被压缩表示的程度。为了保证表查找的高效性，路由表的组织方式需要使得能快速从表中检索到给定目的地的输出通道。 #### 4. 树标记方案 树标记方案是由 Santoro 和 Khatib 提出的一种紧凑路由方法。该方法基于将节点标记为从 0 到 N - 1 的整数，使得每个通道的目的地集合是一个区间。这里引入了循环区间的概念，在集合 ZN = {0, 1, ..., N - 1} 中，循环区间 [a, b) 定义如下： \[ [a, b) = \begin{cases} \{a, a + 1, ..., b - 1\} & \text{if } a < b \\ \{0, ..., b - 1, a, ..., N - 1\} & \text{if } a \geq b \end{cases} \] 当 a < b 时，[a, b) 称为线性区间。 对于树 T，我们可以通过前序遍历为节点编号，使得每个节点的每个输出通道的目的地集合是一个循环区间。具体来说，选择一个任意节点作为根节点，对于每个节点 w，以 w 为根的子树 T[w] 中的节点编号形成一个线性区间 [lw, lw + |T[w]|)。节点 w 向其子节点 u 转发目的地在 T[u] 中的数据包，向其父节点转发目的地不在 T[w] 中的数据包。 在节点 u 进行区间转发的算法如下： ```plaintext (* A packet with address d was received or generated at node u *) if d = lu then deliver the packet locally else begin select (Xi s.t. d E [(Xi, (XHI); send packet via the channel labeled with (Xi end ``` 一个循环区间可以通过给出起点和终点，仅用 2 log N 位来表示。在这种应用中，由于需要存储一组不相交的区间，每个区间使用 log N 位就足够了。只存储每个通道对应的区间的起点，其终点等于同一节点中下一个区间的起点。 树标记方案在树上能实现最优路由，因为树中任意两个节点之间只有一条简单路径。当网络不是树时，可以选择一个固定的生成树 T，并将该方案应用于这棵树，不属于生成树的通道不会被使用，在路由表中用特殊符号标记。 然而，树标记方案也存在一些缺点： - 未使用不属于生成树的通道，造成网络资源浪费。 - 流量集中在树上，可能导致拥塞。 - 生成树中任何一个通道的故障都会使网络分区。 下面通过一个表格来对比不同情况下树标记方案的路径长度与最优路径长度： | 情况 | 树中距离 dr(u, v) | 网络中距离 dc(u, v) | 说明 | | ---- | ---- | ---- | ---- | | 环网络 | 可能为 N - 1 | 可能为 1 | 树标记方案的路径长度与最优路径长度的比值可能非常大 | | 合适生成树 | ≤ 2