Global dynamic routing for scale-free networks

Traffic is essential for many dynamic processes on networks. The efficient routing strategy [G. Yan, T. Zhou, B. Hu, Z. Q. Fu, and B. H. Wang, Phys. Rev. E 73, 046108 (2006)] can reach a very high capacity of more than ten times of that with shortest path strategy. In this paper, we propose a global dynamic routing strategy for network systems based on the information of the queue length of nodes. Under this routing strategy, the traffic capacity is further improved. With time delay of updating node queue lengths and the corresponding paths, the system capacity remains constant, while the travel time for packets increases.

Figure 1

(Color online) Evolution of packet number in the network under different routing strategies. (a) Shortest path routing strategy, (b) efficient routing strategy, and (c) global dynamic routing strategy. (d) The order parameter $\eta$ vs $R$ under the three routing strategies.

Figure 2

(Color online) (a) The network capacity $R_c$ vs average degree $⟨k⟩$ with the same network size $N=500$ under the three different routing strategies. (b) The network capacity $R_c$ vs network size $N$ with the same average degree $⟨k⟩=4$ under the three routing strategies.

Figure 3

(Color online) Evolution of packet number $N_p$ for different $R$ with time delay of $\delta T=20$. The inset depicts the order parameter $\eta$ vs $R$ with $\delta T=20$. The network capacity remains at $R_c=41$. Other parameters are network size $N=500$ and average degree $⟨k⟩=4$.

Figure 4

(Color online) Evolution of $N_p$ for different time delay with $R=R_c=41$. For all $\delta T$, the network capacity remains at $R_c=41$. The inset depicts the saturate value of $N_p$ at the balanced period vs $\delta T$ under $R=R_c=41$. Other parameters are network size $N=500$ and average degree $⟨k⟩=4$.

Figure 5

(Color online) Average packet number in nodes $n\left(k\right)$ vs node degree $k$ with different $\delta T$. Network size $N=500$ and average degree $⟨k⟩=4$.

Figure 6

(Color online) The probability distribution of travel time for different $\delta T$. Network parameters are $N=500$ and average degree $⟨k⟩=4$.

Figure 7

(a) Average travel time vs $\delta T$ with network size $N=500$ and average degree $⟨k⟩=4$. (b) Average waiting time vs $\delta T$ with network size $N=500$ and average degree $⟨k⟩=4$.

Figure 8

(Color online) The probability distribution of path length for different $\delta T$ with network size $N=500$ and average degree $⟨k⟩=4$. The inset depicts the average value of path length vs $\delta T$.