基于SDN的胖树数据中心网络多路径路由算法

彭大芹,,

(重庆邮电大学 通信与信息工程学院,重庆 400065)

0 概述

近年来,大数据、云计算等互联网应用发展迅速,这些新型应用使数据中心内部通信量加倍地增长,带来的问题是数据中心网络内部带宽已经不能满足流量的传输需求[1-2]。为解决该问题,新型数据中心网络通常采用分层的多根网络拓扑,如胖树网络拓扑。这种拓扑使网络更容易扩展,同时也具有多路径路由的特性[3-4]。针对数据中心网络多路径路由问题,比较经典的是基于哈希的ECMP算法,该算法在数量上将数据流均匀地哈希到多条等价路径上[5]。ECMP能够利用树形网络拓扑的冗余链路,实现数据的快速转发,但该算法没有考虑链路实时传输状态及网络流量特征。文献[6]研究发现,数据中心网络流量中90%的数据流持续时间不超过10 s,大小不超过100 KB,而大于100 KB的数据流占总流量大小的90%。因此,ECMP算法可能将多条大数据流散列到同一条链路上,造成网络拥塞。

软件定义网络(Software Definod Network,SDN)是近年提出的一种新型网络技术,其核心思想是将网络的控制平面与数据平面分离,并实现可编程的集中控制。目前,国内外越来越多的研究者专注于利用SDN具有全网视图的特性来解决新型数据中心网络的多路径路由问题,并提出很多改进的路由算法。文献[7]提出一种动态分布式流调度(DDFS)机制,该机制综合分析不同层次交换机的流量调度问题,在一定程度上能够提高核心交换机的交换能力和网络链路利用率。文献[8]提出一种SHR路由机制,该机制使用控制器对网络中的大流进行调度,而将小流的处理权交给交换机。仿真结果表明,该机制改善了吞吐量和流丢弃率等网络性能,但链路利用率并不高。文献[9]中Hedera对大流采用模拟退火算法进行路由,而对小数据流仍然使用ECMP算法进行选路。结果表明该策略仅在ECMP算法的基础上将链路利用率提高了1%～5%,效果并不明显。文献[10]提出的PROBE算法利用类似路由追踪的方式来实现流量细粒度控制。经验证该方法具有一定可行性。

综上所述,针对ECMP算法的缺点以及现有路由算法没有综合考虑链路实时传输状态和流量特征的问题,本文提出一种基于链路实时状态和流量特征的多路径路由(MLF)算法,该算法根据数据中心网络流量特征,将数据流分为大流和小流,并对不同大小的数据流使用不同的路由方式。

1 路由方案设计

路由方案的总体框架如图1所示。其中,胖树拓扑的数据中心网络由支持OpenFlow协议的SDN交换机构建;同时,为了实现提出的MLF算法,本文在Floodlight控制器内设计了信息统计模块、数据存储模块、路径计算模块和流表下发模块,这些模块是完成数据中心网络流量路由的核心功能模块。其中,信息统计模块完成链路状态信息和流信息的收集,主要包括实时链路带宽信息和大流信息;数据存储模块负责存储收集的链路带宽信息和大流信息,并提供相关接口,便于控制器其他模块访问和修改;路径计算模块采用MLF算法为数据流计算路由策略;流表下发模块将路径计算模块计算好的路由策略以流表的形式下发到路径上的各个交换机中,完成数据流的转发。

图1 路由方案总体框架

1.1 网络状态信息收集

本节由信息统计模块完成,包括对网络中链路带宽和大流信息的统计收集。

1)链路带宽信息

Floodlight控制器提供了用于统计交换机各端口带宽信息(即链路带宽信息)的IstatisticsService接口,因此,信息统计模块只需调用该接口即可。对于统计间隔,文献[11]通过实验发现1 s的统计间隔在平均链路利用率上要比5 s的统计间隔更高,本文沿用了这种思想,将链路带宽信息的统计间隔设定为1 s。鉴于胖树拓扑结构特点,信息统计模块只需对汇聚层交换机的端口带宽信息进行统计,具体为调用控制器中进程池(ThreadPool)模块提供的线程,以周期为1 s获取交换机各端口带宽信息,包括发送和接收的总字节数,并将信息发送给数据存储模块进行存储。图2为实验测试过程中打印的由信息统计模块统计的部分交换机端口带宽信息,包括交换机DPID、端口id和端口传输带宽等字段信息,由端口带宽信息便可获得链路带宽信息。

图2 端口带宽信息

2)大流信息

根据数据中心网络流量特征,本文将超过100 KB大小的数据流定义为大流。对于流信息统计,通常的做法是由控制器周期性地向边缘层交换机发送flow_stats_request流统计请求消息,以此获取数据流的精确统计信息。然而,过多的请求响应消息一方面会消耗大量的交换机资源和链路带宽资源,造成网络拥塞,另一方面也会增加控制器的处理时延,造成控制器负担过重[12]。文献[13]的研究发现,生成数据包的服务器主机对应用程序的发包速率感知性更强,检测大流较好的方式是在服务器主机进行。因此,本文使用服务器主机完成对大流信息的统计,当服务器主机发送缓冲区内同一五元组的数据包总大小超过100 KB时,该流便被标记为大流,然后将标识流的五元组和速率等信息通过交换机发送到控制器的信息统计模块。

信息统计模块收集到链路带宽信息和大流信息后,将它们发送到数据存储模块以Java HashMap结构形式存储在NoSQL内存数据库中。对于链路带宽信息,存储区只保存最近统计间隔内的数据,并进行周期性更新;对于大流信息,如果该流已经完成转发,则删除在数据库中的相关信息以释放内存空间,否则继续保留。

1.2 路由算法实现

1.2.1 核心思想

基于链路实时状态和流量特征的多路径路由算法在设计时,重点对不同大小的数据流使用了不同的选路策略。其主要思想如下:

1)大流选路

为了提高大流吞吐量和避免链路拥塞,对于大流,根据最新统计的链路剩余带宽计算出每条路径的权重值,使用哈希算法对流的五元组进行哈希得到哈希值,哈希值对路径权重值的总和取余,根据余数落在路径权重值之间的位置决定使用哪条路径进行路由。具体为:假设网络中有n条小数据流,用F={f1,f2,…,fn}表示,对应每条数据流的请求带宽设为vj,其中j∈{1,2,…,n}。根据k元胖树拓扑结构特点,不同pod下的2台服务器之间共有k条等价路径,设为{p1,p2,…,pk},每条路径有k条链路,并且各交换机之间的链路默认容量是一样的。为避免链路拥塞,本文取链路容量的80%作为拥塞阈值,设为bth。令bmi表示第m条路径第i条链路的已传输带宽,其中i,m∈{1,2,…,k},该带宽信息可直接从数据库中读取。这里需要说明的是,根据k元胖树拓扑结构特点可知,不同Pod连接的每2个服务器之间总共有k条可用路径,而每一条路径总共有k条链路。因此,第m条路径的可用带宽为该路径上k条链路中最小的链路可用带宽,设为bm,表示为:

(1)

定义wm为第m条路径的路径权重,则wm的值即为第m条路径的可用带宽占所有路径可用带宽之和的比值,表示为:

(2)

其中,c为常数,bm和bi分别代表第m条和第i条路径的可用带宽,δ函数用于判断数据流的请求带宽是否大于某条路径的可用带宽。如果大于,则取值为0,表示放弃该条路径;如果小于,则将其加入到可用路径中。δm和δi分别用于判断第m条和第i条路径的可用带宽是否满足数据流的请求带宽。δ函数表示为:

(3)

其中,vj表示第j条数据流的请求带宽。

假设最后得出新的可用路径为k1条,由式(2)可知这k1条路径的权重值之和为c。根据路径权重值为这n条流选择路由路径,具体为:使用流的五元组信息作为哈希算法的输入,将得出的哈希值对c进行取余,取余后的值范围是{0,1,…,c-1},判断求得的余数落在{0～w1,w1～w2,w2～w3,…,wk1-1～wk1}范围内的位置,选择对应的路径;假设落在w1～w2范围内时,则选择w2所在的路径作为路由路径,以此类推。

2)小流选路

根据小流数目多、对时延敏感等特点,同时也为了使小流能够快速转发,本文降低了对小流处理的复杂性,对小流一律采用基于路径可用剩余带宽最大的原则进行选路,即选用式(1)中bm最大的路径。

路由算法流程如图3所示。

图3 路由算法流程

1.2.2 算法实现

路由算法实现部分由路径计算模块完成。控制器默认使用的路由算法为常见的最短路径算法——Dijkstra算法,其主要思想是将网络拓扑图转化为带权有向图G=(V,E),其中,V为网络节点集合,E为连接节点与节点之间边的集合。将顶点V划分为2个集合,第1集合是已求出到源节点的最短路径的目的节点的集合S,第3集合是其他没有确定最短路径的目的节点的集合U,然后依照链路权重值将集合U中的顶点逐渐依次添加到集合S中。针对数据中心网络流量大而密集的特点,该算法容易造成链路拥塞,也不能解决负载均衡问题。

MLF算法的具体步骤如下:

步骤1路由计算模块调用processPacketInMessage()方法对Packet-In数据包进行解析,解析出数据包的IP五元组信息,然后根据防火墙模块的转发规则表判断源目的主机是否可以通信,如果不可以则丢弃;否则继续步骤2。

步骤2检查数据包是否为广播包,如果是则调用doFlood()方法进行广播处理;否则继续步骤3。

步骤3判断数据包的源目的主机是否属于同一网段,即为同一边缘层交换机下的2台主机,如果是则直接进行二层转发;否则继续步骤4。

步骤4读取数据库中的统计信息判断该流是否为大流,如果是则继续步骤5;否则选择可用剩余带宽最大的路径进行转发并跳转到步骤7。

步骤5根据流的请求速率筛选出源目的主机之间的所有可用路径,调用caculateRouteWeight()方法计算每条路径的路径权重值。

步骤6调用hash()方法对流的五元组进行哈希运算,将得到的哈希值对权重值之和取余,根据余值和权重值范围选择路由路径。

步骤7调用pushRoute()方法将路由策略推送到该路径上的所有交换机上。

2 实验与结果分析

2.1 仿真环境设置

采用Mininet[14]网络仿真器和Floodlight控制器搭建实验仿真平台。Mininet是一款强大的网络仿真工具,利用它可以构建包括交换机、链路和主机在内的数据中心网络,同时还支持使用OpenFlow协议与Floodlight控制器相连接。受条件限制,本文只构建了4个Pod来模拟胖树拓扑的数据中心网络场景,如图4所示,包括20台OpenFlow交换机与16台服务器。网络中所有节点之间的链路均设置为全双工链路,并将链路带宽设定为1 Gb/s。使用Iperf[15]工具产生模拟的数据中心网络流量,令主机H1～H8同时向主机H9～H16发送数据流量。根据数据中心网络的流量特征,假设发送的流量中90%的流大小为0 KB～100 KB,10%的流大小大于100 KB,且所有的数据流都服从均匀分布[16]。

图4 网络拓扑场景

2.2 结果分析

本文选取平均链路利用率、网络吞吐量作为性能评价指标,与ECMP算法和SHR机制进行对比,验证MLF算法的性能优势。此外,还在MLF算法的基础上对比区分大小流的选路策略对网络吞吐量的影响。平均链路利用率为网络拓扑中所有链路的平均值,用η(t)表示,用式(4)表示为:

(4)

其中,由上文可知,bmi(t)表示第m条路径第i条链路在t时刻的已传输带宽,可通过信息统计模块得出,N为链路的总条数,BMAX表示链路的默认带宽。对于网络吞吐量,Iperf可以直接测量出端到端的吞吐量,进而可以计算出整个网络的吞吐量。

图5分别采用ECMP、SHR和MLF进行路由的平均链路利用率仿真对比。仿真结果表明,由于ECMP在路由时没有将网络的实时链路状态和数据流的大小考虑在内,仅在数量上将数据流均匀分配到各条等价路径上,导致链路带宽分配不均匀,增加了链路拥塞的可能性,因此它的平均链路利用率要低于MLF和SHR。此外,从图5可以看出,开始时MLF和SHR的平均链路利用率相差不大,但30 s以后,MLF要明显高于SHR。这是因为SHR中是按链路默认带宽比为小流进行选路,没有考虑流量传输后路径上的实时负载情况,这容易造成某条路径上的流量负载过重,导致网络拥塞而降低网络链路利用率。而MLF算法对大流和小流的选路都考虑了链路的实时负载,因而性能要优于SHR。

图5 平均链路利用率对比

图6为网络吞吐量的性能对比。从图6可以看出,当发包速率低于500 Mb/s,由于MLF和SHR中交换机和控制器之间需要频繁发送用于统计链路状态的请求回复信息,而这需要占据一定的传输带宽,因此,它们的网络吞吐量要比ECMP略低。当发包速率超过500 Mb/s时,ECMP的吞吐量要比MLF和SHR低得多,这是由于ECMP静态的散列方式可能将多条大流映射到同一路径上,导致网络拥塞,造成数据流的丢弃,从而影响整个网络的吞吐量,而MLF和SHR根据网络负载的动态变化对流进行选路,在一定程度上提高了网络的吞吐量;此外,MLF的吞吐量要比SHR高,这是因为SHR是通过控制器周期性地发送流统计消息完成对大流的区分,增加了控制器与交换机的通信开销,而MLF是由服务器主机将大流信息上报至控制器,减少了这部分开销。

图6 网络吞吐量对比

为了研究将数据流区分大小进行选路对网络吞吐量的影响,本文在MLF算法上进行了分析比较。具体为不区分大小流与区分大小流,不区分大小流的做法是将所有的数据流按照MLF算法中小流的处理方式进行选路,得出的性能对比如图7所示。从图7中可以看出,开始时两者的性能曲线非常相似,当发包速率超过550 Mb/s时,不区分大小流的网络出现拥塞,链路不能得到有效利用,吞吐量要明显低于区分大小流的选路策略,这是因为不区分大小流的方式可能将很多条大流放在单一路径上传输,造成网络阻塞而影响网络吞吐量。因此,与不区分大小流相比,区分大小流的选路策略能更好地改善网络性能。

图7 区分大小流对网络吞吐量的影响

3 结束语

本文针对SDN架构下的胖树数据中心网络多路径路由问题,提出一种基于链路实时状态和流量特征的多路径路由算法。该算法将数据流分为大流和小流,并对不同大小的数据流使用不同的路由方式。设计算法功能实现的总体框架,给出算法设计思想和算法实现步骤,最后在仿真平台上对算法进行了验证,结果表明,与ECMP算法和SHR路由机制相比,MLF算法能够提高胖树数据中心网络的平均链路利用率和网络吞吐量。另外,本文还验证了区分大小流的路由策略比不区分大小流的路由策略具有更高的网络吞吐量。MLF算法仅对k=4的胖树网络拓扑进行了验证,而未考虑节点数更多的情况;此外,算法也未对其他方面的性能进行分析,如时延等,这是下一阶段的主要工作。

[1] 中国互联网信息中心.第37次中国互联网络发展状态统计报告[EB/OL].[2016-01-31].http://www.cnnic.cn.

[2] GANG D,GONG Z,HONG W.Characteristics research on modern data center network[J].Journal of Computer Research & Development,2014,51(2):395-407.

[3] DALVANDI A,GURUSAMY M,CJUA K C.Application scheduling,placement,and routing for power efficiency in cloud data centers[J].IEEE Transactions on Parallel & Distributed Systems,2017,28(4):947-960.

[4] LEI Y C,WANG K,HSU Y H.Multipath routing in SDN-based data center networks[C]//Proceedings of European Conference on Networks and Communications.Washington D.C.,USA:IEEE Press,2015:365-369.

[5] HOPPS C E.Analysis of an equal-cost multipath algorithm[J].Journal of Allergy & Clinical Immunology,2000,109(1):265.

[6] BENSON T,AKELLA A,MALTZ D A.Network traffic characteristics of data centers in the wild[C]//Proceeding of ACM SIGCOMM Conference on Internet Measurement.New York,USA:ACM Press,2010:114-115.

[7] BHARTI S,PATTANAIK K K.Dynamic distributed flow scheduling with load balancing for data center networks[C]//Proceedings of the 4th International Conference on Ambient Systems,Networks and Tech-nologies.Washington D.C.,USA:IEEE Press,2013:124-130.

[8] 蔡岳平,王昌平.软件定义数据中心网络混合路由机制[J].通信学报,2016,37(4):44-52.

[9] Al-FARES M,RADHAKRISHNAN S,RAGHAVAN B,et al.Hedera:dynamic flow scheduling for data center networks[C]//Proceedings of USENIX Conference on Networked Systems Design and Implementation.[S.1.]:USENIX Association,2010:19-19.

[10] XI Kang,LIU Yulei,CHAO H J.Enabling flow-based routing control in data center networks using probe and ECMP[C]//Proceedings of Computer Communica-tions Workshops.Orlando,USA:IEEE Press,2011:608-613.

[11] CURTIS A R,MOGUL J C,TOURRILHES J,et al.DevoFlow:scaling flow management for high-performance networks[C]//Proceedings of ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications.Toronto,Canada:[s.n.],2011:254-265.

[12] 李 龙,付斌章,陈明宇,等.Nimble:一种适用于OpenFlow网络的快速流调度策略[J].计算机学报,2015,38(5):1056-1068.

[13] CURTIS A R,KIM W,YALAGANDULA P.Mahout:low-overhead datacenter traffic management using end-host-based elephant detection[C]//Proceedings of IEEE INFOCOM’11.Washington D.C.,USA:IEEE Press,2011:1629-1637.

[14] TEAM M.Mininet:An instant virtual network on your laptop[EB/OL].[2016-10-21].http://www.mininet.org/.

[15] 张 白,宋安军.基于Iperf的网络性能测量研究[J].电脑知识与技术,2009,36(5):10227-10229.

[16] ZAHAVI E,KESLASSY I,Kolodny A.Distributed adaptive routing convergence to non-blocking DCN routing assignments[J].IEEE Journal on Selected Areas in Communications,2014,32(1):88-101.