×

A model for stochastic hybrid systems with application to communication networks. (English) Zbl 1131.90322

Summary: We propose a model for stochastic hybrid systems (SHSs) where transitions between discrete modes are triggered by stochastic events much like transitions between states of a continuous-time Markov chains. However, the rate at which transitions occur is allowed to depend both on the continuous and the discrete states of the SHS. Based on results available for piecewise-deterministic Markov process (PDPs), we provide a formula for the extended generator of the SHS, which can be used to compute expectations and the overall distribution of the state.
As an application, we construct a stochastic model for on-off TCP flows that considers both the congestion-avoidance and slow-start modes and takes directly into account the distribution of the number of bytes transmitted. Using the tools derived for SHSs, we model the dynamics of the moments of the sending rate by an infinite system of ODEs, which can be truncated to obtain an approximate finite-dimensional model. This model shows that, for transfer-size distributions reported in the literature, the standard deviation of the sending rate is much larger than its average. Moreover, the later seems to vary little with the probability of packet drop. This has significant implications for the design of congestion control mechanisms.

MSC:

90B18 Communication networks in operations research
60H10 Stochastic ordinary differential equations (aspects of stochastic analysis)
93C65 Discrete event control/observation systems
93E03 Stochastic systems in control theory (general)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.J. Antsaklis, J.A. Stiver, M.D. Lemmon, Hybrid system modeling and autonomous control systems, in: R.L. Grossman, A. Nerode, A.P. Ravn, H. Rishel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, vol. 736, Springer, New York, 1993, pp. 366-392.; P.J. Antsaklis, J.A. Stiver, M.D. Lemmon, Hybrid system modeling and autonomous control systems, in: R.L. Grossman, A. Nerode, A.P. Ravn, H. Rishel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, vol. 736, Springer, New York, 1993, pp. 366-392.
[2] M. Arlitt, R. Friedrich, T. Jin, Workload characterization of a web proxy in a cable modem environment, Technical Report HPL-1999-48, Hwelett-Packard Laboratories, Palo Alto, CA, April 1999.; M. Arlitt, R. Friedrich, T. Jin, Workload characterization of a web proxy in a cable modem environment, Technical Report HPL-1999-48, Hwelett-Packard Laboratories, Palo Alto, CA, April 1999.
[3] A. Back, J. Guckenheimer, M. Myers, A dynamical simulation facility for hybrid systems, in: R.L. Grossman, A. Nerode, A.P. Ravn, H. Rishel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, vol. 736, Springer, New York, 1993.; A. Back, J. Guckenheimer, M. Myers, A dynamical simulation facility for hybrid systems, in: R.L. Grossman, A. Nerode, A.P. Ravn, H. Rishel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, vol. 736, Springer, New York, 1993.
[4] Barford, P.; Bestavros, A.; Bradley, A.; Crovella, M., Changes in web client access patterns, World Wide Web (Special issue on characterization and performance evaluation), 2, 1-2, 15-28 (1999)
[5] Benjelloun, K.; Boukas, E. K., Mean square stochastic stability of linear time-delay system with Markovian jumping parameters, IEEE Trans. Automat. Contr., 43, 10, 1456-1460 (1998) · Zbl 0986.93071
[6] Bensoussan, A.; Lion, J.-L., Impulse Control and Quasi-Variational Inequalities (1984), Gauthier-Villars: Gauthier-Villars Paris, (Contrôle impulsionnel et inéquations quasi-variationnelles, 1982.)
[7] Bohacek, S., A stochastic model of TCP and fair video transmission, (Proceedings of the IEEE INFOCOM (2003))
[8] Bohacek, S.; Hespanha, J. P.; Lee, J.; Obraczka, K., Analysis of a TCP hybrid model, (Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing (October 2001))
[9] Bohacek, S.; Hespanha, J. P.; Lee, J.; Obraczka, K., A hybrid systems modeling framework for fast and accurate simulation of data communication networks, (Proceedings of the ACM International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS) (June 2003))
[10] M.S. Branicky, V.S. Borkar, S.K. Mitter, A unified framework for hybrid control: background, model and theory, in: Proceedings of the 33rd Conference on Decision and Control, vol. 4, December 1994, pp. 4228-4234.; M.S. Branicky, V.S. Borkar, S.K. Mitter, A unified framework for hybrid control: background, model and theory, in: Proceedings of the 33rd Conference on Decision and Control, vol. 4, December 1994, pp. 4228-4234.
[11] R. Brockett, Lecture Notes on Stochastic Control (provided by the author) 2002.; R. Brockett, Lecture Notes on Stochastic Control (provided by the author) 2002.
[12] Brockett, R. W., Hybrid models for motion control systems, (Trentelman, H. L.; Willems, J. C., Essays in Control: Perspectives in the Theory and its Applications (1993), Birkhäuser: Birkhäuser Boston), 29-53 · Zbl 0844.93011
[13] Costa, O. L.V.; Fragoso, M. D., Stability results for discrete-time linear systems with Markovian jumping parameters, J. Math. Anal. Appl., 179, 154-178 (1993) · Zbl 0790.93108
[14] Davis, M. H.A., Markov Models and Optimization, Monographs on Statistics and Applied Probability (1993), Chapman & Hall: Chapman & Hall London, UK · Zbl 0780.60002
[15] Fang, Y.; Loparo, K. A., Stabilization of continuous-time jump linear systems, IEEE Trans. Automat. Contr., 47, 10, 1590-1603 (2002) · Zbl 1364.93632
[16] Filar, J. A.; Gaitsgory, V.; Haurie, A. B., Control of singularly perturbed hybrid stochastic systems, IEEE Trans. Automat. Contr., 46, 2, 179-190 (2001) · Zbl 0992.93054
[17] Ghosh, M. K.; Arapostathis, A.; Marcus, S., Ergodic control of switching diffusions, SIAM J. Contr. Optim., 35, 6, 1952-1988 (1997) · Zbl 0891.93081
[18] J.P. Hespanha, S. Bohacek, K. Obraczka, J. Lee, Hybrid modeling of TCP congestion control, in: M. D. D. Benedetto, A. Sangiovanni-Vincentelli (Eds.), Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, vol. 2034, Springer, Berlin, 2001, pp. 291-304.; J.P. Hespanha, S. Bohacek, K. Obraczka, J. Lee, Hybrid modeling of TCP congestion control, in: M. D. D. Benedetto, A. Sangiovanni-Vincentelli (Eds.), Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, vol. 2034, Springer, Berlin, 2001, pp. 291-304. · Zbl 0996.93504
[19] J. Hu, J. Lygeros, S. Sastry, Towards a theory of stochastic hybrid systems, in: Lynch, Krogh (Eds.), Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, vol. 1790, Springer, Berlin, 2000, pp. 160-173.; J. Hu, J. Lygeros, S. Sastry, Towards a theory of stochastic hybrid systems, in: Lynch, Krogh (Eds.), Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, vol. 1790, Springer, Berlin, 2000, pp. 160-173. · Zbl 0962.93082
[20] G. Irlam, Unix file size survey—1993. Available at , November 1994.; G. Irlam, Unix file size survey—1993. Available at , November 1994.
[21] K. Itô, Stochastic integral, Proceedings of the Imperial Academy of Tokyo, vol. 20, 1944, pp. 519-524.; K. Itô, Stochastic integral, Proceedings of the Imperial Academy of Tokyo, vol. 20, 1944, pp. 519-524.
[22] Jacod, J.; Shiriaev, A. N., Limit Theorems for Stochastic Processes (2002), Springer: Springer Berlin
[23] Johansson, K. H.; Egerstedt, M.; Lygeros, J.; Sastry, S., On the regularization of Zeno hybrid automata, Systems Control Lett., 38, 141-150 (1999) · Zbl 0948.93031
[24] Kunniyur, S.; Srikant, R., Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management, (Proceedings of the ACM SIGCOMM. Proceedings of the ACM SIGCOMM, San Diego, California, USA (2001)) · Zbl 1364.90124
[25] Lakshmikantha, A.; Beck, C.; Srikant, R., Robustness of real and virtual queue based active queue management schemes, (Proceedings of the American Control Conference (June 2003)), 266-271
[26] Low, S. H., A duality model of TCP and queue management algorithms, IEEE ACM Trans. Networking, 11, 4 (2003)
[27] Low, S. H.; Paganini, F.; Doyle, J. C., Internet congestion control, IEEE Contr. System Mag., 22, 1, 28-43 (2002)
[28] Lygeros, J.; Johansson, K. H.; Simić, S. N.; Zhang, J.; Sastry, S. S., Dynamical properties of hybrid automata, IEEE Trans. Automat. Contr., 48, 1, 2-17 (2003) · Zbl 1364.93503
[29] Lygeros, J.; Tomlin, C.; Sastry, S., Controllers for reachability specifications for hybrid systems, Automatica, 35, 3, 349-370 (1999) · Zbl 0943.93043
[30] J. Mahdavi, S. Floyd, TCP-friendly unicast rate-based flow control. Technical Note sent to the end2end-interest mailing list, January 1997.; J. Mahdavi, S. Floyd, TCP-friendly unicast rate-based flow control. Technical Note sent to the end2end-interest mailing list, January 1997.
[31] Mathis, M.; Semke, J.; Mahdavi, J.; Ott, T., The macroscopic behavior of the TCP congestion avoidance algorithm, ACM Comput. Comm. Rev., 27, 3 (1997)
[32] Misra, V.; Gong, W.; Towsley, D., Stochastic differential equation modeling and analysis of TCP-windowsize behavior, (Proceedings of PERFORMANCE’99. Proceedings of PERFORMANCE’99, Istanbul, Turkey (1999))
[33] Misra, V.; Gong, W.; Towsley, D., Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED, (Proceedings of the ACM SIGCOMM (September 2000))
[34] A. Nerode, W. Kohn, Models for hybrid systems: automata, topologies, stability, in: R.L. Grossman, A. Nerode, A.P. Ravn, H. Rishel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, vol. 736, Springer, New York, 1993, pp. 317-356.; A. Nerode, W. Kohn, Models for hybrid systems: automata, topologies, stability, in: R.L. Grossman, A. Nerode, A.P. Ravn, H. Rishel (Eds.), Hybrid Systems, Lecture Notes in Computer Science, vol. 736, Springer, New York, 1993, pp. 317-356.
[35] T. Ott, J.H.B. Kemperman, M. Mathis, Window size behavior in TCP/IP with constant loss probability, in: Proceedings of the DIMACS Workshop on Performance of Realtime Applications on the Internet, November 1996.; T. Ott, J.H.B. Kemperman, M. Mathis, Window size behavior in TCP/IP with constant loss probability, in: Proceedings of the DIMACS Workshop on Performance of Realtime Applications on the Internet, November 1996.
[36] Padhye, J.; Firoiu, V.; Towsley, D.; Kurose, J., Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Trans. Networking, 8, 2, 133-145 (2000)
[37] Pola, G.; Bujorianu, M. L.; Lygeros, J.; Benedetto, M. D.D., Stochastic hybrid models: an overview, (Proceedings of the IFAC Conference on Analysis and Design of Hybrid System (June 2003))
[38] A.V.D. Schaft, H. Schumacher, An Introduction to Hybrid Dynamical Systems, Lecture Notes in Control and Information Science, vol. 251, Springer, London, 2000.; A.V.D. Schaft, H. Schumacher, An Introduction to Hybrid Dynamical Systems, Lecture Notes in Control and Information Science, vol. 251, Springer, London, 2000. · Zbl 0940.93004
[39] Shakkottai, S.; Srikant, R., How good are deterministic fluid models of Internet congestion control?, (Proceedings of the IEEE INFOCOM (June 2002))
[40] Sikdar, B.; Kalyanaraman, S.; Vastola, K., Analytic models for the latency and steady-state throughput of TCP Tahoe Reno and SACK, (Proceedings of the IEEE GLOBECOM (2001)), 25-29 · Zbl 1013.68019
[41] Sikdar, B.; Kalyanaraman, S.; Vastola, K., TCP Reno with random losses: latency; throughput and sensitivity analysis, (Proceedings of the IEEE IPCCC (April 2001)), 188-195
[42] Tavernini, L., Differential automata and their discrete simulators, Nonlinear Anal. Theory, Methods Appl., 11, 6, 665-683 (1987) · Zbl 0666.34005
[43] L. Xiao, A.H.J.P. How, Control with random communication delays via a discrete-time jump system approach, in: Proceedings of the 2000 American Control Conference, vol. 3, 2000, pp. 2199-2204.; L. Xiao, A.H.J.P. How, Control with random communication delays via a discrete-time jump system approach, in: Proceedings of the 2000 American Control Conference, vol. 3, 2000, pp. 2199-2204.
[44] J. Zhang, K. Johansson, J. Lygeros, S. Sastry, Dynamical systems revisited: hybrid systems with Zeno executions, in: Lynch and Krogh (Eds.), Hybrid Systems: Computation and Control, Lecture Notes in Comput. Science, vol. 1790, Springer, Berlin, 2000, pp. 451-464.; J. Zhang, K. Johansson, J. Lygeros, S. Sastry, Dynamical systems revisited: hybrid systems with Zeno executions, in: Lynch and Krogh (Eds.), Hybrid Systems: Computation and Control, Lecture Notes in Comput. Science, vol. 1790, Springer, Berlin, 2000, pp. 451-464. · Zbl 0982.93046
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.