Performance analysis of a finite-buffer discrete-time queue with bulk arrival,bulk service and vacations

This paper considers a finite-buffer discrete-time Geo^X/G^Y/1/K+B queue with multiple vacations that has a wide range of applications including high-speed digital telecommunication systems and various related areas. The main purpose of this paper is to present a performance analysis of this system. For this purpose, we first derive a set of linear equations to compute the steady-state departure-epoch probabilities based on the embedded Markov chain technique. Next, we present numerically stable relationships for the steady-state probabilities of the queue lengths at three different epochs: departure, random, and arrival. Finally, based on these relationships, we present various useful performance measures of interest such as the moments of the number of packets in the queue at three different epochs, the mean delay in the queue of a packet, the loss probability and the probability that server is busy with computational experiences.     

Decentralised output feedback control of Markovian jump interconnected systems with unknown interconnections

The problem of decentralised output feedback control is addressed for Markovian jump interconnected systems with unknown interconnections and general transition rates (TRs) allowed to be unknown or known with uncertainties. A class of decentralised dynamic output feedback controllers are constructed, and a cyclic-small-gain condition is exploited to dispose the unknown interconnections so that the resultant closed-loop system is stochastically stable and satisfies an H_∞ performance. With slack matrices to cope with the nonlinearities incurred by unknown and uncertain TRs in control synthesis, a novel controller design condition is developed in linear matrix inequality formalism. Compared with the existing works, the proposed approach leads to less conservatism. Finally, two examples are used to illustrate the effectiveness of the new results.     

Markovian analysis of production lines with Coxian-2 service times

This paper is concerned with the analysis of reliable production lines. The service times at each station of the line are assumed to follow the Coxian-2 distribution. Raw material arrives at the first station of the line which is assumed that is never empty. Buffers of non-identical capacities are allowed between successive stations. The structure of the transition matrices of these specific type of production lines is examined and a recursive algorithm is developed for generating them, for any number of stations K . This method allows one to obtain the exact solution of a sparse linear system by the use of the Gauss–Seidel method. From the solution of these systems the throughput rate of the production lines is calculated. However, this algorithm is not computationally efficient as it is restricted by the size of the problem. The main contribution of this paper is the study of the transition matrices of production lines with Coxian service times.     

Analysis of discrete-time batch service renewal input queue with multiple working vacations

This paper investigates a discrete-time single server batch service queue with multiple working vacations wherein arrivals occur according to a discrete-time renewal process. The server works with a different service rate rather than completely stopping during the vacation period. The service is performed in batches and the server takes a vacation when the system does not have any waiting customers at a service completion epoch or a vacation completion epoch. We present a recursive method, using the supplementary variable technique to obtain the steady-state queue-length distributions at pre-arrival, arbitrary and outside observer’s observation epochs. The displacement operator method is used to solve simultaneous non-homogeneous difference equations. Some performance measures and waiting-time distribution in the system have also been discussed. Finally, numerical results showing the effect of model parameters on key performance measures are presented.     

Impact of class clustering in a multiclass FCFS queue with order-dependent service times

In multi-class queueing systems, customers of different classes can enter the system. When studying such systems, it is traditionally assumed that the different classes of customers occur randomly and independently in the arrival stream of customers in the system. This is often in contrast to the actual situation. Therefore, we study a multi-class system with so-called class clustering in the customer arrival stream, i.e., (Markovian) correlation occurs in the classes of consecutive customers. The system under investigation consists of one server that is able to serve two classes of customers. In addition, the service-time distribution of a customer depends on the equality or non-equality of its class with the class of the previous customer. This latter feature occurs frequently in practice. For instance, execution of the same task again can lead to both faster or slower processing times. The first case can occur when the execution of a different task entails resetting a machine, or loading new data, et cetera. The opposite situation appears, for instance, when execution of the same task requires postprocessing (such as cooling down or reinitialization of a machine). We deduce the probability generating function (pgf) of the system content, from which we can extract various performance measures, among which the mean values of the system content and the customer delay. We demonstrate that class clustering has a tremendous impact on the system performance, which highlights the necessity to include it in the performance assessment of any system in which it occurs.     

Conditioned asymptotics for tail probabilities in large multiplexers

Consider a buffer whose input is a superposition of L independent identical sources, and which is served at rate sL. Recent work has shown that, under very general circumstances, the stationary tail probabilities for the queue of unfinished work Q in the buffer have the asymptotics P[Q > Lb] ≈ e^−LI(b) for large L. Here the shape function, I, is obtained from a variational expression involving the transient log cumulant generating function of the arrival process.

In this paper, we extend this analysis to cover time-dependent asymptotics for Markov arrival processes subject to conditioning at some instant. In applications we envisage that such conditioning would arise due to knowledge of the queue at a coarse-grained level, for example of the number of current active sources. We show how such partial knowledge can be used to predict future tail probabilities by use of a time dependent, conditioned shape function. We develop some heuristics to describe the time-dependent shape function in terms of a reduced set of quantities associated with the underlying arrivals process and show how to calculate them for renewal arrivals and a class of ON-OFF arrivals. This bypasses the full variational calculation of the shape function for such models.     

On a single server queue with two-stage heterogeneous service and deterministic server vacations

We analyse a single server queue with Poisson arrivals, two stages of heterogeneous service with different general (arbitrary) service time distributions and binomial schedule server vacations with deterministic (constant) vacation periods. After first-stage service the server must provide the second stage service. However, after the second stage service, he may take a vacation or may decide to stay on in the system. For convenience, we designate our model as M/G ₁, G ₂/D/1 queue. We obtain steady state probability generating function of the queue length for various states of the server. Results for some particular cases of interest such as M/E_{k 1} , E_{k 2} /D/1, M/M ₁, M ₂/D/1, M/E _k /D/1 and M/G ₁, G ₂/1 have been obtained from the main results and some known results including M/E_k /1 and M/G/1 have been derived as particular cases of our particular cases.     

A non-equilibrium analysis and control framework for active queue management

We present a non-equilibrium analysis and control approach for the Active Queue Management (AQM) problem in communication networks. Using simplified fluid models, we carry out a bifurcation study of the complex dynamic queue behavior to show that non-equilibrium methods are essential for analysis and optimization in the AQM problem. We investigate an ergodic theoretic framework for stochastic modeling of the non-equilibrium behavior in deterministic models and use it to identify parameters of a fluid model from packet level simulations. For computational tractability, we use set-oriented numerical methods to construct finite-dimensional Markov models, including control Markov chains and hidden Markov models. Subsequently, we develop and analyze an example AQM algorithm using a Markov Decision Process (MDP) based control framework. The control scheme developed is optimal with respect to a reward function, defined over the queue size and aggregate flow rate. We implement and simulate our illustrative AQM algorithm in the ns-2 network simulator. The results obtained confirm the theoretical analysis and exhibit promising performance when compared with well-known alternative schemes under persistent non-equilibrium queue behavior.     

Stochastic controllability of linear systems with Markovian jumps

The notion of stochastic controllability for linear systems subject to Markovian jumps in parameter values is studied. An algebraic necessary and sufficient condition is obtained in terms of an easily computable rank test.     

Passivity analysis of stochastic delayed neural networks with Markovian switching

In this paper, the problem of passivity analysis is investigated for a class of stochastic delayed neural networks with Markovian switching. By applying Lyapunov functional and free-weighting matrix, delay-dependent/independent passivity criteria are presented in terms of linear matrix inequalities. The results herein include existing ones for neural networks without Markovian switching as special cases. An example is given to demonstrate the effectiveness of the proposed criteria.     

Analysis of a finite-buffer bulk-service queue under Markovian arrival process with batch-size-dependent service

We consider a finite capacity single server queue in which the customers arrive according to a Markovian arrival process. The customers are served in batches following a ‘general bulk service rule’. The service times, which depend on the size of the batch, are generally distributed. We obtain, in steady-state, the joint distribution of the random variables of interest at various epochs. Efficient computational procedures in the case of phase type services are presented. An illustrative numerical example to bring out the qualitative nature of the model is presented.     

Stability analysis of Markovian jump systems with delayed impulses

This paper addresses stability for Markovian jump systems with delayed impulses. The delayed impulse has a largely negative effect on the system stability and is not easy to be studied. The main reason is that so many factors such as Markovian switching, impulse, and time-varying delay are simultaneously contained and make its analysis complicated and difficult. In order to analyze these factors clearly, some novel enlarging techniques are presented and used to establish linear matrix inequality (LMI) conditions ultimately. Based on the given methods, more situations such as impulsive instant sequence satisfying a renewal process and Poisson process, respectively, are further studied and better than ones without considering such properties. Two numerical examples are used to show the effectiveness and superiority of the methods.     

Learning and planning in environments with delayed feedback

This work considers the problems of learning and planning in Markovian environments with constant observation and reward delays. We provide a hardness result for the general planning problem and positive results for several special cases with deterministic or otherwise constrained dynamics. We present an algorithm, Model Based Simulation, for planning in such environments and use model-based reinforcement learning to extend this approach to the learning setting in both finite and continuous environments. Empirical comparisons show this algorithm holds significant advantages over others for decision making in delayed-observation environments.     

Stability analysis of multiserver discrete-time queueing systems with renewal-type server interruptions

For many queueing systems, the server is not continuously available. Service interruptions may result from repair times after server failures, planned maintenance periods or periods during which customers from other queues are being served. These service interruptions cause an overall performance degradation which is most striking when interruptions can start while a customer is being served and his service has to start all over after the interruption. This is the so-called preemptive repeat service discipline. This paper investigates stability conditions for discrete-time queueing systems with preemptive server interruptions. Under renewal assumptions for arrival, service and interruption processes, sufficient conditions for the positive recurrence of the single-server and multiserver queueing processes are established for the preemptive repeat different and the preemptive resume service disciplines.     

An MX/G/1 queue with randomized working vacations and at most J vacations

This paper treats a bulk arrival queue with randomized working vacation policy. Whenever the system becomes empty, the server takes a vacation. During the vacation period, customers are to be served at a lower rate. Once the vacation ends, the server will return to the normal working state and begin to serve the customers in the system if any. Otherwise, the server either remains idle with probability p or leaves for another vacation with probability 1?p. This pattern continues until the number of vacations taken reaches J. If the system is empty at the end of the Jth vacation, the server will wait idly for a new arrival. By using supplementary variable technique, we derive the system size distribution at arbitrary epoch, at departure epoch and at busy period initial epoch, as well as some important system characteristics. Numerical examples are provided to illustrate the influence of system parameters on several performance measures.     

Asynchronous control of discrete-time stochastic bilinear systems with Markovian switchings

This paper is concerned with the problem of asynchronous control for a class of discrete-time Markov systems with multiplicative stochastic white noises. Based on a stability analysis scheme developed from mode-dependent Lyapunov function method, we first derive testable conditions in linear matrix inequality (LMI) setting to ensure the robust stability of the closed-loop system. We then recast the proposed stability conditions into equivalent forms that are later utilised to design a multi-mode asynchronous state-feedback controller (ASFC) that makes the closed-loop system stable. An extension to the case of deficient mode information (i.e. transition rates of the system and the controller are not fully accessible) is also presented. Finally, a model of networked control with DC devices is given to demonstrate the efficacy of the proposed design scheme.     

Adaptive control of service in queueing systems

We consider the service-rate selection problem in an M/G/1 queueing system with unknown arrival rate and average cost criterion. An optimal adaptive policy is determined using recently developed results on parameter estimation and adaptive control of semi-Markov processes.     

Predicting departure times in multi-stage queueing systems

We develop an approximation model for the state-dependent sojourn time distribution of customers or orders in a multi-stage, multi-server queueing system, when interarrival and service times can take on general distributions. The model can be used to make probabilistic statements about the departure time of a customer or order, given the number and location of customers currently in process or waiting, and these probabilities can be recomputed while waiting at any point during the sojourn time. The model uses phase-type distributions and a new method to estimate the remaining processing times of customers in service when the sojourn time distribution is computed.     

Robust stabilisation of uncertain delayed Markovian jump systems and its applications

This paper is concerned with the robust stabilsation of uncertain delayed Markovian jump systems. Given a Markovian jump system with time delay and Brownian motion simultaneously, we allow the uncertainty added in the form of additive perturbations and existing in the drift and diffusion sections at the same time. A sufficient condition on the mean square stability of system in the face of such disturbances is obtained, which is similar to small-gain theorem. A kind of partially delay-dependent controller stabilising the resulting closed-loop system is firstly designed to relate to the probability distribution of delay, whose key idea is applied to construct a delayed controller with disordering phenomenon. It is seen that the existence conditions established here could be solved easily. Based on the proposed results, some applications on robust synchronisation of uncertain delayed multi-agent systems with Markovian switching are considered. It is shown that the robust synchronisation of such an uncertain multi-agent network could be achieved by a protocol that each controller being partially delay-dependent or disordering could robustly stabilise a given single Markovian jump system. As for these cases, the proposed protocols could be obtained by solving certain algebraic Riccati equations and inequalities, which also involve weighting factors and depend on the eigenvalues of the Laplacian graph.