基于OpenFlow的负载均衡机制

赵梦亚，龙昭华，蒋贵全，王 奇，秦晓焕

（1.重庆邮电大学 计算机科学与技术学院，重庆400065；2.北京航空航天大学 软件学院，北京100191）

0 引 言

软件定义网络 （software defined network，SDN）［1］已经成为未来网络研究的热点，尤其在数据中心的应用中，网络集中控制的优点能够保证网络中流量调度策略的动态性与灵活性，这是当前传统网络架构所不具备的。然而，数据根据目的地址通过最短路径传输，大流量可能会导致最短链路或网络接口的拥塞，与此同时，与最短路径相比的次最短路径可能空闲，造成整体性能下降与网络资源的浪费，最终导致网络的整体服务质量下降［2］。针对此问题，本文提出了一种提高网络资源利用率的路由算法，通过源节点与目的节点计算出多条路径，并根据各个路径带宽利用率对其进行选择，达到充分利用网络资源，提升网络整体性能的目的，借助OpenFlow 实验平台，对该路由策略进行实现并验证其可行性。

1 总体设计

现有的OpenFlow 控制器系统如Floodlight［3］、NOX［4］等均能够提供用于完成数据帧转发的模块，为OpenFlow交换机网络提供一种基本的简单策略数据转发，这样的路由策略会导致一个严重的问题，总体网络资源占用率并不高的情况下，大量的流进入某条链路导致负载过大，最终导致网络拥塞而造成数据帧的丢失。针对这些问题，提出使用等价多路径技术与OpenFlow 中流相结合方法，设计出针对流的多路径分配策略。

本文采用了支持OpenFlow［5，6］协议的网络架构，主要对Floodlight中现有的单最短路径和数据转发控制进行扩展，转发控制是根据多路径的路径带宽利用率选优进行控制转发，从而实现网络的多链路负载均衡传 输［7，8］。

由于OpenFlow 交换机对控制器提供统一的接口和数据转发功能，控制器对OpenFlow 流表的转发进行统一控制。基于在现有控制器中的数据转发策略模块基础上，提出了适合OpenFlow 网络的多路径路由解决策略。该策略的采用Floodlight控制器进行集中控制，控制器能够获取整个OpenFlow 交换机网络的拓扑结构，当新流接入Open－Flow 交换机时，需要计算出源节点到目的节点间的多条等价可用路径，再根据统计出的已占用的网络资源，综合各路径的状况，将流合理的分配出传输路径。为达到以上目标，本文提出的设计框架如图1所示。

图1 设计框架

在OpenFlow 网络的基础上进行扩展，其中多路径路由模块是依据控制器掌握的OpenFlow 网络的拓扑数据和根据网络链路带宽利用率为流寻找并分配合理路径，并向交换机下发对应流量分发组的OpenFlow 流表。收集网络链路信息是统计交换机流量信息。并计算出K最短路径各个路径的链路带宽利用率，为选择合理的路径提供数据支持。

多路径路由模块是整体网络的核心，实现对源节点和目的节点间多路径路由选择。当外部数据包第一次进入OpenFlow 交换机网络时，将该数据包与流表中的流表项进行匹配，由于流表中没有与该数据包相匹配的流表项，因此将该数据包的第一个数据帧通过OpenFlow 协议数据单元包装发送至控制器。控制器经过以下几步完成对该数据流的处理：

（1）解析数据包的源地址、目的地址；

（2）根据源地址和目的地址查找数据包需要经过的第一个交换机和最后一个交换机；

（3）根据网络拓扑、链路花费计算出第一个交换机和最后一个交换机间的多条可用路径；

（4）根据各个路径的带宽利用率选择最合适的路径供该数据流使用；

（5）创建流规则并告知沿途所有交换机对于该数据流的处理。

网络流量采集和网络流量统计是采用sFlow 技术对整个OpenFlow 交换机网络进行流量监控。使用sFlow 技术代替控制器的轮询收集交换机的统计信息。这样大大节约了网络资源的消耗。sFlow［9］是由InMon公司提出的一种基于 “统计采样方式”的高速交换网络流量监控技术，通过周期性采样来获取网络流量信息。然后把采样包发送至流量分析器进一步分析和处理。让用户实时的掌握网络传输流的性能和状况。sFlow 的网络流量监测实现由两个部分构成：sFlow 代理和sFlow 数据收集器。sFlow 代理对流经过交换机的数据包进行采样处理成sFlow 数据报，发送至指定的sFlow 数据收集器，sFlow 数据收集器可以接收一个或多个sFlow 代理发来的数据并进行分析处理。网络流量统计的功能：

（1）从OpenFlow 交换机网络中按照一定的时间间隔获取网络各链路的工作状态；

（2）将获取的链路信息转为控制器可读格式；

（3）为多路径路由提供数据支持。

2 多链路负载均衡机制的实现

本文的实验设计分为网络流量统计和多路径路径两个功能模块，其中多路径路径是实验设计的核心，决定了整个OpenFlow网络中流的流向，在运行过程调用网络流量统计模块提供的统计数据。本文将对两个模块的实现进行描述。

2.1 收集网络链路信息的实现

网络流量统计模块主要反映OpenFlow 交换机网络的动态信息，是为了解决多路径路由在计算出多条路径后，从中选择合适的路径提供流使用。sFlow 代理是收集网络接口的信息，sFlow 数据收集器统计各sFlow 代理发送的信息。sFlow 代理通过开源项目Host sFlow［10］来实现一种简单的部署方式，安装Host sFlow 后，在配置文件中定义sFlow 收集器的地址，通过启动hsflowd服务后即可周期性地向sFlow 收集器发送网络接口信息。控制器是基于In－Mon公司开发的sFlow－RT［11］收集器软件，并提供RESTAPI接口，以JSON 格式提供数据，根据收集的网络接口数据，计算出每个网络接口利用率。接口已用带宽测量如式 （1）所示

对于交换机节点i与交换机节点j 间的链路li，j带宽利用率如式 （2）所示

路径P 的带宽利用率W（P）为组成该路径的各个链路带宽利用率的最大值

网络流量统计的数据为多路径路由选择路径提供了依据，是整个系统的重要组成部分。

实时带宽利用率η（t）定义为网络中已经使用的链路带宽占网络总链路带宽的比例，Maxload表示为每一条链路上的最大带宽，如式 （4）所示。根据η（t）数值的变化实时显示当前网络的利用率

2.2 多路径路由模块的实现

多路径路由模块是实现名为K 最短路径算法的多路径转发核心模块，该算法是基于MPS［12，13］的K 最短路径算法，在求解无回路最短路径算法时，先对其进行权重转换，其次根据权重来选择从源节点到目的节点中所有链路花费最小的路径。该算法的特点是利用一个候选路径集合X 来寻找K 条无回路最短路径，算法从计算最短路径生成树开始，当找到最小的偏差时，每条弧的权重被替换为相应减少的权重，并只允许最优的弧 （简化权重最小的弧）。由于X 为堆 （数据结构），可以快速计算出简化权重最小的路径。根据简化权重对其具有相同尾结点的弧进行排序。使用该方法可以减少运算的次数，加快寻找偏离边的速度，效率相对较高，该算法的时间复杂度是O（MlgN＋KN），算法在最差情况下的时间复杂度大约是O（NMlgN＋KN），其中N 为交换机的个数，M 为交换机网络的链路数。核心算法的伪代码如图2所示。

根据多路径路由的算法得到从源节点到目的节点间的K 条最短路径，计算出K 条路径上的每条链路带宽剩余容量，一条路径上的剩余带宽容量由属于这条路径的所有链路的最小剩余带宽容量决定。因此，控制器需要维护交换机网络中所有链路的剩余容量。流均衡算法每次为一条流选择某条路径之后，需要修改这条路径上所有链路的剩余容量，即这条路径上所有链路的剩余容量都要减去该流的带宽需求，从而保证路径选择对网络中链路的剩余带宽容量的影响被及时更新［14］。流均衡算法描述：

（1）网络流量统计模块计算出所有链路带宽利用率。

（2）选择X 中每条最短路径中链路的带宽利用率最大的作为本路径的带宽利用率。

（3）检查K 条路径的可用带宽是否满足所需带宽要求，若是，执行下一步，若不是删除不满足的路径，再次计算最短路径达到K 条路径。

（4）选择带宽利用率最小的路径分配给新流。

3 实验测试与分析

本文的所有实验都是部署在Mininet 2.0［15，16］开发环境中，控制器采用了基于Java的控制器Floodlight。根据实际网络部署模拟出相似的网络拓扑结构，并对拓扑策略进行对多路径的路由的设计进行验证。为了使实验过程和效果具有较好的稳定性和对比性，我们对链路的基准参数进行了配置，将链路带宽限定为10 Mbps。控制器中使用链路上数值作为链路的花费。多路径数量设定为5。本文设计了网络拓扑如图3所示。每个交换机均连接一个主机节点。

网络性能测试工具的发送端程序运行在主机节点Host1和Host11上，Host1对应的接收端Host6、Host9、Host12、Host13，Host11 对 应 的 接 收 端 为Host2、Host5、Host7、Host8。两个发送端端按照每2s间隔以5Mbs的速率向相应的4个接收端程序各发送一条数据流，流中字节均为2000字节，流的长度为60s，网络流量采集时间间隔为5s。

本课题实现了最短多路径路由设计的根据网络带宽利用率进行选择路径的算法，并与Floodlight控制器原有的最短路径算法作对比，并在实验中测量了带宽利用率和吞吐率作对比分析。针对每种路由策略，分别进行了3次实验并记录以保证实验的准确性。

图2 算法伪代码

图3 实验拓扑

最短路策略仅采用链路花费最小作为选路依据，并且选择标号最小的一条路径作为流的转发。最短路策略选路结果见表1。

从路径分配表可以看出，流传输路径大部分集中在S1－S2，S2－S3，S3－S4，S11－S4这4 条链路上。而剩余链路则是在空闲状态。从而造成网络资源的利用率较低。

3次实验中，K 最短路由策略为每条流分配的路径见表2。

从表2可以看出，Host1发出的流在3次实验中分配了相同的路径，Host11发出的流到Host2路径中有两个S11－S4－S6－S2和S11－S4－S3－S2，作为等价路径且路径跳数一样，控制器选择其中一条路径作为流转发规则下放至交换机。

表1 最短路策略路径分配

表2 K 最短路径策略路径分配

经过上述3次实验，结合最短路策略和K 最短路由策略所分配的路径，我们以Host12作为接受端来测量对比分析Host1发送数据的时延。

图4是在数量流传输过程中，时延是数据从Host1发出开始到Host12返回的ACK 包所经历的时间，在刚开始时由于要寻找路径时延的花费比较大随后时延趋于稳定，在45s时刻大量的数据流注入OpenFlow 网络，基于最短路径的策略不可避免的出现了拥塞，流传输的不稳定以及丢包会导致时延增大，基于K 最短路径策略在能够将流量均分配给路径，时延在那一时刻之后趋近平稳。

图4 最短路策略和K 最短路由策略时延对比

图5可以看出，在开始阶段K 最短路径路由策略比最短路径策略的带宽利用率高，原因从路径分配表就可以看出，前期由于流量的平稳传输，带宽利用率趋近平稳，但在45s时刻大量的数据流注入OpenFlow 网络，基于最短路径策略的流传输集中的4条链路出现了大量的丢包，网络的带宽利用率没有发生明显的变化，基于K 最短路径策略通过流均衡算法对流量均衡分配给K 条路径，网络带宽利用率较大提高，同时网络吞吐量也得到提高。

图5 最短路策略和K 最短路由策略带宽利用率对比

4 结束语

本文提出了一种参照路径带宽利用率的K 最短路径策略，基于Floodlight集中控制交换机的思想对该策略进行实现。设计基于Floodlight控制器的多路径路由策略，充分利用控制器全局可见、集中控制特点，通过统计网络流量并分析网络链路状态来均衡链路负载、创建转发策略，提高网络服务性能。并通过基于Mininet的实验平台搭建仿真平台，对比了控制器原有的最短路径路由和参照网络状态的多路径路由在网络拓扑的效果。通过实验验证，参照路径带宽利用率的K 最短多路径策略能够提高网络资源的整体利用率，从而提高网络的整体性能。

［1］ZUO Qingyun，CHEN Ming，ZHAO Guangsong，et al.OpenFlow－based SDN technologies ［J］.Journal of Software，2013，24 （5）：1078－1097 （in Chinese）. ［左青云，陈鸣，赵广松，等.基于Open Flow 的SDN 技术研究 ［J］.软件学报，2013，24 （5）：1078－1097.］

［2］ZHANG Jin.Design and implementation of resources allocation in Openflow network ［D］.Beijing：Beijing University of Posts and Telecommunications，2013：10－22 （in Chinese）. ［张瑾.OpenFlow 网络中资源分配的研究与实现 ［D］.北京：北京邮电大学，2013：10－22.］

［3］Floodlight.［EB／OL］.［2014－06－20］.http：／／www.projectfloodlight.org／floodlight／.

［4］NOX.［EB／OL］.［2014－04－12］.http：／／www.noxrepo.org／.

［5］McKeown N，Anderson T，Balakrishnan H，et al.Open－Flow：Enabling innovation in campus networks ［J］.ACM SIGCOMM Computer Communication Review，2008，38 （2）：69－74.

［6］OpenFlow Switch Specication Version 1.3.1［EB／OL］.https：／／www.opennetworking.org／sdn－resources／onf－specifications，2012.

［7］LIU Chunjia.Design and implementation of an OpenFlow－based link load balancing mechanism ［D］.Beijing：University of Chinese Academy of Sciance，2013：31－40 （in Chinese）. ［刘 春佳.一种基于OpernFlow 的链路负载均衡机制的设计与实现［D］.北京：中国科学院大学，2013：31－40.］

［8］YANG Xiaoqin，ZHANG Lifang，CAO Qinghuang，et al.Routing algorithm based on link bandwidth utilization rate［J］.Journal of Computer Applications，2012，32 （9）：2422－2425（in Chinese）.［杨晓琴，章丽芳，曹庆皇，等.基于链路带宽利用率的路由选择算法 ［J］.计算机应用，2012，32 （9）：2422－2425.］

［9］Schmidt RdO，Sadre R，Sperotto A，et al.Lightweight Link dimensioning using sFlow sampling ［C］／／Proceedings of the 9th International Conference on Network and Services Management，2013.

［10］Host sFlow ［EB／OL］. ［2014－07－10］.http：／／sourceforge.net／projects／host－sflow／.

［11］sFlow RT ［EB／OL］.［2014－09－27］.http：／／www.inmon.com／products／sFlow－RT.php.

［12］Yinglin SNJ.K constrained shortest paths problem ［J］.China Management Studies，2009，1：3.

［13］MAO Shaowu，ZHANG Huanguo，HUANG Chongchao，et al.A new fault－tolerance mechanism in communications based on K shortest path algorithm ［J］.Journal of Wuhan University，2013，59 （6）：534－538 （in Chinese）.［毛少武，张焕国，黄崇超，等.改进的K 最短路径算法在通信网络中的应用 ［J］.武汉大学学报，2013，59 （6）：534－538.］

［14］LONG Hui.Research on the OpenFlow－based load－balancing routing in distributed networks［D］.Shanghai：Shanghai Jiao Tong University，2013：43－47 （in Chinese）. ［龙慧.基于OpenFlow 的分布式网络中负载均衡路由的研究 ［D］.上海：上海交通大学，2013：43－47.］

［15］Mininet.［EB／OL］.［2014－02－15］.http：／／mininet.org／.

［16］Bob Lantz BH，Nick McKeown.A network in a laptop：Rapid prototyping for software－defined networks ［C］／／Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks.ACM，2010.