A two-stage approach in solving the state probabilities of the multi-queue M/G/1 model

Abstract

The M/G/1 model is the fundamental basis of the queueing system in many network systems. Usually, the study of the M/G/1 is limited by the assumption of single queue and infinite capacity. In practice, however, these postulations may not be valid, particularly when dealing with many real-world problems. In this paper, a two-stage state-space approach is devoted to solving the state probabilities for the multi-queue finite-capacity M/G/1 model, i.e. q-M/G/1/K_i with K_i buffers in the ith queue. The state probabilities at departure instants are determined by solving a set of state transition equations. Afterward, an embedded Markov chain analysis is applied to derive the state probabilities with another set of state balance equations at arbitrary time instants. The closed forms of the state probabilities are also presented with theorems for reference. Applications of Little's theorem further present the corresponding results for queue lengths and average waiting times. Simulation experiments have demonstrated the correctness of the proposed approaches.

Keywords:

• queueing
• state-space approach
• state probability
• STEs/SBEs

Acknowledgments

This research was supported by the National Science Council under contract numbers NSC97-2221-E-212-032 and NSC102-2221-E-212-013.

Notes

1. In our convention, the priority of messages in Q_i is higher than Q_j, when i < j.

2. Since the M/G/1 is analysed based on the departure instants, the superscript is added in the departure process with the notation ‘EMC’ to emphasise that our analysis is based on the embedded Markov chain.

3. We have assumed that the priority of Q₁ is favoured over Q₂.

Additional information

Notes on contributors

Mu-Song Chen

Mu-Song Chen received his PhD degree in electrical engineering from University of Texas, at Arlington. Currently, he is an associate professor of the Department of Electrical Engineering of Da-Yeh University, Changhua, Taiwan. His areas of research include neuro-fuzzy network, pattern recognition, queuing models, and controller area network.

Hao-Wei Yen

Hao-Wei Yen received his PhD degree at the Department of Electrical Engineering, Da-Yeh University, Changhua, Taiwan. His current researches focus on designing the message scheduling on controller area network by using machine-learning algorithms and adaptive queueing strategies.