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