软件定义数据中心网络多约束节能路由算法

何荣希 雷田颖 林子薇

(大连海事大学信息科学技术学院 辽宁大连 116026)

摘 要 数据中心网络的节能路由算法大体可分为流量感知和拓扑感知两大类. 前者性能的好坏很大程度取决于流量矩阵预判的准确性. 由于实际网络流量动态、随机产生,具有突发性,预判流量矩阵不一定与网络实时流量状态相符,因此,这类算法往往难以保证突发流的可靠传输. 而后者在休眠冗余设备时,仅从保证网络拓扑具有某种程度的连通性出发,并未考虑网络负载情况,可能导致低负载时设备空闲率较高,节能效果有限. 为此,针对fat-tree拓扑的软件定义数据中心网络(software-defined data center network, SDCN),将网络流量因素引入拓扑感知节能路由机制,提出等效节点、最小网络连通子集、孤岛交换机、无效链路等概念以及辅助图模型和SDCN连通条件,给出多约束节能路由优化模型,同时还提出一种多约束节能路由算法(multi-constrained energy-saving routing, MER). MER算法在保证数据流的时延和可靠性要求前提下,尽可能多地休眠冗余交换机和链路,以降低网络能耗. 最后,通过Mininet和Floodlight进行仿真测试. 仿真结果表明:与文献中已有算法相比,MER具有更低的平均分组时延和丢包率,并且可以达到理想的节能效果.

关键词 软件定义网络;数据中心网络;节能路由;拓扑感知;流量感知

作为分布式存储和计算的桥梁,数据中心网络(data center network, DCN)的性能直接影响云计算、大数据等业务的发展[1-2].DCN最初采用传统树型拓扑,存在可扩展性差、部署代价高以及严重的单点失效等问题.近年来,出现了诸如fat-tree等新型拓扑结构,通过使用数量巨大的网络资源来提高网络性能和可靠性[3-4].但是,这些拓扑仍属于分布式网络控制模式,依然存在管理困难、资源利用率低等问题.基于OpenFlow[5]的软件定义网络(software defined network, SDN),将控制平面与数据平面解耦合,支持集中化的网络控制,能实现底层网络设施对上层应用的透明.与传统网络相比,它具有灵活、开放、简单等特点,而且可以获得全网视图和网络状态信息[6].因此,SDN与DCN相结合的软件定义数据中心网络(software-defined data center network, SDCN),可以实现网络自动部署、流量优化、故障自动探测和恢复,并支持多租户以及虚拟机迁移等,从而克服了分布式网络控制模式下的诸多难题[7].

随着能源短缺等问题日益严重,节能减排已成为社会发展面临的重大课题[8-9].基于fat-tree拓扑的新型DCN使网络中出现“富连接”链路,虽然避免了单点故障等问题的发生,但是引入过多网络设备会增加网络能耗,不利于实现绿色节能.另外,DCN往往按照峰值流量需求进行资源部署[10],而多数情况下网络流量都远低于其峰值需求.因此,DCN中很多设备将处于空闲状态,导致网络资源整体利用率较低.如果让这些空闲设备一直处于激活状态,无疑会造成能源浪费.据统计,从全球范围来看,预计2020年全球数据中心(data center, DC)消耗的电量将占总耗电量的8%[11].由于DC消耗了巨大的能量,因此,近年来DC的节能问题已逐渐成为研究热点.由于网络部分的能耗占DC总能耗的20%左右,并且随着硬件技术的发展,比重会进一步提高[9].因此,很有必要研究DCN网络级节能机制.

作为DCN中一种引起广泛关注的网络级节能机制,节能路由的关键是如何合理选择路径,在保障网络性能的前提下使用尽可能少的网络设备承载流量,从而休眠更多空闲设备以降低网络能耗[12].近年来,不少文献[13-17]都对SDCN的节能路由进行讨论.文献[13]提出基于流量的弹性树(elastic tree)算法,依据实时流量监测信息,通过最优化算法、贪婪算法和启发式算法求解最优路径,并尽可能多休眠空闲设备实现节能.文献[14]提出一种基于网络流量矩阵的节能路由算法,可根据预判的流量矩阵在节点对间建立路径,以休眠尽可能多的网络设备.文献[15-16]从负载均衡的角度出发,分别提出PRA算法和IEER算法.二者基本思想一致,都是通过预设一个固定的可靠性参数,并根据该参数休眠网络冗余资源,可在节能的同时提供一定的可靠性保障.文献[17]将流量工程(traffic engineering, TE)与SDN结合,依据网络流量选择最优拓扑子集,并休眠该子集外的网络设备以节能.

总的说来,上述方案本质上均是基于流量预判的节能方案,需要预先知道网络流量,并依据节点对间的流量来选路和休眠冗余资源,属于流量感知(traffic-aware)节能路由.其优点在于网络负载较低时可休眠更多冗余设备,节能效果明显.但是,该类算法性能的好坏,很大程度上取决于流量矩阵预判的准确性.然而,对于实际网络而言,由于数据流量动态、随机产生,往往具有突发性,因此,预判流量矩阵并不一定与网络实时流量状态相符,流量感知节能路由机制可能会出现过度休眠(休眠设备过多),从而导致未包含在流量矩阵中节点对间的数据流无可用资源建立路径,从而造成丢包.另外,即使对于流量矩阵中存在的数据流,网络出现故障时也可能出现无冗余资源传输而丢包,很难保证数据的可靠传输.

为了避免上述流量感知节能路由方案对预判流量矩阵的依赖,文献[18]针对传统互联网提出一种拓扑感知(topology-aware)节能路由算法.该算法不以流量作为考虑对象,而是基于“代数连通度”[19-20]概念,在保证网络中所有节点全连通基础上,通过计算每条链路对网络代数连通度影响的大小,按照影响大小递增顺序休眠冗余链路实现节能.该算法在传统互联网中节能效果较为明显,但是,对于采用fat-tree拓扑、具有“富连接”特点的SDCN,其节能效果有限(具体分析见2.2节).文献[21]针对fat-tree拓扑的特点,提出独立路径集(能够独立满足全网主机连线需求的路径集合)概念,并以最小独立路径集为单位,休眠空闲设备以节能.该算法也属于拓扑感知节能路由算法,当网络规模较大时,由于最小独立路径集仍包含大量核心层交换机,因此,网络中激活设备的冗余度较高,从而影响了算法的节能效果(具体分析见2.2节).

与流量感知节能路由算法不同,拓扑感知节能路由算法都是从保证网络拓扑具有一定程度的连通性出发,通过休眠冗余设备以节能.由于该类算法保证了休眠冗余设备后的网络仍具有一定连通性,因此,与流量感知机制相比可以较好地解决网络中出现突发流量时冗余资源过少导致的丢包率增加问题.但是,这类算法在判定是否休眠设备时仅从保证网络拓扑具有一定程度的连通度出发,并未考虑网络负载的高低,因此,在低负载时其设备空闲率仍然过高,导致其节能效果有限.

通过分析流量感知和拓扑感知2类节能路由方案[13-18,21]的优缺点,本文结合二者各自的优势,将网络流量因素引入拓扑感知节能路由机制,针对SDCN提出一种考虑时延和可靠性要求的多约束节能路由(multi-constrained energy-saving routing, MER)算法.该算法利用SDN控制器掌控全网信息的优势,综合考虑数据流的可靠性和时延性能要求,利用辅助图和SDCN连通条件,选择源、目的节点间综合代价最小的路径来传输数据流,通过合理休眠网络资源以实现节能.仿真结果表明:与已有算法相比,MER算法在节能的同时,具有更低的平均分组时延和丢包率.

本文的主要贡献有3个方面:

1) 结合流量感知和拓扑感知2类节能路由算法的优势,在拓扑感知节能路由机制中引入网络流量因素,综合分析SDCN的连通性、时延等因素对节能路由的影响,提出一种考虑时延和可靠性要求的多约束节能路由优化模型.

2) 针对fat-tree拓扑SDCN的结构特点,提出等效节点、最小网络连通子集、孤岛交换机、无效链路等概念和辅助图模型,给出SDCN连通条件.

3) 基于辅助图模型、SDCN连通条件,提出一种启发式算法MER,并进行仿真评测.

1 多约束节能路由模型

基于fat-tree拓扑的SDCN由交换机、服务器以及连接它们的双向链路构成.SDCN多约束节能路由的目标就是在源和目的节点之间选择合适的路径,在保证数据可靠传输和时延要求前提下,尽可能多地休眠网络设备.由于服务器是数据流的源和目的节点,而服务器直接与边缘层交换机相连.为了保证数据正常通信,服务器、边缘层交换机以及连接它们的链路必须一直处于激活状态.因此,SDCN多约束节能路由问题实际上就是要在分别与源和目的服务器直接相连的边缘层交换机之间选择满足传输可靠性和时延要求的能耗最低路径.为此,将SDCN中由交换机及其连接链路构成的网络子集记为初始网络G0=(N,H,L),G0从上至下可分为核心层、汇聚层和边缘层,其中N=CAE,表示所有交换机构成的节点集合,交换机(节点)数为|N|.CAE分别为核心层、汇聚层和边缘层交换机的集合,CA=CE=AE=∅,各个集合包含交换机数分别为|C|,|A|,|E|.H表示服务器集合,服务器数为|H|.L表示连接各个交换机节点的双向链路(边)的集合,链路数为|L|.如果2个节点之间存在双向边,则称2节点相连接,否则表示其未连接.G0的邻接矩阵、度矩阵和拉普拉斯矩阵分别表示为拓扑将汇聚层交换机和边缘层交换机分为若干集合,每一个集合称为1个PoD(point of delivery)[4].对于有k个PoD的fat-tree拓扑,G0中|N|=(5k24),|C|=(k2)2,|A|=k22,|E|=k22,|L|=k32,|H|=k34,如图1所示.图1中,每一个PoD含有k个交换机(汇聚层和边缘层交换机各k2个).将核心层交换机依次排列,则每k2个交换机为1组,共k2组,每1组连接不同PoD中同一位置的汇聚层交换机.

Fig. 1 SDCN topology with k PoDs
图1 具有k个PoD的SDCN

为了更好地描述多约束节能路由模型,引入以下变量,如表1所示:

Table 1 Explanations of Variables
表1 变量含义

VariablesExplanationsGA feasible subset of G0,G⊆G0G+Set of all feasible subsets of G0,G0⊆G+G∗Optimum subsets of G+,G∗⊆G+L(G)Number of links in G,L(G)≤|L|S(G)Number of switches in G,S(G)≤|N|λ(G)Algebraic connectivity of Gli,sjLink i and switch j in G0,li∈L,sj∈NeiEnergy consumption of lihjEnergy consumption of sjrA feasible route path in GdmaxUpper bound of delay in rθminLower bound of algebraic connectivity in GdiDelay of lidrDelay of r,dr=∑di, li∈r

本文基于Powerdown的设备能耗模型[22],假设交换机和链路存在工作和休眠2种能耗状态.与工作状态相比,休眠状态耗能很小.因此,节能路由就是尽可能选择休眠更多冗余设备的路径,也就是用尽可能少的网络资源(交换机、链路等)来保证边缘层交换机间正常通信,从而保证服务器间的正常通信.为了保证突发数据流的可靠传输,应避免在负载较低时休眠过多的网络设备,即要保证网络具有一定的冗余度,从而保证网络的最低连通性,以满足突发通信流的传输要求.

为了更好地对多约束节能模型描述,引入5个定义.

定义1. 代数连通度[19-20](algebraic connectivity).求网络G0的拉普拉斯矩阵的特征值,得到n个特征值λ1,λ2,…,λn,其中0≤λ1λ2≤…≤λn.定义λ(G0)=λ2G0的代数连通度,它反映了G0的连通状况,其值越大,网络连通性越好,可靠性越高.

定义2. 最小网络连通子集.在G0中,如果只有一个核心层交换机,每一个PoD中只有一个汇聚层交换机,并均与该核心层交换机相连接,而且每一个汇聚层交换机又与该PoD中所有边缘层交换机相连接,则称该网络子集为最小网络连通子集.由fat-tree拓扑的特点可知,它包含|C|个最小网络连通子集,而且每个最小网络连通子集的代数连通度相同.显然,当网络子集至少包含一个最小连通子集时,网络中所有服务器间均可正常通信.

多约束节能路由问题的输入参数可表示为一个三元组(G0,dmax,θmin),其目标就是从G0中源、目的服务器所连接边缘层交换机之间所有可行路径中找到一个最佳网络子集G*,在满足时延和可靠性约束条件下,使交换机和链路的总能耗最小,即:

(1)

s.t.

drdmax,∀rG,

(2)

λ(G)≥θmin.

(3)

式(2)要求G中任意一条可行路径的总时延dr不超过时延阈值dmax,从而保证了数据流的时延要求.式(3)要求G的代数连通度λ(G)不小于连通度阈值θmin,从而保证了网络的最低可靠性要求.

流量矩阵反映了网络中所有源、目的节点对间的流量需求,可反映网络负载情况[23-24].G0的流量矩阵Z可表示为一个主对角线元素为0的|H|×|H|矩阵,即:

(4)

为了结合拓扑感知和流量感知2类节能路由机制的优点,式(3)中θmin的取值除了要保证G中所有服务器间能正常通信外,还应结合网络的负载情况进行调整.网络负载越大,θmin取值相应增大,从而保证网络有较多冗余资源以接纳更多突发流,有利于降低丢包率.

θmin反映G0休眠冗余设备后网络拓扑G*的连通情况(λ(G*)≥θmin),其值应位于G0及其最小网络连通子集的代数连通度θ1θ0之间,即θ0<θmin<θ1,可表示为

θmin=θ0+α×|θ1-θ0

(5)

其中,α(0<α<1)为常数因子,其取值大小可反映网络可靠性要求的高低.当负载一定时,随着α增加,θmin越大,网络连通性越好,可靠性越高,相应地可休眠设备越少.但是,当α增加到一定程度后,θmin的值越来越接近θ1,此时能休眠设备越来越少.如果继续增加α,尽管θmin还可进一步逼近θ1,但是可休眠设备数量变化也不太明显.

另一方面,当α取定时,网络负载越低,θmin越小(更靠近θ0),可休眠设备越多,G*越接近一个最小网络连通子集.尽管此时网络冗余度较低,由于网络负载较低,突发流所导致丢包现象不会太严重.与之对应,网络负载越高,θmin取值越大,网络冗余度越大,越有利于减少突发流丢包.相应地,网络可靠性越高,能耗也会增加.可以通过减少α值来减少θmin,从而降低网络冗余度,以休眠更多设备.可见,通过合理调整α值,可在网络可靠性和节能效果之间进行取舍.

式(5)可实现将网络流量因素引入拓扑感知节能路由机制,从而可结合拓扑感知和流量感知路由算法各自的优势.在保证全网连通前提下,利用网络流量信息来动态调整θmin.低负载时,θmin较小,可以弥补拓扑感知节能算法低负载时设备空闲率过高、节能效果有限的不足.另一方面,网络休眠设备的多少与流量矩阵有关.而且α取值越大,θmin对流量矩阵的依赖程度越高.但是,不同于流量感知节能机制,它在休眠设备时首先要保证网络连通性(至少保留一个最小网络连通子集),而不是仅根据预判流量矩阵尽可能多地休眠冗余设备,无疑可降低出现过度休眠现象,减少流量矩阵预判不准所导致的丢包,有利于降低对流量预判准确性的依赖程度.

一旦初始网络G0给定,则θ1θ0都是定值.并且通过矩阵完成技术[25]等方法可估算出流量矩阵Z.而α为常数,因此,根据式(5)可求出θmin,也为一定值.

由于上述节能路由可以规约为背包问题,而背包问题属于NP难问题[26],所以SDCN的多约束节能路由问题也是一个NP难问题.当网络规模较大时,很难在多项式时间内求解.因此,本文提出辅助图模型和SDCN连通条件,在此基础上提出一种启发式算法——多约束节能路由(MER)算法.

2 多约束节能路由(MER)算法

2.1 辅助图模型

定义3. 等效节点.在基于fat-tree拓扑的SDCN中,每个低层交换机节点连接多个高层父节点,而这些父节点对于其子节点而言具有完全相同的转发功能,因此将同一个低层交换机节点连接的高层父节点称为等效节点.

对于图1所示具有k个PoD的SDCN,生成辅助图的步骤有3步.

步骤1. 获取任意一个最小网络连通子集,记为G01,如图2所示.

步骤2. 根据网络可靠性要求,为每一个PoD增加汇聚层交换机,并添加相应的核心层交换机,同时将添加的设备与G01中原有设备相连接,将此网络记为G02,如图3所示.

Fig. 2 Example of G01
图2 G01示意图

Fig. 3 Example of G02
图3 G02示意图

步骤3. 根据等效节点定义将G02中每一个PoD的汇聚层交换机和边缘层交换机视为一个整体,记为boundi(1≤ik);将boundi中边缘层交换机连接的所有服务器视为一个整体,记为serveri(1≤ik);将所有核心层交换机节点视为一个整体,记为core,得到SDCN辅助图,如图4所示.可见,具有k个PoD的SDCN辅助图由1个corekboundkserver构成.

Fig. 4 Auxiliary graph of SDCN with k PoDs
图4 具有k个PoD的SDCN辅助图

2.2 SDCN连通条件

文献[18]将“代数连通度”概念引入传统互联网,要求λ2>0以保证全网所有节点全连通.与传统互联网不同,基于fat-tree的SDCN具有“富连接”特点,存在很多为避免“单点失效问题”而配置的等效节点.然而对于任意一个节点而言,其等效节点为冗余节点.从图4所示辅助图可以看出:只要保证core与每一个bound连接,而且boundi(1≤ik)内部边缘层交换机全连通,同时boundiserveri(1≤ik)连通,则可以保证SDCN中服务器之间全连通,也就是可以保证正常数据传输.可见,SDCN中并不需要所有节点全连通,只需保证服务器之间连通.由第1节描述可知,SDCN中每一个bound与对应的server始终连通,因此,SDCN中保证服务器全连通仅需在辅助图中保证corebound以及每一个bound中节点间的连通.为了便于描述,将其称为保证SDCN辅助图全连通.

如图1所示,将边缘层、汇聚层和核心层交换机依次编号1~k22,k22+1~k2k2+1~5k24.用a[i][j](1≤i,j≤5k24)表示网络中第i个交换机与第j个交换机的连接情况.如果ij相连(即连通),其值为1,否则其值为0.

定理1. 为了保证SDCN辅助图全连通,必须同时满足2个条件:

条件1. 存在j∈{k2+1,k2+2,…,5k24},使得:

(6)

成立.

条件2. 对于任意的n∈{0,1,2,…,k-1},使得:

(7)

成立.

其中:

m=,

(8)

其中,j必须是满足条件1的核心层交换机.式(8)保证满足条件1的核心层交换机j与每一个bound中第m个汇聚层交换机相连接.

证明. 根据核心层交换机与汇聚层交换机的连接特点和数据流的转发特点可知,条件1要求至少存在一个核心层交换机与其所有连接的汇聚层交换机均处于工作状态,即保证辅助图中core与每一个bound连接.根据汇聚层交换机与边缘层交换机的连接特点可知,条件2要求条件1中所有满足要求的核心层交换机中,至少有一个核心层交换机连接的所有汇聚层交换机分别与本bound中所有边缘层交换机连接,即保证boundi (1≤ik)内部边缘层交换机全连通.

因此,当且仅当同时满足条件1和条件2时,可保证SDCN辅助图全连通,也就是保证了SDCN中边缘层交换机连通.又由于边缘层交换机与服务器总是连通,因此保证了SDCN中服务器连通,也就是保证了SDCN连通.

证毕.

由定理1可知,SDCN中只需保证边缘层交换机之间全连通即可保证全网服务器正常通信.因此,与文献[18,21]相比,可以休眠更多交换机节点和链路,进一步减少能耗.图5给出了与文献[18,21]的对比情况.图5(a)为一个具有4个PoD的SDCN,应用文献[18]节能算法时网络的一种删减情况如图5(b)所示,为了保证所有节点连通,只能删减(休眠)4条链路.应用文献[21]节能算法时网络的一种删减情况如图5(c)所示(图5(c)给出仅含一个最小独立路径集时的网络拓扑),该算法比文献[18]算法的节能效果更好,可以删减(休眠)16条链路和6个交换机.但是从图5(c)中可以发现,在保证网络服务器全连通时,仍然存在冗余设备(1个核心层交换机和对应的4条链路).而依据定理1可知,在fat-tree拓扑的SDCN中,仅需保证辅助图全连通,此时一种可行的删减情况如图5(d)所示,可以删减(休眠)20条链路和7个交换机节点.可见,在fat-tree拓扑SDCN中本文提出的基于辅助图全连通的节能方案优于文献[18,21]的节能方案.

Fig. 5 Comparison between SDCN connectivity conditions and algorithms in Ref [18,21]
图5 SDCN连通条件与文献[18,21]算法对比

2.3 MER算法描述与实现

2.3.1 MER算法架构

MER算法的核心思想是基于SDCN辅助图连通条件对网络拓扑进行“剪枝”,在保证数据流可靠性和时延要求条件下,按照一定的规则从初始网络拓扑中尽可能多地删除冗余交换机和链路,使其休眠,使用较少网络资源进行数据传输,以实现节能.

MER算法主要由拓扑发现模块(topology discovery, TD)、节能路由模块(energy-saving routing, ER)、连通性判断模块(connection judgement, CJ)以及流表下发模块(flow distribution, FD)组成,整体架构如图6所示.

Fig. 6 Algorithm architecture of MER
图6 MER算法总体架构

TD模块是算法的基础模块,是整个算法得以实现的前提.首先对整个SDCN进行感知,获取核心层、汇聚层、边缘层交换机的连接方式以及网络中各链路和节点的基本信息,如时延信息、能耗信息等.然后将所获取信息映射成一个网络拓扑视图,并生成一个对应的网络信息表供ES模块等使用.网络信息表由交换机间连接状态、链路时延、交换机能耗和链路能耗4部分组成.其中,连接状态有连通和断开2种,分别用1和0表示.

ER模块是实现网络节能优化和路由选择的核心功能模块,用于获取最佳路径并完成网络“剪枝”操作,具体描述见2.3.2节.

CJ模块对“剪枝”操作后的网络连通性进行判断,即利用SDCN辅助图连通条件判断所有服务器是否能够正常通信.当满足SDCN连通的必要条件时,说明“剪枝”后的网络可以抽象成一个辅助图,则本模块返回True,否则返回False.

FD模块是MER算法能够在整个网络得以实现的桥梁,核心功能是告知网络中交换机如何对流量进行传输.

2.3.2 节能路由模块

为了更好地描述节能路由(ER)模块,先引入以下定义.

定义4. 孤岛交换机.基于fat-tree拓扑的SDCN,如果度矩阵DG0的元素dii=0(1≤i≤|N|),则称第i个交换机为孤岛交换机.可见,孤岛交换机与其他交换机不相连.

定义5. 无效链路.不能用于构成任何服务器对间可行路径的链路为无效链路.具体而言,对于汇聚层和核心层交换机之间的链路,如果删除该链路后,对应的核心层交换机成为“孤岛交换机”,则此链路为无效链路;对于汇聚层和边缘层交换机之间的链路,如果删除该条链路后,对应的汇聚层交换机成为“孤岛交换机”,则此链路为无效链路.一般而言,如果邻接矩阵FG0中的某一个元素aij=0时,有DG0中的元素djj=0,其中k22≤ik2-1且k2j≤(5k24)-1或者0≤i≤(k22)-1且k22≤jk2-1,则连接第i个交换机和第j个交换机的链路称为无效链路.

图7给出无效链路和孤岛交换机的示例.图7中链路(s2,s4)不能用于构成任何服务器对间的可行路径,因此为无效链路.删除该无效链路后,交换机s2s6未与任何其他交换机连接,因此为孤岛交换机.

Fig. 7 Examples of invalid link and isolated switch
图7 无效链路和孤岛交换机示例

ER模块的主要步骤为

步骤1. 初始化集合PbestPs为空.以每一个核心层交换机为根节点,获取最小网络连通子集,将对应网络子集放入集合G+,即G+={Gj}(1≤j≤|C|).继续步骤2.

步骤2. 计算Gj(1≤j≤|C|)中各个链路和交换机的总能耗Ej,求出所有网络子集的总能耗最小值Emin=min{Ej,1≤j≤|C|}.将能耗等于Emin的网络子集放入集合Gb,即Gb={Gb1,Gb2,…,Gbm},Ebm=Emin,1≤m≤|C|.计算Gb中各个子集的链路总时延,获取链路总时延最小的子集(如果存在多个总时延最小子集,则随机选取1个),记为Gbest.继续步骤3.

步骤3. 计算Gbest中任意2个边缘层交换机间的可行路径r(∀rGbest)的时延dr,判断是否满足drdmax.如果满足,继续步骤4;否则,转到步骤5.

步骤4. 计算Gbest的代数连通度λ(Gbest)并与θmin进行比较.当λ(Gbest)≥θmin时,将Gbest中每对边缘层交换机间时延最小的路径和对应的边缘层交换机对以键值对形式放入集合Pbest中,转到步骤8;否则,对Gbest进行可靠性处理.考虑到对节能效果的影响,结合fat-tree拓扑SDCN的连接特点,在保证汇聚层和边缘层交换机和链路数不变的前提下,依次增加等效的核心层交换机以及相应的与汇聚层连接的链路,以保证可靠性.具体方式是:

首先查看Gbest中的核心层交换机,将与该交换机等效的所有核心层交换机放入集合Cs中,并依次标号;然后按照标号从小到大依次从Cs中取出一个交换机添加到网络中,并将该交换机与相应的汇聚层交换机连接,更新Gbest.一旦增加设备后的代数连通度λ(Gbest)≥θmin,则将修补后满足drdmax的路径与对应的边缘层交换机对以键值对形式放入集合Ps,转到步骤8.如果Cs为空后仍然不满足λ(Gbest)≥θmin,继续步骤5.

步骤5. 依据G0中链路的时延和能耗状态调整链路li(1≤i≤|L|)的代价函数pi,即

(9)

其中,分别表示链路li的时延和能耗因子,其值分别为

(11)

根据pi值将各链路从大到小排序,放入集合Lsort中并依次标号,即Lsort={l1,l2,…,li,lj,lj+1,…},pipj,1≤ij≤|L|.记当前网络为Gt,继续步骤6.

步骤6. 从集合Lsort中依次取出一条链路并尝试删除,即进行“剪枝”操作.当链路li(1≤i≤|L|)为无效链路时,将其删除,并更新Gt;否则,首先尝试从Gt中删除该链路,并调用CJ模块.如果返回True,则检查是否满足λ(Gt)≥θmin.如果满足,则更新Gt;如果不满足λ(Gt)≥θmin或是CJ模块返回False,则将li恢复.然后,从Lsort中选取下一条链路,继续尝试“剪枝”操作.值得注意的是:当链路li被删除时,还需检查与li相连的2个交换机是否成为孤岛交换机,将相应的孤岛交换机从Gt中删除.当尝试删除Lsort中标号最大链路后,继续步骤7.

步骤7. 获取Gt中每对边缘层交换机间满足drdmax的所有可行路径,并将其中dr值最小的路径与对应的边缘层交换机对以键值对形式放入集合Pbest中,将其余满足条件的所有路径与对应的边缘层交换机对以键值对形式放入集合Ps中.值得注意的是:如果某对服务期间所有可行路径都不满足drdmax要求,为了保证任何服务器间的连通,则选择dr值最小的路径和对应的边缘层交换机对以键值对形式放入集合Ps中.更新GbestGt,继续步骤8.

步骤8. 根据Gbest中的连接信息,对网络G0进行最终的节能休眠操作,即休眠仅包含在G0中而未包含在Gbest中的链路和交换机.继续步骤9.

步骤9. 当网络中有新流需要控制器为其选路时,控制器首先根据新流的源和目的服务器确定对应的边缘层交换机标号;然后,依次尝试从Pbest,Ps中获取最佳路径rbest.如果获取成功,则将rbest告知FD模块,由FD模块通知相应交换机转发数据流.如果从PbestPs中都获取失败,则FD模块通知相应的交换机丢弃该流.

现对ER模块的复杂度进行简要分析.

对于k个PoD的SDCN,首先要获取k24个最小连通子集,并对每一个子集进行能耗和时延约束判断,时间复杂度为O(k24).在可靠性处理中,一个核心层交换机至多含有k2-1个等效节点,因此至多进行k2-1次,时间复杂度为O(k2).当网络子集均不满足时延约束或可靠性约束时,需要根据初始网络中k32条链路的性能进行节能优化,并需检查网络中5k24个交换机是否为孤岛交换机,时间复杂度为O(k32+5k24).因此,算法总的时间复杂度为O(k2)+ O(k24)+ O(k32+5k24),近似为O(k32).

3 仿真实验与性能分析

采用Mininet[27]仿真软件搭建支持SDN的数据中心网络,采用Floodlight[28]作为控制器,对所提出的MER算法进行仿真评测,并与IEER算法[16]、ESACON算法[18]和IPSM算法[21]进行对比(IEER属于流量感知算法,后2个属于拓扑感知算法).仿真拓扑采用k=4的fat-tree拓扑,包含16个主机、20个交换机和32条链路.仿真中设置:交换机能耗值为36W,每条链路能耗值为1W[15],链路带宽为1 Gbps,链路时延在1~10 ms之间随机产生,dmax=20 ms,α分别取0.2,0.4,0.6,0.7,0.8.

SDCN中常见的通信模型有1对1通信和1对多通信.为了更加逼真地模拟实际情况,本文采用混合通信模型,即1对1和1对多通信模型共存.根据Benson等人的研究成果[29],本文规定小于100 KB的流为小流,大于100 KB的流为大流.其中90%数据流为小流,10%的数据流为大流.每次测试时的流量大小根据大小流的比例,在对应的范围内随机产生.实验中利用网络负载百分比ε[15]来模拟网络中的不同负载情形.网络负载百分比表示从数据中心所有服务器中随机选取ε%个服务器来发送或者接收数据流[15].仿真评测指标为能耗节省率(energy saving rate, ESR)[15]、平均分组时延(average packet delay, APD)和丢包率(packet loss rate, PLR).仿真结果是进行10次随机实验后的平均值,如图8~10所示.

Fig. 8 Comparison of energy saving rate
图8 能耗节省率比较

Fig. 9 Comparison of average packet delay
图9 平均分组时延比较

Fig. 10 Comparison of packet loss rate
图10 丢包率比较

图8对比了不同网络负载百分比下4种算法的能耗节省率(ESR).从图8可以看出:随着网络负载百分比增加,各算法的ESR均有不同程度的下降.另外,从节能效果上看,ESACON算法的ESR最低,节能效果最差;而IEER算法和MER算法的节能效果较好,优于其他2种算法.在网络负载百分比低于60%时,MER算法的ESR不及IEER算法;但是,随着网络负载百分比进一步增加,其节能效果逐渐优于IEER算法.而IPSM算法的节能效果在网络负载百分比低于80%时不及IEER算法;但随着网络负载百分比继续增大,其ESR逐渐高于IEER算法.主要原因在于:随着网络负载百分比增大,网络中需要激活更多设备来传输数据.同时由于网络负载增加,网络发生拥塞概率增加,导致数据传输时间增加.上述因素都会导致网络能耗增加,因此算法的ESR会随网络负载增加而逐渐下降.另外,ESACON算法要保证网络中所有节点全连通,对于具有“富连接”特点的SDCN而言,该算法使SDCN中等效节点也彼此连通,因而能够休眠的设备较少,其能耗节省率最低.IPSM算法以最小独立路径集为单位进行网络删减,与ESACON算法相比,可休眠更多网络设备,因此,其节能效果优于ESACON算法.IEER算法未考虑网络突发数据流,仅依据流量矩阵建立节点对间的路径并休眠网络设备.因此,网络负载较小时,需要建立的路径较少,休眠设备较多,能耗节省率较高.但是,随着数据流量增大,需要激活更多网络设备,能耗节省率逐渐变低.因此当网络负载百分比较高(>80%)时,其能耗节省率不及IPSM算法.而本文提出的MER算法基于辅助图模型和SDCN连通条件,可以休眠网络中更多冗余设备,因此,在中、高负载情况下其节能效果都明显优于其他算法.

图9对比了不同网络负载百分比下4种算法的平均分组时延(APD)性能.从图9可以看出:随着网络负载百分比的增加,各算法的APD均呈上升趋势.其中MER算法的APD最低,ESACON算法最高,而IEER算法和IPSM算法位于二者之间,并且IEER的APD值略低于IPSM.主要原因在于:随着网络负载增加,网络中会出现一定程度的拥堵,因此,各个算法的APD均会有所增加.由于ESACON,IPSM,IEER这3种算法着重关注如何节能,并未考虑链路时延对网络性能的影响,所选路径的时延性能不一定理想,所以其APD较高.与上述算法不同,MER算法在节能优化过程中充分考虑链路时延的影响,优先尝试删除时延较大的冗余链路,因此其节能优化后的网络所包含高时延链路较少.另外,MER算法在选路时,选择总时延最小且满足时延约束的路径,也有利于进一步降低APD,因此,其平均分组时延性能优于其他3种算法.

图10对比了不同网络负载百分比下4种算法的丢包率(PLR).从图10可以看出:随着网络负载百分比的增加,各算法的PLR均有不同程度的增加.其中,MER算法最低,ESACON算法最高,IEER算法和IPSM算法介于二者之间,并且依次增加.主要原因在于:随着网络负载增加,网络资源逐渐紧张,会出现拥堵现象,因此平均丢包率会有所增加.由于IPSM算法较ESACON算法的平均分组时延较小,数据等待现象较少,所以IPSM算法的丢包率较小,但与IEER算法相比其丢包率仍较高.这是因为IEER算法考虑了负载均衡问题,网络拥堵现象较IPSM算法更少发生,因而丢包率更低.而本文提出的MER算法的丢包率较IEER算法更低,原因在于:MER算法在节能时将时延也作为考虑指标之一,所获得网络子集时延性能较好,所选路径时延较低,能够减少数据等待时间,有利于降低数据包超时被丢弃现象的发生.另外,MER算法结合网络流量和代数连通度来休眠网络设备,通过合理增加网络冗余度以保证非流量矩阵中突发流的正常通信,可以保证网络的可靠性要求,减少突发数据流和网络故障导致的丢包现象发生,也有助于进一步降低丢包率.

从图8~10还可以看出:随着α值增大(α≤0.6),MER算法的节能效果有所下降(仍优于IPSM和ESACON算法,在中、高负载时优于IEER算法),其时延降低,网络可靠性增高,丢包率降低(时延和丢包率仍明显优于其他算法).但是,α取值变化引起MER算法的ESR,APD,PLR值改变不大.这是因为:θmin值随着α值的增加而增大,导致MER算法能休眠设备越少,其能耗增加.由于θmin值越大,网络连通性越高,网络中可用资源越多,从而可降低网络资源不足所导致突发流被丢弃的概率,也有助于减少网络发生拥堵现象,相应地可以降低丢包率和平均分组时延.但是,当α增加到一定程度(α≥0.6)时,θmin值已经非常接近θ1,网络中激活设备越来越多.再继续增加α,所需激活设备数变化不大,因此,MER算法性能变化不明显(图8~10中α=0.6,0.7,0.8时MER性能曲线几乎重叠在一起).

4 结束语

本文利用SDN集中控制的特点来解决DCN的节能路由问题,结合拓扑感知和流量感知2类节能路由各自的优势(在拓扑感知节能路由机制中引入网络流量因素),首先给出多约束节能路由优化模型,然后通过引入等效节点、最小网络连通子集等概念和辅助图模型,给出SDCN连通条件;在此基础上,综合考虑节能以及时延和可靠性约束条件,提出一种适用于SDCN的多约束节能路由算法(MER);最后通过Mininet和Floodlight进行仿真评测.仿真结果表明:MER算法可以达到理想的节能效果,同时可以获得更低的平均分组时延和丢包率.MER算法仅选取影响传输性能的时延和可靠性2个因素进行考虑,在下一步研究中可考虑其他因素的影响,如分析交换机中流表处理能力等性能对能耗节省率的影响.

参考文献

[1]Li Dan, Chen Guihai, Ren Fengyuan, et al. Data center network research progress and trends[J]. Chinese Journal of Computers, 2014, 37(2): 259-274 (in Chinese)(李丹, 陈贵海, 任丰原, 等. 数据中心网络的研究进展与趋势[J]. 计算机学报, 2014, 37(2): 259-274)

[2]Wang Binfeng, Su Jinshu, Chen Lin. Review of the design of data center network for cloud computing[J]. Journal of Computer Research and Development, 2016, 53(9): 2085-2106 (in Chinese)(王斌锋, 苏金树, 陈琳. 云计算数据中心网络设计综述[J]. 计算机研究与发展, 2016, 53(9): 2085-2106)

[3]Shuja J, Bilal K, Masani S A, et al. Survey of techniques and architectures for designing energy-efficient data centers[J]. IEEE Systems Journal, 2016, 10(2): 507-519

[4]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

[5]Nguyen X N, Saucez D, Barakat C, et al. Rules placement problem in OpenFlow networks: A survey[J]. IEEE Communications Surveys & Tutorials, 2016, 18(2): 1273-1286

[6]Nunes B A A, Mendonca M, Nguyen X N, et al. A survey of software-defined networking: Past, present, and future of programmable networks[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1617-1634

[7]Wu Qiang, Xu Xin, Liu Guoyan. Construction of basic network in data center based on SDN technology[J]. Telecommunications Science, 2013, 29(1): 130-133 (in Chinese)(吴强, 徐鑫, 刘国燕. 基于SDN技术的数据中心基础网络构建[J]. 电信科学, 2013, 29(1): 130-133)

[8]Dayarathna M, Wen Yonggang, Fan Rui. Data center energy consumption modeling: A survey[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 732-794

[9]Zhang Guoqiang, Xu Ziqu, Liu Zhen. Research on green network theory and technology[J]. Journal of Software, 2016, 27(3): 736-759 (in Chinese)(张国强, 许自取, 刘真. 绿色网络理论与技术研究[J]. 软件学报, 2016, 27(3): 736-759)

[10]Baccour E, Foufou S, Hamila R, et al. Achieving energy efficiency in data centers with a performance-guaranteed power aware routing[J]. Computer Communications, 2017, 109: 131-145

[11]Gao Peter Xiang, Curtis A R, Wong B, et al. It’s not easy being green[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 211-222

[12]Jiang Hanpeng, Chuck D, Chen Weimei. Energy-aware data center networks[J]. Journal of Network & Computer Applications, 2016, 68: 80-89

[13]Heller B, Seetharaman S, Mahadevan P, et al. Elastic tree: Saving energy in data center networks[C] //Proc of the 7th USENIX Conf on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2010: 249-264

[14]Shang Yunfei, Li Dan, Xu Mingwei. Energy-aware routing in data center network[C] //Proc of the 1st ACM SIGCOMM Workshop on Green Networking. New York: ACM, 2010: 1-7

[15]Xu Mingwei, Shang Yunfei, Li Dan, et al. Greening data center networks with throughput-guaranteed power-aware routing[J]. Computer Networks, 2013, 57(15): 2880-2899

[16]Dong Shi, Li Ruixuan, Li Xiaolin. Energy efficient routing algorithm based on software defined data center network[J]. Journal of Computer Research and Development, 2015, 52(4): 806-812 (in Chinese)(董仕, 李瑞轩, 李晓林. 基于软件定义数据中心网络的节能路由算法[J]. 计算机研究与发展, 2015, 52(4): 806-812)

[17]Han Yoonseon, Seo S S, Li Jian, et al. Software defined networking-based traffic engineering for data center networks[C] //Proc of the 16th Asia-Pacific Network Operations and Management Symp. Piscataway, NJ: IEEE, 2014: 1-6

[18]Cuomo F, Abbagnale A, Cianfrani A, et al. Keeping the connectivity and saving the energy in the Internet[C] //Proc of IEEE Conf on Computer Communications Workshops (INFOCOM WKSHPS). Piscataway, NJ: IEEE, 2011: 319-324

[19]Das K C. The Laplacian spectrum of a graph[J]. Computers & Mathematics with Applications, 2004, 48(5/6): 715-724

[20]Jamakovic A, Uhlig S. On the relationship between the algebraic connectivity and graph’s robustness to node and link failures[C] //Proc of 2007 Next Generation Internet Networks. Piscataway, NJ: IEEE, 2007: 96-102

[21]Zhang Huyin, Wang Sisi, Qian Long, et al. SDN data center networks oriented energy saving mechanism research based on the path resource management[J]. Journal of Chinese Computer Systems, 2017, 38(4): 755-760 (in Chinese)

(张沪寅, 汪思思, 钱龙, 等. 面向SDN数据中心网络的路径资源管理节能机制研究[J]. 小型微型计算机系统, 2017, 38(4): 755-760)

[22]Andrews M, Anta A F, Zhang Lisa, et al. Routing and scheduling for energy and delay minimization in the powerdown model[J]. Networks, 2013, 61(3): 226-237

[23]Roughan M, Zhang Yin, Willinger W, et al. Spatio-temporal compressive sensing and Internet traffic matrices[J]. IEEE/ACM Transactions on Networking, 2012, 20(3): 662-676

[24]Gong Yanlei, Wang Xiong, Malboubi M, et al. Towards accurate online traffic matrix estimation in software-defined networks[C] //Prof of the 1st ACM SIGCOMM Symp on Software Defined Networking Research. New York: ACM, 2015: Article No.26

[25]Crovella M. On traffic matrix completion in the Internet[C] //Proc of the 2012 Internet Measurement Conf. New York: ACM, 2012: 399-412

[26]Karp R M. Reducibility among combinatorial problems[C] //Proc of IBM Research Symp on the Complexity of Computer Computations. Berlin: Springer, 1972: 85-103

[27]Bholebawa I Z, Jha R K, Dalal U D. Performance analysis of proposed OpenFlow-based network architecture using Mininet[J]. Wireless Personal Communications, 2016, 86(2): 943-958

[28]Project Floodlight. The world’s leading open source software-defined networking (SDN) community[EB/OL]. [2018-01-05]. http: //www.projectfloodlight.org

[29]Benson T, Anand A, Akella A, et al. Understanding data center traffic characteristics[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(1): 92-99

Multi-Constrained Energy-Saving Routing Algorithm in Software-Defined Data Center Networks

He Rongxi, Lei Tianying, and Lin Ziwei

(College of Information Science and Technology, Dalian Maritime University, Dalian, Liaoning 116026)

Abstract The proposed energy-saving routing algorithms for data center networks can be broadly classified into two categories: traffic-awareness and topology-awareness. The performance of the former depends largely on the accuracy of the predicted traffic patterns. However, the traffic patterns in the actual network change dynamically, and the predicted traffic patterns might not accord with the real-time traffic patterns of the network. It is often difficult for the traffic-aware energy-saving routing algorithms to guarantee reliable transmission of burst flows. On the other hand, the latter has to ensure the connectivity of the network topology, which does not consider the traffic load. Therefore, there are often lots of idle devices during low traffic load that result in energy waste. For this reason, for a software-defined data center network (SDCN) with fat-tree topology, we combine the advantages of the two kinds of energy-saving routing algorithms, and propose some concepts including equivalent nodes, the minimum subset for network connectivity, isolated switch and invalid link, auxiliary graph model and SDCN connectivity conditions in this paper. On this basis, a multi-constrained energy-saving routing optimization model is described. Moreover, a multi-constrained energy-saving routing algorithm (MER) is also proposed. In order to reduce the network energy consumption, MER algorithm can sleep as many redundant switches and links as possible while guaranteeing the requirements of the flows in delay and reliability. Finally, the performance of the proposed algorithm is evaluated by using Mininet and Floodlight, and the simulation results show that MER has lower average packet delay and packet loss rate than the existing algorithms in the literature with a desired energy saving rate.

Key words software defined network (SDN); data center network; energy-saving routing; topology-aware; traffic-aware

(hrx@dlmu.edu.cn)

DOI:10.7544/issn1000-1239.2019.20180029

收稿日期2018-01-12;修回日期:2018-11-15

基金项目国家自然科学基金项目(61371091);大连海事大学“十三五”重点科研项目(3132016318)

This work was supported by the National Natural Science Foundation of China (61371091) and the “13th Five-Year” Key Research Project of Dalian Maritime University (3132016318).

通信作者雷田颖(cndlmu@sina.com)

中图法分类号 TP393

He Rongxi, born in 1971. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include software defined networking, wireless network and optical network.

Lei Tianying, born in 1992. Master. His main research interests include software defined networking.

Lin Ziwei, born in 1994. Master candidate. Her main research interests include software defined networking.