Efficient routing strategies in scale-free networks with limited bandwidth

We study the traffic dynamics in complex networks where each link is assigned a limited and identical bandwidth. Although the first-in–first-out (FIFO) queuing rule is widely applied in the routing protocol of information packets, here we argue that if we drop this rule, the overall throughput of the network can be remarkably enhanced. We propose some efficient routing strategies that do not strictly obey the FIFO rule. Compared to the routine shortest-path strategy, throughput for both Barabási-Albert (BA) networks and the Internet can be improved by a factor of more than five. We calculate the theoretical limitation of the throughput. In BA networks, our proposed strategy can achieve 88% of the theoretical optimum, yet for the Internet, it is about 12%, implying that we still have a huge space to further improve the routing strategy for the Internet. Finally, we discuss possibly promising ways to design more efficient routing strategies for the Internet.

Figure 1

Comparison among different routing strategies in BA networks with $N=2000$ and $m=m_0=3$, where $m_0$ and $m$ are numbers of starting nodes and new links are added at every time step, respectively. (a) The order parameter $\eta$ as a function of $\lambda$. (b) The network throughput ${\lambda }_c$ averaged over 100 independent realizations as a function of the traffic-awareness parameter, where the error bars of the simulation results are less than the symbol size.

Figure 2

The network throughput ${\lambda }_c$ as a function of the traffic-awareness parameter for (a) different network sizes of BA networks and (b) different degree distributions of the uncorrelated configuration models (UCM) [35] with $N=2000$ and $3<k<N^{\frac{1}{\gamma -1}}$. The results are obtained by averaging over 100 independent realizations.

Figure 3

The average number of packets $n\left(k\right)$ over the nodes with degree $k$. Network parameters are the same as in Fig. 1.

Figure 4

Comparison of different routing strategies for the Internet. (a) The order parameter $\eta$ as a function of $\lambda$. (b) The network throughput ${\lambda }_c$ as a function of the traffic-awareness parameter.

Figure 5

The average number of packets $n\left(k\right)$ over the nodes with degree $k$ for the Internet.