一种多指标综合评价负载均衡路由策略研究

倪晓军，段元新，章 韵，张敏敏

(南京邮电大学 计算机学院·软件学院，江苏 南京 210003)

一种多指标综合评价负载均衡路由策略研究

倪晓军，段元新，章 韵，张敏敏

(南京邮电大学 计算机学院·软件学院，江苏 南京 210003)

目前，OpenFlow网络还没有一套完整的负载均衡解决方案，使得整体网络资源利用率不高。文中利用OpenFlow网络控制器集中控制的优势，在控制器上设计并实现了一种动态负载均衡路由策略。该策略能够根据网络状态信息动态制定数据流转发策略：以链路多指标综合评价值作为链路新的权重，并以此新权重计算源节点与目的节点间的最优路径，从而引导数据流时刻处于最优转发路径上。最后利用Mininet仿真技术，对文中提出的负载均衡路由策略进行性能验证仿真实验。结果表明，文中提出的负载均衡路由策略有效缓解了网络拥塞，提高了链路利用率。

OpenFlow；负载均衡；多指标；路由算法

1 概 述

从20世纪70年代互联网开始到现在，随着业务和应用的不断丰富与发展，网络规模及应用需求的大幅增长，与现有的网络服务能力的矛盾越来越明显。当前网络以IP核心为网络体系架构逐渐暴露出了各式各样的问题，网络承载功能已从数据处理、报文传输等基本需求扩展到从安全性、稳定性等多方面对服务质量做出承诺。随着近年来数据中心的快速发展，作为网络领域的一个经典问题，网络链路的负载均衡开始得到大量关注。尤其是庞大而复杂的网络拓扑数据中心网络，如何对其进行管理和充分利用链路资源，正面临来自流量工程、路径优化、负载均衡等多个方面的挑战。如果不能合理分配网络负载，就很容易造成网络拥塞，影响网络服务的有效交付。链路负载均衡可以实现节点负载的均衡化，避免出现某些链路负载过重而其他链路闲置的情况。数据流均衡算法可以根据获取的网络链路状态信息，动态选择最优路径，具有自适应能力，优化网络资源分配，从而提高整体系统的吞吐量和资源的优化。传统网络采用的负载均衡路由算法大都基于跳数或时延参数，通过最短路径优先算法实现。这些路由策略为相同源地址、目的地址的数据建立唯一传输路径，而且在建立路径时，未考虑网络的传输状态。这样的路由策略由于其参数过于固定，路径选择结果相对单一，可能造成网络局部链路拥塞，导致整体网络资源利用率低下；同时，与最短路径相比，次最短路径或者花费稍长的路径却处于空闲状态。

面对这些问题，研究者不得不借助硬件和相关协议进行网络功能扩展，这种功能扩展和固化的硬件高度耦合的形式，将会导致新的想法和协议无法通过规模化部署得到验证。网络协议从最初的TCP/IP发展到现在的TCP/IP协议簇和上千种补丁协议。整个网络越来越复杂，架构还是一如既往的封闭，缺少灵活性，难以跟上日益变化的网络需求。

在这样的背景下，亟需加快网络技术创新的步伐，开发一种新型网络技术架构来改善这种局面。其中软件定义网络[1-2](Software Defined Networking，SDN)则是近年来未来网络领域诸多方向中坚实且明确的一个研究方向。它提出了一种更加灵活高效的部署模式，以适应企业级网络越来越灵活多变的需求。在SDN技术中尤以OpenFlow[3]技术发展最快。OpenFlow网络采用集中式的控制平面和分布式的转发平面，控制平面利用OpenFlow相关协议对转发平面进行集中控制，以此来完成数据的转发。控制器集中控制能够实现对全网络中每一条链路的信息进行跟踪检测，保证制定数据流在网络中的转发策略时，充分考虑网络的动态性能特征，从而改善网络的负载均衡，提高其传输效率。

2 国内外研究现状

2008年，Nick McKeown教授提出OpenFlow的概念，并详细介绍了OpenFlow协议。OpenFlow凭借集中控制的优势能够有效处理复杂的流量模型，并基于负载状况进行动态的、精细的调整。就负载均衡技术而言，传统网络的负载均衡通常是由负载均衡器完成。与传统网络不同，OpenFlow交换机本身只负责对数据包的转发，负载均衡则由控制器来实现。对于网络负载均衡而言，虽然传统网络中已有很多相关研究和解决方案，但在全新架构的SDN网络中，如何利用OpenFlow协议原理去实现链路负载均衡策略的相关研究并不多，仍然有待开发与完善。目前基于OpenFlow的负载均衡研究主要集中在控制器上，利用控制器集中管理优势，定时对交换机的流量状态进行统计，根据网络链路负载情况动态调整网络中的数据流。

但OpenFlow技术目前还处于发展初期，在协议和处理机制上还存在诸多需要改进和完善的地方[4]。现有的OpenFlow控制器系统，如NOX[5]、FloodLight[6]等，均提供了用于完成数据帧转发的模块，其采用Dijkstra最短路由算法，为OpenFlow交换机网络提供一种简单策略，实现基本的数据转发功能。然而，这种转发方式很容易造成链路阻塞。

针对控制器在负载均衡方面存在的不足，国内外许多学者都在进行这方面的研究。文献[7]中提出的名为Hedera的数据中心网络动态流调度系统，具有可扩展、自适应调度的特点，但其使用的ECMP和VLB等路由策略未考虑路径的带宽剩余容量，很可能会导致多条带宽需求较大数据流的传输路径存在部分公共链路，易导致网络的拥塞。文献[8]中提出的基于OpenFlow的可适应QoS视频流优化框架，采用带时延约束的拉格朗日松弛路由算法计算视频流转发路径。但该论文只单独研究了视频流的转发策略，并未考虑链路传输过程中数据流业务的多样性和复杂性。文献[9]提出了一种在胖树型网络拓扑结构中，基于OpenFlow的动态负载均衡路由算法DLB。虽然DLB这种针对单跳使用贪婪算法的选路策略简单有效，但它没有考虑网络负载的分布情况。该方法选出的源节点到目的节点的整条路径，可能并不是当前最优路径，在这种情况下，甚至会加剧网络的拥塞。文献[10]中的GLB负载均衡算法改进了文献[9]中的DLB算法，使用当前路径最大剩余带宽容量作为选路依据。在进行路径决策时，计算出源节点到目的节点的所有路径，以当前路径最大剩余带宽容量为依据选出最优传输路径。然而，GLB负载均衡算法在选择路径时，只考虑了剩余带宽容量的影响，并未考虑网络中其他链路指标，如：时延、丢包率、链路花费等。

OpenFlow网络目前尚未形成一个完整、可信服的负载均衡路由策略，并且各个学者的研究方案采用的控制器、路由策略、网络拓扑、仿真环境也各不相同，还无法对其性能优劣进行对比。这些路由策略都是在OpenFlow网络中的一些有益尝试，为后续流量工程解决方案的研究提供了新的思路。

综合上述研究成果，文中就数据流在OpenFlow网络中的路径选择问题，利用OpenFlow网络中控制器集中控制的优势，在控制器上设计并实现了一种新的负载均衡路由策略—多指标评价的链路负载均衡路由策略。文中使用多指标评价体系对每条链路进行综合评价，充分考虑链路传输数据流业务的多样性和复杂性，并采用基于主观判断的方法改变链路各指标的权重，引导数据流转发到最适宜的路径上。

3 多指标全局负载均衡路由算法设计

3.1 多指标综合评价模型

目前，网络性能的分析和评价主要侧重于对网络协议或算法的性能进行分析，所涉及到的往往只是某个具体性能指标。然而，对实际或设计的网络本身进行性能评价时，单个性能指标有时并不能反映网络的整体性能。例如，在比较A、B两个网络的性能优劣时，A网络有些性能指标优于B网络，而B网络亦有些性能指标优于A网络，在这种情况下，就很难根据其中某一个性能指标来比较A、B两个网络整体性能的优劣。所以，必须采用多指标评价体系对网络进行综合评价，即将多个指标转换为一个能够反映网络综合性能的指标，来对网络进行评价。为此，文中设计并实现了一种基于多指标综合评价体系的链路负载均衡路由策略。

全球互联网技术权威核心组织IETF的IPPM(IP Performance Metrics)[11]工作组提出了一系列网络性能指标：时延、时延抖动、丢包率、路径利用率、网络吞吐量、网络带宽等，用于评价网络的服务质量[12]。在日常网络使用过程中，可用带宽剩余容量、时延、丢包率三个网络性能指标对网络服务质量影响最大。因此，文中选取可用带宽剩余容量、时延、丢包率三个网络性能指标，以OpenFlow交换机的网络接口作为测量对象，建立网络性能的综合评价模型，如图1所示。该模型以网络接口的流量信息为数据源，对经过接口的流量进行分析，得出该链路的性能指标信息。

图1 链路性能综合评价模型

文中根据网络测量获得的各性能指标数据，建立一套行之有效的评价模型，对网络运行状态进行评价，从而更直观地反映网络的综合性能情况。因各个指标之间的大小评价程度和影响力不同，无法进行统一比较，需要通过数学变换的方式，消除各测量指标数值之间的影响。模糊评估方法广泛应用于各个领域，特别是评价参数较多、评估结论比较模糊的场合，效果更加明显，如大小、高低、好坏的评估。模糊评估方法主要有模糊矩阵法[13-14]、Delphi法[15]、神经网络法[16]等。文中运用模糊集之父—美国学者L.A.Zadeh提出的模糊隶属度函数的方法，结合文献[13-14,17]等提出的模糊评价模型，采用直线型模糊无量纲化方法评价网络性能。此方法的操作步骤是：

(1)正指标，指标测量值越大，网络性能越好，如带宽等。

(2)负指标，指标测量值越大，网络性能越差，如时延等。

最后，采用加权平均评价模型计算路径的综合性能评价值，计算方法如下：

wk的取值可以根据不同的网络服务类型做相应调整。例如，对于网络带宽需求较大的文件传输，可通过相应提高链路可用带宽剩余容量的权重系数来满足其需求。通过调整链路各评价指标的权重，就可以适应各种类型的网络服务。

3.2 链路选择

在得到每一条链路的综合性能评价值后，下一步就是根据该综合评价值选出一条最优转发路径。由于需要动态制定转发策略，每当有新数据流到达OpenFlow网络交换机时，Floodlight控制器都会综合全网络中各链路的负载情况，为新数据流选择适宜的转发路径，实现全网络链路的负载均衡。同时，由于流表中没有与到达交换机的新数据流相匹配的流表项，OpenFlow网络交换机会将数据流的分组封装Packet-in消息发送到控制器，控制器经过以下步骤完成对该数据流的处理：

Step1：解析数据包的源地址、目的地址；

Step2：根据源地址与目的地址，分别查找与其直连的OpenFlow网络交换机；

Step3：根据链路状态计算链路的综合评价值；

Step4：根据网络拓扑结构、链路综合评价值，为该数据流选取最优转发路径；

Step5：创建流规则，并将该数据流的处理规则告知转发路径上的所有交换机。

4 仿真实验与结果分析

为了实现上述实验方案，文中设计并实现了一套基于OpenFlow网络的仿真实验系统。系统架构如图2所示。

图2 仿真实验系统架构图

该实验系统是在一台Windows 8系统主机上运行两台Ubuntu系统虚拟主机。一台虚拟主机运行Mininet[18]仿真软件并部署sFlow[19]代理采集器，另一台虚拟主机运行Floodlight控制器软件和sFlow收集器，sFlow收集器用于收集接口信息并反馈给控制器。sFlow是由InMon、HP和Foundy Networks于2001年联合开发的一种网络监测技术，并已形成RFC3176标准，是一种以设备端口为基本单位的数据流随机采样流量监控技术，不仅可以提供网络的第2～4层实时流量信息，而且可以适应超大网络流量(如大于10 Gbit/s)环境下的流量分析，让用户详细、实时地分析网络传输流的性能、趋势以及存在的问题。sFlow作为一种标准协议，可以提供周期性的网络接口统计采样和数据包采样，也能够提供各接口的流量信息，而且几乎不会对被统计设备造成任何负担，管理成本极低(sFlow的原理和部署过程不再赘述)。两台虚拟主机使用Bridged Adapter模式进行通信。sFlow代理采集器会将采集到的各链路实时性能信息发送至sFlow收集器，sFlow收集器将接收到的链路信息存储到本地数据库中，并每隔一定周期更新一次数据库中的链路信息。当控制器需要为新数据流分配转发路径时，控制器读取本地数据库中的链路信息，相应制定数据流转发策略，从而实现动态调整网络负载。采取传统网络中比较成熟的网络信息采集软件sFlow，可以避免出现因采集链路信息引发Floodlight控制器负荷过大的问题，使控制器在几乎零负荷的情况下就能采集得到网络中的链路信息。

仿真实验采用的网络拓扑结构如图3所示。所有链路带宽限定为5 Mbps，每条链路上的传输时延设定为10～20 ms间的一个随机整数，sFlow收集器收集每个链路上的有效信息并传至Floodlight控制器，设置sFlow统计数据的刷新时间为2 s，三个性能指标所占权重都设为1/3。

图3 模拟实验所用的网络拓扑结构图

为了测试链路评价值的灵敏度，将链路(s2,s1)作为观测主体，向其注入流量，实时观测各链路的综合评价值。实验步骤如下：

Step1：初始状态时，没有其他流量干扰，网络状态趋于稳定，得到的链路综合评价值相对稳定。

Step2：h2以3Mbps的速率向h1发送udp数据包，为链路(s2,s1)注入流量，几秒后以5Mbps的速率向h1发送udp数据包。

实验结果如图4所示。

从图中可以看出，当链路(s2,s1)注入流量后，链路(s2,s1)的综合评价值下降幅度很大，说明模拟实验系统具有对链路信息实时监测计算的能力。

下面采用搭建的仿真实验系统，在转发路径能够正常分配的前提下，分别对文中提出的路由策略与Floodlight控制器的最短路由转发策略进行仿真实验。为保证实验数据具有较高的可靠性，使用以上两种路由策略各进行三次实验，分别记录路径选择结果。实验条件如下：

图4 链路性能评价曲线图

设定主机h1每隔2s启动一次，轮流与h6、h7进行通信，两条数据流均为3Mbps的udp数据流，每条数据流持续时间为60s。

实验结果如表1、表2所示。

表1 Floodlight最短路由转发策略路径分配表

表2 多指标综合评价路由策略路径分配表

从表1可以看出，三次模拟实验Floodlight最短路由策略路径选择结果相同。当两条数据流都在路径s1-s2-s3-s6中传输时，势必会出现链路拥塞问题。而从表2可以看出，多指标综合评价路由策略在进行路径分配时，能够根据网络链路的状态信息，合理分配转发路径，避免了最短路由策略中部分链路过载、部分链路空闲的问题，提高了网络资源的有效利用率。

采用文献[20]中的随机流量模式，分别使用文中提出的路由策略与Floodlight控制器的最短路由转发策略进行仿真实验，对比两种路由策略对网络带宽利用率的影响。实验过程中，每一台主机等概率选择另一台主机进行通信，流量发送速率从0.5Mbps至5Mbps依次增大，每条数据流持续时间为60s。实验结果如图5所示。

从图中可以看出，使用文中提出的基于链路综合评价的数据流负载均衡路由策略，带宽利用率明显高于Floodlight的最短路由策略，且随着数据流发送速率的增大，两者之间的差距越来越明显。因此，基于链路综合评价的负载均衡路由策略可以有效提高网络的利用率。

5 结束语

文中针对OpenFlow网络发展初期负载均衡不完善的问题，分析了现有基于OpenFlow技术负载均衡的研究成果，提出了基于链路多指标评价体系的负载均衡路由策略。该策略采用多个链路指标，对链路的性能进行综合评价，并据此制定数据流转发策略，选取最有利于当前网络负载均衡的传输路径，避免出现局部链路阻塞的问题。最后在Mininet实验平台上搭建性能验证仿真实验系统，验证了文中方案的可行性和有效性。

实验结果表明，文中设计的负载均衡路由策略有效缓解了网络拥塞，提高了网络资源的整体利用效率。但文中也有很多不足之处。例如，由于该路由策略需要计算每条链路的综合评价值，计算量较大，这在一定程度上限制了文中提出的路由策略的应用。针对不足之处，后续还将继续修订完善。

[1] 万 昕.关于SDN如何解决传统网络问题的探究[J].江西通信科技,2013(2):11-13.

[2] 左青云,陈 鸣,赵广松,等.基于OpenFlow的SDN技术研究[J].软件学报,2013,24(5):1078-1097.

[3]FeamsterN,RexfordJ,ZeguraE.TheroadtoSDN:anintellectualhistoryofprogrammablenetworks[J].ACMSIGCOMMComputerCommunicationReview,2014,44(2):87-98.

[4] 张朝昆,崔 勇,唐翯祎,等.软件定义网络(SDN)研究进展[J].软件学报,2015,26(1):62-81.

[5]GudeN,KoponenT,PettitJ,etal.NOX:towardsanoperatingsystemfornetworks[J].ACMSIGCOMMComputerCommunicationReview,2008,38(3):105-110.

[6] Floodlight[EB/OL].[2005-09-06].http://www.projectFloodlight.org/Floodlight/.

[7] Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:dynamic flow scheduling for data center networks[C]//Proc of networked system design and implementation.Berkeley:[s.n.],2010:19-33.

[8] Egilmez H E,Civanlar S,Tekalp A M.An optimization framework for QoS-enabled adaptive video streaming over OpenFlow networks[J].IEEE Transactions on Multimedia,2013,15(3):710-715.

[9] Li Y,Pan D.OpenFlow based load balancing for fat-tree networks with multi-path support[C]//Proc of IEEE international conference on communications.[s.l.]:IEEE,2013.

[10] 吴宇文.基于OpenFlow的网络负载均衡算法的研究与设计[D].上海:华东师范大学,2014.

[11] Network Working Group.RFC 2678,IPPM metrics measuring connectivity[S].Pittsburgh:Network Working Group,1999.

[12] Garzon M,Rose J,Gao Y.DNA implementation of finite-state machines[C]//Proceedings of genetic programming 1997.[s.l.]:[s.n.],1997:479-490.

[13] 赵华琼,唐学文.基于模糊层次分析法的网络业务性能评估模型[J].计算机应用,2013,33(11):3035-3038.

[14] Yang Yunfei,Shi Jihong.Research on business performance evaluation model of power distribution network based on PTN[C]//Proc of international conference on computer science and network technology.[s.l.]:[s.n.],2011:902-905.

[15] Papamichael M K,Cakir C,Chia-Hsin C S,et al.DELPHI:a framework for RTL-based architecture design evaluation using DSENT models:performance analysis of systems and software[C]//Proc of ISPASS.[s.l.]:IEEE,2015:11-20.

[16] Payal A,Rai C S,Reddy B V R.Artificial neural networks for developing localization framework in wireless sensor networks:data mining and intelligent computing[C]//Proc of ICDMIC.[s.l.]:IEEE,2014:1-6.

[17] 袁凌云,王兴超.基于路径和多指标向量的WSN性能评价方法研究[C]//Proceedings of 2009 conference on communication faculty.出版地不详：出版者不详，2009:588-594.

[18] Mininet[EB/OL].[2015-09-06].http://mininet.org/.

[19] 董 青.sFlow统计数据在FloodLight控制器中的使用[EB/OL].[2013-01-17].http://blog.sina.com.cn/s/blog_3f2db1dc01015ah9.html.

[20] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review,2008,38(4):63-74.

Research on Load Balancing Routing Strategy Based on Link Multi-index Evaluation System

NI Xiao-jun,DUAN Yuan-xin,ZHANG Yun,ZHANG Min-min

(College of Computer,College of Software,Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

The underutilization of network resources is low,which resulted from the absence of a complete load-balancing solution in OpenFlow network.In this paper,a dynamic load balancing routing strategy for data flows is proposed and implemented on the controller of OpenFlow network,utilizing the centralized controlling advantages of controllers in OpenFlow network.The strategy could develop a dynamic data flows forwarding policy based on network condition information:the multi-index comprehensive evaluations of links served as the new weights which are applied in calculations of the best path between the source node and the destination node;sequentially the data flows would be forwarded on the best path at all times.At last,the Mininet simulation technology is used in verifying the performance of the proposed load-balancing routing strategy in this paper.The results show that the proposed load-balancing routing strategy can effectively alleviate the congestion of networks and improve the utilization of links.

OpenFlow;load balancing;multi-index;routing algorithm

2015-09-18

2015-12-22

时间：2016-05-25

国家自然科学基金资助项目(61472192)

倪晓军(1969-)，男，硕士，副教授，研究方向为嵌入式系统的设计、实现及其在通信领域中的应用，嵌入式系统在无线传感器网络领域的技术及应用等；段元新(1989-)，女，硕士生，研究方向为软件定义网络、网络性能分析等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1711.062.html

TP393

A

1673-629X(2016)06-0046-05

10.3969/j.issn.1673-629X.2016.06.010