基于时延和能耗的SD-DCN的路由优化算法
姚赞, 王颖, 邱雪松, 文禹棋    
北京邮电大学 网络与交换技术国家重点实验室, 北京 100876
摘要

为了更好地实现数据中心网络的节能,基于交换机链路速率级的能耗特点,基于软件定义网络技术,提出一种Floyd-Warshall动态规划和局部重路由的节能服务质量路由优化算法.控制器在保障流的时延性能前提下,采用流在空间和时间上均衡传输的策略,依次为每个流计算传输路径和传输速率;在选路失败的情况下,尽量用较少的开销提高网络的接受率.仿真结果表明,该算法有效地降低了能耗,同时提高了网络流的接受率.

关键词: 软件定义数据中心网络     节能路由     截止时间感知    
中图分类号:TP393 文献标志码:A 文章编号:1007-5321(2020)02-0046-06 DOI:10.13190/j.jbupt.2019-105
Deadline-Aware and Energy Efficient Routing Optimization Algorithm in SD-DCN
YAO Zan, WANG Ying, QIU Xue-song, WEN Yu-qi    
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
Abstract

Based on link speed-scaling energy consumption strategy, Floyd-Warshall dynamic planning & rerouting parts of flows strategy based routing optimization algorithm was proposed. Considering the condition of flow deadline-aware and balanced transmission of flows strategy in space and time, controller in software defined data center network sorts the online incoming flows and chooses the route and calculates the transmission rate for every flow. In case of routing failure, the algorithm improves the acceptance rate of network traffic with less overhead. Simulations show that the algorithm effectively reduces energy consumption and improves the acceptance rate of network traffic.

Key words: software defined data center network     energy efficient routing     deadline-aware    

数据中心网络设计中大多数时间内的网络设备利用率很低,网络能耗效率极低.构建节能网络对降低网络营运成本、节能减排等均具有着重要意义[1-2].以搜索、社交网络为代表,影响数据交换性能的关键因素是流的截止期限[2-3].因此,在数据中心网络中,在保障业务流的时延性能的同时,如何为到来的流选取服务质量(QoS, quality of service)路由,使得网络的能耗和开销最少,是一个值得研究的问题.

软件定义网络(SDN, software defined network)技术可以对网络流量进行精细化管理,因此其可以更好地在保障业务性能的同时,实现网络节能目标.近几年有很多相关研究,从网络节能的角度,可以分为设备级、链路级和链路速率级节能3类.文献[4-9]主要从设备级和链路级进行节能. Ba等[4]提出了一种数据平面的多个拓扑在线切换的机制,在满足流量动态需求的同时,将部分设备和端口休眠从而实现节能;Fernandez-Fernandez等[5]、Wu等[6]、Chen等[7]和Heller等[8]均提出了最小化活跃链路数目的启发式节能路由算法,在约束条件下,按一定策略对业务流进行排序,按次序对流进行路由,路径的集合即为节能拓扑. Xu等[9]采用带宽独占用的策略,提出一种基于带宽感知的高能效路由算法.以上方法均会选择交换机以及其端口的开关,实时性较差.针对数据中心的应用,更需要考虑端口速率级的节能,其可分为独占式和共享式两种带宽占用方式. Wang等[10]针对时延保障的流,基于松弛和随机舍入技术,提出了一种可抢占的独占式路由和调度方案.基于链路速率级的能耗模型特征,笔者将采用流共享带宽的策略,且流速率可变,从而在空间和时间上进行均衡分配,进一步提高链路速率级的节能.

笔者在数据中心网络拓扑、交换机以及其相关端口开关与否都已确定的场景下,对基于时延和能耗的数据中心网络路由优化问题进行了建模,提出一种改进的Floyd-Warshall动态规划算法,采用非抢占、流速率可变的带宽共享模式,保证时延的同时,从时间和空间两个维度实现节能;当出现寻路失败的情况时,设计了局部流重路由策略来实现路由优化,以较少的网络开销,提高网络接受率.

1 基于时延和能耗的路由问题模型 1.1 链路速率级节能

数据中心网络可以表示为一个无向图G=(V, E),其中V表示所有交换机的集合,E表示所有链路e的集合.每条链路的电力消耗函数f(xe)是链路传输速率xe的函数[1],可通过式(1)进行计算.

$ f({x_e}) = \sigma + \mu x_e^\alpha , 0 \leqslant {x_e} \leqslant \beta C $ (1)

其中:σμα是和链路类型相关的常量;σ是链路空闲状态时的能耗;C是链路的最大传输速率;β是链路冗余度参数,0 < β < 1. f(·)是可加的,α>1.通过观察单条链路能耗模型发现,当α>1时,(a+b)α>aα+bα.不难发现在网络拓扑确定的情况下,当流尽量在时间和空间上均衡传输时,网络能耗最小.

接下来给出一个简单的例子,可以直观上体现流在时间上的均衡传输对节能效果的影响.假设u, v为一对相邻节点,且由链路e相连.对于每个流ji={pi, qi, ri, di, bi},其中pi, qi分别表示其源和目的节点交换机,ri, di分别表示其到达和最晚截止时间,bi表示流的大小.假设在e上有两条流j1={u, v, 0, 7, 35}和j2={u, v, 0, 12, 42},分别使用带宽共享式和带宽独占式两种方案进行传输,如图 1图 2所示.将能耗函数中α设置为2,μ设置为1,由式(1)进行计算可得能耗增量分别为539和616,对比可知图 1带宽共享式传输方案的能耗增量较小.

图 1 带宽共享式传输

图 2 带宽独占式传输

仅需要获取路径上所有链路每个时刻的带宽占用的最高值,流在空间上的均衡传输问题即可转化为单链路的时间均衡传输问题.因此以上结论可以由单条链路扩展到多条链路连接而成的路径,从而证明空间均衡可以有效降低能耗增量.

1.2 问题描述

假设一个较长时间周期内,根据数据中心网络流量的统计规律,开启特定的交换机和相关端口,当前时刻到达的流量矩阵为J.对于每个流jiJ,主要研究在保证其时延传输性能的条件下,为了达到能耗增量最小的目标,SDN控制器如何根据掌握的全局拓扑和负载情况,在线实时地为每个新到来的流jiJ计算传输路径pi、传输区间[ri, di]以及传输速率si(t).更进一步,当寻路失败时,研究如何选取部分之前流(后文统称为局部流)重新计算路由,以留出空间来传输新流,实现以较少的网络开销来提高网络的接受率.

1.3 模型建立

以能耗增量Δϕ最小为主要优化目标.首先假设网络拓扑已经确定,即交换机以及链路的开通与否已经确定,故网络节点能耗模型简化为速率粒度的能耗模型.网络的能耗增量为主要优化目标,由网络中所有链路在新流分配前后的能耗差值得到,如式(2)所示.

优化目标:

$ {\text{min}}\Delta \phi = \sum\limits_{e \in E} {f'({x_e})} - \sum\limits_{e \in E} {f({x_e})} $ (2)

约束条件:

$ \int_{r'{_i}}^{d'{_i}} {{s_i}\left( t \right){\text{d}}t = {b_i}} $ (3)
$ 0 \leqslant {x_e} \leqslant \beta C $ (4)
$ \sum\limits_{v \in N\left( u \right)} {(f_i^{uv} - f_i^{vu})} = \left\{ \begin{gathered} {b_i}, \;\;\;\;\;\;若u = {p_i} \hfill \\ - {b_i}, \;\;\;\;若u = {q_i} \hfill \\ 0, \;\;\;\;\;\;\;\;\;其他 \hfill \\ \end{gathered} \right\} $ (5)

式(3)表示性能约束条件, 每个流必须在其最晚截止时间前完成;式(4)表示资源能力约束条件, 每条链路的带宽占用不能超过链路容量的β倍;式(5)表示流量守恒限制,从源交换机流出的流量等于流入目的交换机的流量,所有中间交换机流入的流量等于其流出流量[1],其中N(u)表示交换机的邻居交换机集合,fiuv表示流ji部署在链路uv上的流量大小,在不分流的情况下,这个数值为wi或者0.

2 基于时延和能耗的路由优化算法

笔者提出一种基于链路速率级节能的QoS路由优化方案,主要分为2部分:首先,对到来的流按照截止时间早晚进行排序,采用Floyd-Warshall动态规划算法依次为每个流寻求最节能的QoS路由,详见2.1小节;其次,为了提高网络流的接受率,同时降低通信开销,在寻路失败情况下,选取之前正在传输的部分流进行局部调整,从而为新流找到合适路径,实现路由优化,详见2.2节.在2.3节详细给出了基于时延和能耗的软件定义数据中心网络(SD-DCN, software defined data center network)路由优化的整个过程.

2.1 Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间的最短路径的一种动态规划算法.笔者选择Floyd-Warshall算法为新到来的流寻找节能QoS路径.首先定义邻接矩阵W,每个元素wijW表示链路的权重,其代表增加新流后的链路能耗增量,如式(6)所示.

$ {w_{uv}} = {\text{ }}\left\{ \begin{gathered} 0, {\text{ }}\;\;若\;u = v{\text{ }} \hfill \\f(x'{_e}) - f({x_e}), {\text{ }}\;\;若u \ne v\;且\left( {u, v} \right) \in E \hfill \\\infty , {\text{ }}\;\;1\;u \ne v且\left( {u, v} \right) \in E \hfill \\ \end{gathered} \right.{\text{ }} $ (6)

对于任意节点u, vV,Floyd-Warshall算法考虑从节点u到节点v的所有中间节点均取自集合{1, 2, …, k}的路径(该集合是V的一个子集).设p为最短路径,对于任意的k>0,通过分析可以看到,中间顶点不超过k的节点uv的最短路径有2种可能:

1) 该路径不含中间顶点k,那么路径p上的所有中间节点都属于集合{1, 2, …, k-1};

2) 该路径含中间顶点k,则可将路径分解为2条路径,分别是从节点u到节点k和从节点k到节点v的路径.

因此,设duv(k)表示从节点u到节点v的所有中间节点全部取自集合{1, 2, …, k}的一条短路径的权重.当k=0时,表示节点u到节点v的路径没有任何中间节点,权重等于两点之间的链路权重;当k≥1时,权重选择经过k和不经过k的权重较小的那个.根据上面的讨论,递归定义如式(7)所示.

$ d_{uv}^{(k)} = \left\{ \begin{gathered} {w_{ij}}, {\text{ }}若k = 0 \hfill \\ {\text{min}}(d_{uv}^{(k - 1)}, d_{uk}^{(k - 1)} + d_{kv}^{(k - 1)}), {\text{ }}若k \geqslant 1{\text{ }} \hfill \\ \end{gathered} \right. $ (7)

根据以上递归公式,采用自底向上的算法以递增次序来计算duv(k)的值,从而得到最短路径,伪代码详见算法1.其中采用带宽共享、速率可变的均衡策略来计算流ji的传输速率si(t),伪代码详见算法2速率计算模块.

Floyd-Warshall算法首先获取网络的节点数目,并对链路的网络能耗增量初始化,如算法中的第1~2行所示.第3~20行以自底向上的方式递归寻路,在每次寻路的过程中,第6~8行首先将两段路puk(k-1)pkv(k-1)合起来,并调用算法2速率计算模块,在满足时延约束的条件下,重新计算两段路上的流的最节能的传输速率;然后判断此路径是否有能力传输该流,如果是,则更新对应路径的带宽占用情况以及能耗增量,反之则继续寻找新的路径,如第9~16行所示.最后第21~24行在算法执行完后,更新所有最短路径的新的负载,并返回ji的传输速率和最短路径.

算法1   Floyd-Warshall算法

输入:   G=(V, E), ji, 网络的邻接矩阵W.

输出:   ji的传输速率si(t)和传输路径pi.

1   n←row[W]; //获取网络节点数目

2   duv0←0;//网络能耗增量初值,均设为0

3   For k←1 to n

4    Do for u←1 to n

5       Do for v←1 to n

6          For epuk(k-1)pkv(k-1) do

7             调动速率计算模块; //计算流可能传输的速率

8            End for

9            If si(t)≠0 then//检测是否分配成功

10               For epuk(k-1)pkv(k-1) do

11                xexe+si(t); //更新链路速率

12               End for

13              $d_{uk}^{k - 1} \leftarrow \sum\limits_{e \in p_{uk}^{(k - 1)}} {[f(x'{_e}) - f({x_e})]} $;

14               $ d_{kv}^{k - 1} \leftarrow \sum\limits_{e \in p_{kv}^{(k - 1)}} {[f(x'{_e}) - f({x_e})]} $; //更新路径上链路的权重,并求和

15              $ d_{uv}^k \leftarrow {\text{min}}(d_{uv}^{(k - 1)}, d_{uk}^{(k - 1)} + d_{kv}^{(k - 1)})$; //选出能耗增量值较小的路径

16               $ d_{uv}^k \leftarrow {\text{min}}(p_{uv}^{(k - 1)}, p_{uk}^{(k - 1)} \cup p_{kv}^{(k - 1)})$; //更新当前最短路径

17              End if

18            End for

19           End for

20        End for//以自底向上的方式递归寻路

21        For eppiqin do

22              f(xe)←f(xe); //选完路之后,仅更新最短路径上的网络负载

23        End for

24        Return si(t),pippiqin,Δϕidpiqin; //返回新流ji的传输速率、传输路径以及网络能耗增量

在算法2速率计算模块,首先第1行选取新流的可传输时间段作为调度区间,在计算之前,第2行先获取puk(k-1)pkv(k-1)路径上同一时间的不同链路带宽占有的最高值A(t),将其转化为单链路的时间均衡问题.接下来的3行定义一个参数平均带宽M=(可调度区间占用的总带宽+新流的带宽)/可调度区间.不难看出,当A(t)>M时,表示此时刻不能传输新流.接着第4~13行通过反复计算,剔除高于平均带宽的区间,直到找出可传输的区间.最后第14~17行通过平均带宽减去已占用带宽即可得到ji的传输速率,并输出.

算法2  速率计算

输入:  G=(V, E), ji, 网络的邻接矩阵W,最短路径权重矩阵D以及路径p.

输出:  ji的传输速率si(t).

1   T=[ri, di]; //可调度的时间区间

2   A(t)←max(xe(t)), tT; //得到puk(k-1)pkv(k-1)路径上同一时间不同链路带宽占有的最高值

3    $M = \left( {\smallint _{{r_i}}^{{d_i}}A\left( t \right){\text{d}}t + {b_i}} \right)/T $; //计算平均带宽

4   Repeat//剔除高于平均带宽的区间,直到找出可调度的区间

5    For tT

6       If A(t)≥M then

7        T′←t;

8        TTT′;

9       End if

10     End for

11    A(t)←max(xe(t)), tT;

12     $ M = \left( {\smallint _{{r_i}}^{{d_i}}A\left( t \right){\text{d}}t + {b_i}} \right)/T$;

13   Until A(t) < M < βC

14   For t=ri to di

15         si(t)=MA(t);

16   End for //计算ji的速率

17   输出ji的传输速率si(t)

2.2 局部重路由策略

经过观察发现,有时整个网络容量虽然够大,由于按照最节能的策略为流选取路径,所以理论上改变之前流的传输路径,能够给后来的流在空间上和时间上腾出余地.因此为了提高流的接受率,同时考虑与节能效果、重新调度引起的开销之间的均衡,可以对局部流进行重新调度.开销主要考虑由局部流重路由带来的控制通信开销,可简化为重路由的流的数目来表示.网络中流量非常大的情况下,开销会非常大.因此为了降低重新调度的开销,提出局部流重路由策略.和新流有着相同源和目的地的流可作为首选的重路由对象,因此主要选取有相同源点和目的节点的流作为局部流,并且继续使用2.1节所提的算法为局部流和新到达的流计算节能QoS路由.

2.3 算法步骤

综上所述,采用Floyd-Warshall算法和局部重路由策略来求解SD-DCN数据流的节能QoS路由优化问题.具体步骤如下:

步骤1   排队:控制器首先对当前到达的集合J里的流,根据截止时间从早到晚进行排序.

步骤2  对集合中排序最小的流寻路. 1)计算单个链路权重.控制器获取当前网络拓扑和负载情况,并计算每条链路是否具备传输新流的能力,并由式(7)计算能耗增量. 2)使用2.1节中的Floyd-Warshall算法寻找节能QoS路径. 3)如果成功,则输出新流的最短路径、传输速率,跳到步骤4;反之,则跳到步骤3,调用局部重路由策略.

步骤3  局部重路由.

1) 对和此新流具有相同起始交换机和目的交换机的所有正在传输的流组成新的集合J′;

2) 对集合J′里的流,参考步骤1,首先根据截止时间早晚排序;

3) 使用2.1节中的Floyd-Warshall算法依次重新进行选路;

4) 如果集合J′里的流均成功找到路径,则通知控制器进行路由优化;反之,则放弃新流的请求.

步骤4  返回步骤2继续为后续流选路,直到集合J为空结束.

3 仿真结果

在Windows7系统下,使用Matlab仿真软件进行编程实现所提算法,硬件平台配置为1块2.4GHz CPU,64GB内存.选取Fat-tree数据中心网络拓扑,包括20个4端口的交换机、16个主机和48条链路.能耗函数中α设置为2,网络链路带宽C设置为180Mbit/s,β设置为0.9.分别使用QoS节能算法、局部重路由算法、独占式算法和离线算法(共享式)这4种算法,对比流经过网络的能耗情况以及流的接受率.

为了更好地显示算法的效果,同时鉴于硬件条件限制,对8~64条工作流进行模拟,且仿真结果只给出交换机端口速率相关的部分功率和能耗值.首先选取8条工作流的开始时间和截止时间在[0, 16]s内服从随机分布,流的大小在[40,200]MB区间服从一致分布.采用不同的4种路由算法来计算网络的能耗情况,如图 3~图 5所示. 图 3表示网络的实时功率,可以明显看到,和其他3种算法相比,因为使用独占式算法的流在时间上传输不均衡,且有丢弃的流,所以端口功率在时间上起伏较大.其他3种均为共享式算法,能耗是随着新流的到来而变化的.其中节能QoS算法放弃了一条流,所以和其他两种相比,中间能耗较低.局部重路由和离线算法对所有流进行传输,传输顺序有些许差异,所以能耗值也有些许差异.

图 3 实时能耗

图 4 能耗增量

图 5 能耗总量

图 4的横坐标表示每条工作流的序号,纵坐标代表新流到来所带来的能耗增量.独占式算法所带来的能耗增量要高于节能QoS算法和局部重路由算法所引起的能耗增量.通过对比图 4中局部重路由与节能QoS算法的曲线可以发现,在横坐标等于3时,后者能耗值不变,前者能耗值增高,是因为第4条流到来时,使用了局部重路由策略.独占式算法的能耗值比其他3种算法的能耗值皆高.离线算法因为按照工作流的截止时间对流进行了重新排序,所以能耗值时而高时而低.

图 5给出了4种算法在8条流的整个传输区间的总体能耗,可以看出独占算法>局部重路由算法>离线算法>节能QoS算法.局部重路由算法比节能QoS算法提高了接受率,所以能耗值较大;同时,因为其重调度的范围较小,相比离线算法,其能耗值也较大.

对不同规模的4组工作流(分别是8条、16条、32条、64条)分别使用4种算法进行仿真,以验证网络对工作流的接受情况.如图 6所示,独占式算法的接受率是最低的,其次是节能QoS算法.随着工作流规模的上升,网络拓扑中的流量强度逐渐增大,链路负载增加,链路容量接近其最大值.未进行重路由的节能QoS算法的接受率逐渐下降,而进行重路由的局部重路由算法以及离线算法的工作流接受率保持在一个大于95%的较高值.

图 6 流的接受率
4 结束语

针对基于时延和能耗的数据中心网络路由优化问题,在数据中心网络拓扑、交换机以及其相关端口开关与否都已确定的场景下,基于空间和时间上均衡可以降低能耗的原理,提出一种Floyd-Warshall动态规划方法和局部重路由策略的QoS路由优化方法,在线依次为每个流选择最优传输方案.本方法以较少的开销,有效地保证了流的时延性能,降低了网络能耗,同时提高了网络接受率.

参考文献
[1]
Andrews M, Anta A, Zhang L, et al. Routing for power minimization in the speed scaling model[J]. IEEE/ACM Trans Netw, 2012, 20(1): 285-294.
[2]
Fan K, Wang Y, Ba J, et al. An approach for energy efficient deadline-constrained flow scheduling and routing[C]//2019 IFIP/IEEE Symposium on Integrated Network and Service Management (IM). Arlington: IEEE Press, 2019: 469-475.
[3]
Yao Z, Wang Y, Ba J, et al. Deadline-aware and energy-efficient dynamic flow scheduling in data center network[C]//International Conference on Network and Service Management. Roma: IEEE Press, 2018: 1-4. https://www.researchgate.net/publication/322511190_Deadline-aware_and_energy-efficient_dynamic_flow_scheduling_in_data_center_network
[4]
Ba J, Wang Y, Zhong, S X, et al. An SDN energy saving method based on topology switch and rerouting[C]//2018 IEEE/IFIP Network Operations and Management Symposium. Taipei: IEEE Press, 2018: 1-5.
[5]
Fernandez-Fernandez A, Cervello-Pastor C, Ochoa-Aday L. Achieving energy efficiency: an energy-aware approach in SDN[C]//2016 IEEE Global Communications Conference (GLOBECOM). Washington, DC: IEEE Press, 2016: 1-7. https://www.researchgate.net/publication/313456588_Achieving_Energy_Efficiency_An_Energy-Aware_Approach_in_SDN
[6]
Wu Z, Ji X, Wang Y, et al. An energy-aware routing for optimizing control and data traffic in SDN[C]//2018 26th International Conference on Systems Engineering (ICSEng). Sydney: IEEE Press, 2018: 1-4.
[7]
Chen Y, Chin T, Huang C, et al. Time efficient energy-aware routing in software defined networks[C]//2018 IEEE 7th International Conference on Cloud Networking (CloudNet). Tokyo: IEEE Press, 2018: 1-7. https://www.researchgate.net/publication/329318458_Time_Efficient_Energy-Aware_Routing_in_Software_Defined_Networks
[8]
Heller B, Seetharaman S, Mahadevan P, et al. ElasticTree: saving energy in data center networks[C]//Nsdi. San Jose: [s. n.], 2010: 249-264. https://www.researchgate.net/publication/220831932_ElasticTree_Saving_Energy_in_Data_Center_Networks
[9]
Xu G, Dai B, Huang B, et al. Bandwidth-aware energy efficient flow scheduling with SDN in data center networks[J]. Future Generation Computer Systems, 2017, 68: 163-174.
[10]
Wang L, Zhang F, Zheng K, et al. Energy-efficient flow scheduling and routing with hard deadlines in data center networks[C]//2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS). Madrid: IEEE Press, 2014: 248-257. http://www.oalib.com/paper/4046296