A probabilistic approach to estimate the mean waiting times in the earliest deadline first polling

详细信息    查看全文

• 作者：Mu-Song Chen¹ ; ^{chenms@mail.dyu.edu.tw} ; Hao-Wei Yen² ; ^{howwayen@yahoo.com.tw}
• 关键词：Queueing theory ; EDF/FCFS/PRI polling ; Probabilistic approach
• 刊名：Computers and Industrial Engineering
• 出版年：2013
• 出版时间：March, 2013
• 年：2013
• 卷：64
• 期：3
• 页码：817-826
• 全文大小：636 K

文摘

In queueing system, the mean waiting times of messages are important measures to characterize the quality of service (QoS) under various requirements. In a time-critical system, message transactions which cannot meet deadline constraints might lead to catastrophic consequences. Currently, the waiting time estimations using the first-come-first-served (FCFS) and priority (PRI) strategies are already well developed. However, in the case of multi-queue dynamic environments, these quantities are more difficult to analyze due to multiple classes of messages are considered. In this paper, we aim to consider a polling system consisting of a number of parallel infinite-capacity single-server queues. We propose a probabilistic approach to derive the waiting times for different classes of messages by using non-preemptive earliest deadline first (EDF) polling policy. The resulting formula can also lead to the FCFS polling and PRI polling by altering the relative deadlines. Moreover, the bounds of waiting times are discussed. The accuracy of the proposed algorithm is established by comparisons with simulation results. The runtime results are in very good convergence with the theoretical predictions made by our formulas, in terms of prediction accuracies of waiting times and untimely service ratios of messages under various scenarios and timing constraints.