Обзор моделей систем поллинга и их применение в телекоммуникационных сетях

Автор: Вишневский Владимир Миронович, Семенова Ольга Валерьевна

Журнал: Проблемы информатики @problem-info

Рубрика: Прикладные информационные технологии

Статья в выпуске: 4 (49), 2020 года.

Бесплатный доступ

В статье представлен обзор работ по исследованию стохастических систем поллинга, опубликованных в период 2007-2019 гг. Приведена классификация дискретных и непрерывных систем поллинга. Описаны точные и приближенные методы исследования систем поллинга с различными типами входящих потоков (пуассоновские и ВМАР-потоки) и количеством очередей, а также различными дисциплинами обслуживания и порядком опроса очередей. Приводится описание применения моделей поллинга в различных приложениях, в частности, для оценки производительности широкополосных беспроводных сетей с централизованным механизмом управления.

Системы поллинга, порядок опроса, дисциплина обслуживания очереди, метод анализа средних, метод производящих функций, широкополосные беспроводные сети

Короткий адрес: https://sciup.org/143178101

IDR: 143178101 | DOI: 10.24411/2073-0667-2020-10015

Список литературы Обзор моделей систем поллинга и их применение в телекоммуникационных сетях

Вишневский В.М., Семенова О. В. Системы иоллинга: теория и применение в широкополосных беспроводных сетях. М.: Техносфера, 2007. 312 с.
Vishnevsky V., Semenova О. Polling Systems: Theory and Applications for Broadband Wireless Networks // LAMBERT Academic Publishing, 2012. 317p*
Boon M. A. A., van der Mei R. D., WTinands E. M. M. Applications of polling systems // Surveys in Operations Research and Management Science. 2011. V. 16, N 2. P. 67-82.
Cao J., Feng WT., Chen Y., Ge N., Wang S. Performance analysis of a polling model with BMAP and across-queue state-dependent service discipline // IEEE Access. 2019. V. 7. P. 127230-127253.
He M., Guan Z., Wu Z., Lu L., Zhou Z., Anisetti M., Damiani E. A polling access control with exhaustive service in wireless body area networks for mobile healthcare using the sleeping schema // Journal of Ambient Intelligence and Humanized Computing. 2019. V. 10, N 10. P. 3761-3774.
Granville K., Drekic S. A 2-class maintenance model with dynamic server behavior // TOP. 2019. DOI: https://doi.org/10.1007/sll750-019-00509-l
Takagi H. Analysis of polling systems. MIT Press, 1986.
Borst S.C. Polling systems. Amsterdam: Stichting Mathematisch Centrum, 1996.
Вишневский В. \!.. Семенова О. В. Математические методы исследования систем поллинга // Автоматика и телемеханика. 2006. № 2. С. 3-56.
Вишневский В.М., Мишкой Г. К., Семенова О. В. Новые модели и методы исследования систем поллинга // Proceedings of the International Conference proceedings Distributed Computer and Communication Networks. Theory and Applications (DCCN-2009, Moscow). M.: R&D Company „Information and Networking Technologies", 2009. C. 79-85.
Borst S.C., Boxma O.J. Polling: past, present, and perspective // TOP. 2018. V. 26, N 3. P. 335-369.
Vishnevsky V. M., Semenova O.V., Bui D.T., Sokolov A.M. Adaptive cyclic polling systems: analysis and application to the broadband wireless networks // Lecture Notes in Computer Science. 2019. V. 11965. P. 30-42.
WTinands E. M.M., Adán I. J.B.F., van Houtum G.J., Down D.G. A state-dependent polling model with k-limited service // Probability in the Engineering and Informational Sciences. 2009. V. 23, N 2. P. 385-408.
Boon M. A. A., Adán I. J. B. F., Boxma O.J. A two-queue polling model with two priority levels in the first queue // Discrete Event Dynamic Systems. 2010. V. 20, N 4. P. 511-536.
Vlasiou M., Adán I. J. B. F., Boxma O.J. A two-station queue with dependent preparation and service times // European Journal of Operational Research. 2009. V. 195, N 1. P. 104-116.
Chernova N., Foss S., Kim B. A polling system whose stability region depends on the whole distribution of service times // Operations Research Letters. 2013. V. 41, N 2. P. 188-190.
Dorsman J.-P. L., Boxma О. J., van der Mei R. D. On two-queue Markovian polling systems with exhaustive service // Queueing Systems. 2014. V. 78, N 4. P. 287-311.
Boon M.A.A., Winands E. M.M. Heavy-traffic analysis of k-limited polling systems // Probability in the Engineering and Informational Sciences. 2014. V. 28, N 4. P. 451-471.
Adán I. J.B.F., Boxma O. J., Kapodistria S., Kulkarni V. G. The shorter queue polling model // Annals of Operations Research. 2016. V. 241, N 1. P. 167-200.
Gaidamaka Yu.V. Model with threshold control for analysing a server with SIP protocol in the overload mode // Automatic Control and Computer Science. 2013. V. 47, N 4. P. 211-218.
Shorgin S., Samouvlov K., Gaidamaka Y., Etezov S. Polling system with threshold control for modeling of SIP server under overload // Advances in Intelligent Systems and Computing. 2014. V. 240. P. 97-107.
Avrachenkov K., Perel E., Yechiali U. Finite-buffer polling system with threshold-based switching policy // TOP. 2016. V. 24, No. 3. P. 541-571.
Perel E., Yechiali U. Two-queue polling systems with switching policy based on the queue that is not being served // Stochastic Models. 2017. V. 33, N 3. P. 430-450.
Jolles A., Perel E., Yechiali U. Alternating server with non-zero switch-over times and opposite-queue threshold-based switching policy // Performance Evaluation. 2018. V. 126. P. 22-38.
Liu Z., Chu Y., Wu J. On the three-queue priority polling system with threshold service policy // Journal of Applied Mathematics and Computing. 2017. V. 53, N 1. P. 445-470.
Chernova N., Foss S., Kim B. On the stability of a polling system with an adaptive service mechanism // Annals of Operations Research. 2012. V. 198, N 1. P. 125-144.
Winands E. M. M., Adán I. J. B. F., van Houtum G. J. Mean value analysis for polling systems // Queueing Systems. 2006. V. 54. P. 35-44.
van der Mei R. D., WTinands E. Heavy traffic analysis of polling models by mean value analysis // Performance Evaluation. 2008. V. 65, N 6-7. P. 400-416.
Vishnevsky V. M., Semenova O.V. Adaptive dynamical polling in wireless networks // Cybernetics and Information Technologies. 2008. V. 8, N 1. P. 3-11.
WTierman A., WTinands E., Boxma O.J. Scheduling in polling systems // Performance Evaluation. 2007. V. 64, N 9-12. P. 1009-1028.
Boon M.A.A., van WTijk A. C.C., Adán I.J.B.F., Boxma O.J. A polling model with smart customers // Queueing Systems. 2010. V. 66. P. 239-274.
Вишневский B.M., Семенова О. В., Шпилев С. А. Дуплексная система циклического обслуживания смешанных очередей // Автоматика и телемеханика. 2009. № 12. С. 121-133.
Yechiali U. Analysis and control of polling systems // Performance Evaluate of Computer and Communication Systems. Ed. Donatielo L., Nelson R. Springer-Verlag. 1993. P. 630-650.
Boxma O.J., Kella O., Kosinski K.M. Queue lengths and workloads in polling systems // Operations Research Letters. 2011. V. 39, N 6. P. 401-405.
Resing J. A. C. Polling systems and multitvpe branching processes // Queueing Systems. 1993. V. 13. P. 413-426.
Guan Z., Zhao D. A delay-guaranteed two-level polling model // Advances in Computer Science and Information Engineering. Advances in Intelligent and Soft Computing. 2012. V. 168. P. 153-158.
Saffer Z., Telek M. Unified analysis of BMAP/G/1 cyclic polling models // Queueing Systems. 2010. V. 64, N 1. P. 69-102.
Вишневский В.М., Дудин А.Н., Клименок В. И. Стохастические системы с коррелированными потоками. Теория и применение в телекоммуникационных сетях. М.: Рекламно-издательский центр „ТЕХНОСФЕРА", 2018.
Dudin A. N., Klimenok V. I., Vishnevsky V. М. Methods to Study Queuing Systems with Correlated Arrivals. 2020. Springer. 410 p.
Hiravama Т., Hong S.J., Krunz M.M. A new approach to analysis of polling systems // Queueing Systems. 2004. V. 48, N 1-2. P. 135-158.
Hiravama T. Multiclass polling systems with Markovian feedback: mean sojourn times in gated and exhaustive systems with local priority and FCFS service orders // Journal of the Operations Research Society of Japan. 2005. V. 48, N3. P. 226-255.
Hiravama T. Markovian polling systems: functional computation for mean waiting times and its computational complexity // Advances in Queueing Theory and Network Applications. W. Yue et al. (eds.) 2009. P. 119-146.
Рыков В. В. К анализу поллинг-систем // Автоматика и телемеханика. 2008. № 6. С. 90114.
van der Mei R. D. Towards a unifying theory on branching-type polling systems in heavy traffic // Queueing Systems. 2007. V. 57, N 1. P. 29-46.
Семенова О. В., Буй 3. Т. Пакет прикладных программ для исследования систем поллинга // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2020. № 50. С. 106-113.
Saffer Z. BMAP/G/1 cyclic polling model with binomial disciplines // Modern Probabilistic Methods for Analysis of Telecommunication Networks. Communications in Computer and Information Science. 2013. V. 356. P. 157-166.
Вишневский В. \!.. Семенова О. В., Буй Д. Т. Использование машинного обучения для исследования систем поллинга с коррелированным входным потоком // Материалы всероссийской конференции с международным участием (ITTMM 2020). Москва, РУДН, 13-17 апреля 2020. С. 248-253.
Saffer Z., Telek М. Stability of periodic polling system with BMAP arrivals // European Journal of Operational Research. 2009. V. 197, N 1. P. 188-195.
Vis P., Bekker R., van der Mei R. D. Transient analysis of cycle lengths in cyclic polling systems // Performance Evaluation. 2015. V. 91. P. 303-317.
Dorsman J.-P. L., Borst S.C., Boxma O.J., Vlasiou M. Markovian polling systems with an application to wireless random-access networks // Performance Evaluation. 2015. V. 85-86. P. 33-51.
Hiravama T. Analysis of multiclass Markovian polling systems with feedback and composite scheduling algorithms // Annals of Operations Research. 2012. V. 198, N 1. P. 83-123.
Fiems D., Altman E. Gated polling with stationary ergodic walking times, Markovian routing and random feedback // Annals of Operations Research. 2012. V. 198, N 1. P. 145-164.
MacPhee I., Menshikov M., Petritis D., Popov S. A Markov chain model of a polling system with parameter regeneration // Annals of Applied Probability. 2007. V. 17, N 5-6. P. 1447-1473.
MacPhee I., Menshikov M., Petritis D., Popov S. Polling systems with parameter regeneration, the general case // Annals of Applied Probability. 2008. V. 18, N 6. P. 2131-2155.
Lee T. Analysis of single buffer random polling system with state-dependent input process and server/station breakdowns // International Journal of Operations Research and Information Systems (IJORIS). 2018. V. 9, N 1. P. 22-50.
Guan Z., Zhao D., Zhao Y. A discrete time two-level mixed service parallel polling model // Journal of Electronics (China). 2012. V. 29, N 1-2. P. 103-110.
Yang Z., Ding H. Characteristics of a two-class polling system model // Tsinghua Science and Technology. 2014. V. 19, N 5. P. 516-520.
Bao L., Zhao D., Zhao Y. A priority-based polling scheduling algorithm for arbitration policy in Network on Chip // Journal of Electronics (China). 2012. V. 29, N 1-2. P. 120-127.
Vishnevsky V. M., Dudin A.N., Semenova O.V., Klimenok V.I. Performance analysis of the BMAP/G/1 V. 68, N 5. P. 446-462.
Vishnevsky V. M., Dudin A.N., Klimenok V. I., Semenova O.V., Shpilev S. Approximate method to study M/G/1-tvpe polling system with adaptive polling mechanism // Quality Technology and Quantitative Management. 2012. V. 2. P. 211-228.
Semenova O.V., Bui D.T. Method of generating functions for performance characteristic analysis of the polling systems with adaptive polling and gated service // Communications in Computer and Information Science. 2018. V. 912. P. 348-359.
Boon M. A. A., Adán I. J. B. F. Mixed gated/exhaustive service in a polling model with priorities // Queueing Systems. 2009. V. 63, N 1-4. P. 383-399.
Boon M.A.A., Adán I.J.B.F., Boxma O.J. A polling model with multiple priority levels // Performance Evaluation. 2010. V. 67, N 6. P. 468-484.
Shapira G., Levy H. On fairness in polling systems // Annals of Operations Research. 2016. https://doi.org/10.1007/sl0479-016-2247-8
Boon M., Boxma O.J., Winands E.J.J. On open problem in polling systems // Queueing Systems. 2011. V. 68, N 3-4. P. 365-374.
Winands E.M.M. Branching-type polling systems with large setups // OR Spectrum. 2011. V. 33. P. 77-97.
Hanbali A. A., de Haan R., Boucherie R. J., van Ommeren J.-K. Time-limited polling systems with batch arrivals and phase-type service times // Annals of Operations Research. 2012. V. 198, N 1. P. 57-82.
Boxma O. J., Groenendijk WT.P. Pseudo conservation laws in cyclic-service systems // Journal of Applied Probability. 1987. V. 24, N 4. P. 949-964.
Leonovich A., Ferng H.-WT. Modeling the IEEE 802.lie HCCA mode // Wireless Networks. 2013. V. 19, N 5. P. 771-783.
de Haan R., Boucherie R. J., van Ommeren J.-K. A polling model with an autonomous server // Queueing Systems. 2009. V. 62, N 3. P. 279-308.
Horng S.-C., Lin S.-Y. Ordinal optimization of G/G/1/K polling systems with k-limited service discipline // Journal of Optimization Theory and Applications. 2009. V. 140, N 2. P. 213-231.
van der Mei R. D., Roubos A. Polling models with multi-phase gated service // Annals of Operations Research. 2012. V. 198, N 1. P. 25-56.
van WTijk A. C. C., Adán I. J. B. F., Boxma O. J., WTierman A. Fairness and efficiency for polling
Remerova M., Foss S., Zwart B. Random fluid limit of an overloaded polling model // Advances in Applied Probability. 2014. V. 46, N 1. P. 76-101.
Ling Y., Liu C., Li Y. Study on queue strategy of gated polling multi-access communication system // Recent Advances in Computer Science and Information Engineering. Lecture Notes in Electrical Engineering. 2012. V. 124. P. 99-105.
Вишневский B.M., Лаконцев Д. В., Семенова О. В., Шпилев С. А. Модель системы пол-линга для исследования широкополосных беспроводных сетей // Автоматика и телемеханика. 2006. № 12. С. 123-135.
Vatutin V. A. Multitvpe Branching processes with immigration in random environment, and polling systems // Siberian Advances in Mathematics. 2011. V. 21, N 1. P. 42-72.
Abidini M. A., Boxma O., Resing J. Analysis and optimization of vacation and polling models with retrials // Performance Evaluation. 2016. V. 98. P. 52-69.
Kim B., Kim J. Analysis of the waiting time distribution for polling systems with retrials and glue periods // Annals of Operations Research. 2019. V. 277, N 2. P. 197-212.
Dorsman J. L., van der Mei R. D., Winands E. M. M. Polling systems with batch service // OR Spectrum. 2012. V. 34. P. 743-761.
Boon M. A. A., Winands E. M. M., Adán I. J. B. F., van Wijk A. C. C. Closed-form waiting time approximations for polling systems // Performance Evaluation. 2011. V. 68, N 3. P. 290-306.
Jiang T., Liu L., Zhu Y. Analysis of a batch service polling system in a multi-phase random environment // Methodology and Computing in Applied Probability. 2017. P. 1-20.
Shomronv M., Yechiali U. Polling systems with positive and negative customers // Technical Report, Department of Statistics and Operations Research, Tel-Aviv University, Tel-Aviv, Israel. 2006.
Shomronv M., Yechiali U. Polling systems with job failures and with station failures // Technical Report, Department of Statistics and Operations Research, Tel-Aviv University, Tel-Aviv, Israel. 2006.
Zorine A. V. On ergodicitv conditions in a polling model with Markov modulated input and state-dependent routing // Queueing Systems. 2014. V. 76, N 2. P. 223-241.
Boon M. A. A. A polling model with reneging at polling instants // Annals of Operations Research. 2012. V. 198, N 1. P. 5-23.
Granville K., Drekic S. On a 2-class polling model with reneging and ^-limited service // Annals of Operations Research. 2019. V. 274, N 1. P. 267-290.
Neuts M.F. Matrix-geometric solutions in stochastic models: an algorithmic approach. Baltimore: Johns Hopkins University Press, 1981.
Boxma O.J., Bruin J., Fralix B.H. Sojourn times in polling systems with various service disciplines // Performance Evaluation. 2009. V. 66, N 11. P. 621-639.
Bekker R., Vis P., Dorsman J.L., van der Mei R. D., Winands E. M. M. The impact of scheduling policies on the waiting-time distributions in polling systems // Queueing Systems: Theory and Applications. 2015. V. 79, N 2. P. 145-172.
Vis P., Bekker R., van der Mei R. D. Heavy-traffic limits for polling models with exhaustive service and non-FCFS service order policies // Advances in Applied Probability. 2015. V. 47, N 4. P. 989-1014.
Kim B., Kim J. Sojourn time distribution in polling systems with processor-sharing policy // Performance Evaluation. 2017. Vol. 114, N 9. P. 97-112.
Cao J., Xie W. Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines // Queueing Systems. 2016. V. 85, N 1-2. P. 117147.
Chen WT.-L. Computing the moments of polling models with batch Poisson arrivals by transform inversion // INFORMS Journal of Computing. 2019. V. 31, N 3. P. 411-632.
Suman R., Krishnamurthv A. Analysis of tandem polling queues with finite buffers // Annals of Operations Research. 2019. https://doi.org/10.1007/sl0479-019-03358-0
Antunes N., Fricker C., Roberts J. Stability of multi-server polling system with server limits // Queueing Systems. 2011. Vol. 68. P. 229-235.
Boxma O., van der Wal J., Yechiali U. Polling with batch service // Stochastic Models. 2008. V. 24, No.4. P. 604-625.
Vlasiou M., Yechiali U. M/G/x> polling systems with random visit times // Probability in the Engineering and Informational Sciences. 2008. V. 22, N 1. P. 212-245.
van der Mei R. D., WTinands E. M.M. A note on polling models with renewal arrivals and nonzero switch-over times // Operations Research Letters. 2008. V. 36. P. 500-505.
van der Mei R. D., Levy H. Polling systems in heavy traffic: Exhaustiveness of service policies // Queueing Systems. 1997. Y. 27. N 3-4. R 227-250.
Dorsman J. L., van der Mei R. D., WTinands E. M. M. A new method for deriving waiting-time approximations in polling systems with renewal arrivals // Stochastic Models. 2011. V. 27. P. 318-332.
Boon M.A.A., van dcr Mci R. D., Winands E.M.M. Heavy traffic analysis of roving server networks /7 Stochastic Models. 2017. V. 33, N 3. P. 1 21.
Mevfrovt T. M. M., Boon M. A. A., Borst S. C., Boxma O. .J. Performance of large-scale polling systems with branching-type and limited service /7 Performance Evaluation. 2019. V. 133. P. 1 24. 106. Kavitha V., Combes R. Mixed polling with rerouting and applications /7 Performance Evaluation. 2013. V. 70, N 11. P. 1001 1027.
Boxma O., Ivanovs .J., Kosinski K., Mandjes M. Levy-driven polling systems and continuous-state branching processes /7 Stochastic Systems. 2011. V. 1, N 2. P. 411 436.
Leskela L., Unger F. Stability of a spatial polling system with greedy myopic service /7 Annals of Operations Research. 2012. V. 198, N 1. P. 165 183.
Kavitha V., Altman E. Continuous polling models and application to ferry assisted WLAN /7 Annals of Operations Research. 2012. V. 198, N 1. P. 185 218.
Beekhuizen P., Denteneer D., Resing .J. Reduction of a polling network to a single node /7 Qucucing Systems. 2008. V. 58. N. 4. P. 303 319.
Matveev A., Feoktistova V., Bolshakova K. On global near optimalitv of special periodic protocols for fluid polling systems with setups /7 .Journal of Optimization Theory and Applications. 2016. V. 171, N 3. P. 1055 1070.
Saffer Z., Telek M., Horvath G. Fluid polling system with Markov modulated load and gated discipline /7 Lecture Notes in Computer Science. 2018. V. 10932. P. 86 102.
Yechiali U., Czerniak O. Fluid polling systems /7 Qucucing Systems. 2009. V. 63, N 12. P. 401 435.
Czerniak O., Altman E., Yechiali U. Orchestrating parallel TCP connections: cyclic and probabilistic polling policies /7 Performance Evaluation. 2012. V. 69, N 3 4. P. 150 163.

Еще

Статья научная