Research and Analysis of Queue Selection Criterions in the Multi-Queue System
| Autor: | Yen Hao-Wei, 顏豪緯 |
|---|---|
| Rok vydání: | 2011 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 99 Queues or waiting lines are an essential part of our everyday life. We all experience to wait in queues to buy movie tickets, make a bank deposit, pay for groceries, wait for car wash, etc. These phenomena can lead to waiting lines and therefore the queueing system. In this sense, queueing theory is the research to study the queueing behaviors in queues. Regarding to different demands of queueing problems, several types of queueing models can be discussed. First, different classes of messages imply different priorities. It is better to allocate different queues to accommodate different levels of messages. Second, the common queueing models assume that the queue capacity is infinite. To real world problems, this assumption becomes unrealistic. In fact, the study of finite length models is more practical and suitable to the actual problems. Furthermore, the limiting behaviors of the finite length models should approach the existing queueing modes with unlimited capacity. Third, if the considered queued messages are timing-constraints, the message scheduling capability has to be robust to provide timely service. To this end, this thesis is intended to analyze multi-queue models with finite or infinite capacities. Furthermore, we propose the message scheduling controller to promote the scheduling capability in time variant environments. The first part of the thesis focuses on applying Earliest Deadline First (EDF) as the Queue Selection Rule (QSR) in a multi-queue M/G/1 model with infinite capacity, e.g. q-M/G/1/inf/FCFS/EDF. The probability density function of waiting times is first derived to estimate the waiting times in queues and other measure quantities. Additionally, by altering the relative deadlines between queues, the discussed q-M/G/1/inf/FCFS/EDF can be equivalent to the model with either FCFS or PRI polling. The second part of this study deals with q-M/G/1 model with finite queue lengths, i.e. q-M/G/1/Ki/FCFS/QSR. Several QSRs are discussed for queue selections. Both Embedded Markov Chain (EMC) and Markov Chain (MC) combined with multi-dimensional state transitions are used to solve the state probabilities. In the EMC approach, four steps are involved, including message arrival probability, queue transition probability, state probability at departure instant (or after service completion), and state probability at arbitrary time. However, only two steps, i.e. queue transition probability and state probability at arbitrary time, are required in the MC approach. From simulation experiments, our methods can estimate the state probabilities and many performance measures accurately when compared with simulation quantities. In the third part of this thesis, the message scheduling controller with machine learning capability is present to satisfy message timing constraints. The MSC is a kind of closed-loop control which provides Type I and Type II learning to regulate internal parameters of the controller. The MSC is capable of dealing with time variant environment and prevents or reduce untimely message service ratios. The proposed MSC can be realized by RBFN, NN or RVM. Simulation results demonstrate that the MSC is very robust in terms of untimely service ratios. Finally, we also derive close formula of the upper bounds of waiting times in the conditions of infinite queue loads. Many aforementioned QSRs, including MSC, EDF, FCFS, WFQ, RR, PRI, are discussed. From simulation results, the theoretical values are well matched with the runtime quantities. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|