![](https://csdnimg.cn/release/download_crawler_static/18270415/bg1.jpg)
收稿日期:20181119;修回日期:20190122 基金项目:安徽省自然科学基金资助项目(1408085MF125)
作者简介:王红运(1993),男,安徽六安人,硕士研究生,主要研究方向为软件定义网络(e17201006@stu.ahu.edu.cn);束永安(1966),男,教
授,主要研究方向为无线网络、下一代网络体系结构.
数据中心网络中基于蚁群算法的动态多路径负载均衡
王红运,束永安
(安徽大学 计算机科学与技术学院,合肥 230601)
摘 要:针对数据中心网络中等价多路径路由算法(equalcostmultipathrouting,ECMP)无法有效调度大象流而
导致流量负载不均衡及易造成网络拥塞的问题,提出了一种基于蚁群算法的动态多路径负载均衡(antcolonyal
gorithmbaseddynamicmultipathloadbalancing,ADMLB)算法。ADMLB算法首先通过控制器获取网络负载信息,
同时检测大象流并标记,然后调用改进蚁群算法,根据大象流所需带宽选择多路径。实验结果表明,与传统 EC
MP和现有流调度算法相比,ADMLB算法降低了链路延迟时间,有效提高了链路带宽利用率。
关键词:数据中心网络;软件定义网络;负载均衡;蚁群算法
中图分类号:TP393 文献标志码:A 文章编号:10013695(2020)07047214803
doi:10.19734/j.issn.10013695.2018.11.0945
DynamicmultipathloadbalancingbasedonantcolonyalgorithminDCN
WangHongyun,ShuYong’an
(CollegeofComputerScience&Technology,AnhuiUniversity,Hefei230601,China)
Abstract:ThetraditionalECMPalgorithm cannoteffectivelyscheduleelephantflowsthatmaycauseloadunbalancingand
networkcongestionindatacenternetworks.Forthisproblem
,thispaperproposedanADMLBalgorithm.Firstly,thecontroller
obtainedtheloadinformationofeachswitchesandlinks,detectedandmarkedtheelephantflowsintheendhost.Then,itcalled
theimprovedantcolonyalgorithm tosolvethemultipathproblemsaccordingtothebandwidthrequirementsoftheelephant
flows.Finally
,itscheduledtheelephantflow.TheexperimentalresultsshowthattheADMLBalgorithmreducesthelinkdelay
andeffectivelyimprovesthelinkbandwidthutilizationcomparedwiththetraditionalECMPandotherexistingalgorithms.
Keywords:datacenternetwork(DCN);softwaredefinednetwork(SDN);loadbalancing;antcolonyalgorithm
软件定义网络(SDN)作为一种新兴的网络架构,将控制层
与数据层分离,能够通过网络全局信息,对网络进行统一部署
和集中控制
[1]
。目前 SDN架构被广泛地应用于数据中心网络
(
DCN)。数据中心网络中数据流主要有时延敏感的老鼠流和
高带宽需求的大象流两种类型。虽然大象流的数量只占
DCN
全部流的 10%,却占用了 80%的带宽资源。研究发现,在交换
机发送端口大象流的出现往往会阻塞老鼠流,造成老鼠流长时
间队列延迟
[2]
。目前大型 DCN中多采用具有多条等价路径的
Clos拓扑结构(如 FatTree
[3]
、FoldedClos
[4]
等),在 DCN中同一
源节点与目的节点对之间存在着大量可用的带宽资源。因此,
基于 SDN架构对网络集中管控的思想,综合全局视图能够实现
DCN链路动态负载均衡,有效解决多路径路由的问题,减少链
路拥塞
[5]
。
目前被广泛应用于 DCN中的等价多路径(ECMP)
[6]
负载
均衡算法是一种较为简单的负载均衡策略。ECMP算法只是
通过哈希散列的方式将流分发到不同的路径上。由于老鼠流
与大象流的持续时间不同,
ECMP算法虽然能够有效地调度老
鼠流,但对于大象流则可能会将多条大象流调度到同一路径
上,发生哈希碰撞,加剧网络拥塞。因此,对大象流进行有效的
路由算法设计,能够实现 DCN的负载均衡,降低网络发生拥塞
的可能,同时提高带宽利用率。本文提出的基于蚁群算法的动
态多路径(ADMLB)算法利用 SDN控制器实时监测 DCN中链
路以及节点负载状态,并通过调用改进蚁群算法对大象流进行
调度,为大象流分配多条最佳路径。因此,ADMLB算法能够解
决网络拥塞控制问题,提高了网络资源的利用率,实现 DCN流
量的负载均衡。
1 相关工作
文献[7]中提出 LABERIO算法第一次引入基于 SDN的动
态路径优化算法来均衡链路负载。LABERIO根据 DCN中当
前可用的链路带宽,选择最优路径,使其可用带宽在所有可能
路径中最大。但如果网络拓扑发生变化,那么 LABERIO算法
也必须进行修改。另外,由于
LABERIO仅在其触发路径优化
算法时才考虑链路负载的瞬时值,所以它可能会在短时间内受
到极值的影响。Hedera
[8]
和 Mahout
[9]
都是 DCN中的动态流调
度方案。这两种方案首先检测大象流,然后利用 SDN对网络
统一管控的能力获取网络状态,控制器通过全局决策,对 DCN
中的大象流进行调度。Hedera和 Mahout解决了 ECMP不能有
效均衡大象流,甚至发生哈希碰撞,加剧网络拥塞的问题。
He
drea通过边缘交换机周期性收集流的信息检测大象流,然而这
样却增加了边缘交换机的负载。为了避免给交换机造成额外
负担,Mahout提出在终端主机上检测大象流,当流的大小超出
设定阈值时,将其标记为大象流。但是
Hedrea与 Mahout在选
择最优路径时,都没有将节点的缓存能力综合考虑在内,如果
路径上节点可用缓存过小,则会造成丢包率升高。
一些工作中提出将大流分割为小流进行路由的方案,如
LetFlow
[10]
与 Hermes
[11]
等是基于可分流的子流路由的负载均
衡方案,虽然可以通过细粒度的流量控制实现更好的负载均
衡,但并不适用于所有情况,限制了方案的适用性。Presto
[12]
以固定的粒度大小分割流量,没有考虑路径条件,而并行路径
上的最佳流量分配需要综合考虑流量需求以及路径条件,因此
缺少路径条件可能无法作出最佳决策
[10]
。同时,由于它们需
第 37卷第 7期
2020年 7月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No7
Jul.2020