Improving the Network Load Balance by Adding an Edge

Abstract:

Some previously proposed ways of improving the network load balance are reducing the link overload or reducing the node overload. Traffic load of a node or traffic load of a link can be characterized by betweenness of the node or betweenness of the edge respectively. Congestion mainly happens on nodes with maximum betweenness, so one way to improve the network load balance is mainly to minimize the maximum betweenness of node in the network. We present four edge addition strategies to minimize the maximum node betweenness by adding an edge. We do experiments on three benchmark networks to verify the effectiveness of the four edge addition strategies. By analyzing the experimental results, we confirm that adding an edge at the suitable location in the network can significantly minimize the maximum betweenness of node and improve the network load balance. It is very useful to mitigate the heavy burden of the most congested router only by adding one link with small cost without changing the network topology massively. Also, our work is helpful for service providers to optimize their network performance by adding an edge or to make good network planning by optimizing the existing network topology incrementally.

• Periodical: Advanced Materials Research (Volumes 433-440)
• Pages: 5147-5151
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.433-440.5147
• Online since: January 2012
• Authors: Zhong Yuan Jiang, Man Gui Liang
• Keywords: Adding an Edge, Betweenness, Congestion, Network Load Balance

References

[1] P. Mahadevan, D. Krioukov, M. Fomenkov, B. Huffaker, X. Dimitropoulos, K. Claffy, A. Vahdat, The Internet AS-Level Topology: Three Data Sources and One Definitive Metric,. In: ACM SIGCOMM CCR (2005).

DOI: 10.1145/1111322.1111328

[2] A. Beygelzimer, G. Grinstein, R. Linsker, I. Rish, Physica A 357 (2005) 593–612.

DOI: 10.1016/j.physa.2005.03.040

[3] Holme P and Kim B J 2002 Phys. Rev. E 65 056109.

[4] T.N. Bui, C. Jones, Information Processing Letters 42 (1992) 153.

[5] G. Yan, T. Zhou, B. Hu, Z.Q. Fu, B.H. Wang, Physical Review E 73 (2006) 046108.

[6] W.X. Wang, B.H. Wang, C.Y. Yin, Y.B. Xie, T. Zhou, Physical Review E 73 (2006) 026111.

[7] P. Echenique, J. Gomez-Gardenes, Y. Moreno, Physical Review E 70 (2004) 056105.

[8] M. Tang, Z.H. Liu, X.M. Liang, P.M. Hui, Physical Review E 80 (2009) 026114.

[9] X. Ling, M.B. Hu, R. Jiang, R.L. Wang, X.B. Cao, Q.S. Wu, Physical Review E 80 (2009) 066110.

[10] B. Danila, Y. Yu, J.A. Marsh, K.E. Bassler, Physical Review E 74 (2006) 046106.

[11] B. Danila, Y.D. Sun, K.E. Bassler, Physical Review E 80 (2009) 066116.

[12] Guo-Qing Zhang, Di Wang, Guo-Jie. Physical Review E 76, 017101 (2007).

[13] A. -L. Barabasi, R. Albert, Science 286 (1999) 509.

[14] D.J. Watts, S.H. Strogatz, Nature 393 (1998) 440.

[15] Erdös P, Rényi A. On the evolution of random graph,. Pulb. Math. Inst. Hung. Acad/ Sci. , 1960, 5: 17-60.

[16] R. Guimerà, A. Díaz-Guilera, F. Vega-Redondo, A. Cabrales, and A. Arenas, Phys. Rev. Lett. 89, 248701 (2002).

DOI: 10.1103/physrevlett.89.248701