Dissertations / Theses on the topic 'Markov queueing model'

Motivé par des applications à large éventail des systèmes d’assemblage à la commande et des systèmes de l’économie collaborative, nous introduisons un modèle d’appariement aléatoire sur les hypergraphes et sur les multigraphes, étendant le modèle par Mairesse et Moyal 2016. Dans cette thèse, le modèle d’appariement aléatoire sur les structures graphiques générales est défini comme suit : étant donné une structure graphique générale de compatibilité S = (V; S) qui est constituée d’un ensemble de nœuds noté par V qui représentent les classes d’éléments et par un ensemble d’arêtes noté par S qui permettent d’apparier entre les différentes classes. Les éléments arrivent au système à un moment aléatoire, par une séquence (supposée être i:i:d:) constituée de différentes classes de V; et demandent d’être appariés selon leur compatibilité dans S: La compatibilité par groupe de deux ou plus (cas hypergraphique) et par groupe de deux avec les possibilités d’apparier entre les éléments de même classe (cas multigraphique). Les éléments, qui ne sont pas appariés, sont stockés dans le système et en attente d’un futur élément compatible et dès qu’ils sont appariés, ils quittent le système ensemble. À l’arrivée, un élément peut trouver plusieurs d’appariements possibles, les éléments qui quittent le système dépendent d’une politique d’appariement Ø à spécifier. Nous étudions la stabilité du modèle d’appariement aléatoire sur l’hypergraphe, pour des différentes topologies hypergraphiques puis, la stabilité du modèle d’appariement aléatoire sur les multigraphes en utilisant son sous-graphe maximal et sur-graphe minimal étendu pour distinguer la zone de stabilité
Motivated by a wide range of assemble-to-order systems and systems of the collaborativeeconomy applications, we introduce a stochastic matching model on hypergraphs and multigraphs, extending the model introduced by Mairesse and Moyal 2016. In this thesis, the stochastic matching model on general graph structures are defined as follows: given a compatibility general graph structure S = (V; S) which of a set of nodes denoted by V that represent the classes of items and by a set of edges denoted by S that allows matching between different classes of items. Items arrive at the system at a random time, by a sequence (assumed to be i:i:d:) that consists of different classes of V; and request to be matched due to their compatibility according to S: The compatibility by groups of two or more (hypergraphical cases) and by groups of two with possibilities of matching between the items of the same classes (multigraphical cases). The unmatched items are stored in the system and wait for a future compatible item and as soon as they are matched they leave it together. Upon arrival, an item may find several possible matches, the items that leave the system depend on a matching policy _ to be specified. We study the stability of the stochastic matching model on hypergraphs, for different hypergraphical topologies. Then, the stability of the stochastic matching model on multigraphs using the maximal subgraph and minimal blow-up to distinguish the zone of stability

This master's thesis deals with queueing theory and its application in designing node models in packet-switched network. There are described general principles of designing queueing theory models and its mathematical background. Further simulator of packet delay in network was created. This application implements two described models - M/M/1 and M/G/1. Application can be used for simulating network nodes and obtaining basic network characteristics like packet delay or packet loss. Next, lab exercise was created, in that exercise students familiarize themselves with basic concepts of queueing theory and examine both analytical and simulation approach to solving queueing systems.

The study of stochastic queueing networks is quite important due to the many applications including transportation, telecommunication, and manufacturing industries. Since there is often no explicit solution to these types of control problems, numerical methods are needed. Following the method of Boué-Dupuis, we use a Dynamic Programming approach of optimization on a controlled Markov Chain that simulates the behavior of a fluid limit of the original process. The search for an optimal control in this case involves a Skorokhod problem to describe the dynamics on the boundary of closed, convex domain. Using relaxed stochastic controls we show that the approximating numerical solution converges to the actual solution as the size of the mesh in the discretized state space goes to zero, and illustrate with an example.
Ph. D.

"A distributed queueing Medium Access Control (MAC) protocol is used in Distributed Queue Dual Bus (DQDB) networks. A modified version of the MAC protocol was proposed by R.R. Pillai and U. Mukherji in an attempt to overcome some of the shortcomings of the DQDB MAC protocol. They analyzed the performance of the system for Bernoulli arrivals and for large propagation delays between the nodes. We extend the performance analysis of the modified MAC protocol for a DQDB type of Network. The parameter of interest to us is the bus access delay. This has two components, viz., the request bus access delay and the data bu6 access delay. We use the model at the request point at node and present methods to evaluate the delay experienced in such a model. The model is an n-priority ./D/l queue with D vacations (non-preemptive priority) where n is the number of nodes sending requests on the request bus for transmission on the data bus. The methods presented help to evaluate the request bus access delay when the arrivals at each node are Markovian Arrival Processes (MAPs). The algorithms for evaluating the mean request bus access delay are based on matrix geometric techniques. Thus, one can use the algorithms developed in the literature to solve for the finite buffers case too. This model, for the request bus access delay, holds irrespective of the propagation delay between the nodes. We also evaluate the inter-departure time of class 1 customers and virtual customers in a 2-priority M/G/l system with G vacations (non-preemptive priority). In the case of Poisson arrivals at all the nodes, we would have a 2-priority M/D/l system with D vacations (non-preemptive priority). We thus evaluate the inter-arrival time of the free slots on the data bus as seen by Node 2. Note that this is independent of the number of active nodes in the network We then develop methods to evaluate the mean data bus access delay experienced by the customers at Node 2 in a three-node network with 2 nodes communicating with the third when the propagation delay between the nodes is large. We consider the case of finite Local Queue buffers at the two nodes. Using this assumption we arrive at process of arrivals to the Combined Queue and the process of free slots on the data bus to be Markov Modulated Bernoulli processes. The model at the combined queue at Node 2 then has a Quasi Birth-Death evolution. Thus, this system is solved by using the Ramaswami-Latouche algorithm. The stationary probabilities are then used to evaluate the mean data bus access delay experienced at Node 2. The finite buffer case of this system can be solved by G.Wi Stewart's algorithm. The method in modelling the system and the results are presented in detail for Poisson arrivals. The extension of this to more complex processes is also explained. We encounter in the analysis an explosion of the state-space of the system. We try to counter this by considering approximations to the process of free slots on the data bus. The approximations considered are on the basis of what are known as Idealized Aggregates. The performance of the approximation is also detailed. It works very well under low and moderate load but underestimates the mean delay under heavy load. Thereafter, we discuss the performance of the system with reference to the mean of the access delay and the standard deviation of the access delay under varying traffic at the two nodes. For this part we use simulation results to discuss the performance. The comparison between the performance measures at both the nodes is also done. Then we develop methods/techniques to understand the performance of the system when we have finite propagation delays between the nodes. We concentrate on the 3-node problem and calculate performance bounds based on linear programs. This is illustrated in detail for Bernoulli arrivals for the case of 1 slot propagation delay between the nodes as well as for the case of 2 slots propagation delay. The performance of the bounds obtained is also detailed. The presence of an idling system at the combined queue of Node 2 makes the bounds somewhat loose. Finally, we discuss the performance of the system with reference to the mean access delay and the standard deviation of the access delay under varying load on the system. Again, we rely on simulation studies. Finally, we study the performance of the system as a multiplexer. For this, we re­strict the traffic to Markov Modulated Processes (or those which would satisfy the Gartner-Ellis Theorem requirements). The traffic is characterized by what are known as Envelope Processes - Lower and Upper. The class of processes which satisfy the conditions of the Gartner-Ellis theorem come under the category where both the Envelope Processes exist and the Minimum Envelope Rate and the Maximum Lower Envelope Rate are the same. We use the system evolution equations at the combined queue at any node to develop re­lations between the various input and output processes. First, this is done for a. system of this kind, in isolation. Then, we consider this system as a part of the modified protocol and present relations, among the various input and output processes, which are specific to the modified protocol. The possible use of all of the above to do Admission Control at the entry point to the Asynchronous Transfer Mode (ATM) network is also presented.

"A distributed queueing Medium Access Control (MAC) protocol is used in Distributed Queue Dual Bus (DQDB) networks. A modified version of the MAC protocol was proposed by R.R. Pillai and U. Mukherji in an attempt to overcome some of the shortcomings of the DQDB MAC protocol. They analyzed the performance of the system for Bernoulli arrivals and for large propagation delays between the nodes. We extend the performance analysis of the modified MAC protocol for a DQDB type of Network. The parameter of interest to us is the bus access delay. This has two components, viz., the request bus access delay and the data bu6 access delay. We use the model at the request point at node and present methods to evaluate the delay experienced in such a model. The model is an n-priority ./D/l queue with D vacations (non-preemptive priority) where n is the number of nodes sending requests on the request bus for transmission on the data bus. The methods presented help to evaluate the request bus access delay when the arrivals at each node are Markovian Arrival Processes (MAPs). The algorithms for evaluating the mean request bus access delay are based on matrix geometric techniques. Thus, one can use the algorithms developed in the literature to solve for the finite buffers case too. This model, for the request bus access delay, holds irrespective of the propagation delay between the nodes. We also evaluate the inter-departure time of class 1 customers and virtual customers in a 2-priority M/G/l system with G vacations (non-preemptive priority). In the case of Poisson arrivals at all the nodes, we would have a 2-priority M/D/l system with D vacations (non-preemptive priority). We thus evaluate the inter-arrival time of the free slots on the data bus as seen by Node 2. Note that this is independent of the number of active nodes in the network We then develop methods to evaluate the mean data bus access delay experienced by the customers at Node 2 in a three-node network with 2 nodes communicating with the third when the propagation delay between the nodes is large. We consider the case of finite Local Queue buffers at the two nodes. Using this assumption we arrive at process of arrivals to the Combined Queue and the process of free slots on the data bus to be Markov Modulated Bernoulli processes. The model at the combined queue at Node 2 then has a Quasi Birth-Death evolution. Thus, this system is solved by using the Ramaswami-Latouche algorithm. The stationary probabilities are then used to evaluate the mean data bus access delay experienced at Node 2. The finite buffer case of this system can be solved by G.Wi Stewart's algorithm. The method in modelling the system and the results are presented in detail for Poisson arrivals. The extension of this to more complex processes is also explained. We encounter in the analysis an explosion of the state-space of the system. We try to counter this by considering approximations to the process of free slots on the data bus. The approximations considered are on the basis of what are known as Idealized Aggregates. The performance of the approximation is also detailed. It works very well under low and moderate load but underestimates the mean delay under heavy load. Thereafter, we discuss the performance of the system with reference to the mean of the access delay and the standard deviation of the access delay under varying traffic at the two nodes. For this part we use simulation results to discuss the performance. The comparison between the performance measures at both the nodes is also done. Then we develop methods/techniques to understand the performance of the system when we have finite propagation delays between the nodes. We concentrate on the 3-node problem and calculate performance bounds based on linear programs. This is illustrated in detail for Bernoulli arrivals for the case of 1 slot propagation delay between the nodes as well as for the case of 2 slots propagation delay. The performance of the bounds obtained is also detailed. The presence of an idling system at the combined queue of Node 2 makes the bounds somewhat loose. Finally, we discuss the performance of the system with reference to the mean access delay and the standard deviation of the access delay under varying load on the system. Again, we rely on simulation studies. Finally, we study the performance of the system as a multiplexer. For this, we re­strict the traffic to Markov Modulated Processes (or those which would satisfy the Gartner-Ellis Theorem requirements). The traffic is characterized by what are known as Envelope Processes - Lower and Upper. The class of processes which satisfy the conditions of the Gartner-Ellis theorem come under the category where both the Envelope Processes exist and the Minimum Envelope Rate and the Maximum Lower Envelope Rate are the same. We use the system evolution equations at the combined queue at any node to develop re­lations between the various input and output processes. First, this is done for a. system of this kind, in isolation. Then, we consider this system as a part of the modified protocol and present relations, among the various input and output processes, which are specific to the modified protocol. The possible use of all of the above to do Admission Control at the entry point to the Asynchronous Transfer Mode (ATM) network is also presented.

The master’s thesis solves models of queueing systems, which use the property of Markov chains. The queueing system is a system, where the objects enter into this system in random moments and require the service. This thesis solves specifically such models of queueing systems, in which the intervals between the objects incomings and service time have exponential distribution. In the theoretical part of the master’s thesis I deal with the topics stochastic process, queueing theory, classification of models and description of the models having Markovian property. In the practical part I describe realization and function of the program, which solves simulation of chosen model M/M/m. At the end I compare results which were calculated in analytic way and by simulation of the model M/M/m.

The performance modelling of large-scale systems using discrete-state approaches is fundamentally hampered by the well-known problem of state-space explosion, which causes exponential growth of the reachable state space as a function of the number of the components which constitute the model. Because they are mapped onto continuous-time Markov chains (CTMCs), models described in the stochastic process algebra PEPA are no exception. This thesis presents a deterministic continuous-state semantics of PEPA which employs ordinary differential equations (ODEs) as the underlying mathematics for the performance evaluation. This is suitable for models consisting of large numbers of replicated components, as the ODE problem size is insensitive to the actual population levels of the system under study. Furthermore, the ODE is given an interpretation as the fluid limit of a properly defined CTMC model when the initial population levels go to infinity. This framework allows the use of existing results which give error bounds to assess the quality of the differential approximation. The computation of performance indices such as throughput, utilisation, and average response time are interpreted deterministically as functions of the ODE solution and are related to corresponding reward structures in the Markovian setting. The differential interpretation of PEPA provides a framework that is conceptually analogous to established approximation methods in queueing networks based on meanvalue analysis, as both approaches aim at reducing the computational cost of the analysis by providing estimates for the expected values of the performance metrics of interest. The relationship between these two techniques is examined in more detail in a comparison between PEPA and the Layered Queueing Network (LQN) model. General patterns of translation of LQN elements into corresponding PEPA components are applied to a substantial case study of a distributed computer system. This model is analysed using stochastic simulation to gauge the soundness of the translation. Furthermore, it is subjected to a series of numerical tests to compare execution runtimes and accuracy of the PEPA differential analysis against the LQN mean-value approximation method. Finally, this thesis discusses the major elements concerning the development of a software toolkit, the PEPA Eclipse Plug-in, which offers a comprehensive modelling environment for PEPA, including modules for static analysis, explicit state-space exploration, numerical solution of the steady-state equilibrium of the Markov chain, stochastic simulation, the differential analysis approach herein presented, and a graphical framework for model editing and visualisation of performance evaluation results.

The ambulance offload delay problem is a well-known result of overcrowding and congestion in emergency departments. Offload delay refers to the situation where area hospitals are unable to accept patients from regional ambulances in a timely manner due to lack of staff and bed capacity. The problem of offload delays is not a simple issue to resolve and has caused severe problems to the emergency medical services (EMS) providers, emergency department (ED) staff, and most importantly patients that are transferred to hospitals by ambulance. Except for several reports on the problem, not much research has been done on the subject. Almost all research to date has focused on either EMS or ED planning and operation and as far as we are aware there are no models which have considered the coordination of these units. We propose an analytical model which will allow us to analyze and explore the ambulance offload delay problem. We use queuing theory to construct a system representing the interaction of EMS and ED, and model the behavior of the system as a continuous time Markov chain. The matrix geometric method will be used to numerically compute various system performance measures under different conditions. We analyze the effect of adding more emergency beds in the ED, adding more ambulances, and reducing the ED patient length of stay, on various system performance measures such as the average number of ambulances in offload delay, average time in offload delay, and ambulance and bed utilization. We will show that adding more beds to the ED or reducing ED patient length of stay will have a positive impact on system performance and in particular will decrease the average number of ambulances experiencing offload delay and the average time in offload delay. Also, it will be shown that increasing the number of ambulances will have a negative impact on offload delays and increases the average number of ambulances in offload delay. However, other system performance measures are improved by adding more ambulances to the system. Finally, we will show the tradeoffs between adding more emergency beds, adding more ambulances, and reducing ED patient length of stay. We conclude that the hospital is the bottleneck in the system and in order to reduce ambulance offload delays, either hospital capacity has to be increased or ED patient length of stay is to be reduced.

This paper presents a new analytical framework for the congestion control of Internet traffic using a queue threshold scheme. This framework includes two discrete-time analytical models for the performance evaluation of a threshold based congestion control mechanism and compares performance measurements through typical numerical results. To satisfy the low delay along with high throughput, model-I incorporates one threshold to make the arrival process step reduce from arrival rate ¿1 directly to ¿2 once the number of packets in the system has reached the threshold value L1. The source operates normally, otherwise. Model-II incorporates two thresholds to make the arrival rate linearly reduce from ¿1 to ¿2 with system contents when the number of packets in the system is between two thresholds L1 and L2. The source operates normally with arrival rate ¿1 before threshold L1, and with arrival rate ¿2 after the threshold L2. In both performance models, the mean packet delay W, probability of packet loss PL and throughput S have been found as functions of the thresholds and maximum drop probability. The performance comparison results for the two models have also been made through typical numerical results. The results clearly demonstrate how different load settings can provide different tradeoffs between throughput, loss probability and delay to suit different service requirements.

The ubiquitous deployment of battery-operated wireless devices has resulted in the need for efficient low latency power allocation schemes. A common phenomenon in wireless transmission systems is congestion, where the transmitter backlog grows due to restrictions in channel usage on a resource-constrained shared access medium. In this research work, we aim to achieve low communication delay of wireless downlink file transmissions operating on power-constrained quasi-static fading channels, using state-dependent transmission rate control and admission of file transmission requests. We employ a Markov queueing model to formulate the low delay objective for exponentially distributed file sizes as a constrained average queue length minimization problem. The corresponding primal problem is known to be expressible as a linear program in occupation measures, and therefore strong duality holds. In our work, we show the primal feasibility of the dual optimal policy w.r.t. the average throughput and power constraints, which is proved under the assumption the optimal average power and throughput are continuous with respect to the Lagrange dual variables at the optimal point. The dual problem is simplified to an iterative optimization using Dinkelbach’s fractional programming method and solved using gradient analysis techniques to analytically derive the ON-OFF threshold characteristics of the admission policy and the recursive structure of the transmission rate policy. We first apply our solution method to a wireless transmission system using the M/M/1 queueing model. Our objective is to minimize the average queue length subject to an upper bound on average transmission power and a lower bound on average admission rate. This constrained average queue length minimization problem is solved using Lagrange dual method. We substitute the individual stationary probabilities in the Lagrange dual function using the product form distribution expressed in terms of the stationary probability of the maximum queue length. The resulting objective function then corresponds to a fractional minimization problem which is solved using Dinkelbach’s method. We analytically derive the ON-OFF threshold characteristic of the optimal admission rates and the recursive structure of the optimal transmission rates. We illustrate the results of our algorithm for different values of throughput and power requirements. We also demonstrate the efficiency of optimal state-dependent rate control for exponentially distributed file sizes compared to benchmark state-independent transmission schemes. We next apply the solution techniques to an energy harvesting wireless transmission system, extending the M/M/1 queueing model. The model uses energy stored in a battery as well as energy packets available from an auxiliary power supply for file transmission. We use the product-form stationary distribution to establish a correspondence between the energy harvesting system and the M/M/1 queueing system. Using the solution approach using Dinkelbach’s method, we derive similar characteristics for the optimal admission and transmission rates. We finally extend the analysis to model a cache-aided wireless transmission system operating under the assumption the cache-hit probability is uniform for all files and queue length states. The system is modeled as a quasi-one-dimensional Markov chain. The stationary probabilities in the Lagrange dual function are expressed in terms of the stationary probability of the empty buffer state using the product of matrices. The solution methods and insights developed from the previous models simplify the analysis of this problem, and we analytically characterize the structure of the optimal admission and transmission rates. The applicability of our solution methodology to these three models of transmission systems illustrates its simplicity and versatility.

Huang, Liang.
Thesis (Ph.D.)--Chinese University of Hong Kong, 2013.
Includes bibliographical references (leaves 109-116).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract also in Chinese.

This thesis presents a cross-layer design and optimization for emerging wideband wireless networks supporting multimedia applications, considering the interactions of the wireless channel characteristics, the physical and link layer protocols, and the user-perceived Quality-of-Service (QoS). As wireless channels are error-prone and broadcast in nature, both the error control mechanisms and the Media Access Control (MAC) protocols are critical for resource utilization and QoS provisioning. How to analyze, design and optimize the high-rate wireless networks by considering the characteristics of the propagation channels and wideband communication technologies is an open, challenging issue. In this thesis, we consider two important wideband wireless systems, the Ultra-Wideband (UWB) and the Orthogonal Frequency-Division Multiplexing (OFDM) systems. First, we propose the packet-level channel models based on Finite State Markov Chains (FSMCs) for the two systems, which present the statistical properties of the propagation channels and the transmission systems. Second, by incorporating the proposed packet-level channel models, we develop analytical frameworks for quantifying the performance of the high-rate wireless networks, combining the channel fading, physical- and link-layer error-control mechanisms and MAC protocols. Third, to mitigate the impact of channel fading and impairments, a cross-layer joint error-control mechanism is proposed. In addition, we also investigate the impact of channel fading on the video streaming applications, and propose a simple admission control algorithm to ensure QoS. As considering the physical-layer characteristics is critical for ensuring QoS and efficiency of resource utilization, the packet-level channel models, cross-layer analytical frameworks, networking protocols and simulation methodologies proposed in this dissertation are essential for future proliferation of high-rate wireless networks.