An M/G/1 Retrial Queueing System with Two-Phase Service and Preemptive Resume

An M/G/1 retrial queueing system with additional phase of service and possible preemptive resume service discipline is considered. For an arbitrarily distributed retrial time distribution, the necessary and sufficient condition for the system stability is obtained, assuming that only the customer at the head of the orbit has priority access to the server. The steady-state distributions of the server state and the number of customers in the orbit are obtained along with other performance measures. The effects of various parameters on the system performance are analysed numerically. A general decomposition law for this retrial queueing system is established.     

多重休假的带启动--关闭期的Geom/G/1排队

本研究多重休假的带启动——关闭期的Geom／G／1离散时间排队，给出稳态队长，等待时间分布的母函数及其随机分解结果，推导出忙期的全假期的母函数，给出该模型的几个特例。     

Approximations for Markovian multi-class queues with preemptive priorities

We discuss the approximation of performance measures in multi-class M/M/k queues with preemptive priorities for large problem instances (many classes and servers) using class aggregation and server reduction. We compared our approximations to exact and simulation results and found that our approach yields small-to-moderate approximation errors.     

An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

A fluid system with coupled input and output,and its application to bottlenecks in ad hoc networks

This paper studies a fluid queue with coupled input and output. Flows arrive according to a Poisson process, and when n flows are present, each of them transmits traffic into the queue at a rate c/(n+1), where the remaining c/(n+1) is used to serve the queue. We assume exponentially distributed flow sizes, so that the queue under consideration can be regarded as a system with Markov fluid input. The rationale behind studying this queue lies in ad hoc networks: bottleneck links have roughly this type of sharing policy. We consider four performance metrics: (i) the stationary workload of the queue, (ii) the queueing delay, i.e., the delay of a ‘packet’ (a fluid particle) that arrives at the queue at an arbitrary point in time, (iii) the flow transfer delay, i.e., the time elapsed between arrival of a flow and the epoch that all its traffic has been put into the queue, and (iv) the sojourn time, i.e., the flow transfer time increased by the time it takes before the last fluid particle of the flow is served. For each of these random variables we compute the Laplace transform. The corresponding tail probabilities decay exponentially, as is shown by a large-deviations analysis. F. Roijers’ work has been carried out partly in the SENTER-NOVEM funded project Easy Wireless.     

M/G/1/N vacation model with varying E-limited service discipline

We define and analyze anM/G/1/N vacation model that uses a service discipline that we call theE-limited with limit variation discipline. According to this discipline, the server provides service until either the system is emptied (i.e. exhausted) or a randomly chosen limit ofl customers has been served. The server then goes on a vacation before returning to service the queue again. The queue length distribution and the Laplace-Stieltjes transforms of the waiting time, busy period and cycle time distributions are found. Further, an expression for the mean waiting time is developed. Several previously analyzed service disciplines, including Bernoulli scheduling, nonexhaustive service and limited service, are special cases of the general varying limit discipline that is analyzed in this paper.     

Optimal intensity control of a multi-class queue

We study a mixed problem of optimal scheduling and input and output control of a single server queue with multi-classes of customers. The model extends the classical optimal scheduling problem by allowing the general point processes as the arrival and departure processes and the control of the arrival and departure intensities. The objective of our scheduling and control problem is to minimize the expected discounted inventory cost over an infinite horizon, and the problem is formulated as an intensity control. We find the well-knownc is the optimal solution to our problem.Supported in part by NSF under grant ECS-8658157, by ONR under contract N00014-84-K-0465, and by a grant from AT&T Bell Laboratories.The work was done while the author was a postdoctoral fellow in the Division of Applied Sciences, Harvard University, Cambridge, Massachusetts 02138.     

Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline

We give in this paper a detailed sample-average analysis of GI/G/1 queues with the preemptive-resume LIFO (last-in-first-out) queue discipline: we study the long-run state behavior of the system by averaging over arrival epochs, departure epochs, as well as time, and obtain relations that express the resulting averages in terms of basic characteristics within busy cycles. These relations, together with the fact that the preemptive-resume LIFO queue discipline is work-conserving, imply new representations for both actual and virtual delays in standard GI/G/1 queues with the FIFO (first-in-first-out) queue discipline. The arguments by which our results are obtained unveil the underlying structural explanations for many classical and somewhat mysterious results relating to queue lengths and/or delays in standard GI/G/1 queues, including the well-known Bene's formula for the delay distribution in M/G/l. We also discuss how to extend our results to settings more general than GI/G/1.