Adaptive local routing strategy on a scale-free network

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

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.

Keywords: local routing scale-free networks preferential probability traffic load

Received: 12 October 2008
Revised: 27 October 2009
Accepted manuscript online:

PACS:	89.75.Hc	(Networks and genealogical trees)
	02.50.Cw	(Probability theory)
	45.70.Vn	(Granular models of complex systems; traffic flow)

Fund: 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

Cite this article:

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

[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

[1]	Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks Guifeng Su(苏桂锋), Xiaowen Li(李晓温), Xiaobing Zhang(张小兵), Yi Zhang(张一). Chin. Phys. B, 2020, 29(8): 088904.
[2]	Multiple-predators-based capture process on complex networks Rajput Ramiz Sharafat, Cunlai Pu(濮存来), Jie Li(李杰), Rongbin Chen(陈荣斌), Zhongqi Xu(许忠奇). Chin. Phys. B, 2017, 26(3): 038901.
[3]	Integrated systemic inflammatory response syndrome epidemic model in scale-free networks Cai Shao-Hong(蔡绍洪), Zhang Da-Min(张达敏), Gong Guang-Wu(龚光武), and Guo Chang-Rui(郭长睿) . Chin. Phys. B, 2011, 20(9): 090503.
[4]	Generalized minimum information path routing strategy on scale-free networks Zhou Si-Yuan(周思源), Wang Kai(王开), Zhang Yi-Feng(张毅锋) Pei Wen-Jiang(裴文江) Pu Cun-Lai(濮存来), and Li Wei(李微) . Chin. Phys. B, 2011, 20(8): 080501.
[5]	Degree and connectivity of the Internet's scale-free topology Zhang Lian-Ming(张连明), Deng Xiao-Heng(邓晓衡), Yu Jian-Ping(余建平), and Wu Xiang-Sheng(伍祥生) . Chin. Phys. B, 2011, 20(4): 048902.
[6]	Poor–rich demarcation of Matthew effect on scale-free systems and its application Yan Dong(闫栋), Dong Ming(董明), Abdelaziz Bouras, and Yu Sui-Ran(于随然) . Chin. Phys. B, 2011, 20(4): 040205.
[7]	Mobile user forecast and power-law acceleration invariance of scale-free networks Guo Jin-Li(郭进利), Guo Zhao-Hua(郭曌华), and Liu Xue-Jiao(刘雪娇) . Chin. Phys. B, 2011, 20(11): 118902.
[8]	Convergence speed of consensus problems over undirected scale-free networks Sun Wei(孙巍) and Dou Li-Hua(窦丽华). Chin. Phys. B, 2010, 19(12): 120513.
[9]	Modelling the spread of sexually transmitted diseases on scale-free networks Liu Mao-Xing(刘茂省) and Ruan Jiong(阮炯). Chin. Phys. B, 2009, 18(6): 2115-2120.
[10]	Improving consensual performance of multi-agent systems in weighted scale-free networks Qi Wei(祁伟), Xu Xin-Jian(许新建), and Wang Ying-Hai(汪映海). Chin. Phys. B, 2009, 18(10): 4217-4221.
[11]	Normalized entropy of rank distribution: a novel measure of heterogeneity of complex networks Wu Jun(吴俊), Tan Yue-Jin(谭跃进), Deng Hong-Zhong(邓宏钟), and Zhu Da-Zhi(朱大智). Chin. Phys. B, 2007, 16(6): 1576-1580.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Adaptive local routing strategy on a scale-free network

Cite this article:

Online attention