目前数据中心网络广泛应用的Fabric架构中会应用大量的ECMP（Equal-Cost Multipath Routing，简写ECMP）,其优点主要体现在可以提高网络冗余性和可靠性，同时也提高了网络资源利用率；大量的ECMP链路在特定场景下运行过程中会引发其他问题。例如，当某条ECMP链路断开后，ECMP组内所有链路流量都会被重新HASH，在有状态的服务器区域（如LVS）中将导致雪崩现象，又或者会出现多级ECMP的HASH极化导致链路拥塞等。
本文将结合ECMP运行原理针对以上问题进行分析，并探讨如何优化ECMP的运用。
等价多路径路由
等价多路径路由，即存在多条到达同一个目的地址的相等开销的路径。当设备支持等价路由时，发往该目的IP 或者目的网段的三层转发流量就可以通过不同的路径分担，实现网络链路的负载均衡，并在链路出现故障时，实现快速切换。
ECMP实现流程
▲图例1：ECMP流程图
? 步骤一：HASH因子的选择
首先数据报文转发查询路由表，确认存在多个等价路由，再根据当前用户配置的流量均衡算法，提取参与 HASH 计算的关键字段，即HASH因子。ECMP 流量均衡可选择的 HASH 因子如下表：
▲图表1：流量均衡模式对应HASH因子表
注：因ECMP为三层转发，即使配置基于源MAC、目的MAC或者源目MAC作为HASH因子，系统也会默认选择源IP作为HASH因子。另外，在选择提取HASH因子为目的IP时，系统会默认选择源目IP作为HASH因子。
? 步骤二：HASH计算
基于步骤一提取的 HASH 因子，根据 HASH 算法进行计算，得出相应的 HASH lb-key(load-balance key)。 ECMP 流量均衡支持的 HASH 算法包括异或（XOR）、CRC、 CRC+扰码等。
ASH算法有很多种，我们以XOR算法为例做出说明。XOR运算法则包括两个输入比特位相同时为0，不同则为1。HASH因子不同，运算结果也不尽相同。
1、HASH因子为IP address source（SIP） ●SIP XOR 0 ，得出一个32bit的数值a；
●将数值a再进行高16bit和低16bit做XOR计算得出16bit数值b； ●数值b的15~12bit与11~8bit再做XOR计算，得出4bit数值c； ●数值c替换数值b的11~8bit，得出数值d； ●数值d截取低位10bit即为lb key。 2、HASH因子为SIP+DIP/DIP
●DIP XOR SIP ，得出一个32bit的数值a； ●剩余运算步骤与SIP运算一致。 3、HASH因子为SIP+DIP+SP+DP ●SIP XOR DIP得到32bit的数值a；
●数值a的低16bit XOR SP 得到32bit的数值b；
●数值b的低 16bit XOR DP 得到 32bit 的数值c； ●数值c的高16bit XOR 低16bit得到16bit的数值d； ●数值d的15～12bit XOR 11～8bit，得到4bit的数值e； ●数值e替换数值d的11～8bit，得出数值f； ●数值f截取低10bit，即为lb-key
? 步骤三：确认转发下一跳
数据报文经过路由查表后找到对应ECMP 基值（base-ptr）,根据 HASH 因子通过 HASH 算法计算获得 HASH lb-key 后，进行 ECMP 下一跳链路数（Member-count）求余计算，再与ECMP基值进行加法运算得出转发下一跳index，即确定了下一跳转发路由。
计算公式：Next-hop =（lb-key % Member-count）+ base-ptr
上述流程为ECMP常规转发流程，但在特定网络环境下运行过程中就会出现问题，接下来继续分析数据中心网络中ECMP遇到的2个常见问题。
? 问题一 单链路故障导致ECMP组所有数据流被重新HASH计算
当Leaf交换机发送6条数据流到LVS服务器，Leaf先进行HASH运算负载均衡到每一台LVS服务器上，正常流量转发如图例2所示：
▲图例2：ECMP转发图
当某台LVS服务器网卡出现故障或者链路出现故障，Leaf交换机会将ECMP组内数据流将重新HASH计算，再进行负载均衡到剩余有效链路上，进而导致TCP会话断开，发生雪崩现象，例如一些支付类业务，同一个用户的一次支付过程会调用多个业务服务，业务侧要求一次支付的过程都落在同一个处理服务器上，
当出现单条链路故障后不仅影响该链路所在LVS承载的用户，同时还影响该ECMP组下其他LVS承载的用户，如图例3所示：
▲图例3：故障后ECMP转发图
1、优化方案：
为避免单台LVS服务器故障或者单链路故障导致整个ECMP组内流量全部被重新HASH，ECMP可采用弹性HASH算法来优化。采用弹性HASH算法后，仅将故障链路的流量重新HASH到其他活跃链路上，而非故障链路上的数据流则无需改变下一跳。实现效果如图例4所示：
▲图例4：ECMP弹性HASH算法
弹性HASH具体实现原理：
▲图例5：弹性HASH流程
在交换机上生成一张索引表（RH Flow Set Table），用于存放相关索引值对应下一跳路由地址。数据报文经过路由查表后找到对应ECMP 基值，提取HASH因子进行HASH运算，在HASH Key与ECMP数量取余数时无论是否出现故障链路，均以最初数量进行取余运算，因此运算结果一致，非故障链路数据依然按照原有链路转发。如下图中，链路3故障后软件CPU将及时更新RH flow table，将失效链路用正常链路均匀替换。
▲图例6：弹性HASH索引表替换示意图
? 问题二 HASH极化问题
如图例7所示，在Leaf设备和Spine设备均采用上联链路数为偶数且ECMP算法及HASH因子一致的情况下，数据流在Leaf设备上经过一次HASH计算，将数据流负载分担到两台Spine上，均衡后效果为数据流1、
2、3转发至Spine-1，数据流4、5、6转发至Spine-2，Spine再进行HASH计算负载分担到两台DCI核心上，因在Spine层采用的HASH算法与Leaf的HASH算法一致，最终Spine-1的数据流1、2、3均转发至DCI-1上，未负载分担到DCI-2上任何数据流，而Spine-2的数据流4、5、6均转发至DCI-2上，未负载分担到DCI-1上任何数据流，同理Leaf-2发送的数据流也是如此，进而产生HASH极化问题，导致SPINE和DCI之间链路有一条空闲，极大的浪费了网络资源，甚至会导致流量拥塞。
▲图例7：HASH极化
1、优化方案：
? 同厂商Leaf设备和Spine设备均采用相同上联链路数场景下，应避免在相邻的两台设备上使用相同的负载均衡算法；
? 设备在运行HASH计算时，除传统的五元组外，可以增添扰动因子，避免HASH计算结果相同。
HASH扰动的计算过程中HASH因子仍然正常提取，再增加用户自定义随机扰动因子，经过HASH算法运算时，不同交换机HASH计算结果就将不一致，以达到避免HASH极化现象的出现。
▲图例8：HASH扰动计算过程
动态负载均衡技术实现
在数据中心网络中，突发流量多，并且存在大象流和老鼠流并存现象，本文所描述的基于数据流五元组的HASH算法，并结合HASH扰动因子技术实现流量负载均衡，但无法实现大象流和老鼠流并存的网络中多链路之间的流量负载均衡。
我们的新一代25G数据中心网络解决方案中所采用的芯片，已能够支持DLB（Dynamic load balance，动态链路负载）特性，可基于流量负载状态实现动态的HASH负载均衡。具体实现方法是交换机为每条进行负载均衡的数据流创建一个流表，基于流表记录流量统计信息，根据流量统计信息动态调整链路负载均衡。
技术盛宴丨数据中心网络等价多路径(ECMP)技术应用研究 - 图文
