Please wait a minute...
Chin. Phys. B, 2010, Vol. 19(4): 040513    DOI: 10.1088/1674-1056/19/4/040513
GENERAL Prev   Next  

Adaptive local routing strategy on a scale-free network

Ren Feng-Yuana, Liu Fengb, Zhao Hanb, Li Mingb, Zhu Yan-Bob
a Department of Computer Science and Technology,Tsinghua University, Beijing 100084, China; b School of Electronics and Information Engineering, Beihang University, Beijing 100191, China
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:  traffic load      local routing      scale-free networks      preferential probability  
Received:  12 October 2008      Revised:  27 October 2009      Published:  15 April 2010
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, 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, 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, Li Wei. Chin. Phys. B, 2011, 20(8): 080501.
[5] Poor–rich demarcation of Matthew effect on scale-free systems and its application
Yan Dong, Dong Ming, Abdelaziz Bouras, Yu Sui-Ran. Chin. Phys. B, 2011, 20(4): 040205.
[6] Degree and connectivity of the Internet's scale-free topology
Zhang Lian-Ming, Deng Xiao-Heng, Yu Jian-Ping, Wu Xiang-Sheng. Chin. Phys. B, 2011, 20(4): 048902.
[7] Mobile user forecast and power-law acceleration invariance of scale-free networks
Guo Jin-Li, Guo Zhao-Hua, Liu Xue-Jiao. Chin. Phys. B, 2011, 20(11): 118902.
[8] Convergence speed of consensus problems over undirected scale-free networks
Sun Wei, Dou Li-Hua. Chin. Phys. B, 2010, 19(12): 120513.
[9] Improving consensual performance of multi-agent systems in weighted scale-free networks
Qi Wei, Xu Xin-Jian, Wang Ying-Hai. Chin. Phys. B, 2009, 18(10): 4217-4221.
[10] Normalized entropy of rank distribution: a novel measure of heterogeneity of complex networks
Wu Jun, Tan Yue-Jin, Deng Hong-Zhong, Zhu Da-Zhi. Chin. Phys. B, 2007, 16(6): 1576-1580.
No Suggested Reading articles found!