无感知路由策略综述

### 无感知路由策略综述 在大规模并行系统或像互联网这样的大规模通信网络中，路由协议对于系统的性能和可用性起着至关重要的作用。而路径选择策略则是路由协议的核心组成部分。 #### 1. 路由策略概述 路由策略主要分为自适应路由和无感知路由两种。 - **自适应路由**：其路径选择策略会基于多种信息，如之前为其他请求选择的路径，或者对请求模式的先验知识（如果有的话）。这种策略可以根据系统中的当前流量动态调整路由决策，有望获得计算出的路由路径的最佳质量。然而，在分布式场景中实现它可能会很困难，因为用于做出路由决策的所有非本地信息都需要分发到做出该决策的节点，这需要额外的通信，在评估路径选择策略的性能时也需要考虑这一点。 - **无感知路由**：对于无感知算法，为一个请求选择的路由不依赖于任何其他请求，即路由决策完全独立于网络中的当前流量。实际上，无感知算法的路由路径可能仅取决于源节点、目标节点，对于随机化路由算法还可能取决于一些随机比特。因此，这种算法可以通过路由表轻松实现，路由表在每个节点 $v \in V$ 存储了到每个可能目标节点的路径的概率分布。也可以将随机化无感知路由算法视为指定了网络中每个源 - 目标节点对之间的单位流，而确定性无感知算法则为每对节点指定了一条单一的路由路径。 尽管无感知路由具有简单性这一理想特性，但重要的是要量化与自适应路由相比，使用无感知路由算法可能导致的性能损失。不过，许多研究结果表明，对于许多成本度量组合和许多网络，无感知路由是一个强大的概念，能够提供与自适应路由相似的性能保证。 #### 2. 网络模型与成本度量 - **网络模型**：将网络建模为边加权图 $G = (V, E)$，其中 $V$ 是节点集，用 $n$ 表示 $V$ 的基数，即 $|V| = n$。权重函数 $c : E \to R^+_0$ 描述了边 $e \in E$ 的链路容量，假设权重函数 $c$ 是归一化的，即链路的最小非零容量为 1，用 $c_{max}$ 表示网络链路的最大容量。随机化无感知路由方案由每个源 - 目标对 $s, t$ 的 $s - t$ 路径上的概率分布组成，等效地，这种概率分布可以看作是 $s$ 和 $t$ 之间的单位流。为了简化讨论，通常假设使用无感知路径选择策略输出的路由算法可以进行分数路由，即源 $s$ 到目标 $t$ 的需求为 $d$ 的路由请求可以通过 $s$ 和 $t$ 之间值为 $d$ 的流来满足，而不限于仅使用一条路径。使用分数路由时，可以忽略单个路由请求，只需每个源 - 目标对之间的总需求，通过需求矩阵 $D$ 来评估路径选择策略的不同性能指标，需求矩阵 $D$ 是一个 $n \times n$ 的非负矩阵，对角元素为 0。 - **成本度量**： - **延迟相关度量**：通常希望路由路径较短，这可以通过最小化扩张（dilation）或总负载来实现，总负载可以看作是最小化消息的平均路径长度，这两个成本度量都对应于最小化网络中的延迟。然而，仅关注这些基于距离的成本度量可能会在网络中造成严重的瓶颈，从而对系统的吞吐量产生不利影响。 - **吞吐量相关度量**：为了实现高吞吐量，需要将通信负载均匀分布在所有网络资源上，这对应于最小化拥塞（congestion），这通常是分析虚拟电路路由算法时考虑的主要目标。 - **分组路由成本度量**：在分组路由中，如果给定一组分组以及每个分组从其源到目的地的路径，对于许多协议，将分组调度到其目的地所需的路由时间接近 $C + D$，其中 $C$ 表示拥塞，$D$ 表示路径系统的扩张。因此，对于分组路由应用，应最小化拥塞 + 扩张这一成本度量。 研究结果的表述方式有两种，一种是绝对术语，例如“超立方体中的任何排列都可以由无感知算法以最多 $O(\log n)$ 的拥塞进行路由”；另一种是竞争/近似框架，它将无感知算法的性能与最优算法的性能进行比较，例如“网格中的任何路由实例都可以以最多 $O(\log n) \cdot C_{opt}$ 的拥塞进行路由，其中 $C_{opt}$ 表示该实例可以获得的最优拥塞”，通常后一种结果更可取，无感知方案的性能与最优路径选择之间的因子称为竞争比。 #### 3. 部分研究结果 - **确定性无感知路由**：Borodin 和 Hopcroft 的研究表明，为了获得良好的性能，需要进行随机化。他们指出，对于一个具有 $n$ 个节点和最大度 $\Delta$ 的（未加权，即 $\forall e \in E : c(e) = 1$）网络，以及一个确定性无感知路由方案，存在一个排列路由实例，使得无