中国物理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, 刘锋2, 赵寒2, 李 明2, 朱衍波2   

  1. (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)   

  1. 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

摘要: 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)