互联网智能路由架构及算法

doi:10.11959/j.issn.1000-0801.2020285

电信科学 ›› 2020, Vol. 36 ›› Issue (10): 12-20.doi: 10.11959/j.issn.1000-0801.2020285

互联网智能路由架构及算法

桂飞,程阳,李丹,洪思虹

清华大学，北京 100084

修回日期:2020-10-10 出版日期:2020-10-20 发布日期:2020-11-07
作者简介:桂飞（1994- ），男，清华大学博士生，主要研究方向为智能网络|程阳（1992- ），男，清华大学博士生，主要研究方向为高性能网络系统的设计与优化、分布式机器学习系统|李丹（1981- ），男，博士，清华大学教授、博士生导师，主要研究方向为数据中心网络、网络智能和可信任互联网。入选教育部“青年长江学者”奖励计划，获得国家优秀青年基金项目资助，国家“973”项目首席科学家，国家重点研发计划项目负责人。IEEE Transactions on Computers、IEEE Transactions on Wireless Communications等国际学术期刊编委，ACM SIGCOMM、IEEE INFOCOM等国际学术会议程序委员会委员|洪思虹（1997- ），女，清华大学硕士生，主要研究方向为网络智能传输算法以及网络智能路由算法
基金资助:
国家重点研发计划项目(2018YFB1800500);国家自然科学基金资助项目(61772305);广东省重点研发计划项目(2018B010113001)

Internet intelligent routing architecture and algorithm

Fei GUI,Yang CHENG,Dan LI,Sihong HONG

Tsinghua University,Beijing 100084,China

Revised:2020-10-10 Online:2020-10-20 Published:2020-11-07
Supported by:
The National Key Research and Development Programs of China(2018YFB1800500);The National Natural Science Foundation of China(61772305);Guangdong Provencal Key Research and Development Programs(2018B010113001)

摘要/Abstract

摘要：

突发流量在网络中非常普遍，会严重损害用户体验。突发流量往往能在短时间（如毫秒级别）内充满链路，导致网络拥塞和频繁分组丢失，端到端时延增加。传统路由算法要么是流量无关（如 OSPF（open shortest path first，开放式最短路径优先））的，无法对实时流量的变化做出调整；要么是集中式控制的（如线性规划），面临求解时延过大而无法有效应对突发流量的问题。提出了一种新的智能路由算法解决突发流量的问题。一方面，提出的算法能利用机器学习强大的建模能力，通过对网络历史数据的挖掘来学习“隐式”的路由决策依据。另一方面，提出的算法能借助机器学习的快速推理能力降低决策时延，提高系统对突发流量的响应速度。实验结果表明，在真实流量数据集下，相比较其他路由算法，提出的智能路由算法能降低13%～70%的瓶颈链路利用率。

关键词: 互联网路由算法, 突发流量, 机器学习, 深度强化学习

Abstract:

Traffic bursts are common in networks, which have a significant impact on quality of user experience. In the case of traffic bursts, huge volumes of packets can overwhelm the physical links in a short time duration(i.e., milliseconds), resulting in congestion and frequent packet loss. However, traditional routing schemes are either traffic oblivious such as OSPF, which can’t adapt to real-time traffic changes, or centralized control such as linear programming, which can’t efficiently react to traffic bursts due to slow computation. To address this problem in a practical and efficient approach, a novel intelligent routing algorithm based on machine learning (ML) was proposed. On the one hand, the proposed algorithm can leverage the promising modelling ability of machine learning to learn the implicit clue of routing decision. On the other hand, the proposed algorithm enjoys the ultralow processing latency benefited from the fast inference of ML, thus speeding up the reaction to traffic bursts. Experiments on two open-source datasets demonstrate that the proposed scheme can reduce utilization of bottleneck link by 13%～70%, compared with the baselines.

Key words: internet routing algorithm, traffic burst, machine learning, deep reinforcement learning

中图分类号:

TN915

桂飞,程阳,李丹,洪思虹. 互联网智能路由架构及算法[J]. 电信科学, 2020, 36(10): 12-20.

Fei GUI,Yang CHENG,Dan LI,Sihong HONG. Internet intelligent routing architecture and algorithm[J]. Telecommunications Science, 2020, 36(10): 12-20.

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 29

[1]	BOGLE J , BHATIA N , GHOBADI M ,et al. TEAVAR:striking the right utilization-availability balance in WAN traffic engineering[C]// Proceedings of the ACM Special Interest Group on Data Communication. New York:ACM Press, 2019: 29-43.
[2]	HONG C Y , KANDULA S , MAHAJAN R ,et al. Achieving high utilization with software-driven wan[C]// Proceedings of 2013 ACM SIGCOMM Computer Communication Review. New York:ACM Press, 2013.
[3]	KUMAR P , YUAN Y , YU C ,et al. Semi-oblivious traffic engineering:the road not taken[C]// Proceedings of 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18).[S.l.:s.n]. 2018.
[4]	IETF. Analysis of an equal-cost multi-path algorithm:RFC 2992[S]. 2000.
[5]	FORTZ B , THORUP M . Internet traffic engineering by optimizing OSPF weights[C]// Proceedings of IEEE INFOCOM’ 2000. Piscataway:IEEE Press, 2000.
[6]	APPLEGATE D , COHEN E . Making routing robust to changing traffic demands:algorithms and evaluation[J]. IEEE/ACM Transactions on Networking (TON), 2006,14(6): 1193-1206.
[7]	HAO W , XIE H Y , QIU L L ,et al. COPE:traffic engineering in dynamic networks[C]// Proceedings of 2006 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications.[S.l.:s.n]. 2006.
[8]	ZHANG Y C , TIAN Y , WANG W D ,et al. Federated routing scheme for largescale domain network[C]// Proceedings of IEEE International Conference on Computer Communications poster (Infocom’2020). Piscataway:IEEE Press, 2020.
[9]	FONTUGNE R , ABRY P , FUKUDA K ,et al. Scaling in internet traffic:a 14 year and 3 day longitudinal study[J]. ACM Transaction on Networking, 2017
[10]	XenaNetworks.Microburst[R]. 2019.
[11]	JIANG H , DOVROLIS C . Why is the internet traffic bursty in short time scales?[C]// Proceedings of Sigmetric. New York:ACM Press, 2005.
[12]	KAPOOR R , SNOEREN A C , VOELKER G M ,et al. Bullettrains:a study of NIC burst behavior at microsecond timescales[C]// Proceedings of 9 th ACM Conference on Emerging Networking Experiments ＆ Technologies. New York:ACM Press, 2013.
[13]	HUANG Q , LEE P C , BAO Y G . SketchLearn:relieving user burdens in approximate measurement with automated statistical inference[C]// Proceedings of ACM SIGCOMM 2018. New York:ACM Press, 2018.
[14]	HUANG Q , SUN H F , LEE P C ,et al. OmniMon:re-architecting network telemetry with resource efficiency and full accuracy[C]// Proceedings of ACM SIGCOMM 2020. New York:ACM Press, 2020.
[15]	CHEN X , HUANG Q , ZHANG D ,et al. ApproSync:approximate state synchronization for programmable networks[C]// Proceedings of IEEE ICNP 2020. Piscataway:IEEE Press, 2020.
[16]	CHEN X , LIU H Y , HUANG Q ,et al. SPEED:scalable and high-performance deployment for data plane programs[C]// Proceedings of IEEE ICNP 2020. Piscataway:IEEE Press, 2020.
[17]	SRIKANTH K , PADHYE J , BAHL V . Flyways to De-Congest data center networks[C]// Proceedings of Hotnet 2009.[S.l.:s.n]. 2009.
[18]	LIU X , SRIDHARAN A , MACHIRAJU S ,et al. Experiences in a 3G network:interplay between the wireless channel and applications[C]// Proceedings of ACM International Conference on Mobile Computing ＆ Networking. New York:ACM Press, 2008.
[19]	BENSON T , ANAND A , AKELLA A ,et al. MicroTE:fine grained traffic engineering for data centers[C]// Proceedings the Seventh Conference on emerging Networking Experiments and Technologies 2011.[S.l.:s.n]. 2011.
[20]	VALADARSKY A , SCHAPIRA M , SHAHAF D ,et al. Learning to route[C]// Proceedings of the 16th ACM Workshop on Hot Topics in Networks. New York:ACM Press, 2017.
[21]	BOYAN J A , LITTMAN M L . Packet routing in dynamically changing networks:A reinforcement learning approach[C]// Proceedings of the 6th International Conference on Neural Information Processing Systems 1993. New York:ACM Press, 1994.
[22]	PINYOANUNTAPONG P , LEE M , WANG P . Delay-optimal traffic engineering through multi-agent reinforcement learning[C]// Proceedings of IEEE INFOCOM 2019 Workshop on Network Intelligence(NI 2019)Machine Learning for Networking. Piscataway:IEEE Press, 2019.
[23]	XU Z Y , TANG J , MENG J S ,et al. Experience-driven networking:a deep reinforcement learning based approach[C]// Proceedings of IEEE Conference on Computer Communications (IEEE INFOCOM 2018). Piscataway:IEEE Press, 2018.
[24]	蔡鑫, 娄京生 . 基于LSTM深度学习模型的中国电信官方微博用户情绪分析[J]. 电信科学, 2017,33(12): 136-141.
	CAI X , LOU J S . Sentiment analysis of telecom official micro-blog users based on LSTM deep learning model[J]. Telecommunications Science, 2017,33(12): 136-141.
[25]	GIBNEYE. Google AI algorithm masters ancient game of Go[J]. Nature News, 2016,529(7587):445.
[26]	LOWE R , WU Y , TAMAR A ,et al. Multi-agent actor-critic for mixed cooperative-competitive environments[C]// Proceedings of Advances in Neural Information Processing Systems.[S.l.:s.n]. 2017.
[27]	FOERSTER J , FARQUHAR G , AFOURAS T ,et al. Counterfactual multi-agent policy gradients[C]// Proceedings of AAAI 2018.[S.l.:s.n]. 2018.
[28]	ZHANG Y . 6 months of abilene traffic matrices[Z].2004. 2004.
[29]	UHLIG S , QUOITIN B , LEPROPRE J ,et al. Providing publicintradomain traffic matrices to the research community[C]// Proceedings of ACM SIGCOMM Computer Communication Review. New York:ACM Press, 2006.

互联网智能路由架构及算法

Internet intelligent routing architecture and algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 29

相关文章 15

Metrics

推荐阅读 0

[1]	郭泽华, 朱昊文, 徐同文. 面向分布式机器学习的网络模态创新[J]. 电信科学, 2023, 39(6): 44-51.
[2]	胡珈玮, 刘晓谦, 唐昕柯, 董宇涵. 基于DQN的UUV辅助水下无线光通信轨迹规划系统[J]. 电信科学, 2023, 39(5): 42-47.
[3]	廖熙雯, 冷甦鹏, 明昱君, 李天扬. 基于数字孪生的城市交通流智能预测与导引策略[J]. 电信科学, 2023, 39(3): 70-79.
[4]	刘雅琼, 吕哲, 赵亚飞, 寿国础. AI技术在卫星通信/互联网领域的应用综述[J]. 电信科学, 2023, 39(2): 10-24.
[5]	康宇, 刘雅琼, 赵彤雨, 寿国础. AI算法在车联网通信与计算中的应用综述[J]. 电信科学, 2023, 39(1): 1-19.
[6]	章坚武, 安彦军, 邓黄燕. DNS攻击检测与安全防护研究综述[J]. 电信科学, 2022, 38(9): 1-17.
[7]	邓丹昊, 王朝炜, 江帆, 王卫东. 无人机辅助无蜂窝大规模MIMO中的空地协同调度[J]. 电信科学, 2022, 38(8): 37-44.
[8]	周志超, 冯毅, 夏小涵, 冯瑜瑶, 蔡超, 邱佳慧, 杨立辉, 乌云霄. 基于移动蜂窝网的机器学习室外指纹定位方案[J]. 电信科学, 2021, 37(8): 85-95.
[9]	伍仲丽, 曹园园, 黄文睿, 戴彬, 莫益军. 面向确定性网络的按需智能路由技术[J]. 电信科学, 2021, 37(11): 11-16.
[10]	李想,李原,张子飞,杨哲. 基于密度聚类的网络性能故障大数据分析方法[J]. 电信科学, 2020, 36(9): 51-58.
[11]	肖子玉. 面向2030的未来网络关键技术综述——Beyond 5G[J]. 电信科学, 2020, 36(9): 114-121.
[12]	邱亚星,王希栋,边森,岳磊. 基于聚类分析和深度学习的多频多模网络负载均衡优化[J]. 电信科学, 2020, 36(7): 156-162.
[13]	欧阳晔,杨爱东,孟凡语. 一种博弈论辅助的机器学习算法检测用户流失行为[J]. 电信科学, 2020, 36(6): 79-89.
[14]	林锋,徐柳婧,陈晓华,戚伟强,陈可,朱添田. 一种基于多视角特征融合的Webshell检测方法[J]. 电信科学, 2020, 36(6): 125-132.
[15]	盛剑涛,陈茂飞,刘东鑫,汪来富,史国水,金华敏. 基于组合分类器的恶意域名检测技术[J]. 电信科学, 2020, 36(5): 47-55.