基于图卷积神经网络的智能路由算法

doi:10.19678/j.issn.1000-3428.0060768

摘要/Abstract

摘要： 使用特定数学模型的路由转发算法难以满足用户多样化的服务质量需求，基于深度学习的智能路由方案因具有准确性、高效性、通用性等优势，成为路由决策的发展方向。然而，目前多数智能路由算法在网络拓扑动态变化时需要重新训练，造成路由更新不及时，难以应对网络拓扑动态变化。提出一种基于图卷积神经网络（GCN）的智能路由算法。线下利用提前采集的网络信息，根据路由开销标签训练GCN智能路由模型，通过该模型输出单跳路由开销。线上采集实时信息并根据模型输出的路由开销结果对网络层路由协议进行调整，计算最小路由开销的路由路径，实现自适应网络更新。算法利用GCN的图数据结构处理不规则的网络拓扑，通过图卷积算子自动提取特征解决路由网络多属性参数提取的问题，同时引入模糊C均值算法进行网络状态离散化分析，为数据集生成标签，从而有效监督GCN模型训练。实验结果表明，该算法较ECMP、DRL-TE和SmartRoute算法路由性能更好，其平均丢包率、时延和吞吐量指标均为最优，且相较于单一的流量模式具有更强的泛化能力。

关键词: 深度学习, 图卷积神经网络, 智能路由, 模糊C均值聚类, 网络拓扑

Abstract: The routing and forwarding algorithm using a specific mathematical model struggles to meet the diversified quality of service required by users. The intelligent routing scheme based on deep learning has become the development direction of routing decision-making because of its advantages of accuracy, efficiency, and universality. However, currently, most intelligent routing algorithms need to be retrained when the network topology changes dynamically, resulting in untimely route updates and difficult-to-handle dynamic changes of network topology. In this study, an intelligent routing algorithm based on the Graph Convolutional Neural Network(GCN) framework is proposed. When offline, it uses the network information collected in advance to train the GCN intelligent routing model according to the routing overhead label. Then, the single hop routing overhead is output through the model. When online, it collects real-time information, adjusts the network layer routing protocol according to the routing overhead results output by the model, calculates the network routing path with the minimum routing overhead, and realizes automatic adaptation to network updates. The algorithm uses the graph data structure of GCN to deal with irregular network topologies and automatically extracts the features through the graph convolution operator to solve the problem of multi-attribute parameter extraction of the routing network. Meanwhile, the Fuzzy C-Means(FCM) algorithm is introduced to discretize the network state and generate labels for the data set to effectively supervise the training of GCN model. Experimental results demonstrate that the algorithm attains better routing performance than those of ECMP, DRL-TE, and SmartRoute algorithms. Furthermore, its average packet loss rate, delay, and throughput are the best among the compared algorithms, and it has stronger generalization ability compared to a single traffic mode.

Key words: Deep Learning(DL), Graph Convolutional Neural Network(GCN), intelligent routing, Fuzzy C-Means(FCM) clustering, network topology

中图分类号:

TP393.06

唐鑫, 徐彦彦, 潘少明. 基于图卷积神经网络的智能路由算法[J]. 计算机工程, 2022, 48(3): 38-45.

TANG Xin, XU Yanyan, PAN Shaoming. Intelligent Routing Algorithm Based on the Graph Convolutional Neural Network Framework[J]. Computer Engineering, 2022, 48(3): 38-45.

http://www.ecice06.com/CN/Y2022/V48/I3/38

图/表 12

20220330200426

20220330200429

20220330200433

20220330200436

20220330200441

20220330200444

20220330200448

20220330200451

20220330200455

20220330200458

20220330200502

20220330200506

参考文献

[1] GHORBANI S, YANG Z, GODFREY P B, et al.DRILL:micro load balancing for low-latency data center networks[C]//Proceedings of Conference of 2017 ACM Special Interest Group on Data Communication.New York, USA:ACM Press, 2017:225-238.
[2] 生龙, 马建飞, 杨瑞欣, 等.基于特征交换的CNN图像分类算法研究[J].计算机工程, 2020, 46(9):268-273. SHENG L, MA J F, YANG R X, et al.Research on CNN image classification algorithm based on feature exchange[J].Computer Engineering, 2020, 46(9):268-273.(in Chinese)
[3] 潘少明, 王玉杰, 种衍文.基于图卷积神经网络的跨域行人再识别[J].华中科技大学学报(自然科学版), 2020, 48(9):44-49. PAN S M, WANG Y J, CHONG Y W.Cross-domain person re-identification using graph convolutional networks[J].Journal of Huazhong University of Science and Technology (Natural Science Edition), 2020, 48(9):44-49.(in Chinese)
[4] 刘辰屹, 徐明伟, 耿男, 等.基于机器学习的智能路由算法综述[J].计算机研究与发展, 2020, 57(4):671-687. LIU C Y, XU M W, GENG N, et al.A survey on machine learning based routing alorithms[J].Journal of Computer Research and Development, 2020, 57(4):671-687.(in Chinese)
[5] MAO B, FADLULLAH Z M, TANG F, et al.Routing or computing?The paradigm shift towards intelligent computer network packet transmission based on deep learning[J].IEEE Transactions on Computers, 2017, 66(11):1946-1960.
[6] RAO Z, XU Y, PAN S.An intelligent routing method based on network partition[J].Computer Communications, 2020, 160(5):25-33.
[7] MAO B, FADLULLAH Z M, TANG F, et al.A tensor based deep learning technique for intelligent packet routing[C]//Proceedings of 2017 IEEE Global Communications Conference.Washington D.C., USA:IEEE Press, 2017:1-6.
[8] MAO B, TANG F, FADLULLAH Z M, et al.An intelligent packet forwarding approach for disaster recovery networks[C]//Proceedings of 2019 IEEE International Conference on Communications.Washington D.C., USA:IEEE Press, 2019:1-6.
[9] LU J, FENG L, YANG J, et al.Artificial agent:the fusion of artificial intelligence and a mobile agent for energy-efficient traffic control in wireless sensor networks[J].Future Generation Computer Systems, 2019, 95(12):45-51.
[10] 肖凯翔.基于机器学习的路由增强技术研究[D].成都:电子科技大学, 2019. XIAO K X.Routing enhancement technology research based on machine learning[D].Chengdu:University of Electronic Science and Technology, 2019.(in Chinese)
[11] 丁瑞金, 高飞飞, 邢玲.基于深度强化学习的物联网智能路由策略[J].物联网学报, 2019, 3(2):56-63. DING R J, GAO F F, XING L.Intelligent routing strategy in the Internet of things based on deep reinforcement learning[J].Chinese Journal on Internet of Things, 2019, 3(2):56-63.(in Chinese)
[12] TANG F, MAO B, FADLULLAH Z M, et al.On removing routing protocol from future wireless networks:a real-time deep learning approach for intelligent traffic control[J].IEEE Wireless Communications, 2018, 25(1):154-160.
[13] FABIEN G, GEORG C.Learning and generating distributed routing protocols using graph-based deep learning[C]//Proceedings of 2018 Workshop on Big Data Analytics and Machine Learning for Data Communication Networks.New York, USA:ACM Press, 2018:40-45.
[14] KIPF T N, WELLING M.Semi-supervised classification with graph convolutional networks[C]//Proceedings of the 5th International Conference on Learning Representations.Toulon, France:ICLR, 2017:1-10.
[15] MUSA N, GERHARD H, ADNAN A M.Software defined networking for improved wireless sensor network management:a survey[J].Sensors, 2017, 17(5):1031.
[16] 肖宇鹏, 何云斌, 万静, 等.基于模糊C-均值的空间不确定数据聚类[J].计算机工程, 2015, 41(10):47-52. XIAO Y P, HE Y B, WAN J, et al.Clustering of space uncertain data based on fuzzy C-means[J].Computer Engineering, 2015, 41(10):47-52.(in Chinese)
[17] HAO Y, LIU P Y, ZHANG L, et al.NS3-AI:enable applying artificial intelligence to network simulation in ns-3[C]//Proceedings of 2020 Workshop on ns-3.New York, USA:ACM Press, 2020:57-64.
[18] KRZYSZTOF R, JOSÉ S V, ALBERT M, et al.Unveiling the potential of graph neural networks for network modeling and optimization in SDN[C]//Proceedings of 2019 ACM Symposium on SDN Research.New York, USA:ACM Press, 2019:140-151.
[19] RHAMDANI F, SUWASTIKA N A, NUGROHO M A.Equal-cost multipath routing in data center network based on software defined network[C]//Proceedings of the 6th International Conference on Information and Communication Technology.Washington D.C., USA:IEEE Press, 2018:222-226.
[20] XU Z Y, TANG J, MENG J S, et al.Experience-driven networking:a deep reinforcement learning based approach[C]//Proceedings of 2018 IEEE Conference on Computer Communications.Washington D.C., USA:IEEE Press, 2018:1871-1879.
[21] 张鹏, 陈博.基于图神经网络的智能路由机制[J].计算机工程, 2021, 47(12):171-176, 184. ZHANG P, CHEN B.Intelligent routing mechanism based on graph neural networks[J].Computer Engineering, 2021, 47(12):171-176, 184.(in Chinese)

选择文件类型/文献管理软件名称

选择包含的内容