Homogeneous and Heterogeneous Traffic of Data Packets on Complex Networks: The Traffic Congestion Phenomenon
- 1 SELEX Sistemi Integrati S.p.A., Roma, Italy
- 2 SELEX Sistemi Integrati S.p.A., Roma, Italy
- 3 CERI, Università di Roma “La Sapienza”, Roma, Italy
- 4 Dipartimento di Scienze Sociali, Università Politecnica delle Marche, Ancona, Italy
- 5 CERI, Università di Roma “La Sapienza”, Roma, Italy
Abstract
We study the congestion phenomenon in a mathematical model of the data packets traffic in transmission networks as a function of the topology and of the load of the network. Two types of traffic are considered: homogeneous and heterogeneous traffic. The congestion phenomenon is studied in stationary conditions through the behaviour of two quantities: the mean travel time of a packet and the mean number of packets that have not reached their destination and are traveling in the network. We define a transformation that maps a network having the small world property (Inet 3037 in our numerical experiments) into a (modified) lattice network that has the same number of nodes. This map changes the capacity of the branches of the graphs representing the networks and can be regarded as an “interpolation” between the two classes of networks. Using this transformation we compare the behaviour of Inet 3037 to the behaviour of a modified rectangular lattice and we study the behaviour of the interpolating networks. This study suggests how to change the network topology and the branch capacities in order to alleviate the congestion phenomenon. In the website: http://www.ceri.uniroma1.it/ceri/zirilli/w6 some auxiliary material including animations and stereo?graphic scenes that helps the understanding of this paper is shown.
- A. Farina, A. Graziano, F. Mariani and F. Zirilli, “Probabilistic Analysis of Failures in Power Transmission Networks and Phase Transitions: A Study Case of a High Voltage Power Transmission Network,” Journal of Optimization Theory and Applications, Vol. 139, No. 1, 2008, pp. 171-199. doi:10.1007/s10957-008-9435-x
- L. Kocarev and G. Vattay, “Complex Dynamics in Communication Networks,” Springer Verlag, Berlin, 2005. doi:10.1007/b94627
- W. Aiello, F. Chung and L. Lu, “Random Evolution in Massive Graphs,” In: J. Abello, P. M. Pardalos and M. G. C. Resende, Eds., Handbook of Massive Data Sets, Kluwer Academic Publisher, Norwell, 2002, pp. 97-122.
- A. L. Fabrikant, E. Koutsoupias and C. Papadimitriou, “Heuristically Optimized Trade-offs: A New Paradigm for Power Law in the Internet,” In: P. Widmayer, F. Triquero, R. Morales, M. Hennessy, S. Eidenbenz and R. Conejo, Eds., Lectures Notes in Computer Science, Springer Verlag, Berlin, 2002, pp. 110-122.
- A. L. Barabasi and R. Albert, “Emergence of Scaling in Random Network,” Science, Vol. 286, No. 5439, 1999, pp. 509-512. doi:10.1126/science.286.5439.509
- S. Jamin and J. Winick, “Inet-3.0: Internet Topology Generator,” University of Michigan, Ann Arbor, 2002.
- A. Medina, A. Lakhina, I. Matta and J. Byers, “BRITE: An Approach to Universal Topology Generation,” 2001. http://www.cs.bu.edu/brite/publications/BriteMascots.pdf
- Y. Aumann and Y. Rabani, “An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm,” SIAM Journal on Computing, Vol. 27, No. 1, 1998, pp. 291-301. doi:10.1137/S0097539794285983
- H. Okamura and P. Seymour, “Multicommodity Flows in Planar Graphs,” Journal of Combinatorial Theory B, Vol. 31, No. 1, 1981, pp. 75-81. doi:10.1016/S0095-8956(81)80012-3
- F. T. Leighton, “Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes,” Morgan Kaufmann Publishers, San Francisco, 1992.
- S. Leonardi, “On-Line Network Routing,” In: A. Fiat and G. Woeginger, Eds., Online Algorithms—The State of the Art, Springer Verlag, Berlin, 1998, pp. 242-267.
- M. Faloutsos, P. Faloutsos and C. Faloutsos, “On PowerLaw Relationships of the Internet Topology,” ACM/ SIGCOMM Computer Communication Review, Vol. 29, No. 4, 1999, pp. 251-262. doi:10.1145/316194.316229
- L. Subramanian, S. Agarwal, J. Rexford and R. H. Katz, “Characterizing the Internet Hierarchy from Multiple Vantage Points,” 2002. http://research.microsoft.com/en-us/people/sagarwal/infocom02.pdf