基于多层虚拟拓扑节能的SDN数据中心网络流量调度算法

李宏慧 李炜东 付学良

(内蒙古农业大学计算机与信息工程学院 内蒙古 呼和浩特 010011)

0 引 言

随着云计算、物联网和大数据技术的快速发展，数据中心的规模变得越来越大，其能源消耗巨大并且不断增长[1]，极大限制了其运营及发展。据统计，2015年我国数据中心能耗高达1 000亿kW·h，超过我国社会用电量1.5%，相当于整个三峡大坝一年的发电量[2]。随着近期5G通信等技术的快速增长，预计到2020年我国数据中心能耗占比将增长至8%[3]。

数据中心设备包括外围设备和网络设备。数据中心网络的能耗占数据中心的总能耗达到了15%～20%[4]。随着外围设备，例如服务器、存储设备、制冷设备等节能技术的快速发展及部署，网络部分的能耗占比将会变得越来越多。为了保证数据中心的可靠性和可用性，交换机等网络设备几乎永不关机，不论数据中心网络负载量大小，均以接近100%的功率持续运行。

为了提高数据中心网络可靠性和网络容量，人们提出了许多“富连接”的数据中心网络架构，如，Fat-Tree[5]、Monsoon[6]、BCube[7]、Helios[8]等。其中Fat-Tree结构简单，对分带宽大，并且可提供服务器之间的多条等价路由，成为热门候选。但是，相对于传统数据中心，这种结构引入较多的交换机，进一步增加了网络的能耗。

当今的数据中心网络多采用等价多路径(Equal-CostMultipath，ECMP)路由算法[9]对数据流进行调度。在Fat-Tree型数据中心网络中，到达任意一个目的服务器结点存在多条等价路径，ECMP算法利用静态哈希函数从中选择一条路径来路由数据流。由此实现负载均衡。但是，ECMP未考虑网络的能耗问题。

在Fat-Tree型数据中心网络中，当网络流量负载较低时，可以通过节能流量调度方法和休眠空闲的交换机设备降低网络能耗，提高能源利用率[10-11]。这种方法的基本思想就是利用部分交换机设备及端口承载当前的数据流，同时休眠空闲的网络交换机及端口，从而实现降低网络的总能耗。为此，要求能够对数据中心网络进行全局监控和对资源的统一管理调度，并且需要交换机具有较强的计算能力，以及方便可行的状态转换(开启/休眠)能力。但是，传统的数据中心网络中，交换机的路由转发表都是采用分布式的方法，独立地进行计算。

软件定义网络(Software Defined Networking,SDN)[12]作为一种新型的网络架构，为实现数据中心网络的节能流量调度提供了新的平台。SDN实现了网络交换设备控制平面和数据转发平面的分离，形成了逻辑上统一的控制器，实现对网络通信流量和网络资源的集中调度和管理。在SDN数据中心网络中，可以方便地实现交换设备及其端口的休眠或开启[13]。

针对“富连接”数据中心网络在低负载时能源利用率较低的问题，本文在Fat-Tree拓扑的SDN数据中心网络中，提出了一种节能的多层虚拟子拓扑的流量调度算法(EMV-SDN)。实验结果表明，在网络能源消耗和延时方面，EMV-SDN算法均优于ECMP以及Dijkstra算法。

1 相关工作

SDN技术使得数据中心网络的计算能力大大提高，能够对网络资源，例如交换机、端口等进行细粒度化管理，并且较易实现休眠或唤醒设备。由此，基于SDN的数据中心网络节能问题成为了当下的一个研究热点[14]。

Heller等[10]提出了弹性树(ElasticTree)机制实现数据中心网络节能，提供网络的可扩展性。该机制根据网络通信负载的大小，动态调整交换机和链路的活跃状态。实验结果表明，该方法在保证能承载激增的通信数据量的同时，可以节省高达50%的网络能耗。但是，所提出的优化算法计算复杂度高，使得流量调度的实时性较差。另外，引入的接口计数器增加了额外的硬件开销。

为了节省“富连接”(如Fat-Tree型)数据中心网络的能源消耗，Shang等[11]从路由角度出发，提出了能量感知路由方法。核心思想是：在无损网络性能的前提下，用尽可能少的网络设备来提供路由服务，同时，休眠空闲的网络设备，从而达到节能的目的。但是，该算法需要进一步完善以适应延迟敏感型的流量调度问题。

Tu等[15]提出了两种不同的数据中心网络节能算法，可应用在不同场景中，例如，延时敏感型的应用或延时不敏感的应用，并且与网络拓扑无关，通过SDN集中化管理和流量预处理，可以达到较好的节能效果。但是，当网络负载较重时，使用的贪心算法会产生一定的时延。另外，其未考虑链路和交换机的开启时间对网络时延的影响。

Li等[16]提出了一种新的能量感知流量调度方法EXR(EXclusive Routing)。它的核心思想就是按照时间先后顺序调度数据流，使得每个数据流独占路由途中的链路带宽。由此数据中心网络不会出现瓶颈链路，改善了活跃的交换机和链路的利用率，从而实现了数据中心网络的节能。实验结果表明，该方法在节能和平均完成时间上均优于公平共享路由方法。但是，EXR不能保证交换机的能效，因为它通过贪婪策略选择可用链路的路径，按优先级顺序调度数据流。

文献[17]提出了新的路由算法，解决数据中心网络的负载均衡和能耗问题。其基本思想是，首先定量分析负载均衡，然后提出了将负载均衡与节能有效结合的节能路由算法，实现了在降低网络能耗的同时保证网络具有较高的可靠性。该算法在应对突发流量上存在提升的空间。

文献[18]针对通用拓扑的数据中心网络的节能问题，推导出了能效数学模型，提出了一种基于果蝇优化算法的节能路由机制求解数学模型。该机制模拟果蝇觅食过程，在寻路过程中，不断调整方向和位置，确定路由的下一个节点，最终找到最优节能路径。该机制既可以提高能效又能使得网络性能优于已有的方法。但该算法的时间复杂度较高。

文献[19]提出了一种新的节能调度和路由方法。该方法在时间维度上最小化数据中心流量的总能源消耗，提高了交换机的利用率，并且满足了数据流的要求，例如截止时间等。实验结果表明，该算法能有效降低通信流量的总能耗，并且缩短了数据流的平均完成时间。但是，该方法主要针对的是有特定时延限制的网络数据流的调度问题。

针对弹性拓扑节能机制中利用贪心算法计算节能路径时，解的质量无法保证的问题，文献[1]提出了改进的混合遗传算法求解优化路径。基于SDN，该算法能够规划出优化的节能路由，避免了局部最优和收敛较慢的问题，进一步提高了数据中心网络的能源利用率。

文献[20]提出了Fat-Tree型数据中心网络的节能路径规划系统ESPP，利用SDN控制器收集网络状态信息，计算节能路径来调度数据流，从而实现降低能源消耗的目标。测试结果证明了算法的有效性。但是，ESPP的能耗模型需要进一步完善，需要更全面考虑能耗影响因子。

综上所述，现有的节能流量调度算法尚在以下几方面存在可以提升的空间。首先，算法应能随着网络流量的动态变化动态地路由流量，在节省能耗的同时满足流量调度实时性的需求。同时，从网络全局角度考虑节能流量路由问题，在节能的同时保证网络的性能。

2 节能流量调度问题数学模型

数据中心网络总能源消耗定义为网络中所有活跃的(处于工作状态的)交换机和链路的能源消耗。任意链路的能源消耗表示为COSTl，是该链路两个端点(即交换机端口)的能耗，交换机节点v的能耗COSTv是指该交换机机架和线卡的能源消耗。

节能流量调度问题的优化数学模型如下:

(1)

s.t.

(2)

(3)

xl≤yvv∈V,l∈Lv

(4)

(5)

(6)

式(1)为优化目标函数，即数据中心网络总能源消耗。式(2)为链路容量限制约束条件。它说明任意活跃链路l能承载的数据流总带宽不能超过链路l的总容量。处于休眠状态的链路不能承载任何数据流。式(3)为流守恒约束条件。对于任意数据流f，如果节点v是其源节点，则该节点只有流出数据流；如果v是数据流的目的节点，则该节点只有流入数据流；否则，任意中间节点v的流入数据流与流出数据流相同。式(4)说明，对于任意交换机节点v，如果v处于休眠状态，则与之相连的链路状态均为休眠状态。式(5)的含义为如果与交换机节点v相连的链路均处于休眠状态，则可将交换机v置于休眠状态。式(6)说明了变量的取值范围。

3 节能流量调度算法EMV-SDN

为了求解上述优化数学模型，针对文献中存在的不足，本文提出了基于多层虚拟拓扑的SDN数据中心网络节能流量调度算法EMV_SDN。首先将SDN控制器收集的数据中心网络拓扑划分为多层虚拟拓扑(即第一层、第二层、第三层等多层虚拟子拓扑)，开启第一层虚拟拓扑,关闭其他高层虚拟拓扑。对于每一条到达的数据流，根据当前虚拟拓扑的最大链路利用率，决定是否需要开启高一层虚拟拓扑，然后在已开启的虚拟拓扑结构中，利用改进的贪婪算法计算路径调度该数据流。最后依据一定的条件，关闭已开启的高一层虚拟拓扑，以此实现节能的目标。

3.1 算法描述

节能流量调度算法EMV-SDN流程如图1所示。输入为SDN控制器收集的数据中心网络拓扑以及新到达网络的数据流。输出为数据流的路由以及已开启的一层或多层虚拟拓扑。SDN控制器根据数据流路由生成流表项下发交换机，调度数据流。

图1 节能流量调度算法流程

EMV-SDN算法步骤如下：

步骤1初始化。

1) 在给定的数据中心网络拓扑中，计算出任意两服务器节点之间的K-最短路径。

2) 将给定的网络拓扑分成多层虚拟拓扑。

3) 开启第一层虚拟拓扑,关闭其他高层拓扑。

对于新到达的数据流f，执行如下步骤。

步骤2利用SDN控制器的sflow软件，收集当前开启的虚拟拓扑链路利用情况，计算出最大链路利用率μ。

步骤3若μ>阈值1，预开启高一层虚拟拓扑，即唤醒其中的交换机，但是其中的链路状态保持不变。基于此，在节能的同时，可以尽快地响应并调度突发数据流，减少平均网络时延。否则，转步骤5。

步骤4若μ>阈值2，开启并使用高一层虚拟拓扑,即唤醒已欲开启的高一层虚拟拓扑中的链路，使其处于活跃状态。否则，转步骤5。

步骤6在选中的路径上路由数据流。

步骤7调用sflow收集链路状态，计算最大链路利用率μ。

步骤8若μ<阈值1并且持续时间>T,若已开启过高一层拓扑，则在数据流传递结束后休眠高一层虚拟拓扑，即休眠其中的交换机和链路。由此实现数据中心网络的节能。这样做的目的也是为了避免频繁开启/休眠交换机及链路引起网络震荡。

步骤9如果流量调度未完成，转步骤2；否则，算法结束。

综上所述，EMV-SDN采用了高一层虚拟拓扑预开启机制应对突发数据流，对数据流实时调度，减少平均网络时延。利用改进的贪心算法选择路由降低了算法的复杂度。采用的逐层开启/休眠更高一层虚拟拓扑，可以在节能的同时简化交换机的配置，节省配置时间。通过将数据流路由到最大链路利用率最小的路径上，实现网络的负载均衡。另外，为了防止网络震荡，当网络负载较轻(μ<阈值1)并且持续了一定时间后，EMV-SDN算法才将高一层拓扑休眠。

3.2 多层虚拟拓扑生成算法

生成多层虚拟拓扑就是把实际物理拓扑划分为第一层、第二层、第三层等多层虚拟拓扑。多层虚拟拓扑生成算法具体步骤如下：

步骤1SDN控制器利用地址解析协议ARP收集数据中心网络拓扑信息。

步骤2利用Kruskal最小生成树算法，根据核心交换机数量n生成n个以核心交换机为根结点的独立最小生成树MSTi(i=0,1,…,n)。将每个MSTi中的结点交换机和链路分别存入图Gi(Vi,Li)(i=0,1,…,n)中。

步骤3将选作第一层虚拟拓扑VG1=G0(V0,L0)。

步骤4将VG1与G1(V1,L1)合并构成第二层虚拟拓扑VG2。构成方法定义为：

1)VG2的结点集合定义为V0∪V1-V0。

2)VG2的链路集合定义为L0∪L1-L0。

步骤5将第二层拓扑VG2与G2(V2,L2)合并构成第三层虚拟拓扑VG3。

步骤6以此类推，依次构成更高层拓扑。

对于数据中心网络的Fat-Tree拓扑结构，每个MDTi均是唯一的，合并后构成的最高层拓扑即为原始物理拓扑。

对于如图2所示的K=4的Fat-Tree拓扑结构，利用上述多层虚拟拓扑生成算法，可以得到如图3所示的第一层、第二层、第三层和第四层虚拟拓扑。

图2 K=4的Fat-Tree 拓扑结构

图3 多层虚拟拓扑

采用上述方法依次构成更高一层虚拟拓扑的主要目的是简化交换机和链路的开启/关闭操作，节省了网络配置时间，减少了网络时延。因为在开启高一层虚拟拓扑，例如VG2时，只需开启休眠中的结点和链路，而不需要重复开启VG1中的结点和链路，并且在关闭高一层拓扑,如VG2时，只需关闭其中包含的节点和链路。

4 实 验

为了检验提出的多层虚拟拓扑节能流量算法EMV-SDN的性能，本文利用Floodlight控制器和Mininet[21]仿真平台搭建Fat-tree型数据中心网络拓扑。采用能源消耗比例和数据流的平均完成时间作为算法性能的衡量指标。能源消耗比例计算公式为：

(7)

式中：COSTe为在节能调度算法下的能源消耗;COSTo为没有采用任何节能措施的能源消耗。由此可知，对于不同的节能调度算法，能源消耗比例越低，算法节能效果越好。

在多层虚拟拓扑下，将提出的EMV-SDN与ECMP和Dijkstra最短路径算法进行比较。实验结果表明，EMV-SDN在能源消耗比例和平均完成时间等方面优于其他两种算法。

4.1 实验设置

4.1.1网络拓扑

选用如图2所示的K=4的Fat-tree型网络拓扑，在Mininet平台上进行仿真实验。其中所有交换机均为48个端口的OpenFlow交换机，各条链路带宽均设置为100 Mbit/s。

4.1.2流量模式

选用工具软件Iperf产生数据中心网络中的数据流。每台主机产生的流的长度、产生时间均不同，其中数据流的长度服从指数分布，流的产生时间服从泊松分布。分别采用随机模式(Random)、交错模式(Staggered)和间隔模式(Stride)来确定数据流的目的节点[5]。

(1) Random：主机i向主机j以相等概率p随机发送数据。

(2) Staggered(pe,pp)：主机i以pe的概率向上层同属边缘交换机发送数据，以pp的概率向同属于一个pod的主机发送数据，以1-(pe+pp)的概率向其他pod的主机发送数据。

(3) Stride(x):主机向主机(i+x)modn发送数据，n为数据中心网络中主机的总数。

4.1.3交换机能耗

交换机的能耗包括机架、线卡、端口等组件的能耗。不同类型的交换机中各组件的能耗不尽相同。表1给出了不同类型交换机的组件能耗数据[1]。

表1 交换机组件能耗 W

4.2 能源消耗比例比较

在上述三种流量模式下，本文比较了算法EMV-SDN与ECMP和Dijkstra的能耗消耗比例。进行了多次实验，每次实验持续时间约为30分钟，取中间10分钟计算数据中心网络能耗。图4-图6为三种流量模式下三种算法比较结果。其中：横坐标为实验持续时间；纵坐标为数据中心网络能源消耗比例。

图4 Random(0.25)模式下的能源消耗比例

图5 Staggered(0,0.2)模式下的能源消耗比例

图6 Stride(6)模式下的能源消耗比例

4.2.1Random流量模式

图4展示了在Random通信模式下三种算法的能耗比较结果。可以看出，EMV-SDN算法比ECMP的能源消耗比例降低了1.50～7.81百分点，平均能源消耗比例降低了2.25百分点。EMV-SDN算法与Dijkstra算法相比，能源消耗比例降低了0.75～42.92百分点，平均能源消耗比例降低了6.52百分点。

4.2.2Staggered模式

在Staggered模式中，pe、pp分别取值为0和0.2。图5给出在该种通信模式下三种算法的能耗比。可以看出，EMV-SDN算法与ECMP算法相比，能源消耗比例降低了1.44～24.61百分点；与Dijkstra算法相比能源消耗比例降低了1.25～42.91百分点。与ECMP和Dijkstra相比，EMV-SDN平均能源消耗比例分别降低了2.52百分点和6.65百分点。

4.2.3Stride模式

在Stride间隔通信模式中，x取值为6。图6展示了在Stride模式下三种算法的能耗比，可以看出，EMV-SDN的能源消耗比例比ECMP降低了0.75到24.62百分点，比Dijkstra算法降低了0.63～42.89百分点。EMV-SDN算法的平均能源消耗比例比ECMP和Dijkstra算法分别降低了4.27百分点和10.77百分点。

从图4-图6可见，在三种通信模式下，所提出的EMV-SDN算法能源消耗比均低于ECMP和Dijkstra算法。这是由于EMV-SDN能够根据当前链路利用率，动态调整高一层虚拟子拓扑的工作状态，从而达到节能的目的。另外，EMV-SDN算法能够在开启的子拓扑中找到跳数最少并且最大链路利用率最小的路径来路由数据流。而ECMP算法未考虑链路状态，随机将流调度到一条最短路径上，未能根据拓扑变化进行路径的调整。Dijkstra算法只计算出最短路径，不能很好地结合链路的状态和链路利用率，可能会使得最短路径上的链路过于拥堵，导致过早开启高一层虚拟子拓扑，造成能源消耗均高于其他两种算法。

4.3 平均完成时间比较

图7从时延方面比较了EMV-SDN、ECMP和Dijkstra三种算法。可以看出，在三种通信模式下，EMV-SDN算法的平均完成时间均最短。与ECMP和Dijkstra相比，采用EMV-SDN节能调度算法，在Random模式下，数据流平均完成时间分别降低了22%和40%；在Staggered模式下，平均完成时间分别降低了21%和39%；在Stride模式下，平均完成时间分别降低了14%和31%。

图7 不同通信模式下算法的平均完成时间比较

就平均完成时间而言，EMV-SDN算法的性能也优于ECMP和Dijkstra。这主要是由于EMV-SDN算法能够在拓扑结构发生变化时及时通过链路着色和链路利用率计算出路径来对数据流进行调度，减少了链路的拥塞，从而使数据流较快地到达终点。而ECMP算法在对流的调度上没有考虑链路利用率，随机将流量分配到一条最短路径中，可能导致链路拥堵，延缓了流到达时间。Dijkstra算法找一条最短路径来路由数据流，同样未考虑链路利用率，并且它不能很好地适应网络虚拟拓扑的变化，从而使得Dijkstra算法调度的数据流平均完成时间最长。

5 结 语

针对“富连接”数据中心网络在负载较低时能源利用率较低的问题，本文提出Fat-Tree型SDN数据中心网络的节能流量调度机制。首先对节能流量调度问题建立整形线性规划(ILP)优化数学模型，然后利用多层虚拟拓扑下的节能流量调度算法求解该数学模型，得到节能的数据流调度路径。通过休眠空闲的网络交换设备和端口，实现降低数据中心总能源消耗的目标。仿真实验结果表明，提出的多层虚拟拓扑的节能流量调度机制EMV-SDN优于ECMP和Dijkstra最短路径算法。在三种不同的通信模式下，不论能源消耗比例还是平均完成时间，EMV-SDN均比其他两种算法表现优异。