An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service

BAO Li-yong; DING Xin-yu; DING Hong-wei; GUAN Zheng; GE Jun-yang

doi:10.12263/DZXB.20220827

您当前的位置：

首页 >

文章列表页 >

An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service

PAPERS | 更新时间：2025-12-11

- An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service
- ACTA ELECTRONICA SINICA Vol. 52, Issue 3, Pages: 838-848(2024)
- 作者机构：
  
  云南大学信息学院，云南昆明 650091
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(61072079;61461053)
- DOI：10.12263/DZXB.20220827
  CLC： TP393
- Received：14 July 2022，
  
  Revised：2023-05-09，
  
  Published：25 March 2024
- 稿件说明：
移动端阅览
保利勇,丁新昱,丁洪伟,等.离散时间的完全服务并行优化轮询排队系统特性分析[J].电子学报,2024,52(03):838-848.

BAO Li-yong, DING Xin-yu, DING Hong-wei, et al.An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service[J].Acta Electronica Sinica, 2024, 52(03): 838-848.
保利勇,丁新昱,丁洪伟,等.离散时间的完全服务并行优化轮询排队系统特性分析[J].电子学报,2024,52(03):838-848. DOI：10.12263/DZXB.20220827

BAO Li-yong, DING Xin-yu, DING Hong-wei, et al.An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service[J].Acta Electronica Sinica, 2024, 52(03): 838-848. DOI：10.12263/DZXB.20220827

摘要

轮询是一种依次有序服务的系统资源动态调度机制.针对服务器在站点间查询、服务和转移过程中的流水线作业方式导致了系统整体服务效率较低的问题，本文提出了完全服务的并行优化轮询系统.首先，构建了系统的单服务器多队列排队模型和相应的系统状态方程，并精确解析出系统特性参数的完整数学解析表达式.此外，还提出了一种系统状态稳定性的判定方法，对不同负载状态下的系统稳定性进行了定量分析.计算机仿真的统计分析结果与理论计算值相一致.最后，系统性能分析表明，在保持周期性、无冲突服务的基础上，系统的队长、时延特性和稳定状态下负载能力均得到了较大的提高.

Abstract

Polling is a dynamic scheduling mechanism of system resources with orderly services. Considering the low service efficiency of the whole system in the pipelining process of the server

this paper proposes a novel system of parallel optimization polling based on an exhaustive service policy. Firstly

the systematic single-server multi-queue queuing model and its equations of state transfer are constructed. Secondly

the complete mathematical analytical expressions of the system characteristic parameters are accurately analyzed. In addition

this paper attempts a method to quantitatively analyze the system stability under different load states. The statistical analysis result of the computer is consistent with the theoretical calculation value. Moreover

the system performance analysis shows that the queuing length

waiting delay characteristics and load capacity in steady state of the polling system have been greatly improved while maintaining periodic and conflict-free services.

关键词

Keywords

references

TEYMOORI P , SOHRABY K , KIM K . A fair and efficient resource allocation scheme for multi-server distributed systems and networks [J ] . IEEE Transactions on Mobile Computing , 2016 , 15 ( 9 ): 2137 - 2150 .

FRALIX B . A new look at a smart polling model [J ] . Mathematical Methods of Operations Research , 2018 , 88 ( 3 ): 339 - 367 .

XU J , GAUTAM N . On competitive analysis for polling systems [J ] . Naval Research Logistics , 2020 , 67 ( 6 ): 404 - 419 .

VLADLMIR V , OLGA S . Polling systems and their application to telecommunication networks [J ] . Mathematics , 2021 , 9 ( 2 ): 117 .

BIANCHI G . Performance analysis of the IEEE 802.11 distributed coordination function [J ] . IEEE Journal on Selected Areas in Communications , 2000 , 18 ( 3 ): 535 - 547 .

TOUMI M , SEMCHEDINE F . Improving the throughput in lightly disturbed IEEE 802.11 DCF saturated network using the fragmentation mechanism under basic access Mode [J ] . Wireless Personal Communications , 2021 , 118 ( 4 ): 2383 - 2397 .

DVIR N , HASSIN R , YECHIALI U . Strategic behaviour in a tandem queue with alternating server [J ] . Queueing Systems , 2020 , 96 ( 3 ): 205 - 244 .

ABHISHEK , BOON M A A , BOXMA O J , et al . A single-server queue with batch arrivals and semi-Markov services [J ] . Queueing Systems , 2017 , 86 ( 3 ): 217 - 240 .

BORST S , BOXMA O J . Polling: Past, present, and perspective [J ] . TOP , 2018 , 26 ( 3 ): 335 - 369 .

TAKAGI H . Mean message waiting times in symmetric multi-queue systems with cyclic service [J ] . Performance Evaluation , 1985 , 5 ( 4 ): 271 - 277 .

赵东风 , 郑苏民 . 查询式完全服务排队模型分析 [J ] . 电子学报 , 1994 , 22 ( 5 ): 102 - 107 .

ZHAO D F , ZHENG S M . Analysis of a polling model with exhaustive service [J ] . Acta Electronica Sinica , 1994 , 22 ( 5 ): 102 - 107 . (in Chinese)

LEE G , SHIN S , JEONG J . Efficient hybrid polling for ultra-low latency storage devices [J ] . Journal of Systems Architecture , 2022 , 122 : 102338 .

JIANG T , LU X Z , LIU L , et al . Strategic behavior of customers and optimal control for batch service polling systems with priorities [J ] . Complexity , 2020 , 2020 : 6015372 .

RAN W X , LIU S , ZHANG Z . A polling-based dynamic order-picking system considering priority orders [J ] . Complexity , 2020 , 2020 : 4595316 .

BOON M A A , ADAN I J B F , BOXMA O J . A polling model with multiple priority levels [J ] . Performance Evaluation , 2010 , 67 ( 6 ): 468 - 484 .

PEREL E , PEREL N , YECHIALI U . A polling system with‘join the shortest - serve the longest' policy [J ] . Computers & Operations Research , 2020 , 114 : 104809 .

MEYFROYT T M M , BOON M A A , BORST S C , et al . Performance of large-scale polling systems with branching-type and limited service [J ] . Performance Evaluation , 2019 , 133 : 1 - 24 .

YANG Z J , MAO L , YAN B , et al . Performance analysis and prediction of asymmetric two-level priority polling system based on BP neural network [J ] . Applied Soft Computing , 2021 , 99 : 106880 .

ADAN I J B F , BOXMA O J , KAPODISTRIA S , et al . The shorter queue polling model [J ] . Annals of Operations Research , 2016 , 241 ( 1 ): 167 - 200 .

KIM B , KIM J . Analysis of the waiting time distribution for polling systems with retrials and glue periods [J ] . Annals of Operations Research , 2019 , 277 ( 2 ): 197 - 212 .

UNCU N . Load balancing in polling systems under different policies via simulation optimization [J ] . International Journal of Simulation Modelling , 2022 , 21 ( 2 ): 273 - 283 .

VAN DER GAAST J P , ADAN I J B F , KOSTER R B M DK . The analysis of batch sojourn-times in polling systems [J ] . Queueing Systems , 2017 , 85 ( 3 ): 313 - 335 .

BOON M A A , BOXMA O J , KELLA O , et al . Queue-length balance equations in multiclass multiserver queues and their generalizations [J ] . Queueing Systems , 2017 , 86 ( 3 ): 277 - 299 .

PAPACONSTANTINOU X , BERTSIMAS D . Relations between the prearrival and the postdeparture state probabilities and the fcfs waiting time distribution in the Ek/G/s queue [J ] . Naval Research Logistics , 1990 , 37 ( 1 ): 135 - 149 .

HEBUTERNE G . Relation between states observed by arriving and departing customers in bulk systems [J ] . Stochastic Processes and Their Applications , 1987 , 27 ( 2 ): 279 - 289 .

BOON M A A , WINANDS E M M . Open problems for critically loaded k-limited polling systems [J ] . Queueing Systems , 2022 , 100 ( 3 ): 281 - 283 .

ADAN I J B F , KULKARNI V G , LEE N , et al . Optimal routeing in two-queue polling systems [J ] . Journal of Applied Probability , 2018 , 55 ( 3 ): 944 - 967 .

JOLLES A , PEREL E , YECHIALI U . Alternating server with non-zero switch-over times and opposite-queue threshold-based switching policy [J ] . Performance Evaluation , 2018 , 126 : 22 - 38 .

罗启鹏 , 保利勇 , 丁洪伟 , 等 . 离散时间并行优化门限服务轮询系统排队特性解析 [J ] . 电子学报 , 2019 , 47 ( 9 ): 1937 - 1942 .

LUO Q P , BAO L Y , DING H W , et al . Performance analysis of discrete time polling queuing system based on parallel optimization gated service [J ] . Acta Electronica Sinica , 2019 , 47 ( 9 ): 1937 - 1942 . (in Chinese)

刘春花 , 赵东风 , 丁洪伟 . 周期查询系统并行调度策略研究 [J ] . 云南大学学报(自然科学版) , 2003 , 25 ( 5 ): 401 - 404 .

LIU C H , ZHAO D F , DING H W . Study of parallel schedules for polling systems with limited service [J ] . Journal of Yunnan University (Natural Science) , 2003 , 25 ( 5 ): 401 - 404 . (in Chinese)

SAFFER Z , TELEK M , HORVÁTH G . Analysis of Markov-modulated fluid polling systems with gated discipline [J ] . Journal of Industrial & Management Optimization , 2021 , 17 ( 2 ): 575 - 599 .

DUDIN A , DUDIN S , KLIMENOK V , et al . Vacation queueing model for performance evaluation of multiple access information transmission systems without transmission interruption [J ] . Mathematics , 2021 , 9 ( 13 ): 1508 .

ZEIFMAN A , KOROLEV V , SATIN Y . Two approaches to the construction of perturbation bounds for continuous-time markov chains [J ] . Mathematics , 2020 , 8 ( 2 ): 253 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on Two-class Priority Based Polling System

A Fair On-Demand Access Protocol for Mobile Ad Hoc Networks

Convergent Cascade-Form Adaptive IIR Filter

Related Author

ZHAO Yi-fan

DING Hong-wei

ZHAO Dong-feng

YANG Zhi-jun

LIU Kai

LI Han-tao

ZHANG Jun

CHEN Chuan-long

Related Institution

Department of Communication Engineering,Yunnan University

Educational and Scientific Institute,Educational Department of Yunnan Province

Department of Communication EngineeringYunnan UniversityKunmingYunnan 650091China

Educational and Scientific InstituteEducational Department of Yunnan ProvinceKunmingYunnan 650223China

School of Electronics and Information Engineering, Beijing University of Aeronautics and Astronautics

⁰