A discrete-time retrial queueing model with one server

This paper presents a one-server queueing model with retrials in discrete-time. The number of primary jobs arriving in a time slot follows a general probability distribution and the different numbers of primary arrivals in consecutive time slots are mutually independent. Each job requires from the server a generally distributed number of slots for its service, and the service times of the different jobs are independent. Jobs arriving in a slot can start their service only at the beginning of the next slot. When upon arrival jobs find the server busy all incoming jobs are sent into orbit. When upon arrival in a slot jobs find the server idle, then one of the incoming jobs (randomly chosen) in that slot starts its service at the beginning of the next slot, whereas the other incoming jobs in that slot, if any, are sent into orbit. During each slot jobs in the orbit try to re-enter the system individually, independent of each other, with a given retrial probability.     

A single server queueing system with two phases of service subject to server breakdown and Bernoulli vacation

This paper deals with a single server M/G/1 queue with two phases of heterogeneous service and unreliable server. We assume that customers arrive to the system according to a Poisson process with rate λ. After completion of two successive phases of service the server either goes for a vacation with probability p(0 ? p ? 1) or may continue to serve the next unit, if any, with probability q(=1 ? p). Otherwise it remains in the system until a customer arrives. While the server is working with any phase of service, it may breakdown at any instant and the service channel will fail for a short interval of time. For this model, we first derive the joint distribution of state of the server and queue size, which is one of the chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch. 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.     

Queueing systems with different types of server interruptions

We consider a queueing system with disruptive and non-disruptive server interruptions. Both disruptive and non-disruptive interruptions may start when there is a customer in service. The customer repeats its service after a disruptive interruption, and continues its service after a non-disruptive interruption. Using a transform approach, we obtain various performance measures such as the moments of the queue content and waiting times. We illustrate our approach by means of some numerical examples.     

Optimal server scheduling in nonpreemptive finite-population queueing systems

We consider a finite-population queueing system with heterogeneous classes of customers and a single server. For the case of nonpreemptive service, we fully characterize the structure of the server's optimal service policy that minimizes the total average customer waiting costs. We show that the optimal service policy may never serve some classes of customers. For those classes that are served, we show that the optimal service policy is a simple static priority policy. We also derive sufficient conditions that determine the optimal priority sequence.     

Analysis of discrete-time queueing systems with priority jumps

This text is a summary of the author’s PhD thesis supervised by Herwig Bruneel and Joris Walraevens, and defended on 5 March 2009 at Ghent University. The thesis is written in English and is available from the author upon request. The work deals with several priority scheduling disciplines with so-called priority jumps. An efficient priority scheduling discipline is of great importance in modern telecommunication devices. Static priority scheduling achieves maximum service differentiation between different types of traffic, but may have a too severe impact on the performance of lower-priority traffic. Introducing priority jumps aims for a more gradual service differentiation. In the thesis, we propose several (types of) jumping mechanisms, and we analyse their effect on the performance of a discrete-time queueing system.     

Stabilization analysis for discrete-time systems with time delay

The stabilization problem for a class of discrete-time systems with time-varying delay is investigated. By constructing an augmented Lyapunov function, some sufficient conditions guaranteeing exponential stabilization are established in forms of linear matrix inequality (LMI) technique. When norm-bounded parameter uncertainties appear in the delayed discrete-time system, a delay-dependent robust exponential stabilization criterion is also presented. All of the criteria obtained in this paper are strict linear matrix inequality conditions, which make the controller gain matrix can be solved directly. Three numerical examples are provided to demonstrate the effectiveness and improvement of the derived results.     

A quorum queueing system with an unreliable server

We analyze a bulk service queueing system with an unreliable server, Poisson input, and general service and repair times. A stability condition and steady state system size distributions are obtained. The optimal management policy is discussed and illustrative examples are provided.     

A discrete-time queueing system with optional LCFS discipline

We consider a discrete-time queueing system in which the arriving customers decide with a certain probability to be served under a LCFS-PR discipline and with complementary probability to join the queue. The arrivals are assumed to be geometrical and the service times are arbitrarily distributed. The service times of the expelled customers are independent of their previous ones. We carry out an extensive analysis of the system developing recursive formulae and generating functions for the steady-state distribution of the number of customers in the system and obtaining also recursive formulae and generating functions for the stationary distribution of the busy period and sojourn time as well as some performance measures.     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

Analysis of a discrete-time queueing system with time-limited service

We analyze a discrete-time, single-server queueing system in which the length of each service period is limited. The server takes a vacation when the limit expires or the queue empties, whichever occurs first. In the former case, the preempted service is resumed after the vacation without loss or creation of any work. This system models the transmission of message frames from a station on timed-token local-area networks (for example, FDDI and IEEE 802.4 token bus). We study the process of the unfinished work and the joint process of the queue size and the remaining service time. By using the technique of discrete Fourier transforms to determine some unknown functions in the governing equations, we numerically obtain exact mean waiting times.A part of the work of H. Takagi was done while he was with IBM Research, Tokyo Research Laboratory.     

An auxiliary server threshold queueing model and its application to the operational characteristics of web server system

This paper analyzes an auxiliary server queueing model in which secondary servers are added to the main server(s) when the queue length exceeds some predetermined threshold value at the main queue. We model this system by the level-dependent quasi-birth-death (QBD) process and develop computation algorithms. We apply this model to the web-server system to explore some specific operational characteristics and draw some useful conclusions.     

Diffusion approximations for open queueing networks with service interruptions

This paper establishes functional central limit theorems describing the heavy-traffic behavior of open single-class queueing networks with service interruptions. In particular, each station has a single server which is alternatively up and down. There are two treatments of the up and down times. The first treatment corresponds to fixed up and down times and leads to a reflected Brownian motion, just as when there are no service interruptions, but with different parameters. To represent long rare interruptions, the second treatment has growing up and down times with the up and down times being of ordern andn ^1/2, respectively, when the traffic intensities are of order 1-n^–1/2. In this case we establish convergence in the SkorohodM ₁ topology to a multidimensional reflection of multidimensional Brownian motion plus a multidimensional jump process.     

Waiting time approximation in multi-class queueing systems with multiple types of class-dependent interruptions

We consider a single-server queue subject to class-dependent interruptions motivated by vessel queueing at entrances of waterways. Two classes of customers and k types of possibly simultaneous and class-dependent service interruptions are considered. We have employed service completion time analysis and proposed approximations to obtain the expected waiting time of a customer (vessel) in the queue.     

A two-server queueing system with periodic and credit-based server availabilities

A discrete-time, two-server queueing system is studied in this paper. The service time of a customer (cell) is fixed and equal to one time unit. Server 1 provides for periodic service of the queue (periodT). Server 2 provides for service only when server 1 is unavailable and provided that the associated service credit is nonzero. The resulting system is shown to model the queueing behavior of a network user which is subject to traffic regulation for congestion avoidance in high speed ATM networks. A general methodology is developed for the study of this queueing system, based on renewal theory. The dimensionality of the developed model is independent ofT;T increases with the network speed. The cell loss probabilities are computed in the case of finite capacity queue.Research supported by the National Science Foundation under grant NCR-9011962.     

A queueing system with random server capacity and multiple control

The authors study queueing, input and output processes in a queueing system with bulk service and state dependent service delay. The input flow of customers, modulated by a semi-Markov process, is served by a single server that takes batches of a certain fixed size if available or waits until the queue accumulates enough customers for service. In the latter case, the batch taken for service is of random size dependent on the state of the system, while service duration depends both on the state of the system and on the batch size taken. The authors establish a necessary and sufficient condition for equilibrium of the system and obtain the following results: Explicit formulas for steady state distribution of the queueing process, intensity of the input and output processes, and mean values of idle and busy periods. They employ theory of semi-regenerative processes and illustrate the results by a number of examples. In one of them an optimization problem is discussed.     

The departure process of discrete-time queueing systems with Markovian type inputs

This paper proposes a unified matrix-analytic approach to characterize the output processes of general discrete-time lossless/lossy queueing systems in which time is synchronized/slotted into fixed length intervals called slots. The arrival process can be continuous- or discrete-time Markovian processes. It can be either renewal or non-renewal. The service of a customer commences at the beginning of a slot, consumes a random number of slots, and completes at the end of a later slot. The service times are independent and follow a common and general distribution. Systems with and without server vacations are both treated in this paper. These queueing systems have potential applications in asynchronous transfer mode (ATM) networks, packet radio networks, etc. Since the output process of a node in a queueing network becomes an input process to some node at the next stage, the results of this paper can be used to facilitate end-to-end performance analysis which has attracted more and more attention in the literature. This revised version was published online in June 2006 with corrections to the Cover Date.     

A multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.