×

Traffic dynamics on complex networks: a survey. (English) Zbl 1264.90031

Summary: Traffic dynamics on complex networks are intriguing in recent years due to their practical implications in real communication networks. In this survey, we give a brief review of studies on traffic routing dynamics on complex networks. Strategies for improving transport efficiency, including designing efficient routing strategies and making appropriate adjustments to the underlying network structure, are introduced in this survey. Finally, a few open problems are discussed.

MSC:

90B18 Communication networks in operations research
68M10 Network design and communication in computer systems
90B20 Traffic problems in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1087.68509
[2] R. Pastor-Satorras, A. Vázquez, and A. Vespignani, “Dynamical and correlation properties of the internet,” Physical Review Letters, vol. 87, no. 25, Article ID 258701, 4 pages, 2001.
[3] H. Li and M. Maresca, “Polymorphic-torus network,” IEEE Transactions on Computers, vol. 38, no. 9, pp. 1345-1351, 1989. · doi:10.1109/12.29479
[4] W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, “On the self-similar nature of Ethernet traffic,” Computer Communication Review, vol. 23, article 283, 1993.
[5] T. Ohira and R. Sawatari, “Phase transition in a computer network traffic model,” Physical Review E, vol. 58, no. 1, pp. 193-195, 1998.
[6] A. Arenas, A. Díaz-Guilerà, and R. Guimerà, “Communication in networks with hierarchical branching,” Physical Review Letters, vol. 86, no. 14, pp. 3196-3199, 2001. · doi:10.1103/PhysRevLett.86.3196
[7] R. Guimerà, A. Arenas, A. Díaz-Guilerà, and F. Giralt, “Dynamical properties of model communication networks,” Physical Review E, vol. 66, no. 2, Article ID 026704, 8 pages, 2002. · doi:10.1103/PhysRevE.66.026704
[8] T. M. Janaki and N. Gupte, “Connectivity strategies to enhance the capacity of weight-bearing networks,” Physical Review E, vol. 67, no. 2, Article ID 021503, 6 pages, 2003.
[9] R. V. Solé and S. Valverde, “Information transfer and phase transitions in a model of internet traffic,” Physica A, vol. 289, no. 3-4, pp. 595-605, 2001. · Zbl 0971.68500 · doi:10.1016/S0378-4371(00)00536-7
[10] S. Valverde and R. V. Solé, “Self-organized critical traffic in parallel computer networks,” Physica A, vol. 312, no. 3-4, pp. 636-648, 2002. · Zbl 0997.68003 · doi:10.1016/S0378-4371(02)00872-5
[11] D. K. Arrowsmith, R. J. Mondragon, J. M. Pittsy, and M. Woolf, Report 08 Institut Mittag-Leffler, Stockholm, Sweden, 2004.
[12] M. S. Taqqu, W. Willinger, and R. Sherman, “Proof of a fundamental result in self-similar traffic modeling,” vol. 27, article 5.
[13] M. E. Crovella and A. Bestavros, “Self-similarity in world wide web traffic: evidence and possible causes,” IEEE/ACM Transactions on Networking, vol. 5, no. 6, pp. 835-846, 1997.
[14] X. Jia, W. Zhao, and J. Li, “An integrated routing and admission control mechanism for real-time multicast connections in ATM networks,” IEEE Transactions on Communications, vol. 49, no. 9, pp. 1515-1519, 2001. · Zbl 1011.94502 · doi:10.1109/26.950337
[15] M. Li and W. Zhao, “Asymptotic identity in min-plus algebra: a report on CPNS,” Computational and Mathematical Methods in Medicine, vol. 2012, Article ID 154038, 11 pages, 2012. · Zbl 1233.68032 · doi:10.1155/2012/154038
[16] M. Li and W. Zhao, “Visiting power laws in cyber-physical networking systems,” Mathematical Problems in Engineering, vol. 2012, 2012.
[17] E. G. Bakhoum and C. Toma, “Specific mathematical aspects of dynamics generated by coherence functions,” Mathematical Problems in Engineering, vol. 2011, Article ID 436198, 10 pages, 2011. · Zbl 1248.37075
[18] E. G. Bakhoum and C. Toma, “Dynamical aspects of macroscopic and quantum transitions due to coherence function and time series events,” Mathematical Problems in Engineering, vol. 2010, Article ID 428903, 13 pages, 2010. · Zbl 1191.35219 · doi:10.1155/2010/428903
[19] D. J. Watts and S. H. Strogatz, “Collective dynamics of “small-world” networks,” Nature, vol. 393, no. 6684, pp. 440-442, 1998. · Zbl 1368.05139
[20] A. L. Barabási, R. Albert, and A. Vespignani, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509-512, 1999. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[21] A. L. Barabási, R. Albert, and H. Jeong, “Mean-field theory for scale-free random networks,” Physica A, vol. 272, no. 1, pp. 173-187, 1999. · doi:10.1016/S0378-4371(99)00291-5
[22] L. Zhao, Y. C. Lai, K. Park, and N. Ye, “Onset of traffic congestion in complex networks,” Physical Review E, vol. 71, no. 2, Article ID 026125, 8 pages, 2005. · doi:10.1103/PhysRevE.71.026125
[23] J. D. Noh and H. Rieger, “Random walks on complex networks,” Physical Review Letters, vol. 92, no. 11, Article ID 118701, 4 pages, 2004. · doi:10.1103/PhysRevLett.92.118701
[24] Z. Eisler and J. Kertész, “Random walks on complex networks with inhomogeneous impact,” Physical Review E, vol. 71, no. 5, Article ID 057104, pp. 1-4, 2005. · doi:10.1103/PhysRevE.71.057104
[25] B. Tadić, S. Thurner, and G. J. Rodgers, “Traffic on complex networks: towards understanding global statistical properties from microscopic density fluctuations,” Physical Review E, vol. 69, no. 3, Article ID 036102, 5 pages, 2004. · doi:10.1103/PhysRevE.69.036102
[26] R. Guimerà, A. Díaz-Guilerà, F. Vega-Redondo, A. Cabrales, and A. Arenas, “Optimal network topologies for local search with congestion,” Physical Review Letters, vol. 89, no. 24, Article ID 248701, 4 pages, 2002.
[27] G. Mukherjee and S. S. Manna, “Phase transition in a directed traffic flow network,” Physical Review E, vol. 71, no. 6, Article ID 066108, pp. 1-6, 2005. · doi:10.1103/PhysRevE.71.066108
[28] T. Zhou, G. Yan, B. H. Wang et al., “Traffic dynamics on complex networks,” Dynamics of Continuous, Discrete and Impulsive Systems Series B, vol. 13, no. 3-4, pp. 463-469, 2006. · Zbl 1112.68325
[29] Z. Wu, G. Peng, W. Wong, and K. Yeung, “Improved routing strategies for data traffic in scale-free networks,” Journal of Statistical Mechanics, vol. 2008, no. 11, Article ID P11002, 2008. · doi:10.1088/1742-5468/2008/11/P11002
[30] H. Zhang, Z. H. Liu, M. Tang, and P. M. Hui, “An adaptive routing strategy for packet delivery in complex networks,” Physics Letters, Section A, vol. 364, no. 3-4, pp. 177-182, 2007. · Zbl 1203.90036 · doi:10.1016/j.physleta.2006.12.009
[31] Z. Chen and X. Wang, “Effects of network structure and routing strategy on network capacity,” Physical Review E, vol. 73, no. 3, Article ID 036107, pp. 1-5, 2006. · doi:10.1103/PhysRevE.73.036107
[32] M. B. Hu, B. H. Wang, R. Jiang, Q. S. Wu, and Y. H. Wu, “The effect of bandwidth in scale-free network traffic,” Europhysics Letters, vol. 79, no. 1, Article ID 14003, 2007. · doi:10.1209/0295-5075/79/14003
[33] M. B. Hu, R. Jiang, Y. H. Wu, and Q. S. Wu, “The effect of link and node capacity on traffic dynamics in weighted scale-free networks,” in Proceedings of the International Conference on Complex Sciences, vol. 4, part 1 of Lecture Notes of the Institute for Computer Sciences and Telecommunications, pp. 580-588, Springer, Berling Heidelberg, Germany, 2009.
[34] R. Jiang, M. B. Hu, W. X. Wang, G. Yan, Q. S. Wu, and B. H. Wang, “Traffic dynamics of packets generated with none-homogeneously selected sources and destinations in scale-free networks,” Dynamics of Continuous, Discrete and Impulsive Systems B Supplement, vol. 14, supplement 7, pp. 51-54, 2007.
[35] M. E. J. Newman, “Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality,” Physical Review E, vol. 64, no. 1, Article ID 016132, 2001.
[36] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, no. 2, Article ID 026113, 2004. · Zbl 1032.91716 · doi:10.1103/PhysRevE.69.026113
[37] K. I. Goh, B. Kahng, and D. Kim, “Universal behavior of load distribution in scale-free networks,” Physical Review Letters, vol. 98, article 278701, 2004. · Zbl 1030.68005
[38] M. Barthélemy, “Betweenness centrality in large complex networks,” European Physical Journal B, vol. 38, no. 2, pp. 163-168, 2004. · doi:10.1140/epjb/e2004-00111-4
[39] W. Huang and T. W. S. Chow, “Investigation of both local and global topological ingredients on transport efficiency in scale-free networks,” Chaos, vol. 19, no. 4, Article ID 043124, 2009. · Zbl 06437221 · doi:10.1063/1.3272217
[40] D. Krioukov, K. Fall, and X. Yang, “Compact routing on internet-like graphs,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 209-219, March 2004.
[41] A. S. Tanenbaum, Computer Network, Prentice Hall Press, 1996.
[42] C. Huitema, Routing in the Internet, Prentice Hall, Up per Saddle River, NJ, USA, 2000.
[43] B. Danila, Y. Yu, J. A. Marsh, Z. Toroczkai, and K. E. Bassler, “Transport optimization on complex networks,” Chaos, vol. 17, no. 2, Article ID 026102, 2007. · Zbl 1159.37342 · doi:10.1063/1.2731718
[44] G. Yan, T. Zhou, B. Hu, Z. Q. Fu, and B. H. Wang, “Efficient routing on complex networks,” Physical Review E, vol. 73, no. 4, Article ID 046108, pp. 1-5, 2006. · doi:10.1103/PhysRevE.73.046108
[45] P. Echenique, J. Gomez-Gardenes, and Y. Moreno, “Improved routing strategies for Internet traffic delivery,” Physical Review E, vol. 70, no. 5, Article ID 056105, 2004. · doi:10.1103/PhysRevE.70.056105
[46] P. Echenique, J. Gomez-gardenes, and Y. Moreno, “Dynamics of jamming transitions in complex networks,” Europhysics Letters, vol. 71, no. 2, pp. 325-331, 2005. · doi:10.1209/epl/i2005-10080-8
[47] L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, “Search in power-law networks,” Physical Review E, vol. 64, no. 4, Article ID 046135, 2001.
[48] R. Albert, H. Jeong, and A. L. Barabási, “Diameter of the world-wide web,” Nature, vol. 401, no. 6749, pp. 130-131, 1999. · doi:10.1038/43601
[49] W. X. Wang, C. Y. Yin, G. Yan, and B. H. Wang, “Integrating local static and dynamic information for routing traffic,” Physical Review E, vol. 74, no. 1, Article ID 016101, 2006. · doi:10.1103/PhysRevE.74.016101
[50] M. B. Hu, R. Jiang, Y. H. Wu, W. X. Wang, and Q. S. Wu, “Urban traffic from the perspective of dual graph,” European Physical Journal B, vol. 63, no. 1, pp. 127-133, 2008. · doi:10.1140/epjb/e2008-00219-5
[51] S. Scellato, L. Fortuna, M. Frasca, J. Gómez-Gardeñes, and V. Latora, “Traffic optimization in transport networks based on local routing,” European Physical Journal B, vol. 73, no. 2, pp. 303-308, 2010. · Zbl 1188.90066 · doi:10.1140/epjb/e2009-00438-2
[52] J. M. Kleinberg, “Navigation in a small world,” Nature, vol. 406, article 845, 2000. · Zbl 1296.05181 · doi:10.1038/35022643
[53] B. J. Kim, C. N. Yoon, S. K. Han, and H. Jeong, “Path finding strategies in scale-free networks,” Physical Review E, vol. 65, no. 2, Article ID 027103, 2002. · doi:10.1103/PhysRevE.65.027103
[54] C. P. Herrero, “Self-avoiding walks on scale-free networks,” Physical Review E, vol. 71, no. 1, Article ID 016103, 2005. · doi:10.1103/PhysRevE.71.016103
[55] S. J. Yang, “Exploring complex networks by walking on them,” Physical Review E, vol. 71, no. 1, Article ID 016107, 2005. · doi:10.1103/PhysRevE.71.016107
[56] W. X. Wang, B. H. Wang, C. Y. Yin, Y. B. Xie, and T. Zhou, “Traffic dynamics based on local routing protocol on a scale-free network,” Physical Review E, vol. 73, no. 2, Article ID 026111, 2006. · doi:10.1103/PhysRevE.73.026111
[57] C. Y. Yin, B. H. Wang, W. X. Wang, T. Zhou, and H. J. Yang, “Efficient routing on scale-free networks based on local information,” Physics Letters, Section A, vol. 351, no. 4-5, pp. 220-224, 2006. · Zbl 1234.68026 · doi:10.1016/j.physleta.2005.10.104
[58] B. Tadić and G. J. Rodgers, “Packet transport on scale-free networks,” Advances in Complex Systems, vol. 5, article 445, 2002.
[59] B. Tadić and S. Thurner, “Information super-diffusion on structured networks,” Physica A, vol. 332, no. 1-4, pp. 566-584, 2004. · Zbl 02023546 · doi:10.1016/j.physa.2003.10.007
[60] X. Ling, M. B. Hu, R. Jiang, and Q. S. Wu, “Global dynamic routing for scale-free networks,” Physical Review E, vol. 81, no. 1, Article ID 016113, 2010. · doi:10.1103/PhysRevE.81.016113
[61] A. E. Motter, “Cascade control and defense in complex networks,” Physical Review Letters, vol. 93, no. 9, Article ID 98701, 2004. · doi:10.1103/PhysRevLett.93.098701
[62] A. E. Motter, N. Gulbahce, E. Almaas, and A. L. Barabási, “Predicting synthetic rescues in metabolic networks,” Molecular Systems Biology, vol. 4, article 168, 2008. · doi:10.1038/msb.2008.1
[63] T. Nishikawa and A. E. Motter, “Network synchronization landscape reveals compensatory structures, quantization, and the positive effect of negative interactions,” The Proceedings of the National Academy of Sciences USA, vol. 107, no. 23, Article ID 10342, 2010.
[64] Z. Liu, M. B. Hu, R. Jiang, W. X. Wang, and Q. S. Wu, “Method to enhance traffic capacity for scale-free networks,” Physical Review E, vol. 76, no. 3, Article ID 037101, 2007. · doi:10.1103/PhysRevE.76.037101
[65] G. Q. Zhang, D. Wang, and G. J. Li, “Enhancing the transmission efficiency by edge deletion in scale-free networks,” Physical Review E, vol. 76, no. 1, Article ID 017101, 2007. · doi:10.1103/PhysRevE.76.017101
[66] W. Huang and T. W. S. Chow, “An efficient strategy for enhancing traffic capacity by removing links in scale-free networks,” Journal of Statistical Mechanics, vol. 2010, no. 1, Article ID P01016, 2010. · doi:10.1088/1742-5468/2010/01/P01016
[67] T. J. P. Penna, “Traveling salesman problem and Tsallis statistics,” Physical Review E, vol. 51, no. 1, pp. R1-R3, 1995. · doi:10.1103/PhysRevE.51.R1
[68] D. A. Stariolo and C. Tsallis, Annual Review of Computational Physics II, Edited by D. Stauffer, World Scientific, Singapore, 1994.
[69] W. Huang and T. W. S. Chow, “Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network,” Chaos, vol. 20, no. 3, Article ID 033123, 2010. · Zbl 06437385 · doi:10.1063/1.3490745
[70] A. E. Motter and Y. C. Lai, “Cascade-based attacks on complex networks,” Physical Review E, vol. 66, no. 6, Article ID 065102, 2002. · doi:10.1103/PhysRevE.66.065102
[71] L. Zhao, K. Park, and Y. C. Lai, “Attack vulnerability of scale-free networks due to cascading breakdown,” Physical Review E, vol. 70, no. 3, Article ID 035101, 2004. · doi:10.1103/PhysRevE.70.035101
[72] A. E. Motter, “Cascade control and defense in complex networks,” Physical Review Letters, vol. 93, no. 9, Article ID 098701, 2004. · doi:10.1103/PhysRevLett.93.098701
[73] L. Zhang, K. Park, Y. C. Lai, and N. Ye, “Tolerance of scale-free networks against attack-induced cascades,” Physical Review E, vol. 72, no. 2, Article ID 025104, pp. 1-4, 2005. · doi:10.1103/PhysRevE.72.025104
[74] R. Yang, W. X. Wang, Y. C. Lai, and G. Chen, “Optimal weighting scheme for suppressing cascades and traffic congestion in complex networks,” Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, vol. 79, no. 2, Article ID 026112, 2009. · doi:10.1103/PhysRevE.79.026112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.