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

何荣希 雷田颖 林子薇

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

作为分布式存储和计算的桥梁，数据中心网络(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 多约束节能路由模型

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

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

Table 1 Explanations of Variables表1 变量含义

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

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

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

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

(1)

s.t.

dr≤dmax,∀r∈G,

(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，可表示为

(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≤i≤k)；将boundi中边缘层交换机连接的所有服务器视为一个整体，记为serveri(1≤i≤k)；将所有核心层交换机节点视为一个整体，记为core，得到SDCN辅助图，如图4所示.可见，具有k个PoD的SDCN辅助图由1个core、k个bound和k个server构成.

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≤i≤k)内部边缘层交换机全连通，同时boundi和serveri(1≤i≤k)连通，则可以保证SDCN中服务器之间全连通，也就是可以保证正常数据传输.可见，SDCN中并不需要所有节点全连通，只需保证服务器之间连通.由第1节描述可知，SDCN中每一个bound与对应的server始终连通，因此，SDCN中保证服务器全连通仅需在辅助图中保证core和bound以及每一个bound中节点间的连通.为了便于描述，将其称为保证SDCN辅助图全连通.

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

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

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

(6)

成立.

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

(7)

成立.

其中：

(8)

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

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

因此，当且仅当同时满足条件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≤i≤k2-1且k2≤j≤(5k24)-1或者0≤i≤(k22)-1且k22≤j≤k2-1，则连接第i个交换机和第j个交换机的链路称为无效链路.

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

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

ER模块的主要步骤为

步骤1. 初始化集合Pbest和Ps为空.以每一个核心层交换机为根节点，获取最小网络连通子集，将对应网络子集放入集合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(∀r∈Gbest)的时延dr，判断是否满足dr≤dmax.如果满足，继续步骤4；否则，转到步骤5.

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

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

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

(9)

(11)

根据pi值将各链路从大到小排序，放入集合Lsort中并依次标号，即Lsort={l1,l2,…,li,lj,lj+1,…}，pi≥pj，1≤i≤j≤|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中每对边缘层交换机间满足dr≤dmax的所有可行路径，并将其中dr值最小的路径与对应的边缘层交换机对以键值对形式放入集合Pbest中，将其余满足条件的所有路径与对应的边缘层交换机对以键值对形式放入集合Ps中.值得注意的是：如果某对服务期间所有可行路径都不满足dr≤dmax要求，为了保证任何服务器间的连通，则选择dr值最小的路径和对应的边缘层交换机对以键值对形式放入集合Ps中.更新Gbest为Gt，继续步骤8.

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

步骤9. 当网络中有新流需要控制器为其选路时，控制器首先根据新流的源和目的服务器确定对应的边缘层交换机标号；然后，依次尝试从Pbest,Ps中获取最佳路径rbest.如果获取成功，则将rbest告知FD模块，由FD模块通知相应交换机转发数据流.如果从Pbest或Ps中都获取失败，则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个因素进行考虑，在下一步研究中可考虑其他因素的影响，如分析交换机中流表处理能力等性能对能耗节省率的影响.