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.
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 Science), 2019
, 2019(2)
: 69
-76,96
.
DOI: 10.3969/j.issn.1000-5641.2019.02.008
[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.