Adaptive local routing strategy on a scale-free network

doi:10.1088/1674-1056/19/4/040513

中国物理B ›› 2010, Vol. 19 ›› Issue (4): 40513-040513.doi: 10.1088/1674-1056/19/4/040513

Adaptive local routing strategy on a scale-free network

任丰原¹, 刘锋², 赵寒², 李明², 朱衍波²

(1)Department of Computer Science and Technology,Tsinghua University, Beijing 100084, China; (2)School of Electronics and Information Engineering, Beihang University, Beijing 100191, China

收稿日期:2008-10-12 修回日期:2009-10-27 出版日期:2010-04-15 发布日期:2010-04-15
基金资助:
Project supported in part by the National Natural Science Foundation of China (Grant Nos.~60872011 and 60502017), the State Key Development Program for Basic Research of China (Grant Nos.~2009CB320504 and 2010CB731800), and Program for New Century Excelle

Adaptive local routing strategy on a scale-free network

Liu Feng(刘锋)^a)† Zhao Han(赵寒)^a), Li Ming(李明)^a), Ren Feng-Yuan(任丰原)^b), and Zhu Yan-Bo(朱衍波)^a)

^a School of Electronics and Information Engineering, Beihang University, Beijing 100191, China; ^b Department of Computer Science and Technology,Tsinghua University, Beijing 100084, China

Received:2008-10-12 Revised:2009-10-27 Online:2010-04-15 Published:2010-04-15
Supported by:
Project supported in part by the National Natural Science Foundation of China (Grant Nos.~60872011 and 60502017), the State Key Development Program for Basic Research of China (Grant Nos.~2009CB320504 and 2010CB731800), and Program for New Century Excelle

摘要/Abstract

摘要： Due to the heterogeneity of the structure on a scale-free network, making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult. In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination, an adaptive local routing strategy on a scale-free network is proposed, in which the node adjusts the forwarding probability with the dynamical traffic load (packet queue length) and the degree distribution of neighbouring nodes. The critical queue length of a node is set to be proportional to its degree, and the node with high degree has a larger critical queue length to store and forward more packets. When the queue length of a high degree node is shorter than its critical queue length, it has a higher probability to forward packets. After higher degree nodes are saturated (whose queue lengths are longer than their critical queue lengths), more packets will be delivered by the lower degree nodes around them. The adaptive local routing strategy increases the probability of a packet finding its destination quickly, and improves the transmission capacity on the scale-free network by reducing routing hops. The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.

Abstract: Due to the heterogeneity of the structure on a scale-free network, making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult. In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination, an adaptive local routing strategy on a scale-free network is proposed, in which the node adjusts the forwarding probability with the dynamical traffic load (packet queue length) and the degree distribution of neighbouring nodes. The critical queue length of a node is set to be proportional to its degree, and the node with high degree has a larger critical queue length to store and forward more packets. When the queue length of a high degree node is shorter than its critical queue length, it has a higher probability to forward packets. After higher degree nodes are saturated (whose queue lengths are longer than their critical queue lengths), more packets will be delivered by the lower degree nodes around them. The adaptive local routing strategy increases the probability of a packet finding its destination quickly, and improves the transmission capacity on the scale-free network by reducing routing hops. The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.

Key words: local routing, scale-free networks, preferential probability, traffic load

中图分类号: (Networks and genealogical trees)

89.75.Hc

02.50.Cw (Probability theory) 45.70.Vn (Granular models of complex systems; traffic flow)

刘锋, 赵寒, 李明, 任丰原, 朱衍波. Adaptive local routing strategy on a scale-free network[J]. 中国物理B, 2010, 19(4): 40513-040513.

Liu Feng(刘锋) Zhao Han(赵寒), Li Ming(李明), Ren Feng-Yuan(任丰原), and Zhu Yan-Bo(朱衍波). Adaptive local routing strategy on a scale-free network[J]. Chin. Phys. B, 2010, 19(4): 40513-040513.

参考文献 17

[1]	Watts D J and Strogatz S H 1998 Nature (London) 393 440
[2]	Albert R, Jeong H and Barabasi A L 1999 Nature (London) 401] 130
[3]	Jeong H, Mason S P and Barabasi A L 2001 Nature (London) 411] 41
[4]	Tadi B and Thurner S 2005 Physica A 346 183
[5]	Echenique P, Gardenes J G and Moreno Y 2004 Phys. Rev. E 70] 056105
[6]	Guimera R, Guilera A D, Redondo E V and Arenas A 2002 Phys. Rev. Lett. 89 248701
[7]	Tadi B and Thurner S and Rodgers G J 2004 Phys. Rev. E 69 036102
[8]	Danila B, Yu Y, Marsh J A and Bassler K E 2006 Phys. Rev. E 74 046106
[9]	Yan G, Zhou T, Fu Z Q and Wang B H 2006 Phys. Rev. E 73 046108
[10]	Hughes R D 1995 Random Walks: Random Walks and Random Environments] (Oxford: Clarendon) Vol. 1
[11]	Wang W X, Wang B H, Yin C Y, Xie Y B and Zhou T 2006 Phys. Rev. E 73 026111
[12]	Adamic L A, Lukose R M, Puniyani A R and Huberman B A 2001 Phys. Rev. E 64 046135
[13]	Kim B J, Yoon C N, Han S K and Jeong H 2002 Phys. Rev. E 65 027103
[14]	Moura A P S d, Motter A E and Grebogi C 2003 Phys. Rev. E 68 036106
[15]	Barabasi A L and Albert R 1999 Science 286 509
[16]	Guimera R, Arenas A, Guilera A D and Giralt F 2002 Phys. Rev. E 66 026704
[17]	Arenas A, Guilera A D and Guimera R 2001 Phys. Rev. Lett. 86 3196

Adaptive local routing strategy on a scale-free network

Adaptive local routing strategy on a scale-free network

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 17

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Fuzhong Nian(年福忠) and Xia Zhang(张霞). Topological phase transition in network spreading[J]. 中国物理B, 2023, 32(3): 38901-038901.
[2]	Yijun Ran(冉义军), Tianyu Liu(刘天宇), Tao Jia(贾韬), and Xiao-Ke Xu(许小可). A novel similarity measure for mining missing links in long-path networks[J]. 中国物理B, 2022, 31(6): 68902-068902.
[3]	Dan-Dan Zhao(赵丹丹), Wang-Xin Peng(彭王鑫), Hao Peng(彭浩), and Wei Wang(王伟). Effects of heterogeneous adoption thresholds on contact-limited social contagions[J]. 中国物理B, 2022, 31(6): 68906-068906.
[4]	Dong-Jie Qian(钱冬杰). Explosive synchronization in a mobile network in the presence of a positive feedback mechanism[J]. 中国物理B, 2022, 31(1): 10503-010503.
[5]	Yu-Wei Yan(严玉为), Yuan Jiang(蒋沅), Rong-Bin Yu(余荣斌), Song-Qing Yang(杨松青), and Cheng Hong(洪成). Cascading failures of overload behaviors using a new coupled network model between edges[J]. 中国物理B, 2022, 31(1): 18901-018901.
[6]	Fuzhong Nian(年福忠), Jingzhou Li(李经洲), and Xin Guo(郭鑫). Evolution mechanism of Weibo top news competition[J]. 中国物理B, 2021, 30(12): 128901-128901.
[7]	Dongli Duan(段东立), Tao Chai(柴涛), Xixi Wu(武茜茜), Chengxing Wu(吴成星), Shubin Si(司书宾), and Genqing Bian(边根庆). Identification of unstable individuals in dynamic networks[J]. 中国物理B, 2021, 30(9): 90501-090501.
[8]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[9]	Xiao-Long Peng(彭小龙) and Yi-Dan Zhang(张译丹). Contagion dynamics on adaptive multiplex networks with awareness-dependent rewiring[J]. 中国物理B, 2021, 30(5): 58901-058901.
[10]	Zi-Wei Yuan(袁紫薇), Chang-Chun Lv(吕长春), Shu-Bin Si(司书宾), and Dong-Li Duan(段东立). Dynamical robustness of networks based on betweenness against multi-node attack[J]. 中国物理B, 2021, 30(5): 50501-050501.
[11]	. [J]. 中国物理B, 2021, 30(4): 48901-.
[12]	. [J]. 中国物理B, 2020, 29(12): 128901-.
[13]	. [J]. 中国物理B, 2020, 29(12): 128902-.
[14]	苏桂锋, 李晓温, 张小兵, 张一. Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks[J]. 中国物理B, 2020, 29(8): 88904-088904.
[15]	闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.