【学习笔记】基于OpenFlow的数据中心网络负载均衡算法

2016年电子技术应用第5期

作者：董宏成，郑飞毅

0 引言

近年来，数据中心呈现爆炸式的急速发展，大量公司开始建立自己的大型互联网数据中心(Internet Data Center，IDC)。云计算技术的出现对数据中心网络提出了新的挑战，比如网络安全、虚拟机迁移、多租户管理、负载均衡等。传统的数据中心采用专用的负载均衡设备实现网络资源的有效利用，具有设备成本高昂和可扩展性差等问题，而基于软件定义网络的集中化的调度方式能够提高资源利用率，简化网络管理，降低运维成本。

SDN[1]是一种将控制层和转发层分离的新型网络架构，交换机只负责数据流的转发，降低了网络交换机的负载，控制层的功能全部由运行于服务器上的控制器实现。控制器需要下发流表到交换机才能支持转发层设备的有效运行，而控制层与转发层之间的通信需要遵守一定的规则，目前较普遍的是采用OpenFlow[2]协议来实现信息交互。本文目的是在SDN网络架构下解决网络流量高峰期链路的负载分布不均匀问题，设计了负载均衡机制的总体框架、实现流程图以及具体实现。

1 数据中心网络流量特征

国内外学者对真实数据中心网络流量特征进行了深入的观察研究。Mckeown研究表明数据中心网络流量与传统的局域网和广域网流量有着极大的不同，内部节点间的数据流量在数据中心网络所有流量中占主导地位[3]。Greenberg指出数据中心80%的数据流量为数据中心内部的流量，而且85%的数据流小于100 KB[4]。目前采用最多的是Fattree[5]网络拓扑，它可以为两两节点之间的流量提供多条路径，这样从理论上能降低单一路径的负载率过高的问题，而在实际应用中还是会出现某条路径上流量拥塞严重而其他可用路径却处于闲置状态的问题。

数据中心网络流量模型由大流和小流组成，每个数据流由许多数据包组成，这些数据包具有5个相同特征（源IP地址、源端口号、目的IP地址、目的端口号、协议类型）。而大流是造成部分链路拥塞的主要原因，所以负载均衡机制主要针对大流，在调度过程中尽量忽视小流来降低调度开销。数据流的大小由其所含字节数决定，同时数据流越大，持续的时间越长，小流持续时间很短。本文将字节数大于100 KB的流界定为大流。

2 负载均衡实现的总体框架

控制器的负载均衡功能模块如图1所示，主要包括拓扑发现模块、大流监测模块、流量收集模块、路径计算模块、流表导入模块。拓扑发现模块帮助控制器掌握通过全局的拓扑信息，包括主机的位置信息、交换机之间的连接等。大流监测模块在链路利用率最大路径上找出并标记大流。流量收集模块周期性地收集OpenFlow交换机网络的流量信息，为两个节点之间的多条路径选择提供参考流量监测模块统计交换机接口的流量信息，用于分析计算各链路的链路利用率。路径计算模块为大流的重路由提供支持，是实现负载均衡功能的重要部件。流表导入模块是通过控制器向OpenFlow交换机发送Packet_out消息实现的，动态地将大流的最终得出的重路由路径添加到交换机流表，从而实现OpenFlow网络的负载均衡功能。负载均衡算法的实现流程如图2所示。

3 各功能模块的数学建模与实现

首先为负载均衡制定一个启动阈值，这里采用负载均衡参数：

其中loadi，j(t)代表在t时刻链路<i，j>上的已经被占用的带宽[6]，N是网络中所有链路的数目。下面简单描述各模块的实现方式。

3.1 拓扑发现模块

拓扑发现模块的功能是收集网络的拓扑信息，将其保存在拓扑图表中，并对网络的拓扑结构进行管理。控制器与交换机之间是在OpenFlow标准协议的基础下进行通信的，但是控制器并不能通过Open。Flow协议获得网络的拓扑结构，是通过LLDP组件[7]发送LLDP(Link Layer Discovery Protocol)数据包到OpenFlow交换机，再收集并解析交换机反馈的LLDP数据包，从而实现网络拓扑感知。

3.2 大流监测模块

由于本文所提出的负载均衡机制是针对大流的，所以必须有一种方法将大流和小流区分开来。文献[8]对3种主流的大流监测机制进行了分析比较，包括采样监测、应用监测和统计监测。文献[9]中提出探测大流最有效的方式是在终端主机进行，一方面占用的资源比例相对交换机要少，从而避免大流监测占用过多的交换机端资源；另一方面流的状态也取决于终端应用程序生成数据包的快慢，而不是网络的链路状态，终端对应用程序发包速率的可知性更强。监测原理是通过观测终端主机socket缓存区，当缓存区内具有相同特征的数据包大小超过100 KB，它就会被标记为大流，本文便采用对主机端的统计监测方式来进行大流监测，主机端需要精确统计和维护数据流的速率和字节等信息，再将统计信息通过交换机发送到控制器，从而实现控制器的大流监测功能。

3.3 流量收集模块

这个组件的目的是询问每个OpenFlow交换机的流量信息，再将所有收到的反馈信息进行联合并最终存储到控制器的存储单元。这些收集到的数据被路径计算模块用来计算不同链路上的负载，因为基于权重的多路径路由的核心思想是将大流的数据包分配到负载较轻的链路上，因此需要确切知道路径上所有可能的链路负载。这个单元模块周期性地通过轮询的方式收集每个OpenFlow交换机的流数量、流表以及端口数据，并作为一个快照对象进行存储。每个快照对象都会通过一串数字标识，每个周期生成新的快照对象后数字标识会自动加1，存储区只会保存最新的2个快照对象，其他的功能模块都有获得快照对象数据的权限。

3.4 路径计算模块

初始状态采用Floyd[10]算法计算基于跳数的Top-K最短路径，然后需要对每条路径的状态进行评估。本文主要对路径的两个方面指标进行评估，一个是路径所包含链路的长度，这个体现在跳数（Hop Count）；另外一个指标是路径上的负载，这个体现在这条路径所包含的交换机和链路上的流量。由于每条路径上包含多个交换机以及多条链路，不能简单地以总流量的平均数来表示这条路径的负载，而应该根据特定的交换机和链路来代表该路径的负载情况。交换机的负载通过它所统计的PC(Packet Count)和BC(Byte Count)来体现，链路的负载通过端口的转发率（Forwarding Rate）来表示。这些数据可以通过控制器周期性地向OpenFlow交换机发送状态请求消息得到。每条路径的负载状况可以表示为S=(H，P，B，F)，其中H表示跳数；P=Max(P1，P2，…，PH)，Pi表示该路径的第i台交换机所转发的封包数量，共包含H台交换机；B=Max(B1，B2，…，BH)，Bi表示该路径的第i台交换机所转发的字节数量。F=Max(F1，F2，…，FH)，Fi表示该链路经过的第i台交换机出端口的转发率。由于参数之间的差异比较大，需要先进行如下变换[11]：

每一条路径可以用矩阵R=(rh rp rb rf)表示,权重向量W=(0.35，0.20，0.20，0.25)，各个参数值根据经验自己定义，这里路径的长度取0.35显示了其重要性。每个节点对之间的所有路径可以通过一个矩阵表示为：

Qi表示路径i最后的权值，根据权值可以确定数据流经i节点传输到j节点的最佳路径。路径计算模块伪代码如下：

Algorithm : Route Construction

(1)Connect the topology with the RYU controller

(2)Detect the topology and do the following activities:

(3)Calculate top K shortest paths between each pair of nodes using Top-K Shortest Path algorithm(TKSP is the extension of Open Shortest Path First).

(4)Evaluate the Top-K path with the proposed method.

(5)Sort the paths between each pair of nodes according to the evaluation and store the results to the controller.

(6)Reconstruct the path using step1-5 in case of a node/link failure.

3.5 流表导入模块

中心控制器通过路径计算模块产生的结果生成转发规则，然后封装到Packet_out消息中导入到支持OpenFlow的交换机，交换机流表添加该转发规则并根据更新的流表项来指导流量转发。由于网络流量和拓扑结构都是不可预测的，交换机流表会伴随负载均衡机制实时、动态地更新，而且过期的流表项会根据交换机配置而删除。

4 实验结果分析

本文采用Mininet2.2.0[12]作为一个开发环境模拟数据中心网络场景，搭建如图3所示的网络拓扑结构，在Ubuntu Kylin 14.04.3上运行RYU控制器，结合iperf工具来产生TCP(Transmission Control Protocol)数据流和UDP(User Datagram Protocol)数据流，并且能够测量端到端的吞吐量，从而得出整个网络的吞吐量。host1～4同时向host5～8发送数据流量，在RYU[12]控制器中结合拓扑发现模块、流量监测模块、路径计算模块和流表导入模块来对负载均衡算法进行验证。仿真实验通过h1～h16传输时延、总吞吐量和总体链路利用率这3个指标来验证本文所提出的负载均衡算法的有效性。总体链路利用率通过下式得到：

其中，MAXLOAD代表每条物理链路最大带宽，仿真实验的信息见表1。

选择h1和h16为网络时延测量的观测对象,实验结果如图4所示，在实验进行的前47 s数据包从h1～h16延时很低，而且本文所提出的LB(Load balance)算法和基于最短路径算法的时延曲线表现出了极高的相似度。这是因为刚开始时链路负载较轻，两种算法都是采用h1-S1-S9-h16来传输流量，而LB算法由于需要监测数据流量并且周期性地向控制器发送网络状态信息，这样会产生部分开销而导致延时略高于基于最短路径算法；但是47 s之后LB算法下的时延明显低于采用OSPF算法的时延，这是因为太多的流量集中在最短路径h1-S1-S9-h16，而其他可用路径处于空闲状态，负载不均衡度大于判决门限，就会触发负载均衡机制，原路径上的流量会转移到其他可用路径，链路利用率也得到了明显提升，如图5所示。网络整体吞吐量的性能比较如图6所示，当负载低于550 Mb/s时，两者的性能曲线非常相似，由于LB算法需要传输额外的链路状态信息导致吞吐量会略高于550 Mb/s；当负载超过550 Mb/s，基于最短路径算法网络出现拥塞，其他可用链路得不到有效利用，吞吐量的增长明显放缓。而LB算法下的网络吞吐量在550～700 Mb/s区间能一直保持快速增长。因此本文提出的LB算法相比传统的OSPF算法能够在负载不均衡情况下改善网络性能。

5 结束语

本文设计了负载均衡功能实现的总体框架，主要包括拓扑发现模块、流量监测模块、路径计算模块、流表导入模块。设计了负载均衡功能的实现流程图，对相关的数学模型进行了详细的分析设计，确定了以大流为目标流的调度策略，并通过实验验证了该负载均衡算法相比传统的OSPF算法能够实现更低的网络延时和更高的总体链路利用率和吞吐量。

该算法的不足之处是没有考虑到大流出现重复调度的情况，如果某个大流被多次选为目标流调度，可能会使情况更糟糕，而且流的转移开销也会影响负载均衡的实现效率。降低大流在调度过程中的开销具有重要的意义，上述两点将是下一步需要重点关注的内容。

参考文献

[1] 左青云，陈鸣，赵广松.基于Open Flow的SDN技术研究[J].软件学报，2013，24（5）：1078-1097.

[2] Open Networking Foundation.OpenFlow[EB/OL].(2016)[2016].https：//www.opennetworking.org/en/sdn-resources/openflow.

[3] MCKEOWN N，ANDERSON T，BALAKRISHNAN H，et al.OpenFlow：Enabling innovation in campus networks[J].SIGCOMM Computer Communication Review，2008，38(2)：69-74.

[4] GREENBERG A，HAMILTON J R，JAIN N，et al.VL2：A scalable and flexible data center network[C].Proceedings of the AC_MSIGCOMM 2009 Conference on Data Communication.Barcelona，Spain，2009：51-62.

[5] GREENBERG A，HAMILTON J，MALTZ D A，et al.The cost of a cloud：research problems in data center networks[C].In ACM SIGCOMM，2008：68-73.

[6] Long Hui.Research on the OpenFlow -based load-balancing routing in distributed networks[D].Shanghai：Shanghai Jiao Tong University，2013.

[7] 张远.基于OpenFlow的负载均衡研究[D].北京：北京工业大学，2014.

[8] 李龙，付斌章.Nimble：一种适用于OpenFlow网络的快速流调度策略[J].计算机学报，2015，38（5）：1056-1068.

[9] CURTIS A R，KIM W.Mahout：low-overhead datacenter traffic management using end-host-based elephant detection[J].IEEE INFOCOM，2011，2(3)：1629-1637.

[10] BACKHOUSE R C，EIJINDE J P H W，GASTEREN A.J.M.V.Calculating path algorithms[J].Science of Computer Programming，1994，22(1-2)：3-19.

[11] Li Jun，Chang Xiangqing，Ren Yongmao，et al.An effective path load balancing mechanism based on SDN[C].IEEE 13th International Conference on Trust，Security and Privacy in Computing and Communications，2014.

[12] Mininet Team.Mininet：An instant virtual network on your laptop[EB/OL].(2016)[2016].http://www.mininet.org/.