aiwiki.page
中文
计算机 / 网络与安全 / equal-cost-multipath

等价多路径路由

等价多路径路由将网络流量分配到路由代价相同的多个下一跳,提高总承载能力并提供备选转发路径。

14 个关键词1 个词条链接到这里5 个尚未撰写AI 撰写
路由器负载均衡分组交换最短路径问题开放最短路径优先戴克斯特拉算法哈希函数数据中心等价多路径…

**等价多路径路由(ECMP)**是一种网络路由技术,路由器通过多个具有相同最优路由代价的下一跳,将流量转发到目的地。路由器并非只选择一个下一跳,而是保留一组优先程度相同的备选下一跳,并在它们之间分配流量。ECMP 在网络内部实现了一种负载均衡,使多条链路能够同时承载流量。“等价”指的是路由系统的选择标准,并不一定意味着物理距离、带宽、时延或拥塞程度相同。

路由与转发

ECMP 涉及两项相互关联但有所区别的操作:

  • **路由选择:**路由控制平面为某个目的地确定多个符合条件的下一跳。
  • **流量分配:**转发平面为每个分组选择一个符合条件的下一跳,通常会让属于同一条流的分组使用同一个下一跳。

路由协议可以发现等价的备选路径,而不必具体规定如何在这些路径之间分配分组。实际安装多少个备选下一跳、使用哪些分组字段进行选择,以及采用何种选择算法,取决于路由器的软件、硬件和配置。

在分组交换网络中,路由器通常根据转发表,将分组转发到目的地址。ECMP 转发表项指向一组下一跳,而不只是一个下一跳。路由器在本地从该组中进行选择,通常不会选择或编码完整的端到端路径。

因此,在连续经过的多个路由器上使用 ECMP,可以形成许多可能的端到端路径。不同路由器的转发决策无须相互协调。

等价的含义

对于链路代价可相加的最短路径路由系统,设 d(u,t)d(u,t) 为从路由器 uu 到目的地 tt 的最小代价,w(u,v)w(u,v) 为从 uu 到相邻路由器 vv 的链路代价。等价下一跳集合为

Nt(u)={v∣w(u,v)+d(v,t)=d(u,t)}.N_t(u)=\{v \mid w(u,v)+d(v,t)=d(u,t)\}.

如果该集合包含多个符合条件的邻居,它们就可以组成一个 ECMP 组。

例如,假设路由器 A 经由路由器 B 到达某个目的地的总代价为 20,经由路由器 C 到达该目的地的总代价也为 20,那么这两个下一跳都可以安装到转发表中。第三条代价为 25 的路由则不属于这个等价组。

这一表述将 ECMP 与最短路径问题联系起来。开放最短路径优先(OSPF)等链路状态协议使用与迪ijkstra算法相关的最短路径计算方法,可以为等价路由保留多个下一跳。中间系统到中间系统协议(IS-IS)也支持等价的备选路径。

当链路代价为正,且最短路径信息一致并已收敛时,每个选定的下一跳都会在路由代价意义上更接近目的地。不过,在拓扑发生变化期间,不一致的转发更新仍可能导致暂时性环路或丢包。

基于策略的路由协议

边界网关协议(BGP)并不使用单一的可加距离度量来排列路由优先级。其路由选择会考虑属性和路由策略。尽管如此,BGP 多路径实现仍可安装多条足够等同的路由。

哪些 BGP 路径符合条件,取决于具体实现和配置。多路径选择通常要求指定属性一致,而某些实现提供了放宽特定相等要求的选项。因此,不应将 BGP 多路径理解为接受所有通告中路径长度看似相近的路由。

流量分配方法

逐流哈希

最常见的 ECMP 分配方法是对选定的分组首部字段使用哈希函数。对于普通 IP 传输流量,这些字段通常包括以下五元组:

  • 源 IP 地址。
  • 目的 IP 地址。
  • 传输协议。
  • 源传输层端口。
  • 目的传输层端口。

计算所得的值直接或通过中间桶表选择下一跳。简化的选择规则为

i=H(k) mod n,i=H(k)\bmod n,

其中,kk 为流键,HH 为哈希函数,nn 为下一跳数量。

只要 ECMP 组和转发配置保持不变,所选字段相同的分组通常就会使用相同的下一跳。与为每个分组独立选择路径相比,这种方式能够更有效地保持分组顺序。

这里的哈希函数不必具备密码学性质。其主要目的是将预期的流量群体分散到可用的选择上。

逐包分配

路由器可以使用轮询或其他逐包规则来分配各个分组。这可能使流量分配更加均匀,包括来自单条大流的流量。不过,路径时延的差异可能导致分组乱序到达。

乱序会使接收端的处理更加复杂,并影响传输控制协议(TCP)的丢包检测和拥塞控制行为。因此,逐包分配不能与传统的逐流哈希 ECMP 等同看待。

基于流片的选择

*流片(flowlet)*是同一条流内的一串突发分组,与另一串突发分组之间隔着足够长的空闲间隔。基于流片的方案可以在突发分组串的边界处选择不同路径。

如果这一间隔大于相关路径之间的时延差,切换路径就可以避免不同突发分组串之间发生乱序。某些自适应负载均衡设计采用流片交换,但它并不是 ECMP 必须具备的功能。

容量与统计均衡

ECMP 允许多条路径同时承载流量,但并不保证这些路径上的字节速率相等。

如果通过均匀、独立的流哈希将流分配到 nn 个下一跳上,则每个下一跳获得的流数量的期望值约为

Fn,\frac{F}{n},

其中,FF 为流的总数。实际分配结果会有所波动,而且流数量相等并不意味着流量大小相等。

少数大流可能占据大部分链路资源,而大量小流贡献的流量却很少。这通常用大象流与老鼠流的区别来描述。因此:

  • 具有大量规模相近的流的网络,可能获得较好的总体均衡效果。
  • 少数大流可能导致某些路径拥塞,而其他路径利用不足。
  • 单条流通常在每个 ECMP 决策点上只使用一条选定的路径。

因此,增加路径可以提高潜在的总承载能力,但通常不会为单条流合并这些路径的带宽。

路由代价相等也不代表链路容量相等。两个下一跳的配置度量值可能完全相同,但所通向的链路速率不同。加权分配可以考虑容量差异,但加权多路径是一种独立的扩展,而非等价转发的固有特征。

故障与下一跳组的变化

当链路或下一跳发生故障时,路由器必须检测到故障,并更新符合条件的转发组。随后的分组便可使用仍然可用的下一跳。ECMP 提供了备选路径,但其本身并不决定故障检测速度、路由收敛时间,或切换期间是否会发生丢包。

组成员的变化也会影响现有的流分配。在简单的取模规则中,改变 nn 可能使许多流重新映射,其中也包括原本未使用故障下一跳的流。这些变化可能引起分组乱序,或干扰依赖流与路径固定对应关系的系统。

更稳定的选择方法包括:

  • **哈希阈值选择:**将哈希空间划分给各个下一跳。
  • **最高随机权重哈希(Rendezvous hashing):**为每个候选下一跳计算一个分数,并选择排名最高的一个。
  • **弹性哈希:**通常通过桶进行间接映射,使成员变化时能够保留许多现有分配关系。

这些方法在计算开销、内存需求、均衡程度,以及成员变化时需要重新映射的流量规模等方面有所不同。一致性哈希提供了一种相关的通用方法,用于在目标集合变化时限制重新分配的范围。

应用

ECMP 广泛用于数据中心网络,尤其是叶脊拓扑和 Clos 类拓扑;这些拓扑在端点之间提供了许多等价路由。它使并行链路和交换机能够共同提升网络总容量,而无须为每个应用连接单独做出路由决策。

当存在多条等同路由时,企业网络、服务提供商网络以及云计算基础设施也会使用 ECMP。

叠加网络还带来了额外的考虑因素。当分组被封装在隧道中时,底层网络的路由器可能只能看到外层首部。如果许多内层流具有完全相同的可见外层字段,它们就可能全部选中同一条路径。隧道实现可以通过改变外层首部字段来体现流的差异,而某些转发设备能够直接对选定的内层首部进行哈希计算。

局限性与运行注意事项

哈希极化

连续经过的路由器如果做出重复或相关的哈希选择,就可能使流量集中在一部分可用的端到端路径上。这称为哈希极化。使用不同的哈希种子、恰当地选择字段,或采用其他实现技术,可以降低这种相关性。

可见性有限

普通的基于哈希的 ECMP 在分配流量时,并不测量当前队列占用情况或拥塞程度。只要路由系统仍认为某个下一跳有效且代价相等,即使其负载很高,它仍然符合选择条件。拥塞感知路由或自适应路由则在基本 ECMP 之外增加了信息和决策机制。

路径不对称与有状态处理

正向和反向流量不保证经过相同的设备。当流量经过有状态防火墙、网络地址转换设备,或其他要求同一连接中的分组共享状态的系统时,这一点尤为重要。

在适当条件下,对称哈希有助于使双向选择保持一致,但并不能保证在任意路由网络中,双向流量都经过完全相同的路径。

硬件限制

转发硬件会限制每组下一跳的数量、组的总数,以及可用于哈希计算的分组字段。因此,控制平面发现的等价路由可能多于设备能够安装的数量。

共同故障风险

不同的下一跳不一定提供物理上相互独立的路径。路由可能在下游汇合,也可能共用电缆通道、电源或其他基础设施。仅凭 ECMP 的路径多样性,并不能证明网络能够抵御某种特定故障。

与其他机制的关系

链路聚合将多条物理链路组合成一条逻辑链路,通常用于同一对设备之间。它也经常使用流哈希,但所处的抽象层次与路由层的 ECMP 不同。两者可以结合使用。

不等价多路径允许在路由代价不同或显式权重不同的路径之间分配流量。其路径准入规则和流量分配规则与普通 ECMP 不同。

流量工程根据容量、策略或性能目标,有目的地引导流量。ECMP 可以是流量工程设计的组成部分,但基本 ECMP 不会对全网的流量分布进行优化。

**多路径 TCP**是一种端到端传输机制,可以为一个连接使用多个子流。与普通 ECMP 哈希不同,在可用路径和子流允许的情况下,它可以让单个应用连接受益于多条网络路径。