Методы регенеративного моделирования для анализа многосерверных систем обслуживания

Александр Сергеевич Румянцев, Ирина Валерьевна Пешкова, Alexander Rumyantsev, Irina Peshkova

Аннотация


В статье представлены методы регенеративного моделирования многосерверных систем обслуживания в применении к доверительному оцениванию их характеристик. Кроме известных методов построения классической и слабой регенерации, представлены методы искусственной регенерации и регенеративных огибающих в применении к современным моделям, таким как модель многосерверной системы с управлением энергоэффективностью и модель вычислительного кластера.

Ключевые слова


регенеративное моделирование; доверительное оценивание; многосерверные системы; метод расщепления, высокопроизводительный вычислительный кластер

Полный текст:

PDF

Литература


Sutter H. The free lunch is over: A fundamental turn toward concurrency in software // Dr. Dobb’s Journal. 2005. P. 1-9.

Rumyantsev A., Morozov E. Stability criterion of a multiserver model with simultaneous service. Annals of Operations Research. 2017 (First Online: 2015). Vol. 252. No. 1. P. 29-39. DOI: 10.1007/s10479-015-1917-2

Feitelson D. G. Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press, New York, 2015. DOI: 10.1017/CBO9781139939690

Asmussen S. Applied probability and queues. Springer-Verlag, New York, 2003. DOI: 10.1007/b97236

Kalashnikov V. Topics on regenerative processes. CRC Press, Roca Baton. 1994.

Shedler G. Regeneration and networks of queues. Springer-Verlag, 1987. DOI: 10.1007/978-1-4612-1050-4

Glynn P., Iglehart D. Simulation methods for queues: an overview. Queueing Systems. 1988. Vol.3, P. 221-256. DOI: 10.1007/BF01161216

Thorrison H. Coupling, stationarity, and regeneration. Springer-Verlag, New York, 2000. DOI: 10.1007/978-1-4612-1236-2

Foss S., Kalashnikov V. Regeneration and renovation in queues // Queueing Systems. 1991. N. 8. P. 211-224. DOI: 10.1007/BF02412251

Kalashnikov V. V. Regenerative queueing processes and their qualitative and quantitative analysis // Queueing Systems. 1990. Vol. 6. P. 113-136. DOI: 10.1007/BF02411469

Foss S. G. On the ergodicity conditions for stochastically recursive sequences // Queueing Systems. 1992. Vol. 12. P. 287-296. DOI: 10.1007/BF01158804

Glynn P. Wide-sense regeneration for Harris recurrent Markov processes: an open problem // Queueing Systems. 2011. Vol. 68, no. 3-4. P. 305-311. DOI: 10.1007/s11134-011-9238-x

Sigman K., Wolff R. W. A review of regenerative processes // SIAM Review. 1993. Vol. 35, no. 2. P. 269-288. DOI: 10.1137/1035046

Andronov A. Artificial regeneration points for stochastic simulation of complex systems // Simulation Technology: Science and Art. 10th European Simulation Symposium ESS'98, Proceedings. 1998. P. 34-40.

Morozov E. V. Coupling and stochastic monotonicity of queueing processes. Петрозаводск: Изд-во ПетрГУ, 2013. 72 с.

Morozov E., Rumyantsev A., Peshkova I. Monotonocity and stochastic bounds for simultaneous service multiserver systems // 8th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops. Institute of Electrical and Electronics Engineers. 2016. P. 294-297. DOI: 10.1109/ICUMT.2016.7765374

Крэйн М., Лемуан О. Введение в регенеративный метод анализа моделей. М.: Наука, 1982.

Морозов Е. В., Дельгадо Р. Анализ стационарности регенеративных систем обслуживания // Автоматика и Телемеханика. 2009. Т. 70. С. 42-58.

Borovkov A. A. Asymptotic Methods in Queueing Theory. Wiley, New York, 1984.

Foss S., Konstantopoulos T. An overview of some stochastic stability methods // Journal of the Operations Research Society of Japan. 2004. Vol. 47, no. 4. P. 275-303.

Боровков А. А. Теория вероятностей. М., 1972.

Kiefer J., Wolfowitz J. On the theory of queues with many servers // Transactions of the American Mathematical Society. 1955. P. 1-18. DOI: 10.1090/S0002-9947-1955-0066587-3

Charlot F., Ghidouche M., Hamami M. Irreducibilite et recurrence au sens de Harris des <> des files GI/G/q // Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. P. 187-203.

Sigman K. Queues as Harris recurrent Markov chains // Queueing Systems. 1988. Vol. 3. P. 179-198. DOI: 10.1007/BF01189048

% Sigman K. Queues as Harris recurrent Markov chains // Queueing Systems. 1988. Т. 3. № 2. С. 179–198.

Whitt W. Embedded renewal processes in the GI/G/s queue // Journal of Applied Probability. 1972. Vol. 9. P. 650-658. DOI: 10.1017/S0021900200035944

Whitt W. Comparing counting processes and queues // Advances in Applied Probability. 1981. Vol. 13, no. 1. P. 207-220. DOI: 10.2307/1426475

Morozov E. Stochastic boundness of some queueing systems. Preprint No R-95-2022, ISSN 0908-1216, Dept. Math. and Computer Sci., Aalborg Univ., Aalborg, Denmark. 1995.

Morozov E. The tightness in the ergodic analysis of regenerative queueing processes // Queueing Systems. 1997. Vol. 27. P. 179-203. DOI: 10.1023/A:1019114131583

Feller W. An introduction to probability theory and its applications. Wiley, New York, 1950.

Nummelin E. A Splitting Technique for Harris Recurrent Markov Chains // Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. P. 309-318. DOI: 10.1007/BF00534764

Athreya K. B., Ney P. A new approach to the limit theory of recurrent Markov Chains // Transactions of the American Mathematical Society. 1978. Vol. 245. P. 493-501. DOI: 10.1090/S0002-9947-1978-0511425-0

Morozov E., Rumyantsev A. Stability Analysis of a MAP/M/s Cluster Model by Matrix-Analytic Method. Lecture Notes in Computer Science. Computer Performance Engineering: 13th European Workshop. 2016. Vol. 9951. P. 63-76. DOI: 10.1007/978-3-319-46433-6_5

Morozov E., Rumyantsev A., Nekrasova R. Peshkova I. A Regeneration-Based Estimation of High Performance Multiserver Systems // Communications in Computer and Information Science. 2016. Vol. 608. P. 271-282. DOI: 10.1007/978-3-319-39207-3_24

Морозов Е.В., Румянцев А.С. Модели многосерверных систем для анализа вычислительного кластера // Труды Карельского научного центра РАН. 2011. Вып. 5. С. 75-85.

Nguyen T. A. et al. Availability Modeling and Analysis for Software Defined Networks // 2015 IEEE 21st Pacific Rim International Symposium on Dependable Computing (PRDC), Zhangjiajie, 2015. P. 159-168. DOI: 10.1109/PRDC.2015.27

S. Ross. Simulation // Academic Press. New York. 1997.

REFERENCES IN ENGLISH

Sutter H. The free lunch is over: A fundamental turn toward concurrency in software // Dr. Dobb’s Journal. 2005. P. 1-9.

Rumyantsev A., Morozov E. Stability criterion of a multiserver model with simultaneous service. Annals of Operations Research. 2017 (First Online: 2015). Vol. 252. No. 1. P. 29-39. DOI: 10.1007/s10479-015-1917-2

Feitelson D. G. Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press, New York, 2015. DOI: 10.1017/CBO9781139939690

Asmussen S. Applied probability and queues. Springer-Verlag, New York, 2003. DOI: 10.1007/b97236

Kalashnikov V. Topics on regenerative processes. CRC Press, Roca Baton. 1994.

Shedler G. Regeneration and networks of queues. Springer-Verlag, 1987. DOI: 10.1007/978-1-4612-1050-4

Glynn P., Iglehart D. Simulation methods for queues: an overview. Queueing Systems. 1988. Vol.3, P. 221-256. DOI: 10.1007/BF01161216

Thorrison H. Coupling, stationarity, and regeneration. Springer-Verlag, New York, 2000. DOI: 10.1007/978-1-4612-1236-2

Foss S., Kalashnikov V. Regeneration and renovation in queues // Queueing Systems. 1991. N. 8. P. 211-224. DOI: 10.1007/BF02412251

Kalashnikov V. V. Regenerative queueing processes and their qualitative and quantitative analysis // Queueing Systems. 1990. Vol. 6. P. 113-136. DOI: 10.1007/BF02411469

Foss S. G. On the ergodicity conditions for stochastically recursive sequences // Queueing Systems. 1992. Vol. 12. P. 287-296. DOI: 10.1007/BF01158804

Glynn P. Wide-sense regeneration for Harris recurrent Markov processes: an open problem // Queueing Systems. 2011. Vol. 68, no. 3-4. P. 305-311. DOI: 10.1007/s11134-011-9238-x

Sigman K., Wolff R. W. A review of regenerative processes // SIAM Review. 1993. Vol. 35, no. 2. P. 269-288. DOI: 10.1137/1035046

Andronov A. Artificial regeneration points for stochastic simulation of complex systems // Simulation Technology: Science and Art. 10th European Simulation Symposium ESS'98, Proceedings. 1998. P. 34-40.

Morozov E. V. Coupling and stochastic monotonicity of queueing processes. Петрозаводск: Изд-во ПетрГУ, 2013. 72 с.

Morozov E., Rumyantsev A., Peshkova I. Monotonocity and stochastic bounds for simultaneous service multiserver systems // 8th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops. Institute of Electrical and Electronics Engineers. 2016. P. 294-297. DOI: 10.1109/ICUMT.2016.7765374

Crane M. A., Lemoine A. J. An Introduction to the Regenerative Method for Simulation Analysis (in Russian). Moscow: Nauka, 1982.

Morozov E. V., Delgado R. Stability analysis of regenerative queueing systems (in Russian) // Avtomatika i Telemekhanika. 2009. Т. 70. С. 42-58.

Borovkov A. A. Asymptotic Methods in Queueing Theory. Wiley, New York, 1984.

Foss S., Konstantopoulos T. An overview of some stochastic stability methods // Journal of the Operations Research Society of Japan. 2004. Vol. 47, no. 4. P. 275-303.

Borovkov A. A. Probability Theory (in Russian). Moscow, 1972.

Kiefer J., Wolfowitz J. On the theory of queues with many servers // Transactions of the American Mathematical Society. 1955. P. 1-18. DOI: 10.1090/S0002-9947-1955-0066587-3

Charlot F., Ghidouche M., Hamami M. Irreducibilite et recurrence au sens de Harris des <> des files GI/G/q // Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. P. 187-203.

Sigman K. Queues as Harris recurrent Markov chains // Queueing Systems. 1988. Vol. 3. P. 179-198. DOI: 10.1007/BF01189048

% Sigman K. Queues as Harris recurrent Markov chains // Queueing Systems. 1988. Т. 3. № 2. С. 179–198.

Whitt W. Embedded renewal processes in the GI/G/s queue // Journal of Applied Probability. 1972. Vol. 9. P. 650-658. DOI: 10.1017/S0021900200035944

Whitt W. Comparing counting processes and queues // Advances in Applied Probability. 1981. Vol. 13, no. 1. P. 207-220. DOI: 10.2307/1426475

Morozov E. Stochastic boundness of some queueing systems. Preprint No R-95-2022, ISSN 0908-1216, Dept. Math. and Computer Sci., Aalborg Univ., Aalborg, Denmark. 1995.

Morozov E. The tightness in the ergodic analysis of regenerative queueing processes // Queueing Systems. 1997. Vol. 27. P. 179-203. DOI: 10.1023/A:1019114131583

Feller W. An introduction to probability theory and its applications. Wiley, New York, 1950.

Nummelin E. A Splitting Technique for Harris Recurrent Markov Chains // Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete. 1978. Vol. 43. P. 309-318. DOI: 10.1007/BF00534764

Athreya K. B., Ney P. A new approach to the limit theory of recurrent Markov Chains // Transactions of the American Mathematical Society. 1978. Vol. 245. P. 493-501. DOI: 10.1090/S0002-9947-1978-0511425-0

Morozov E., Rumyantsev A. Stability Analysis of a MAP/M/s Cluster Model by Matrix-Analytic Method. Lecture Notes in Computer Science. Computer Performance Engineering: 13th European Workshop. 2016. Vol. 9951. P. 63-76. DOI: 10.1007/978-3-319-46433-6_5

Morozov E., Rumyantsev A., Nekrasova R. Peshkova I. A Regeneration-Based Estimation of High Performance Multiserver Systems // Communications in Computer and Information Science. 2016. Vol. 608. P. 271-282. DOI: 10.1007/978-3-319-39207-3_24

Morozov E. V., Rumyantsev A. S. Multiserver system models for high performance cluster analysis (in Russian) // Transactions of Karelian Research Centre of RAS. 2011. Vol. 5. P. 75-85.

Nguyen T. A. et al. Availability Modeling and Analysis for Software Defined Networks // 2015 IEEE 21st Pacific Rim International Symposium on Dependable Computing (PRDC), Zhangjiajie, 2015. P. 159-168. DOI: 10.1109/PRDC.2015.27

S. Ross. Simulation // Academic Press. New York. 1997.




DOI: http://dx.doi.org/10.17076/mat838

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

© Труды КарНЦ РАН, 2014-2019