Abstract—The routing method of random-walks is robust to the change of network topology. However, congestion occurs easily for random-walks because packets usually take a long trip in the networks to arrive at their destinations. In this paper, we propose a method to minimize the congestion for random-walks via local adaptive congestion control. The method uses linear-prediction to estimate the queue length for nodes and local adaptive evolution equations that enable nodes to self-coordinate their accepting probabilities to the incoming packets. We apply the method to the BA scale-free networks. The results show that the congestion is delayed remarkably and the phase transition from free-flow to congestion occurs in a smooth way with the increase of prediction orders. We also investigate the distribution of accepting probability of nodes as a function of node degrees, and find a hierarchical (degree-based) organization of the accepting rates is strongly beneficial to avoiding the network congestion. Furthermore, we compare our method with several existing methods on the performance of avoiding congestion on the BA networks and a real example. The results show that our method performs best under the same packet generation probability in the networks.

Index Terms—Random-walks, self-coordinate, adaptive congestion control, networks

Cite: Yang Liu, Yi Shen, and Lei Ding, “Minimize Congestion for Random-Walks in Networks via Local Adaptive Congestion Control," Journal of Communications, vol. 11, no. 6, pp. 579-585, 2016. Doi: 10.12720/jcm.11.6.579-585