Adaptive local routing strategy on a scale-free network

任丰原^{1}, 刘锋^{2}, 赵寒^{2}, 李 明^{2}, 朱衍波^{2}

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

Adaptive local routing strategy on a scale-free network

Ren Feng-Yuan^{a}, Liu Feng^{b}, Zhao Han^{b}, Li Ming^{b}, Zhu Yan-Bo^{b}

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

摘要 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.

(Granular models of complex systems; traffic flow)

基金资助: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[J]. 中国物理B, 2010, 19(4): 40513-040513.
Liu Feng, Zhao Han, Li Ming, Ren Feng-Yuan, Zhu Yan-Bo. Adaptive local routing strategy on a scale-free network. Chin. Phys. B, 2010, 19(4): 40513-040513.