基于流量分配倾向度的SDN多路径负载均衡

李道全，黄泰铭，于 波，王 雪

(青岛理工大学 信息与控制工程学院，山东 青岛 266520)

0 引 言

在传统网络中，网络流量的传输通常使用最短路径的单路径路由机制。然而随着网络规模的不断扩大，单路径的路由机制易导致部分链路负载过重、链路负载不均衡、整体网络资源浪费等问题。

软件定义网络[1](software defined network)是一种新型网络体系架构。SDN的出现与迅速发展，为传统网络单路径路由方式向多路径路由方式的转变提供了诸多便利，多路径路由的出现增加了网络传输的路径选择，一定程度上降低了部分链路的传输负载。尽管如此，现有的多路径路由通常是依靠路径选择算法从多路径中选取最优路径进行网络流量的传输，或是多路径平均分配流量实现多路径路由，并没有依据各路径的性能而完全利用所有可用路径资源，易导致资源浪费与链路负载不均衡的问题。

本文提出的基于多路径路由的负载均衡策略在查找所有可用路径的同时收集各链路的带宽与时延参数，并将本文提出的一种流量分配倾向度(FDP)应用到OpenFlow组表技术中，依据每条路径的带宽与时延的不同公平地分配网络流量到所有可用路径。仿真结果表明，该策略可有效降低单一路径的负载，提高SDN网络中对于多路径的使用率，实现了多路径路由的负载均衡。

1 相关研究

SDN技术概念由OpenFlow协议发展而来[2]。OpenFlow协议是用来描述控制器和OpenFlow交换机之间交互所用信息的标准，以及控制器和OpenFlow交换机的接口标准[3]。SDN技术将控制功能从网络设备中分离出来，实现了对于网络功能的全局集中控制(其架构如图1所示)，其可编程性也为多路径路由的部署和应用提供了便利。

图1 SDN架构

近年来针对多路径路由的相关研究有如下进展：Chiesa等对等价多路径(equal-cost-multipath，ECMP)在大型网络中的应用研究[4]。ECMP是指到达同一目的地的流量传输中，存在多条相同带宽的路径同时参与转发，实现了多路径的负载均衡和链路备份。ECMP部署较为简单，且被广泛应用。但ECMP的缺点在于必须应用到所有路径带宽相等的树形网络拓扑，适用于大型网络工程。然而在真实的网络环境中，各路径的带宽、时延与可靠性等并不一样，尤其是在路径间带宽差异较大的情况下，应用ECMP会导致资源利用率较差[5]。针对于ECMP的不足，Zhou等提出了加权多路径(weighted-cost-multipath，WCMP)[6]。WCMP可根据各路径带宽的不同按比例传递流量，解决了ECMP在处理拓扑不对称方面的弱点，从而提高了网络中流量带宽和负载均衡的公平性。但WCMP普遍依据路径的带宽属性来设定权值，并未考虑到在流量传输过程中各链路的时延变化等因素。除了多路径路由的算法研究以外，Ronald等曾提出多路径路由协议(MPTCP)与OpenFlow的研究[7]。MPTCP在传统的TCP内核组件中添加了MPTCP组件和面向每个OpenFlow交换机端口的TCP子流组件。MPTCP组件将字节流拆分为多个分段，并将这些分段传递给TCP子流组件，且MPTCP组件中设置了子流拥塞控制机制，可将拥塞路径的流量转移到拥塞小的链路中，从而可以应用于路径带宽不同的网络环境下。MPTCP的解决方案使用多个随机选择的路径，它作为一个TCP进程工作，并不支持UDP等其它协议[8]。此外，MPTCP本身无法进行全局链路感知，如何与SDN完美结合仍是一个难题，且通信过程中必须确保通信双方都已安装MPTCP协议栈，这为MPTCP的广泛部署带来了困难。

2 多路径路由负载均衡的设计与实现

本文提出了一种基于流量分配倾向度的SDN多路径路由的负载均衡策略，其实现过程共分为以下3个步骤：

(1)首先由控制器通过深度优先遍历算法(DFS)获取多路径及每条路径拓扑，同时采集并保存各路径的带宽与时延信息；

(2)随后依据每条路径的带宽和时延参数计算出各路径的流量分配倾向度(flow distribution propensity，FDP)；

(3)在各路径中安装OpenFlow组表，将计算好的流量分配倾向度设置成为OpenFlow Select组表中的bucket值，实现网络流量依据各路径FDP的比值分配到所有可用路径。

仿真实验结果表明，该策略可有效提高SDN网络中对于多路径的使用率，实现了多路径路由的负载均衡。

2.1 多路径发现与信息采集

在传统网络环境下，因无法获取全局网络拓扑和路径信息，网络流量的传输依靠逐跳路由和源路由两种方式，通过最优路径算法选取最优的单一路径完成流量的传递[9]。而SDN技术因其数控分离和可编程性的特点，使得SDN控制器可以获取并管理全局网络拓扑信息。拓扑的发现与管理机制是由SDN控制器中的Switches模块向底层网络(OpenFlow交换机)发送包含LLDP(link layer discovery protocol)的packet_out数据包来实现的，OpenFlow交换机在收到LLDP数据包后，会向控制器发出包含交换机间链路信息的packet_in数据包，SDN控制器再依据链路发现协议搜集到的反馈信息识别和管理网络拓扑[10]。这样的链路发现机制会消耗不小的通信流量，并产生一定的时延代价。

为简化多路径拓扑发现过程，减少通信消耗、降低时延代价，本文采用深度优先遍历(DFS)的算法思想来实现多路径拓扑发现，深度优先遍历路径获取的过程描述如下所示：

假设给定网络拓扑G(H,S)，其中H代表主机集合，S为SDN控制器所管理的OpenFlow交换机集合。以查找任意两个主机之间的所有可用多路径为目的，则其深度优先遍历路径查找过程可参考文献[11]。

2.2 路径信息采集

在多路径拓扑发现的同时，SDN控制器可以借助OpenFlow协议提供的交互信息来采集各OpenFlow交换机端口参数的信息。

OpenFlow协议[12]主要支持3种消息类型，分别是controller-to-switch、symmetric(对称型消息)以及asynchronous(异步型消息)，每种消息分别对应多个事件。其中controller-to-switch消息类型中的Read-Stats事件可帮助SDN控制器获取各OpenFlow交换机的状态信息，包含各端口的带宽和时延等。

考虑到在真实网络环境中，各链路的带宽和时延等参数不一定完全相同，因此本文在实现基于多路径路由的负载均衡时，为确保分配到各路径中的流量更为合理，需要采集各OpenFlow交换机端口的带宽与时延信息，并结合应用到后文提出的流量分配倾向度，实现网络流量的按比例分配。

(1)最大剩余带宽

在数据传输过程中，为防止路径拥塞的情况发生，本文需使用SDN控制器获取OpenFlow交换机端口的带宽信息并计算出各路径的最大剩余带宽。

首先计算出路径已用带宽，其计算公式如式(1)所示

(1)

其中，UsedBands代表采集时间间隔T内端口s的已用带宽，bytesrx代表T间隔内该端口接收的数据字节总数，bytestx代表T间隔内该端口传输的数据字节总数。

对于每条路径p={s1,s2,…,sn}，其最大剩余带宽为p包含的所有OpenFlow交换机端口的最小剩余带宽值，因此路径最大剩余带宽Bp计算公式如式(2)所示

Bp=min{Bsi-UsedBandsi|1≤i≤n}

(2)

其中，Bsi代表路径p上的OpenFlow交换机si的总带宽。

(2)时延

在SDN网络中，任意路径p={s1,s2,…,sn}的链路集合应为l={l1,l2,…,ln-1}，且路径p的时延应为该路径所包含的所有链路l的时延总和。

在SDN网络中获取某链路时延原理如图2所示。设某单一链路包含两个OpenFlow交换机SA和SB，SDN控制器可以通过向SA发送包含LLDP的数据包，并指示其将数据包转发至SB，同时记录数据发送的时间戳，然后与收到来自SB的packet_in报文的时间戳相减，即可得到SA的时延D1。同理可获取SB的时延D2。除此之外，控制器与交换机之间的往返时延由图2中虚线所示，此部分时延由echo报文测试，分别为Da和Db。因此链路l的时延计算公式如式(3)所示

Dl=(D1+D2-Da-Db)

(3)

因此路径p的时延计算公式如式(4)所示

(4)

图2 时延原理

2.3 OpenFlow组表技术应用

OpenFlow所提供的组表(group table)技术[13]，允许把端口组合成一个输出端口集合，是支持SDN多路径路由的重要技术。组表(如图3所示)的功能在于它包含独立的操作列表，每个单独的操作列表都被称为动作桶(OpenFlow bucket)，每个动作桶或动作桶列表都可用于输入数据包，并为其指定确切的动作(Action)，动作的不同取决于组表类型的不同。组表共分为4种类型：All，Select，Indirect，Fast Failover。其中Select组表的应用场景就是多路径路由和负载均衡，如图4所示，Select组中的每个动作桶都有一个分配的权重(bucket weight)，且进入组的每一个包都被发送到动作桶中。值得注意的是，动作桶分配的权值支持自定义。因此在基于多路径路由的负载均衡方案设计中，合理的动作桶权值设置是决定多路径路由效果的关键。

图3 OpenFlow组表结构

图4 Select类型组表结构

2.4 流量分配倾向度(FDP)

现有的多路径路由在进行流量分配时广泛采用等价多路径(ECMP)，或是采用依据链路带宽的加权多路径(WCMP)，然而在网络环境中各个路径的差异不仅仅体现在带宽的大小，时延和稳定性等特点也会影响路径的传输性能。

本文依据路径的带宽与时延差异，设置了流量分配倾向度(FDP)。设路径p的流量分配倾向度为Ip，其定义如式(5)所示

(5)

在网络拓扑中，链路的带宽通常为10 Mbps以上，而流量传输过程中各链路的时延通常为小数，在设置流量分配倾向度时，本文期待路径的带宽越高、时延越低，则其流量分配倾向度越高。因此式(5)中采用路径的时延作为分母，路径可用带宽最小值作为分子。

在多路径网络环境下，本文将每一个包含多路径的OpenFlow交换机安装并使用OpenFlow组表技术中的select组表，将设置好的流量分配倾向度(FDP)应用到select组表中的动作桶的权值(bucket weight)中，设动作桶权值为wp，其定义如式(6)所示

wp=Ip

(6)

为说明多路径的流量分配过程，应对其建立数学模型以进行模拟。设两个通信终端h1与h2之间包含n条可用路径pi(1≤i≤n)，其动作桶权值为wpi，且与其FDP值Ipi相等。每当有新流量Tj(j≥1)到来时，select组表在处理流量Tj中所包含的所有数据包时，会根据各路径wpi的不同，将需转发的数据包散列到所有可用路径pi中。设流量Tj中包含的数据包个数为Q，则每条可用路径所分配的数据包流量定义如式(7)所示

(7)

∑qpi=Q

(8)

其中，式(8)为约束条件，表示所有可用路径转发的数据包总和应为流量Tj所包含的数据包总量。

通过结合使用OpenFlow组表中的select组表和流量分配倾向度FDP，包含多转发路径的OpenFlow交换机在每次流量转发过程中都可以实现数据包的按比例散列，从而实现了流量的均衡分配，达到了多路径负载均衡的目标。

3 实验及结果分析

3.1 实验环境与网络拓扑配置

为验证前面提出的SDN多路径路由负载均衡策略，本部分对该策略进行了仿真实验。本实验以Ubuntu16.04为操作系统，应用mininet作为网络仿真软件搭建网络拓扑，使用Ryu软件作为SDN控制器。mininet和Ryu安装在一台处理器为Intel i5 6500，主频为3.2 GHz，4 G内存，操作系统为64位Linux的计算机上。Ryu控制器的运行环境为64位Python2.7。

本文提出的多路径路由策略通过编写Ryu控制器应用文件来实现，使用的是Python编程语言。

为展示较为明显的实验效果，本实验拓扑应用如图5所示的网络结构，其中包含一个SDN控制器，H={h1,h2,h3,h4}代表主机集合，S={s1,s2,s3,s4,s5}为SDN控制器所管理的OpenFlow交换机集合，且每条链路应用了默认的带宽和时延参数，以简单模拟真实的网络环境。

图5 实验网络拓扑

为模拟主机之间的通信，本实验使用iperf命令设置h1为服务主机，h2-h4为客户端主机。

3.2 实验过程与结果分析

本文的实验为模拟h2-h4这3个客户端主机同时发送流量至服务器主机h1，通过对比使用多路径路由策略前后，s5交换机的3个转发端口Pt={port1,port2,port3}对于数据包传输量的变化来验证负载均衡的效果。

实验首先通过深度优先遍历可查找出h2-h4和h1之间共有3条可用路径：①s5→s3→s2→s1；②s5→s4→s1；③s5→s1。通过使用Open vSwitch自带的指令dump-flows、dump-groups和dump-ports分别查看数据流和组表的状态信息以及端口的数据包转发情况，可以判断出Pt={port1,port2,port3}分别对用路径①②③。

随后依据控制器采集的路径信息计算出3条路径的流量分配倾向度(FDP)比值为5∶2∶3。

为对比负载均衡效果，在实验在负载均衡前后使用Open vSwitch指令查看并记录{port1,port2,port3}这3个端口转发数据包量的变化。

如图6所示，在使用多路径路由策略前，port3端口所对应的路径为默认的最短路径，其转发数据包个数达到106数量级，而port1与port2端口所对应的路径虽然设置了较高的带宽和较低的时延参数，却只转发了102数量级的数据包，这使得port3对应的路径负载较高，而其余两条路径的负载很低，在流量请求高峰期时会出现负载失衡的情况，影响了网络服务质量。

图6 多路径路由前s5交换机各端口数据包转发情况

而图7所示的是使用了本文的多路径路由策略后，3个端口转发数据包个数对比，port3虽然是默认的最短路径，却因链路性能(取决于带宽和时延设置)较差、FDP值较低，其转发的数据包个数明显降低；port1与port2因具备较优的链路性能也可以转发大量的数据包，从而实现了基于多路径的负载均衡。

图7 多路径路由后s5交换机各端口数据包转发情况

图8展示了在使用多路径路由策略前后，port1-port3转发端口所转发的数据包所占百分比，由此图可明显看出，在负载均衡实现前，port1与port2两个端口各仅转发了0.02%的数据包，而负载均衡实现后，3个转发端口所转发的数据包占比为5.5∶2∶2.5，基本符合其相应的FDP比值。

图8 负载均衡前后s5交换机各端口转发数据包占比

4 结束语

本文提出了一种基于流量分配倾向度(FDP)的SDN多路径路由负载均衡策略。该策略首先通过SDN控制器实现多路径的查找与信息采集，随后结合OpenFlow组表技术，实现了SDN网络中基于多路径的负载均衡。在使用OpenFlow组表时，本文设计了流量分配倾向度，该倾向度综合考虑了各路径的带宽和时延，使网络流量可以依据倾向度按比例分配到所有可用路径中，有效降低了单路径的负载，实现了多路径的负载均衡。最后的模拟仿真实验结果也验证了该策略的可行性和优越性。下一步的研究将考虑在多路径性能发生变化时如何动态地应用此策略。