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

摘要

In queueing system, the mean waiting times of messages are important measures to characterize the quality of service (QpS) 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.