无标度网络局部信息的动态路由算法

doi:10.3969/j.issn.1000-5641.2019.02.008

华东师范大学学报(自然科学版) ›› 2019, Vol. 2019 ›› Issue (2): 69-76,96.doi: 10.3969/j.issn.1000-5641.2019.02.008

无标度网络局部信息的动态路由算法

韩定定¹, 柳康², 唐明²

1. 复旦大学信息科学与工程学院, 上海 200433;
2. 华东师范大学信息科学技术学院, 上海 200241

收稿日期:2018-03-02 出版日期:2019-03-25 发布日期:2019-03-27
作者简介:韩定定,女,教授,博士生导师,研究方向为复杂网络与智能信息处理.E-mail:ddhan@fudan.edu.cn.
基金资助:
国家自然科学基金（11875133）

Dynamic routing algorithm based on local information in a free-scale network

HAN Ding-ding¹, LIU Kang², TANG Ming²

1. School of Information Science and Technology, Fudan University, Shanghai 200433, China;
2. School of Information Science and Technology, East China Normal University, Shanghai 200241, China

Received:2018-03-02 Online:2019-03-25 Published:2019-03-27

摘要/Abstract

摘要： 提出了一个在无标度网络上基于局部信息的数据包路由算法，该路由算法引入两个可调参数α和β，分别调节度值与队列长度的路由偏好.通过调节这两个参数来改变网络的传输容量，并找到了该算法的最佳参数组合.对其他动态特性包括平均路由时间和流量负载也进行了相应研究.模拟仿真研究表明，该路由算法较传统的局部路由算法，不仅降低了网络的丢包率，而且提高了网络的传输能力.实证研究证明，基于局部信息的无标度网络动态路由算法对大规模通信网络的拥塞有一定的改善作用.

关键词: 无标度网络, 动态路由算法, 局部信息, 传输容量, 拥塞

Abstract: We proposed a packet routing algorithm with two tunable parameters, α and β, which control the routing preference of degree and queue length, respectively, based on local information in a scale-free network. By adjusting the parameters to change network transmission capability, we found an optimal combination of the two parameters.Other dynamic properties, including average packet travel time and traffic load were also studied. Simulation research showed that the proposed algorithm not only reducedpacket loss rates, but also improved transmission capability and alleviated traffic congestion. We also compared the algorithm with other classical routing algorithms, based on real networks, and the proposed algorithm also displayed good results.

Key words: scale-free network, dynamic routing algorithm, local information, transmission capability, congestion

中图分类号:

TP393

韩定定, 柳康, 唐明. 无标度网络局部信息的动态路由算法[J]. 华东师范大学学报(自然科学版), 2019, 2019(2): 69-76,96.

HAN Ding-ding, LIU Kang, TANG Ming. Dynamic routing algorithm based on local information in a free-scale network[J]. Journal of East China Normal University(Natural Sc, 2019, 2019(2): 69-76,96.

参考文献

[1] 韩定定, 钱江海, 马余刚. 实证研究复杂网络的拓扑与动力学行为[M]. 北京:北京大学出版社, 2012.
[2] QIAN J H, CHEN Q, HAN D D, et al. Origin of Gibrat law in internet:Asymmetric distribution of the correlation[J]. Physical Review E, 2014, 89(6):062808.
[3] FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the internet topology[J]. ACM Sigcomm Computer Communication Review, 1999, 29(4):251-262.
[4] SIGANOS G, FALOUTSOS M, FALOUTSOS P, et al. Power laws and the AS-level internet topology[J]. IEEE/ACM Transactions on Networking, 2003, 11(4):514-524.
[5] CHEN Q, QiIAN J H, HAN D D. Non-Gaussian behavior of the internet topological fluctuations[J]. International Journal of Modern Physics C, 2014, 25(5):1440012.
[6] 韩定定, 柳康, 陈超, 等. 基于空间活跃度网络的搜索算法研究[J]. 复杂系统与复杂性科学, 2017, 14(2):103-109.
[7] CHEN Q, QIAN J H, ZHU L, et al. Optimal temporal path on spatial decaying networks[J]. Journal of Applied Analysis & Computation, 2016, 6(1):30-37.
[8] CHEN Q, QIAN J H, ZHU L, et al. Optimal transport in time-varying small-world networks[J]. Physical Review E, 2016, 93(3):032321.
[9] GUIMERÀ R, ARENAS A, DÍAZGUILERA A, et al. Dynamical properties of model communication networks[J]. Physical Review E, 2002, 66(2 Pt 2):026704.
[10] ZHAO L, LAI Y C, PARK K, et al. Onset of traffic congestion in complex networks[J]. Physical Review E, 2005, 71(2):026125.
[11] KRIOUKOV D, FALL K, YANG X. Compact routing on internet-like graphs[C]//IEEE Conference on Computer Communications. IEEE, 2004:209-219.
[12] WANG W X, WANG B H, YIN C Y, et al. Traffic dynamics based on local routing protocol on a scale-free network[J]. Physical Review E, 2006, 73(2):026111.
[13] WANG W X, YIN C Y, YAN G, et al. Integrating local static and dynamic information for routing traffic[J]. Physical Review E, 2006, 74(2):016101.
[14] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 5439(286):509-512.
[15] TAN F, WU J, XIA Y, et al. Traffic congestion in interconnected complex networks[J]. Physical Review E, 2014, 89(6):062813.

无标度网络局部信息的动态路由算法

Dynamic routing algorithm based on local information in a free-scale network

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	胡亚琴, 唐明. 层间耦合关联对多层网络交通传输的影响[J]. 华东师范大学学报（自然科学版）, 2021, 2021(3): 105-113.
[2]	马飞, 姚兵. 基于两种不同择优概率下的无标度网络模型[J]. 华东师范大学学报(自然科学版), 2017, 2017(6): 42-49.
[3]	张辉;易发胜 . 基于模糊控制的TCP拥塞避免算法 [J]. 华东师范大学学报(自然科学版), 2009, 2009(4): 107-114.