计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 112-116.doi: 10.11896/j.issn.1002-137X.2018.04.017

• 网络与通信 • 上一篇    下一篇

基于有向无环图的互联网域内节能路由算法

耿海军,施新刚,王之梁,尹霞,尹少平   

  1. 山西大学软件学院 太原030006,清华大学网络科学与网络空间研究院 北京100048,清华大学网络科学与网络空间研究院 北京100048,清华大学计算机科学与技术系 北京100048,山西大学软件学院 太原030006
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家重点基础研究发展计划(“863”计划)基金资助

Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph

GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping   

  • Online:2018-04-15 Published:2018-05-11

摘要: 互联网在快速发展的过程中面临新的挑战,其中网络能耗问题尤为突出。学术界提出了大量用于 解决网络能耗问题 的方案,然而这些方案都考虑了网络中的实时流量数据,计算复杂度较高,不利于实际部署。对此,提出一种基于有向无环图的互联网域内节能路由算法(Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph,EEBDAG),该方法 利用有向无环图来解决因链路关闭造成的路由环路和网络性能下降等问题, 仅须考虑网络拓扑结构,不需要考虑网络中的实时流量数据 。实验结果表明,EEBDAG不仅具有较低的节能比率,而且具有较低的链路利用率,为ISP解决互联网节能问题提供了一种全新的方案。

关键词: 域内路由,能耗,绿色网络,有向无环图

Abstract: With the rapid development of Internet,it is facing lots of challenges,in which the problem of network energy consumption is particularly prominent.Therefore,the academics put forward a large number of schemes to solve the problem.However,all of these methods need to consider the real-time traffic data in the network,and the computation complexity is very high,which is inconvenient to the actual deployment.Therefore,this paper proposed an energy-efficient intra-domain routing algorithm based on directed acyclic graph,which merely relies on network topology,without traffic awareness.The proposed scheme builds a directed acyclic graph for each node in the network,for the purpose of avoiding routing loops and alleviating the network performance degradation caused by cutting off links.Experimental results show that EEBDAG not only has lower energy-saving ratio,but also has lower link utilization,which provides an efficient solution for the ISP solving the Internet energy saving problem.

Key words: Intra-domain routing,Energy consumption,Green network,Directed acyclic graph

[1] The Climate Group.Smart 2020:Enabling the low carbon economy in the information age[R].London,2008.
[2] LANGE C,KOSIANKOWSKI D,WEIDMANN R,et al.Energy Consumption of Telecommunication Networks and Related Improvement Options[J].IEEE Journal of Selected Topics inQuantum Electronics,2011,17(2):285-295.
[3] CLARK D.The design philosophy of the DARPA internet protocols [C]∥ACM SIGCOMM Computer Communication Review.1988:106-114.
[4] FISHER W,SUCHARA M,REXFORD J.Greening backbone networks:reducing energy consumption by shutting off cables in bundled links[C]∥Proceedings of the First ACM SIGCOMM Workshop on Green Networking.2010:29-34.
[5] MINERAUD J,WANG L,BALASUB RAMANI A M S,et al.Hybrid renewable energy routing for ISP networks[C]∥IEEE Conference on Computer Communications.2016:1-9.
[6] YANG Y,WANG D,PAN D,et al.Wind Blows,Traffic Flows:Green Internet Routing under Renewable Energy[C]∥IEEE Conference on Computer Communications.2016.
[7] CHIARAVIGLIO,LUCA,MELLIA M,et al.Minimizing ISPNetwork Energy Cost:Formulation and Solutions[J].IEEE/ACM Transactions on Networking,2012,20(2):463-476.
[8] LI Q,XU M,YANG Y,et al.Safe and Practical Energy-Efficient Detour Routing in IP Networks [J].IEEE/ACM Transactions on Networking,2014,22(6):1925-1937.
[9] ZHANG M,YI C,LIU B,et al.GreenTE:Power-aware traffic-engineering[C]∥IEEE International Conference on Network Protocols.IEEE Computer Society,2010:21-30.
[10] KRIST P.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]∥2015 IEEE 23rd International Conference on Network Protocols(ICNP).IEEE,2015:376-385.
[11] OHARA Y,IMAHORI S,METER R V.MARA:Maximum Alternative Routing Algorithm[C]∥Proceedings of IEEE INFOCOM.2009:298-306.
[12] KWONG K W,GAO L,ZHANG Z L,et al.On the feasibility and efficacy of protection routing in IP networks[J].IEEE/ACM Transactions on Networking,2011,19(5):1543-1556.
[13] SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel [J].IEEE/ACM Transactions on Networking,2016,12(1):2-16.
[14] http://www.cs.bu.edu/brite.
[15] Power Management for the Cisco 12000 Series Router.http://www.cisco.com/en/US/docs/ios/12_0s/feature/guide/12spower.html.
[16] CHABAREK J,SOMMERS J,BARFORD P,et al.Power-Awareness in Network Design and Routing[C]∥INFOCOM 2008.2008.
[17] RAHMAN M M,SAHA S,CHENGAN U,et al.IP Traffic Matrix Estimation Methods:Comparisons and Improvements[C]∥ICC 2006.2006:90-96.
[18] XU D H,CHIANG M,REXFORD J.Link-state routing withhop-by-hop forwarding can achieve optimal traffic engineering[C]∥INFOCOM 2008.2008:1717-1730.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .