Characterizing the departure process of a single server queue from the embedded Markov renewal process at departures

In the literature, performance analyses of numerous single server queues are done by analyzing the embedded Markov renewal processes at departures. In this paper, we characterize the departure processes for a large class of such queueing systems. Results obtained include the Laplace–Stieltjes transform (LST) of the stationary distribution function of interdeparture times and recursive formula for {_cn ≡ the covariance between interdeparture times of lag n}. Departure processes of queues are difficult to characterize and for queues other than M/G/1 this is the first time that {_cn} can be computed through an explicit recursive formula. With this formula, we can calculate {_cn} very quickly, which provides deeper insight into the correlation structure of the departure process compared to the previous research. Numerical examples show that increasing server irregularity (i.e., the randomness of the service time distribution) destroys the short-range dependence of interdeparture times, while increasing system load strengthens both the short-range and the long-range dependence of interdeparture times. These findings show that the correlation structure of the departure process is greatly affected by server regularity and system load. Our results can also be applied to the performance analysis of a series of queues. We give an application to the performance analysis of a series of queues, and the results appear to be accurate. This revised version was published online in June 2006 with corrections to the Cover Date.     

Departure Processes of BMAP/G/1 Queues

A unified approach is applied to analyze the departure processes of finite/infinite BMAP/G/1 queueing systems for both vacationless and vacation arrangements via characterizing the moments, the z-transform of the scaled autocovariance function of interdeparture times C _P (z), and lag n (n1) covariance of interdeparture times. From a structural point of view, knowing departure process helps one to understand the impact of service mechanisms on arrivals. Through numerical experiments, we investigate and discuss how the departure statistics are affected by service and vacation distributions as well as the system capacity. From a practical perspective, output process analysis serves to bridge the nodal performance and connectionwise performance. Our results can be then used to facilitate connection- or networkwise performance analysis in the current high-speed networks.     

A Discrete-Time Geo /G/1 Retrial Queue with General Retrial Times

We consider a discrete-time Geo/G/1 retrial queue in which the retrial time has a general distribution and the server, after each service completion, begins a process of search in order to find the following customer to be served. We study the Markov chain underlying the considered queueing system and its ergodicity condition. We find the generating function of the number of customers in the orbit and in the system. We derive the stochastic decomposition law and as an application we give bounds for the proximity between the steady-state distributions for our queueing system and its corresponding standard system. Also, we develop recursive formulae for calculating the steady-state distribution of the orbit and system sizes. Besides, we prove that the M/G/1 retrial queue with general retrial times can be approximated by our corresponding discrete-time system. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Exact and approximate numerical solutions of steady-state distributions arising in the queueGI/G/1

In this paper we first obtain, in a unified way, closed-form analytic expressions in terms of roots of the so-called characteristic equation (c.e.), and then discuss the exact numerical solutions of steady-state distributions of (i) actual queueing time, (ii) virtual queueing time, (iii) actual idle time, and (iv) interdeparture time for the queueGI/R/1, whereR denotes the class of distributions whose Laplace-Stieltjes transforms (LSTs) are rational functions (ratios of a polynomial of degree at mostn to a polynomial of degreen). For the purpose of numerical discussions of idle- and interdeparture-time distributions, the interarrival-time distribution is also taken to belong to the classR. It is also shown that numerical computations of the idle-time distribution ofR/G/1 queues can be done even ifG is not taken asR. Throughout the discussions it is assumed that the queue discipline is first-come-first-served (FCFS). For the tail of the actual queueing-time distribution ofGI/R/1, approximations in terms of one or more roots of the c.e. are also discussed. If more than one root is used, they are taken in ascending order of magnitude. Numerical aspects have been tested for a variety of complex interarrival- and service-time distributions. The analysis is not restricted to generalized distributions with phases such as Coxian-n (C _n ), but also covers nonphase type distributions such as uniform (U) and deterministic (D). Some numerical results are also presented in the form of tables and figures. It is expected that the results obtained from the present study should prove to be useful not only to practitioners, but also to queueing theorists who would like to test the accuracies of inequalities, bounds or approximations.     

A queue with a pair of instantaneous independent bernoulli feedback processes

In this paper we are concerned with several random processes that occur in M/G₂/l queue with instantaneous feedback in which the feedback decision process is a pair of independent Bernoulli processes. The stationary distribution of the output process has been obtained. Results for particular queues with feedback and without feedback are obtained. Some operating characteristics are derived for this queue. Some interesting results are obtained for departure processes. Optimum service rate is obtained. Numerical examples are provided to test the feasibility of the queueing model     

Implementation of Markovian Queueing Network Model with Multiple Closed Chains

Mathematical strategy portrays the performance evaluation of computer and communication system and it deals with the stochastic properties of the multiclass Markovian queueing system with class-dependent and server-dependent service times. An algorithm is designed where the job transitions are characterized by more than one closed Markov chain. Generating functions are implemented to derive closed form of solutions and product form solution with the parameters such as stability, normalizations constant and marginal distributions. For such a system with N servers and L chains, the solutions are considerably more complicated than those for the systems with one sub-chain only. In Multi-class queueing network, a job moves from a queue to another queue with some probability after getting a service. A multiple class of customer could be open or closed where each class has its own set of queueing parameters. These parameters are obtained by analyzing each station in isolation under the assumption that the arrival process of each class is a state-dependent Markovian process along with different service time distributions. An algorithmic approach is implemented from the generating function representation for the general class of Networks. Based on the algorithmic approach it is proved that how open and closed sub-chain interact with each other in such system. Specifically, computation techniques are provided for the calculation of the Markovian model for multiple chains and it is shown that these algorithms converge exponentially fast.     

The M/G/1 Queue with Finite Workload Capacity

We consider the M/G/1 queueing system in which customers whose admission to the system would increase the workload beyond a prespecified finite capacity limit are not accepted. Various results on the distribution of the workload are derived; in particular, we give explicit formulas for its stationary distribution for M/M/1 and in the general case, under the preemptive LIFO discipline, for the joint stationary distribution of the number of customers in the system and their residual service times. Furthermore, the Laplace transform of the length of a busy period is determined. Finally, for M/D/1 the busy period distribution is derived in closed form.     

Analysis of stationary discrete-time GI/D-MSP/1 queue with finite and infinite buffers

This paper considers a single-server queueing model with finite and infinite buffers in which customers arrive according to a discrete-time renewal process. The customers are served one at a time under discrete-time Markovian service process (D-MSP). This service process is similar to the discrete-time Markovian arrival process (D-MAP), where arrivals are replaced with service completions. Using the imbedded Markov chain technique and the matrix-geometric method, we obtain the system-length distribution at a prearrival epoch. We also provide the steady-state system-length distribution at an arbitrary epoch by using the supplementary variable technique and the classical argument based on renewal-theory. The analysis of actual-waiting-time (in the queue) distribution (measured in slots) has also been investigated. Further, we derive the coefficient of correlation of the lagged interdeparture intervals. Moreover, computational experiences with a variety of numerical results in the form of tables and graphs are discussed.     

The M/Ek/r machine interference model steady state equations and numerical solutions

This paper studies the machine interference problem in which the running times follow the negative exponential distribution, the repair times the Erlang distribution and the number of operatives is more than one. The steady state equations are derived and it is shown that unlike the case of the M/E_k/r ordinary queueing model, the solution cannot be taken in closed form. An efficient numerical procedure is developed instead, based on a decomposition principle. Tabulated results of the average number of machines running and the operative utilization for a range of the problem parameters are given, for the cases M/E₃/2 and M/E₃/3. A tentative conclusion for a closeness in performance between the models M/M/r and M/E_k/r is drawn.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

Transient analysis of an M/G/1 retrial queue subject to disasters and server failures

An M/G/1 retrial queueing system with disasters and unreliable server is investigated in this paper. Primary customers arrive in the system according to a Poisson process, and they receive service immediately if the server is available upon their arrivals. Otherwise, they will enter a retrial orbit and try their luck after a random time interval. We assume the catastrophes occur following a Poisson stream, and if a catastrophe occurs, all customers in the system are deleted immediately and it also causes the server’s breakdown. Besides, the server has an exponential lifetime in addition to the catastrophe process. Whenever the server breaks down, it is sent for repair immediately. It is assumed that the service time and two kinds of repair time of the server are all arbitrarily distributed. By applying the supplementary variables method, we obtain the Laplace transforms of the transient solutions and also the steady-state solutions for both queueing measures and reliability quantities of interest. Finally, numerical inversion of Laplace transforms is carried out for the blocking probability of the system, and the effects of several system parameters on the blocking probability are illustrated by numerical inversion results.     

Identifiability of the MAP 2/G/1 queueing system

In this paper, we study how the lack of a unique representation for the two-state Markovian arrival process (MAP ₂) can influence statistical estimation for the MAP ₂/G/1 queueing system. In particular, given two equivalent representations of the same MAP ₂, we find that the steady-state distributions of the queuing system can be identified.     

M/G/1 retrial queueing systems with two types of calls and finite capacity

We consider anM/G/1 priority retrial queueing system with two types of calls which models a telephone switching system and a cellular mobile communication system. In the case that arriving calls are blocked due to the server being busy, type I calls are queued in a priority queue of finite capacityK whereas type II calls enter the retrial group in order to try service again after a random amount of time. In this paper we find the joint generating function of the numbers of calls in the priority queue and the retrial group in closed form. When ₁=0, it is shown that our results are consistent with the known results for a classical retrial queueing system.     

Probability analysis of the repairable queueing systemM/G(E k /H)/1

The repairable queueing system (RQS) in which the server has an exponential lifetime distribution has been studied in several articles [1–4]. Here, we deal with the new RQSM/G(E _k /H)/1 in which the lifetime distribution of the server is Erlangian. By forming a vector Markov process, i.e. by using the method of supplementary variables, we obtained some system characters, the reliability indices of the server, and the time distribution of a customer spent on the server. For this RQS, the generalized service time distribution of each customer will depend on the remainder life of the server. Based on this, a new kind of queues, for which the service time distributions are chosen by the customers in some stochastic manner, appears in queueing theory.Project supported by the National Natural Science Foundation of China.     

Analyzing the discrete-timeG (G)/Geo/1 queue using complex contour integration

In this paper, a discrete-time single-server queueing system with an infinite waiting room, referred to as theG ^(G)/Geo/1 model, i.e., a system with general interarrival-time distribution, general arrival bulk-size distribution and geometrical service times, is studied. A method of analysis based on integration along contours in the complex plane is presented. Using this technique, analytical expressions are obtained for the probability generating functions of the system contents at various observation epochs and of the delay and waiting time of an arbitrary customer, assuming a first-come-first-served queueing discipline, under the single restriction that the probability generating function for the interarrival-time distribution be rational. Furthermore, treating several special cases we rediscover a number of well-known results, such as Hunter's result for theG/Geo/1 model. Finally, as an illustration of the generality of the analysis, it is applied to the derivation of the waiting time and the delay of the more generalG ^(G)/G/1 model and the system contents of a multi-server buffer-system with independent arrivals and random output interruptions.Both authors wish to thank the Belgian National Fund for Scientific Research (NFWO) for support of this work.     

Comparison of two randomized policy M/G/1 queues with second optional service, server breakdown and startup

The problem addressed in this paper is to compare the minimum cost of the two randomized control policies in the M/G/1 queueing system with an unreliable server, a second optional service, and general startup times. All arrived customers demand the first required service, and only some of the arrived customers demand a second optional service. The server needs a startup time before providing the first required service until the system becomes empty. After all customers are served in the queue, the server immediately takes a vacation and the system operates the (T, p)-policy or (p, N)-policy. For those two policies, the expected cost functions are established to determine the joint optimal threshold values of (T, p) and (p, N), respectively. In addition, we obtain the explicit closed form of the joint optimal solutions for those two policies. Based on the minimal cost, we show that the optimal (p, N)-policy indeed outperforms the optimal (T, p)-policy. Numerical examples are also presented for illustrative purposes.     

Optimal Exercise Strategies for Operational Risk Insurance via Multiple Stopping Times

In this paper we demonstrate how to develop analytic closed form solutions to optimal multiple stopping time problems arising in the setting in which the value function acts on a compound process that is modified by the actions taken at the stopping times. This class of problem is particularly relevant in insurance and risk management settings and we demonstrate this on an important application domain based on insurance strategies in Operational Risk management for financial institutions. In this area of risk management the most prevalent class of loss process models is the Loss Distribution Approach (LDA) framework which involves modelling annual losses via a compound process. Given an LDA model framework, we consider Operational Risk insurance products that mitigate the risk for such loss processes and may reduce capital requirements. In particular, we consider insurance products that grant the policy holder the right to insure k of its annual Operational losses in a horizon of T years. We consider two insurance product structures and two general model settings, the first are families of relevant LDA loss models that we can obtain closed form optimal stopping rules for under each generic insurance mitigation structure and then secondly classes of LDA models for which we can develop closed form approximations of the optimal stopping rules. In particular, for losses following a compound Poisson process with jump size given by an Inverse-Gaussian distribution and two generic types of insurance mitigation, we are able to derive analytic expressions for the loss process modified by the insurance application, as well as closed form solutions for the optimal multiple stopping rules in discrete time (annually). When the combination of insurance mitigation and jump size distribution does not lead to tractable stopping rules we develop a principled class of closed form approximations to the optimal decision rule. These approximations are developed based on a class of orthogonal Askey polynomial series basis expansion representations of the annual loss compound process distribution and functions of this annual loss.     

The General Two-Server Queueing Loss System: Discrete-Time Analysis and Numerical Approximation of Continuous-Time Systems

The Erlang Loss formula is a widely used model for determining values of the long-run proportion of customers that are lost (p_loss values) in multi-server loss systems with Poisson arrival processes. There is a need for models that are less restrictive. Here, the general two-server loss system is investigated with no restrictions on the form that the renewal type input process takes; i.e. the underlying model is based on the GI/G/2 model of queueing theory. The analysis is carried out in discrete time leading to a compact system of equations that can be solved numerically, or in special cases exactly, to obtain p_loss values. Exact results are obtained for some specific loss systems involving geometric distributions and, by taking appropriate limits, these results are extended to their continuous-time counterparts. A simple numerical procedure is developed to allow systems involving arbitrary continuous distributions to be approximated by the discrete-time model, leading to very accurate results for a set of test problems.     

Generalized M/G/C/C state dependent queueing models and pedestrian traffic flows

The generality and usefulness ofM/G/C/C state dependent queueing models for modelling pedestrian traffic flows is explored in this paper. We demonstrate that the departure process and the reversed process of these generalizedM/G/C/C queues is a Poisson process and that the limiting distribution of the number of customers in the queue depends onG only through its mean. Consequently, the models developed in this paper are useful not only for the analysis of pedestrian traffic flows, but also for the design of the physical systems accommodating these flows. We demonstrate how theM/G/C/C state dependent model is incorporated into the modelling of large scale facilities where the blocking probabilities in the links of the network can be controlled. Finally, extensions of this work to queueing network applications where blocking cannot be controlled are also presented, and we examine an approximation technique based on the expansion method for incorporating theseM/G/C/C queues in series, merge, and splitting topologies of these networks.     

具有可变到达率的多重休假Geo~(λ_1,λ_2)/G/1排队分析

本文考虑顾客到达与服务员休假相关的多重休假离散时间排队系统,用更新过程及u-变换分析了系统的队长性质.分别得到系统在三种时点(n~-,n~+,n)处的队长分布的递推解,进而揭示了在不同到达率条件下系统队长分布不再具有随机分解特性,得到了系统在四种时点(n~-,n~+,n,离去时点D_n)处稳态队长分布的重要关系(不同于连续时间排队系统).