基于可编程数据平面的DLB算法实现

刘熙

（锐捷网络股份有限公司 福建省福州市 350002）

1 引言

近年来，数据平面可编程技术的发展，为网络领域的发展注入了新的活力。在高性能转发领域，支持协议无关的交换架构PISA（Protocol Independent Switch Architecture）的可编程转发芯片，结合P4（Programming Protocol-Independent Packet Processors）这样的高级语言，使得网络拥有者、工程师、架构师及管理员可以自上而下地定义数据包的完整处理流程[1]。程序员通过编程，可以将交换机变为一个架顶交换机(Top-Of-Rack,TOR)、一道防火墙或一个负载平衡器，或者支持新的自动诊断功能和新的拥塞控制算法等[1]。

PISA 架构（如图1）主要由可编程的报文解析器(PARSER)、可编程的匹配动作单元模块（MATCH-ACTION UNIT，简称MAU）和报文组装模块（DEPARSER）构成[1,2,3]。在流水线入口，可编程的报文解析器负责对数据包进行预处理和解析。可编程的匹配动作单元模块主要用于各种查找表操作，芯片内部包含多级匹配动作单元并以流水线的方式组合而成。每级匹配动作单元内都包含一定数量的哈希资源、SRAM 资源、TCAM 资源和ALU 资源等。哈希资源可以用于实现各自查找表算法，SRAM 资源可以用来实现精确匹配表的存储与查找，TCAM 资源则可以用来实现模糊匹配表的存储与查找，ALU 资源可以实现内部的相关控制，具备逻辑与或的运算能力和加减的运算能力，从而实计数(Counter)、流量计(Meter)以及寄存器(Register)的功能。报文组装模块则将查表结果作用于报文之上，增加一些新的报文头部，或删除一些报文头部，或修改已有报文头部中的一些字段，并将处理完成的报文提交给缓存管理模块入队，调度模块则根据选择的调度算法将报文调度出队，经过下行流水线处理最终由出口端口转发给下一跳设备。

图1：PISA 架构

2 概述

2.1 网络负载均衡

负载均衡(Load Balance，简称LB)，是指将负载（工作任务）进行平衡、分摊到多个操作单元上进行运行，从而协同完成工作任务，达到提高系统的吞吐量、减小响应时间、优化系统资源的效果。而网络的负载均衡是指对网络上的负载情况进行平衡分配的一种处理方法。通过采用某些负载均衡算法实现多路径的选择，使得各路径的负载分配均等，从而提高网络的资源的利用率。

网络技术中，通常采用等价多链路(Equal Cost Multi Path,ECMP)或链路聚合(Link Aggregation,LAG)实现负荷分担和链路备份。其中，ECMP 的原理是，为一个目的地址配置多条相同开销的物理链路组成ECMP，发往该目的地址的报文可以通过该ECMP包含的多条物理链路进行转发，若某条物理链路出现故障，则可以使用其它物理链路代替出现故障的物理链路完成报文的转发；LAG的原理是，将连接到同一网络设备的多条物理链路汇聚成LAG，发往该网络设备的报文可以通过该LAG 包含的多条物理链路进行转发，若某条物理链路出现故障，则可以使用其它物理链路代替出现故障的物理链路完成报文的转发。

从ECMP 或LAG 包含的多条物理链路中选取一条物理链路转发报文的过程即为负载均衡。目前常用的负载均衡方法是，接收到报文后，基于该报文的目的地址确定该报文的出口为ECMP 或LAG 时，基于该报文的IP 五元组信息（IP 源地址、IP 目的地址、IP 协议号，四层协议源端口、四层协议目的端口）计算该报文的哈希值，将该报文的哈希值与该报文的出口包含的物理出口总数进行取模运算，最后根据取模运算结果，从该报文的出口包含的所有物理出口中选取一个物理出口转发该报文。

这种基于IP 五元组的哈希值的负载均衡方法，也叫逐流均衡。这种均衡方法，对于同一个流，所有报文都走相同的物理端口，因此数据包的传输是保序的，对于TCP 这样要求严格保序的通信协议来说非常适合。但是，可能存在多个数据流的报文的哈希值相同或者多个数据流的报文的哈希值不同但基于哈希值选择的物理出口相同的问题，从而导致该多个数据流的报文通过同一个物理出口进行转发处理，进而造成局部物理出口的负载过重。

还有一种符合均衡方法，叫逐包均衡。指采用轮询方式，将报文在所有等价路径上轮流发送。这种均衡方式的优点很明显，所有等价路径的网络负载可以实现均等。但是缺点也很明显，即：不同路径的网络时延可能不同，最终可能造成报文序列的乱序，这对像TCP 这样要求强序传输的协议来说是致命的。

如何在报文传输保序和网络负载均衡之间找到一个平衡支点，这就是动态负载均衡（Dynamic Load Balance，简称DLB)要解决的问题。

2.2 Flowlet原理

网络通信中，大多数流量是TCP 流量。TCP 通信采用滑动窗口方式发送，为了性能考虑，报文会根据窗口大小以批量方式发送，因此TCP 报文实际上是以Burst 方式发送出来的。对于每个TCP 流，每次burst 之间存在时间间隙。当这种间隙足够大的时候，可以进行TCP 流的底层链路的切换。此时，旧链路上的packet 均已经离开了链路或者至少将要离开链路，因此切换链路将不会造成乱序，不会破坏TCP 的强序要求[4,5]。而这种Burst 发送的多个报文，业界称之为Flowlet[4,5,6]，意为微小的流。

由于存在burst 和对应的间隙，一个TCP Flow 可以切割为若干个TCP Flowlet，属于同一个Flowlet 的报文必须选择相同的链路，属于不同Flowlet 的报文可以选择走不同的链路。如图2所示。

图2：Flowlet 示意图

2.3 DLB均衡算法实现

DLB 技术是一种在满足TCP 保序传输要求的前提下提高网络负载均衡效果的技术。基于可编程芯片实现的DLB算法，包括两大模块：

（1）均衡模块：利用Flowlet 原理对流量的负载进行动态调整，选择最优路径调度新的Flowlet；

（2）监控模块：在转发面对链路进行负载监控，实时更新最优路径信息。

DLB算法原理图如图3所示，DLB算法的整体处理流程如下：

图3：DLB算法原理图

均衡模块（在报文入口方向）：

（1）DLB 分组：根据报文的源口信息、目的信息（LAG 或者ECMP）等信息进行匹配查找，获取报文对应的DLB 分组信息，DLB 分组信息包括：

①分组标识(DLB_ID)：分组标识采用数值来表示，比如自然数1,2,3,4 等。不同分组的标识不同。

②分组掩码(MASK)：包括高位掩码(HI_MASK)和低位掩码(LO_MASK)，这两个掩码和生成FlowID 有关。高位掩码用于设定FlowID 的区间，低位掩码用于设定FlowID 的区间偏移量。不同分组的分组掩码是不同的。

③Flowlet 老化时间(IDLE_Timeout)：老化时间是一个相对时间戳，可以根据转发场景需要设置此老化时间的大小。比如100μ 秒。

（2）计算FLOW_ID：

①计算报文的HASH 值。对于IP 报文，一般根据报文的五元组信息，计算出对应的哈希值；对于非IP报文，可以根据其他信息（比如MPLS 报文可以根据MPLS 标签）计算报文的哈希值。

②根据公式 FLOW_ID = HI_MASK | (HASH & LO_MASK)，先将Hash 值和分组低位掩码进行按位与运算，然后再和分组高位掩码进行按位或运算，最终得到报文的FLOW_ID。

（3）Flowlet 老化判断：

①获取报文当前的的时间戳Cur_Timestamp；

②使用报文的FLOW_ID 作为索引，从寄存器数组Flowlet_TSTAMP 获取记录的上一次转发报文的时间戳LAST_Timestamp。

③判断不等式Cur_Timestamp>LAST_Timestamp + IDLE_Timeout 是否成立，如果成立则说明Flowlet 已老化（当前的报文视为新的Flowlet），反之则说明Flowlet 没有老化（当前的报文视为旧的Flowlet）。

（4）选择最优路径：对于新的Flowlet 情况，采用轮询方式为报文选择新的路径。算法如下：

①使用报文的DLB_ID 作为索引，从寄存器数组PREF_PATH_SET 获取优选路径集合对应的端口位图(PREF_PORTMAP)，位图中非0 的bit 位表示对应的端口为可用物理端口。比如0b10101011，表示物理端口1、2、4、6、8 为可用端口。

②根据DLB_ID，从寄存器数组SN_GEN 获取一个在一定范围内递增且超过范围则重置的序列号SN。比如SN 可以取值1 ～127，则SN 值超过127 时重新置0。

③根据PREF_PORTMAP 和SN，选择最优出口。比如，当PREF_PORTMAP 值为0b10101011，SN 值为1 时，选择第一个物理口；当PREF_PORTMAP 值为0b10101011，SN 值为2 时，选择第二个物理口。由于SN 值是递增的，因此为新的Flowlet 分配到的优选出口是依次轮询分配的。

④当最优路径不存在时，即PREF_PORTMAP 值为全0，此时从候选路径集合中基于SN 值选择端口。候选路径集合为所有可用的等价成员口集合。

（5）保存转发路径：

①对于新的Flowlet 情况，以FLOW_ID 作为索引，将选择的出口信息更新到寄存器数组Flowlet Path 对应成员。

②对于旧的Flowlet 情况，以FLOW_ID 作为索引，从寄存器数组Flowlet Path 对应成员获取保存的出口信息。

监控模块1（在报文的出口方向）

（1）出口测速：

①利用计量器资源，为每个物理端口进行实时测速。比如，采用单桶令牌的计量器，当端口的报文速率超过配置的速率阈值时，计量器执行结果为红色；当端口的报文速率低于配置的速率阈值时，计量器执行结果为绿色。

②为了使测速结果更稳定，还可以采用多次测量取平均颜色的做法。比如每轮累计统计1000 个报文的计量器颜色总量，当红色总量(比如600 个）大于绿色总量（比如400 个）时判定平均颜色为红色。

（2）权值计算和变化确认：

①根据端口的计量器颜色信息和端口的出口队列深度（可选），调整端口的转发优先级。比如发现端口的计量器颜色为红色且出口队列深度超过配置的阈值时，降低端口的转发优先级，需要将它从优选路径中移除。当发现端口的计量器颜色恢复为绿色且出口队列深度低于配置的阈值时，提高端口的转发优先级。

②用一组寄存器PORT_PRIORITY 保存端口上一次的权值信息。比较当前的权值信息与寄存器保存的上一次权值信息是否发生变化，如果有变化则更新权值信息，并返回权值变化确认(设置PRIORITY_ACK 为1)。

（3）镜像反馈：当端口的权值发生变化时，触发一个用于调整最优路径的PREF 报文镜像。

①获取出端口的对应DLB 的物理成员口位图，比如第一个物理成员口对应位图可以表示为0b0000 0001，第二个物理成员口对应的位图0b0000 0010。

②触发一个指向回环口的镜像报文。镜像报文的头部封装这些信息：DLB ID、物理成员口位图、端口权值。

监控模块2（在报文的回环口入口方向）：

更新最优路径：回环口收到PREF 报文镜像后，从报文中提取DLB ID、物理成员口位图、端口权值这些信息，更新PREF_PATH_SET 的最优路径信息。将端口权值低于最优路径权值的物理成员口对应位图，从最优路径的位图中移除；将端口权值高于或等于最优路径权值的物理成员口对应位图，添加到最优路径的位图中。

3 结语

借助可编程芯片，我们在数据平面实现了DLB算法，通过均衡模块和监控模块的配合，在确保数据流中的报文不会出现乱序的情况下，有效地改善了负载均衡效果，提高了网络转发性能。可编程交换芯片作为一种新的技术，为未来网络的发展注入了新的活力，很多传统交换芯片无法实现或难以实现的功能和应用可通过可编程交换芯片快速得到实现，极大提升了转发面功能的迭代更新，加速网络领域的创新。