基于代数连通度的域内节能路由算法

doi:10.11896/jsjkx.190600064

计算机科学 ›› 2020, Vol. 47 ›› Issue (4): 238-242.doi: 10.11896/jsjkx.190600064

基于代数连通度的域内节能路由算法

耿海军¹, 张雯祥¹, 尹霞²

1 山西大学软件学院太原030006;
2 清华大学计算机科学与技术系北京100084

收稿日期:2019-06-13 出版日期:2020-04-15 发布日期:2020-04-15
通讯作者: 耿海军(ghj123025449@163.com)
基金资助:
国家自然科学基金 (61702315);山西省高等学校科技创新项目(201802013);国家重点研发计划(2018YFB1800401)

Intra-domain Energy Efficient Routing Algorithm Based on Algebraic Connectivity

GENG Hai-jun¹, ZHANG Wen-xiang¹, YIN Xia²

1 School of Software Engineering,Shanxi University,Taiyuan 030006,China;
2 Department of Computer Science Technology,Tsinghua University,Beijing 100084,China

Received:2019-06-13 Online:2020-04-15 Published:2020-04-15
Contact: GENG Hai-jun,born in 1983,Ph.D,lecturer,is a member of China Computer Federation.His man research interests include future Internet architecture and routing algorithm.
Supported by:
This work was supported by the National Natural Science Foundation of China (61702315),Scientific and Technological Innovation Programs of Higher Education Institutions in Shanxi (201802013) and National Key R&D Program of China (2018YFB1800401).

摘要/Abstract

摘要： 通过节能路由算法减少网络能耗是网络中需要解决的一个关键性的科学问题。如今已有的节能方案都是在已知流量矩阵的前提下研究网络节能,由于实时流量难以获取,使得这些方案都难以在实际中部署。因此,文中提出一种基于代数连通度的域内节能方案(Intra-domain Energy Efficient Routing Scheme Based on Algebraic Connectivity,EERSBAC)。EERSBAC不需要网络中的实时流量矩阵,仅依靠网络中的拓扑结构就可以实现节能。首先,提出链路关键度模型,利用链路关键度模型计算出网络中所有链路的重要程度;然后,提出代数连通度模型,利用代数连通度模型可以定量的衡量网络的连通性能。实验结果表明,EERSBAC不仅能够降低网络能耗,而且具有较小的路径拉伸度。

关键词: 代数连通度, 节能路由, 链路关键度, 链路介数, 路径拉伸度

Abstract: Reducing network energy consumption through energy-efficient routing algorithm is a key scientific problem in the network.However,the existing energy-efficient routing algorithms are all based on the known traffic matrix,because the real-time traffic is difficult to obtain.Therefore,this paper proposed an intra-domain energy efficient routing scheme based on algebraic connectivity (EERSBAC).EERSBAC does not need the real-time traffic matrix in the network,but only relies on the topological structure of the network to achieve energy saving.Firstly,a link criticality model is proposed to calculate the importance of all links in the network.And then,an algebraic connectivity model is proposed to quantitatively measure the connectivity performance of the network.The experimental results show that EERSBAC not only reduce network energy consumption,but also has a smaller path stretch.

Key words: Algebraic connectivity, Energy efficient routing, Link betweenness, Link criticality, Path stretch

中图分类号:

TP393.2

耿海军, 张雯祥, 尹霞. 基于代数连通度的域内节能路由算法[J]. 计算机科学, 2020, 47(4): 238-242. https://doi.org/10.11896/jsjkx.190600064

GENG Hai-jun, ZHANG Wen-xiang, YIN Xia. Intra-domain Energy Efficient Routing Algorithm Based on Algebraic Connectivity[J]. Computer Science, 2020, 47(4): 238-242. https://doi.org/10.11896/jsjkx.190600064

参考文献

[1]GUPTA M,SINGH S.Greening of the Internet[C]//Proceedings of the ACM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications (SIGCOMM 2003).2003:19-26.
[2]JIA X,JIANG Y,GUO Z,et al.Intelligent Path Control for Energy-saving in Hybrid SDN Networks.Computer Networks,2018,131:65-76.
[3]KOCAOGLU M,MALAK D,AKAN O.Fundamentals of Green Communications and Computing:Modeling and Simulation.IEEE Computer Society Press,2012.
[4]XU M,SHANG Y,LI D,et al.Greening data center networks with throughput-guaranteed power-aware routing.Computer Networks,2013,57(15):2880-2899.
[5]YANG Y,WANG D,PAN D,et al.Wind blows,traffic flows:Green Internet routing under renewable energy[C]//Procee-dings of the IEEE Conference on Computer Communications (INFOCOM).2016:1-9.
[6]MINERAUD J,WANG L,BALASUBRAMANIAM S,et al.Hybrid renewable energy routing for ISP networks[C]//Proceedings of the IEEE Conference on Computer Communications (INFOCOM).2016:1-9.
[7]CHABAREK J ,SOMMERS J ,BARFORD P ,et al.PowerAwareness in Network Design and Routing[C]//Proceedings of the IEEE Conference on Computer Communications (INFOCOM).2008:457-465.
[8]CHIARAVIGLIO L,CIULLO D,MELLIA M,et al.Modeling sleep mode gains in energy-aware networks .Computer Networks,2013,57(15):3051-3066.
[9]ANDREWS M,ANTA A F,ZHANG L,et al.Routing for Energy Minimization in the Speed Scaling Model[C]//Conference on Information Communications.IEEE Press,2010:2435-2443.
[10]CHIARAVIGLIO L,CIANFRANI A,ROUZIC E L,et al.Sleep modes effectiveness in backbone networks with limited configurations.Computer Networks the International Journal of Computer & Telecommunications Networking,2013,57(15):2931-2948.
[11]ZHANG M,YI C,LIU B,et al.GreenTE:Power-aware trafficengineering[C]//The IEEE International Conference on Network Protocols.IEEE Computer Society,2010:21-30.
[12]CHIARAVIGLIO L,MELLIA M,NERI F.Minimizing ISPNetwork Energy Cost:Formulation and Solutions.IEEE/ACM Transactions on Networking,2012,20(2):463-476.
[13]YANG Y,XU M,WANG D,et al.A Hop-by-Hop RoutingMechanism for Green Internet.IEEE Transactions on Parallel & Distributed Systems,2016,27(1):2-16.
[14]ZHOU B,ZHANG F,WANG L,et al.HDEER:A Distributed Routing Scheme for Energy-Efficient Networking.IEEE Journal on Selected Areas in Communications,2016,34(5):1713-1727.
[15]MERRIS R.Laplacian matrices of graphs:a survey.Linear Algebra & Its Applications,1994,197-198(2):143-176.
[16]CUOMO F,CIANFRANI A,POLVERINI M,et al.Networkpruning for energy saving in the Internet.Computer Networks,2012,56(10):2317-2550.
[17]GENG H,SHI X,WANG Z,et al.A hop-by-hop dynamic distributed multipath routing mechanism for link state network.Computer Communications,2018,116:225-239.
[18]YANG Y,XU M,LI Q.Fast Rerouting Against Multi-LinkFailures Without Topology Constraint.IEEE/ACM Transactions on Networking,2017:1-14.
[19]GENG H,SHI X,YIN X,et al.Algebra and algorithms for multipath QoS routing in link state networks.Journal of Communications and Networks,2017,19(2):189-200.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于代数连通度的域内节能路由算法

Intra-domain Energy Efficient Routing Algorithm Based on Algebraic Connectivity

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0

[1]	张举, 王浩, 罗舒婷, 耿海军, 尹霞. 基于遗传算法的混合软件定义网络路由节能算法 Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm 计算机科学, 2020, 47(6): 236-241. https://doi.org/10.11896/jsjkx.191000139
[2]	苏凡军,杜可怡. WSNs中基于信任度的节能机会路由算法 Trust Based Energy Efficient Opportunistic Routing Algorithm in Wireless Sensor Networks 计算机科学, 2020, 47(2): 300-305. https://doi.org/10.11896/jsjkx.190100172
[3]	张举, 耿海军, 刘洁琦. 基于网络熵的域内节能路由方案 Intra-domain Energy Efficiency Routing Scheme Based on Network Entropy 计算机科学, 2019, 46(2): 76-80. https://doi.org/10.11896/j.issn.1002-137X.2019.02.012