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

doi:10.3969/j.issn.1000-5641.2019.02.008

Journal of East China Normal University(Natural Sc ›› 2019, Vol. 2019 ›› Issue (2): 69-76,96.doi: 10.3969/j.issn.1000-5641.2019.02.008

• Computer Science • Previous Articles Next Articles

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

CLC Number:

TP393

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Yaqin HU, Ming TANG. The impact of coupling patterns on transport in multilayer networks [J]. Journal of East China Normal University(Natural Science), 2021, 2021(3): 105-113.
[2]	MA Fei, YAO Bing. One scale-free network model based on two different preferential attachment probabilities [J]. Journal of East China Normal University(Natural Sc, 2017, 2017(6): 42-49.
[3]	ZHANG Hui;YI Fasheng . Fuzzy control based DCA algorithm [J]. Journal of East China Normal University(Natural Sc, 2009, 2009(4): 107-114.