A redundancy elimination routing strategy to minimize network energy consumption
-
摘要: 拥有海量连接的5G网络中存在大量相同或相似的数据请求,造成网络带宽的严重浪费。因此,从消除冗余数据的角度出发,本文提出一种节能路由策略,用于解决流量高峰和低谷时期下网络流的路由路径选择问题;通过求解最小化网络能耗问题,进一步提出了一种流抢占路由算法。理论推导及仿真结果表明,本文提出的算法在流完成时间和活动链路数量方面均优于传统路由算法。Abstract: Due to the characteristics of massive connections, there are a large number of identical or similar data requests in the 5G network, resulting in a serious waste of network bandwidth. Therefore, from the perspective of eliminating redundant data, this paper proposes an energy-saving routing strategy to solve the problem of routing paths selection for network flows during traffic peaks and valleys. By solving the problem of minimizing network energy consumption, a flow preemption routing algorithm is proposed. The theoretical derivation and simulation results show that the proposed algorithm outperforms the traditional routing algorithm in terms of flow completion time and number of active links.
-
0. 引言
近年来5G网络快速发展,巨大的流量数据被上传到数据中心。为了处理类似多播流量[1-2]等被多个用户重复请求的数据,数据中心的能源消耗急剧增加[3-4]。目前,降低数据中心能耗的策略多从优化链路配置和动态路由等角度出发,如关闭或者睡眠不活动的网络元件[5-7],或者通过消除冗余来增加链路容量。然而,这些策略在降低网络能耗的同时也增加了路由器能耗。
为了平衡路由器能耗和网络能耗,许多研究开始引入软件定义网络(software defined network,SDN)技术[8-10]。SDN技术将网络由硬变软,通过软件代替手工编排,实现网络服务自动化的同时也使网络更加灵活扩展[11]。因此,节能的思想主要集中在通过SDN的集中式控制方式,为网络流量选择合适链路,使更多网络元件进入休眠,以达到节省能源的目的[12-13]。例如通过网络高负载时段提供的最大容量依次传输流量,以提高网络吞吐量并缩短平均流量完成时间[14]。虽然在节能上有了新的思路,但是却没有考虑到冗余数据的消除。
本文结合冗余消除(redundancy elimination,RE)与网络设备休眠,提出一种流抢占路由策略,为网络流找到最佳传输链路,同时使不活动的路由器设备进入休眠,来实现整个网络的能耗最小化。
1. 流抢占路由模型
在Fat-tree网络下,RE的流抢占路由策略基于SDN,将网络设备的控制面与数据面分离,由SDN控制器集中管理并控制网络中的路由传输、链路及流量状态。
假设此时网络中已经有$ k $个流正在被发送,当第$ k+1 $个流到达时,SDN控制器就需要为其选择合适的路由策略,使传输这$ k+1 $个流所需的网络总能耗最小。
如果用$ R $表示路由器集合,$ L=\left\{\right(I, j\left)\right|I, j\in R\} $表示两两路由器间的有向链路集合。二元变量$ {l}_{\left(i, j\right)} $表示链路$ \left(i, j\right) $是否活动,如果是则$ {l}_{\left(i, j\right)}=1 $,反之$ {l}_{\left(i, j\right)}=0 $。由此,制定最小化网络能耗问题计算式为
$$ \mathrm{m}\mathrm{i}\mathrm{n}\left\{{\sum }_{i\in R}^{}\left({P}_{R}+{N}_{i}{P}_{\mathrm{R}\mathrm{E}}\right){t}_{i}+{\sum }_{\left(i, j\right)\in L}^{}{l}_{\left(i, j\right)}{P}_{L}{t}_{\left(i, j\right)}\right\} \text{,} $$ (1) 式中:$ {t}_{i}、{t}_{\left(i, j\right)} $分别表示在传输这$ k+1 $个流时,路由器$ i $和链路$ \left(i, j\right) $的工作时间;$ {P}_{\mathrm{R}\mathrm{E}} $指路由器执行RE的能耗。
式(1)显示活动路由器、RE路由器和活动链路的能耗均是由自身的功率、有效工作时间以及自身数量构成。以上问题主要从活动网络设备的有效工作时间及自身数量2个角度来降低网络能耗。
2. 最小化问题求解
在上述模型中,如果遇到有些网络流的传输链路全部或部分相同的情况,通过一个接一个地没有时间重叠地传输网络流,可以降低$ {t}_{i}、{t}_{\left(i, j\right)} $。所以,式(1)描述的问题可简化为最小化活动链路和RE路由器的数量,以此来实现网络总能耗最小化目的。为此,路由器$ i $的RE功能用二元变量$ {e}_{i}、{d}_{i} $表示,若$ {e}_{i}=1 $则执行编码,$ {d}_{i}=1 $则执行解码。另外,$ {f}_{\left(i, j\right)}^{ab}、{g}_{\left(i, j\right)}^{ab} $分别表示链路$ \left(i, j\right) $上非冗余流和冗余流。综上所述,式(1)可以转换为
$$ \mathrm{m}\mathrm{i}\mathrm{n}\left\{{\sum }_{i\in R}^{}\left({e}_{i}+{d}_{i}\right)+{\sum }_{\left(i, j\right)\in L}^{}{l}_{\left(i, j\right)}\right\} \text{,} $$ (2) 具有如下约束:
$$ {\sum }_{(i, j)\in L}^{}{g}_{\left(i, j\right)}^{ab}-{\sum }_{\left(j, i\right)\in L}^{}{g}_{\left(j, i\right)}^{ab}\le {e}_{i} \text{,} $$ (3) $$ {\sum }_{\left(j, i\right)\in L}^{}{g}_{\left(j, i\right)}^{ab}-{\sum }_{(i, j)\in L}^{}{g}_{\left(i, j\right)}^{ab}\le {d}_{i} \text{,} $$ (4) $$ {f}_{\left(i, j\right)}^{ab}+{g}_{\left(i, j\right)}^{ab}\le {l}_{(i, j)}{C}_{(i, j)} \text{,} $$ (5) $$ {e}_{i}+{d}_{i}\le {\sum }_{(i, j)\in L}^{}{l}_{\left(i, j\right)} 。 $$ (6) 约束(3)和约束(4)分别用来确定路由器$ i $是否启用编码或解码功能。如果流入$ i $的编码流总量小于流出的编码流总量,那么$ i $启用了编码功能(即$ {e}_{i}=1 $),反之则启用了解码功能(即$ {d}_{i}=1 $)。约束(5)确保链路不会发生过载情况,即分配在活动链路$ \left(i, j\right) $上的所有流量之和不应该超过该活动链路的容量。约束(6)表示如果一个路由器$ i $被关闭,则该路由器上的RE功能也将不能使用。
式(2)是一个有约束的0-1线性规划问题,使用拉格朗日松弛法可将其转化为一个连续问题进行求解。首先构造式(2)的拉格朗日松弛问题
$$ \begin{array}{c}\mathrm{m}\mathrm{i}\mathrm{n}\mathscr{L}\left({e}_{i}, {d}_{i}, {l}_{\left(i, j\right)}, \alpha , \beta , \theta \right)= \\ \left\{{\sum }_{i\in R}\left({\alpha }_{i}-{\beta }_{i}\right)\left({\sum }_{(i, j)\in L}{g}_{\left(i, j\right)}^{ab}-{\sum }_{\left(j, i\right)\in L}{g}_{\left(j, i\right)}^{ab}\right)+ \\ {\sum }_{(i, j)\in L}{\theta }_{\left(i, j\right)}\left({f}_{\left(i, j\right)}^{ab}+{g}_{\left(i, j\right)}^{ab}\right)\right\}+\mathrm{m}\mathrm{i}\mathrm{n}\left\{{\sum }_{i\in R}\left(1-{\alpha }_{i}\right){e}_{i} + \\{\sum }_{i\in R}\left(1-{\beta }_{i}\right){d}_{i}+{\sum }_{(i, j)\in L}\left(1-{\theta }_{(i, j)}{C}_{(i, j)}\right){l}_{(i, j)}\right\} 。\end{array} $$ 那么该问题的拉格朗日对偶函数$ \mathrm{\delta }\left(\alpha , \beta , \theta \right)=\mathrm{m}\mathrm{i}\mathrm{n}\mathscr{L} $。
由于$ {e}_{i}、{d}_{i}、{l}_{ij} $的组合取值中只有{1,0,1},{0,1,1},{0,0,1}和{0,0,0}满足约束(6),因此得到显式的对偶函数。
当$ A={\sum }_{i\in R}\left({\alpha }_{i}-{\beta }_{i}\right)\left({\sum }_{(i, j)\in L}{g}_{\left(i, j\right)}^{ab}-{\sum }_{\left(j, i\right)\in L}{g}_{\left(j, i\right)}^{ab}\right)+{\sum }_{\left(i, j\right)\in L}{\theta }_{\left(i, j\right)}\left({f}_{\left(i, j\right)}^{ab}+{g}_{\left(i, j\right)}^{ab}\right) $时,
$$\begin{array}{c} \mathrm{\delta }\left(\alpha , \beta , \theta \right)=\mathrm{m}\mathrm{i}\mathrm{n}\mathscr{L}=\\A+\sum \limits_{i\in R}\sum \limits_{ij\in L}\mathrm{m}\mathrm{i}\mathrm{n}\{2-{\mathrm{\alpha }}_{i}-{\theta }_{\left(i, j\right)}{C}_{\left(i, j\right)}, \end{array} $$ $$ 2-{\beta }_{i}-{\theta }_{\left(i, j\right)}{C}_{\left(i, j\right)}, 1-{\theta }_{\left(i, j\right)}{C}_{\left(i, j\right)}, 0\}\mathrm{。} $$ (8) 由对偶性质得到原问题的对偶问题表述为$ \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{\delta }\left(\alpha , \beta , \theta \right) $,其中$ \alpha \ge 0 $,$ \beta \ge 0 $,$ \theta \ge 0 $。为了防止求解对偶问题的过程中出现不可微点,引入凝聚函数$ {F}_{\varepsilon }\left(x\right)=\varepsilon \mathrm{l}\mathrm{n}\left\{\sum\limits _{i=1}^{m}\mathrm{e}\mathrm{x}\mathrm{p}\left[{\varepsilon }^{-1}{f}_{i}\left(x\right)\right]\right\} $,则
$$\begin{array}{c} \mathrm{m}\mathrm{a}\mathrm{x}\stackrel{-}{\delta }\left(\alpha , \beta , \theta \right)= \\ A+{\sum }_{i\in R}^{}{\sum }_{ij\in L}^{}\varepsilon \mathrm{l}\mathrm{n}\left\{{\mathrm{e}}^{-{\varepsilon }^{-1}\left(2-{\alpha }_{i}-{\theta }_{\left(i, j\right)}{C}_{\left(i, j\right)}\right)}+\\{\mathrm{e}}^{-{\varepsilon }^{-1}\left(2-{\beta }_{i}-{\theta }_{\left(i, j\right)}{C}_{\left(i, j\right)}\right)}+{\mathrm{e}}^{-{\varepsilon }^{-1}\left(1-{\theta }_{\left(i, j\right)}{C}_{\left(i, j\right)}\right)}+1\right\} 。\end{array} $$ (9) 由于该凝聚函数与对偶函数满足$ 0\le \stackrel{-}{\delta }\left(\alpha , \beta , \theta \right)-\mathrm{\delta }\left(\alpha , \beta , \theta \right)\le \varepsilon \mathrm{l}\mathrm{n}4 $[15-16]。因此,当$ \mathrm{\varepsilon }\to 0 $时,$ \mathrm{m}\mathrm{a}\mathrm{x}\stackrel{-}{\delta }\left(\alpha , \beta , \theta \right) $的最优值近似于$ \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{\delta }\left(\alpha , \beta , \theta \right) $的最优值。接着,通过计算凸函数$ \stackrel{-}{\delta }\left(\alpha , \beta , \theta \right) $的一阶偏导得到$ {\alpha }_{i}、{\beta }_{i}、{\theta }_{\left(i, j\right)} $的表达式。最后,获得对偶问题的最优解,进一步根据式(8)推导出原-对偶关系。由于篇幅有限,本文省略了详细的推导过程。
3. 算法设计
本文采用流抢占路由算法来描述以上问题的求解过程。在该算法中,输入网络拓扑$ G\left(R, L\right) $、目标流量的$ {f}_{\left(i, j\right)}^{ab} $和$ {g}_{\left(i, j\right)}^{ab} $,就可以获取目标流量的最优路由路径,即$ {e}_{i}^{\mathrm{*}}\mathrm{、}{d}_{i}^{\mathrm{*}}\mathrm{、}{l}_{\left(i, j\right)}^{\mathrm{*}} $。
算法详细步骤:第1步,初始化$ {e}_{i}、{d}_{i}、{l}_{\left(i, j\right)}, $ $ \mathrm{设}\mathrm{定}\varepsilon > 0 $,$ k=0 $,$ \tau $为一个极小的正值,阈值$ \omega < 0 $。第2步,对于所有的$ i\in R $以及所有的$ \left(i, j\right)\in L $,都需要计算$ \stackrel{-}{\delta }\left(\alpha , \beta , \theta \right) $的一阶偏导,得到最优解$ {\alpha }^{\mathrm{*}}\mathrm{、}{\beta }^{\mathrm{*}}\mathrm{、}{\theta }^{\mathrm{*}} $,并且根据这些最优解进一步计算原-对偶关系式。第3步,将第2步求得的原-对偶关系式与阈值$ \omega $比较,得到$ {e}_{i}^{k}\mathrm{、}{d}_{i}^{k}\mathrm{、}{l}_{\left(i, j\right)}^{k} $。第4步,如果第3步的解$ {e}_{i}^{k}\mathrm{、}{d}_{i}^{k}\mathrm{、}{l}_{\left(i, j\right)}^{k} $同时满足约束(3)~(5),则将$ {e}_{i}^{k} $的值赋给$ {e}_{i}^{\mathrm{*}} $,$ {d}_{i}^{k}\mathrm{的}\mathrm{值}\mathrm{赋}\mathrm{给}{d}_{i}^{\mathrm{*}} $,$ {l}_{\left(i, j\right)}^{k}\mathrm{的}\mathrm{值}\mathrm{赋}\mathrm{给}{l}_{\left(i, j\right)}^{\mathrm{*}} $,输出$ {e}_{i}^{\mathrm{*}}\mathrm{、}{d}_{i}^{\mathrm{*}}\mathrm{、}{l}_{\left(i, j\right)}^{\mathrm{*}} $作为最终结果;否则就更新$ \omega \mathrm{和}k $的值,即$ {\omega }^{k+1}\leftarrow {\omega }^{k}+\mathrm{\tau } $,$ k\leftarrow k+1 $,并返回第3步重新计算$ {e}_{i}^{k}\mathrm{、}{d}_{i}^{k}\mathrm{、}{l}_{\left(i, j\right)}^{k} $,直到$ {\omega }^{k+1} $收敛于0,停止算法。
从该算法中不难看出,对于任意流量,确定其路由路径的时间复杂度是$ O\left(L\right) $,这是因为对于每条链路的活动与否都需要根据算法来判断。同样地,确定路由器是否编解码的时间复杂度是$ O\left(R\right) $。阈值$ \omega $从负数逐渐收敛到0需要有限次数(设为$ K $),因此该算法的总时间复杂度为$ O\left(K\left(R+L\right)\right) $。
4. 实验仿真
实验使用Mininet仿真平台[17-18]来搭建基于SDN的k阶Fat-Tree网络拓扑,并且使用Iperf工具生成数据流量。
不同冗余速率对比结果如图 1所示。算法在冗余速率($ \gamma $)分别为$ 50\mathrm{\%} $(高冗余)、$ 75\mathrm{\%} $(中冗余)和$ 90\mathrm{\%} $(低冗余)下的网络能耗节省。无论在流量冗余较高还是较低时,所提出的算法都可以聚合较多的流量需求,从而关闭更多的链路以节省能量。
不同网络规模对比结果如图 2所示。表明所提出算法在不同规模的Fat-Tree网络下的节能效果。设$ \gamma =50\mathrm{\%} $,并且网络大小分别为$ k=\mathrm{4, 8}, 16 $。随着网络规模的扩大,所提出算法的节能效果增加。在$ k=4 $网络中,当带宽/需求率相同时,所提出算法也比传统路由感知算法[19]更加节能。当然,随着容量/需求率的增长,由于节能的空间有限,所提出的算法会通过更早地完成流量传输来达到节能目的。
图 2 不同网络规模对比注:k为网络拓扑大小,EXR为文献[20]中的算法。5. 总结与展望
本文研究了Fat-tree网络中RE下的节能路由问题,即如何启用路由器的RE功能并为每个网络流找到最优的路由路径。制定了一个网络能耗最小化问题,并使用拉格朗日对偶的连续化方法将此优化问题转变为线性0-1规划问题,进而求解。最后,仿真实验表明本文提出的算法在冗余速率、网络规模等方面均具有明显的节能效果。
本文提出的路由方案不会影响服务器的能耗,原因为:(1)该方案主要考虑如何通过灵活选择路由路径来聚集流量,从而提高网络设备的利用率并降低网络能耗;(2)在该方案中服务器主要用于接收和发送网络流,不参与路由路径的选择。因此,该方案不会增加服务器的利用率,也不会在降低网络设备能耗的同时增加服务器能耗。
此外,在流量高峰时期频繁地切换网络设备的模式,可能会导致网络振荡和性能下降。为了解决这个问题,未来工作中可以考虑在边缘设备上进行网络流的缓存和流量整形,将分散到达的网络流先集中为多个突发流量组,再发送至网络,使网络设备尽可能地集中处理和转发网络流,从而减少设备的模式切换次数和延长休眠时间。与此同时,为了提高路由计算的实时性和可扩展性,拟进一步探讨分布式节能路由算法和网络流调度策略。
-
图 2 不同网络规模对比
注:k为网络拓扑大小,EXR为文献[20]中的算法。
-
[1] 钟掖, 龙玉江, 赵威扬, 等. 基于软件定义网络的电力云数据中心流量控制技术[J]. 科学技术创新, 2021(15): 80-81. https://www.cnki.com.cn/Article/CJFDTOTAL-HLKX202115037.htm [2] 杜鑫乐, 徐恪, 李彤. 数据中心网络的流量控制: 研究现状与趋势[J]. 计算机学报, 2021, 44(7): 1287-1309. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX202107001.htm [3] 蔺昊欣, 彭妍妍, 夏玉娟. 我国数据中心能耗评价方法标准综述[J]. 中国能源, 2020, 42(8): 36-39. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGLN202008015.htm [4] AHMED K M U, BOLLEN M H J, ALVAREZ M. A review of data centers energy consumption and reliability modeling[J]. IEEE Access, 2021(9): 152536-152563. [5] ZHAO Y, WANG X, HE Q, et al. Power-efficient software defined data center network[J]. IEEE Internet of Things Journal, 2021, 8(12): 10018-10033. doi: 10.1109/JIOT.2020.3048524 [6] AL-KASEEM B R, TAHA Z K, ABDULMAJEED S W, et al. Optimized energy-efficient path planning strategy in WSN with multiple mobile sinks[J]. IEEE Access, 2021(9): 82833-82847. [7] CHANG X, YANG S, JIANG Y, et al. Research on key energy-saving technologies in green data centers[C]//MEIKANG Q. 2020 IEEE international conference on smart cloud. Piscataway: IEEE, 2020: 111-115. [8] JAIN S, KUMAR A, MANDAL S, et al. B4: experience with a globally-deployed software defined WAN[C]//DAH M C. Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM. New York: ACM, 2013: 3-14. [9] FANG S, YU Y, FOH C H, et al. A loss-free multipathing solution for data center network using software-defined networking approach[J]. IEEE Transactions on Magnetics, 2013, 49(6): 2723-2730. doi: 10.1109/TMAG.2013.2254703 [10] COMER D, RASTEGARNIA A, REED WJ. DCLab: a reconfigurable SDN testbed for datacenter networks[J]. IEEE Networking Letters, 2020, 2(3): 145-148. doi: 10.1109/LNET.2020.3005902 [11] DIEGO K, FERNANDO M V R, PAULO E V, et al. Software-defined networking: a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14-76. [12] HUANG H, GUO S, LI P, et al. Cost minimization for rule caching in software defined networking[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(4): 1007-1016. [13] 曾悦. 软件定义数据中心网络中节能路由策略研究[D]. 重庆: 西南大学, 2019. [14] BALAKIRUTHIGA B, DEEPALAKSHMI P, MOHANTY S, et al. Segment routing based energy aware routing for software defined data center[J]. Cognitive Systems Research, 2020(64): 146-163. [15] 李艳艳, 李兴斯. 求解线性0-1规划的一种连续化方法[J]. 大连理工大学学报, 2009, 49(2): 299-302. https://www.cnki.com.cn/Article/CJFDTOTAL-DLLG200902024.htm [16] 胡贵平. 例谈拉格朗日乘数法解二元函数最值及推广[J]. 数学教学研究, 2021, 40(4): 62-63. https://www.cnki.com.cn/Article/CJFDTOTAL-SXJY202104015.htm [17] KETI F, ASKAR S. Emulation of software defined networks using mininet in different simulation environments[C]//AI-DABASS D. 20156th international conference on intelligent systems, modelling and simulation. Piscataway: IEEE, 2015: 205-210. [18] XIANG Z, SEELING P. Mininet: an instant virtual network on your computer[J]. Computing in Communication Networks, 2020: 219-230. [19] LI D, SHANG Y, HE W, et al. EXR: greening data center network with software defined exclusive routing[J]. IEEE Transactions on Computers, 2015, 64(9): 2534-2544.
下载: