A hybrid systems modeling framework for fast and accurate simulation of data communication networks

ABSTRACT

In this paper we present a general hybrid systems modeling framework to describe the flow of traffic in communication networks. To characterize network behavior, these models use averaging to continuously approximate discrete variables such as congestion window and queue size. Because averaging occurs over short time intervals, one still models discrete events such as the occurrence of a drop and the consequent reaction (e.g., congestion control). The proposed hybrid systems modeling framework fills the gap between packet-level and fluid-based models: by averaging discrete variables over a very short time scale (on the order of a round-trip time), our models are able to capture the dynamics of transient phenomena fairly accurately. This provides significant flexibility in modeling various congestion control mechanisms, different queuing policies, multicast transmission, etc. We validate our hybrid modeling methodology by comparing simulations of the hybrid models against packet-level simulations. We find that the probability density functions produced by <tt>ns-2</tt> and our hybrid model match very closely with an L¹-distance of less than 1%. We also present complexity analysis of <tt>ns-2</tt> and the hybrid model. These tests indicate that hybrid models are considerably faster.

REFERENCES

• 1: Jong Suk Ahn , Peter B. Danzig, Packet network simulation: speedup and accuracy versus timing granularity, IEEE/ACM Transactions on Networking (TON), v.4 n.5, p.743-757, Oct. 1996 [doi>10.1109/90.541322]
• 2: S. Bohacek. Fair pricing of video transmissions using best-effort and purchased bandwidth. In Proc. of the 40th Annual Allerton Conf. on Comm., Contr., and Computing, 2002.
• 3: S. Bohacek, J. P. Hespanha, J. Lee, and K. Obraczka. Analysis of a TCP hybrid model. In Proc. of the 39th Annual Allerton Conf. on Comm., Contr., and Computing, Oct. 2001.
• 4: S. Bohacek, J. P. Hespanha, J. Lee, and K. Obraczka. A hybrid systems modeling framework for fast and accurate simulation of data communication networks: Extended version. Technical report, University of California, Santa Barbara, Nov. 2002.
• 5: N. Cardwell, S. Savage, and T. Anderson. Modeling TCP latency. In Proc. of the IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000.
• 6: Luc Devroye, A course in density estimation, Birkhauser Boston Inc., Cambridge, MA, 1987
• 7: Kevin Fall , Sally Floyd, Simulation-based comparisons of Tahoe, Reno and SACK TCP, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.5-21, July 1996 [doi>10.1145/235160.235162]
• 8: Sally Floyd, Connections with multiple congested gateways in packet-switched networks part 1: one-way traffic, ACM SIGCOMM Computer Communication Review, v.21 n.5, p.30-47, Oct. 1991 [doi>10.1145/122431.122434]
• 9: Sally Floyd , Mark Handley , Jitendra Padhye , Jörg Widmer, Equation-based congestion control for unicast applications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.43-56, August 28-September 01, 2000, Stockholm, Sweden
• 10: Y. Guo, W. Gong, and D. Towsley. Time-stepped hybrid simulation (TSHS) for large scale networks. In Proc. of the IEEE INFOCOM, Mar. 2000.
• 11: F. Hernández-Campos , J. S. Marron , F. D. Smith , G. Samorodnitsky, Variable Heavy Tailed Durations in Internet Traffic, Part I: Understanding Heavy Tails, Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'02), p.43, October 11-16, 2002
• 12: H. Hisamatsu, H. Ohsaki, , and M. Murata. On modeling feedback congestion control mechanism of TCP using fluid flow approximation and queuing theory. In Proc. of 4th Asia-Pacific Symp. on Information and Telecommunication Technologies, 2001.
• 13: Polly Huang , Deborah Estrin , John Heidemann, Enabling Large-Scale Simulation: Selective Abstraction Approach to the Study of Multicast Protocol, Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.241, July 19-24, 1998
• 14: G. Kesidis, A. Singh, D. Cheung, and W. Kwok. Feasibility of fluid-event-driven simulation for ATM networks. In Proc. IEEE GLOBECOM, volume 3, pages 2013--2017, Nov. 1996.
• 15: K. Kumaran and D. Mitra. Performance and fluid simulations of a novel shared buffer management system. In Proc. of the IEEE INFOCOM, pages 1449--1461, Mar. 1998.
• 16: Srisankar Kunniyur , R. Srikant, Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.123-134, August 2001, San Diego, California, United States
• 17: T. V. Lakshman , B. Suter , U. Madhow, Window-Based Error Recovery and Flow Control with a Slow Acknowledgement Channel: A Study of TCP/IP Performance, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1199, April 09-11, 1997
• 18: B. Liu, D. R. Figueiredo, J. K. Yang Guo, and D. Towsley. A study of networks simulation efficiency: Fluid simulation vs. packet-level simulation. In Proc. of the IEEE INFOCOM, volume 3, pages 1244--1253, Apr. 2001.
• 19: S. H. Low, F. Paganini, J. Wang, S. Adlakha, and J. C. Doyle. Dynamics of TCP/RED and a scalable control. In Proc. of the IEEE INFOCOM, June 2002.
• 20: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 21: V. Misra, W. Gong, and D. Towsley. Stochastic differential equation modeling and analysis of TCP-windowsize behavior. In Proc. of PERFORMANCE'99, Istanbul, Turkey, 1999.
• 22: Vishal Misra , Wei-Bo Gong , Don Towsley, Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.151-160, August 28-September 01, 2000, Stockholm, Sweden
• 23: Modelica Association. Modelica --- A Unified Object-Oriented Language for Physical Systems Modeling: Tutorial. Available at http://www.modelica.org/.
• 24: T. Ott, J. H. B. Kemperman, and M. Mathis. Window size behavior in TCP/IP with constant loss probability. In Proc. of the DIMACS Workshop on Performance of Realtime Applications on the Internet, Nov. 1996.
• 25: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 26: Lili Qiu , Yin Zhang , Srinivasan Keshav, Understanding the performance of many TCP flows, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.37 n.3-4, p.277-306, November 5, 2001 [doi>10.1016/S1389-1286(01)00203-1 ]
• 27: QualNet user manual. Available at http://www.scalable-networks.com.
• 28: Scalable simulation framework. Available at http://www.ssfnet.org/.
• 29: Schaft A. J. van der , J. M. Schumacher, Introduction to Hybrid Dynamical Systems, Springer-Verlag, London, 1999
• 30: H. D. Schwetman, Hybrid simulation models of computer systems, Communications of the ACM, v.21 n.9, p.718-723, Sept. 1978 [doi>10.1145/359588.359594]
• 31: B. Sikdar, S. Kalyanaraman, and K. Vastola. Analytic models for the latency and steady-state throughput of TCP Tahoe, Reno and SACK. In Proc. of IEEE GLOBECOM, pages 25--29, 2001.
• 32: The VINT Project, a collaboration between researchers at UC Berkeley, LBL, USC/ISI, and Xerox PARC. The ns Manual (formerly ns Notes and Documentation), Oct. 2000. Available at http://www.isi.edu/nsnam/ns/ns-documentation.html.
• 33: A. Yan and W. Gong. Fluid simulation for high speed networks. IEEE Trans. on Inform. Theory, June 1999.
• 34: Lixia Zhang , Scott Shenker , Daivd D. Clark, Observations on the dynamics of a congestion control algorithm: the effects of two-way traffic, Proceedings of the conference on Communications architecture & protocols, p.133-147, September 03-06, 1991, Zurich, Switzerland

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

General Terms:
Algorithms, Performance

Keywords:
TCP, UDP, congestion control, data communication networks, hybrid systems, simulation