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

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

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

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

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

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

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

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

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

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

IDR: 143178098

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

  • Вишневский В.М., Семенова О. В. Системы иоллинга: теория и применение в широкополосных беспроводных сетях. М.: Техносфера, 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.
  • 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.
  • 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.
Еще
Статья обзорная
SciUp 2024 © 2024 ©