This paper studies the input-queued switch operating under the MaxWeight algorithm when the arrivals are according to a Markovian process. We exactly characterize the heavy-traffic scaled mean sum queue length in the heavy-traffic limit, and show that it is within a factor of less than 2 from a universal lower bound. Moreover, we obtain lower and upper bounds that are applicable in all traffic regimes and become tight in the heavy-traffic regime.

We obtain these results by generalizing the drift method recently developed for the case of independent and identically distributed arrivals to the case of Markovian arrivals. We illustrate this generalization by first obtaining the heavy-traffic mean queue length and its distribution in a single-server queue under Markovian arrivals and then applying it to the case of an input-queued switch.

The key idea is to exploit the geometric mixing of finite-state Markov chains, and to work with a time horizon that is chosen so that the error due to mixing depends on the heavy-traffic parameter.

We study the exact asymptotics for the distribution of the first time, τx, a Lévy process Xt crosses a fixed negative level -x. We prove that ℙ{τx >t} ~V(x) ℙ{Xt≥0}/t as t→∞ for a certain function V(x). Using known results for the large deviations of random walks, we obtain asymptotics for ℙ{τx>t} explicitly in both light- and heavy-tailed cases.

Consider the single-server queue with an infinite buffer and a first-in–first-out discipline, either of type M/M/1 or Geom/Geom/1. Denote by 𝒜 the arrival process and by s the services. Assume the stability condition to be satisfied. Denote by 𝒟 the departure process in equilibrium and by r the time spent by the customers at the very back of the queue. We prove that (𝒟, r) has the same law as (𝒜, s), which is an extension of the classical Burke theorem. In fact, r can be viewed as the sequence of departures from a dual storage model. This duality between the two models also appears when studying the transient behaviour of a tandem by means of the Robinson–Schensted–Knuth algorithm: the first and last rows of the resulting semistandard Young tableau are respectively the last instant of departure from the queue and the total number of departures from the store.

We derive an integral equation for the transient probabilities and expected number in the queue for the multiserver queue with Poisson arrivals, exponential service for time-varying arrival and departure rates, and a time-varying number of servers. The method is a straightforward application of generating functions. We can express pĉ−1(t), the probability that ĉ − 1 customers are in the queue or being served, in terms of a Volterra equation of the second kind, where ĉ is the maximum number of servers working during the day. Each of the other transient probabilities is expressed in terms of integral equations in pĉ−1(t) and the transition probabilities of a certain time-dependent random walk. In this random walk, the rate of steps to the right equals the arrival rate of the queue and the rate of steps to the left equals the departure rate of the queue when all servers are busy.

Using a known fact that a Galton–Watson branching process can be represented as an embedded random walk, together with a result of Heyde (1964), we first derive finite exponential moment results for the total number of descendants of an individual. We use this basic and simple result to prove analogous results for the population size at time t and the total number of descendants by time t in an age-dependent branching process. This has applications in justifying the interchange of expectation and derivative operators in simulation-based derivative estimation for generalized semi-Markov processes. Next, using the result of Heyde (1964), we show that, in a stable GI/GI/1 queue, the length of a busy period and the number of customers served in a busy period have finite exponential moments if and only if the service time does.

We derive two kinds of rate conservation laws for describing the time-dependent behavior of a process defined with a stationary marked point process and starting at time 0. These formulas are called TRCLs (time-dependent rate conservation laws). It is shown that TRCLs are useful to study the transient behaviors of risk and storage processes with stationary claim and supply processes and with a general premium and release rates, respectively. Detailed discussions are given for the severity for the risk process, and for the workload process of a single-server queue.

Shanthikumar and Sumita (1986) proved that the stationary system queue length distribution just after a departure instant is geometric for GI/GI/1 with LCFS-P/H service discipline and with a constant acceptance probability of an arriving customer, where P denotes preemptive and H is a restarting policy which may depend on the history of preemption. They also got interesting relationships among characteristics. We generalize those results for G/G/1 with an arbitrary restarting LCFS-P and with an arbitrary acceptance policy. Several corollaries are obtained. Fakinos' (1987) and Yamazaki's (1990) expressions for the system queue length distribution are extended. For a Poisson arrival case, we extend the well-known insensitivity for LCFS-P/resume, and discuss the stationary distribution for LCFS-P/repeat.

It is shown that among all work-conserving service disciplines that are independent of the future history, the first-come-first-served (FCFS) service discipline minimizes [maximizes] the average sojourn time in a G/GI/1 queueing system with new better [worse] than used in expectation (NBUE[NWUE]) service time distribution. We prove this result using a new basic identity of G/GI/1 queues that may be of independent interest. Using a relationship between the workload and the number of customers in the system with different lengths of attained service it is shown that the average sojourn time is minimized [maximized] by the least-attained-service time (LAST) service discipline when the service time has the decreasing [increasing] mean residual life (DMRL[IMRL]) property.

In a recent paper by Shanthikumar and Sumita (1987), it is conjectured that the ergodic sojourn time of a customer in G/IFR/1 queues is minimized by FIFO (first in, first out) discipline in the sense of increasing and convex ordering. This paper shows that their conjecture is true. In fact, FIFO discipline minimizes for any non-decreasing and convex function f, where N is the (constant) number of arrivals, θ (k) is the customer identity of the kth departing customer, and an and τ n denote the arriving and departing times of the nth customer, respectively.

We consider a queue which is obtained by slightly modifying the M/PH/1 queue, so that weak correlations are introduced among the interarrival times. We show how the stationary probability distribution may be studied by a perturbation analysis.

In this paper we investigate the server's busy period in a single-server queueing situation in which the interarrival interval T preceding the arrival of a customer and his service time S are assumed correlated. A closed-form expression is obtained for the Laplace transform bn(z) of the joint probability and probability density function of the busy period duration and the number of customers served in it. Some numerical values are given showing the effect of correlation between T and S.

This paper establishes a link between the Wiener–Hopf factorization and the phase-type method for studying the GI/G/1 queue. Using the Wiener–Hopf factorization, infinite-matrix type results are established for the GI/G/1 queue. An iterative numerical procedure (‘Levinson&s method’) based on these results is described. This method does not always converge. For the situation where either the interarrival times or the service times are of the so-called almost phase type (APH) an alternative, probabilistic derivation of the same results is given. This alternative derivation shows that in the APH situation Levinson&s method converges, converges essentially monotonically, and converges to the correct values.

The algorithm has been coded and examples of numerical results are included.

We discuss a single-server queue whose input is the versatile Markovian point process recently introduced by Neuts [22] herein to be called the N-process. Special cases of the N-process discussed earlier in the literature include a number of complex models such as the Markov-modulated Poisson process, the superposition of a Poisson process and a phase-type renewal process, etc. This queueing model has great appeal in its applicability to real world situations especially such as those involving inhibition or stimulation of arrivals by certain renewals. The paper presents formulas in forms which are computationally tractable and provides a unified treatment of many models which were discussed earlier by several authors and which turn out to be special cases. Among the topics discussed are busy-period characteristics, queue-length distributions, moments of the queue length and virtual waiting time. We draw particular attention to our generalization of the Pollaczek–Khinchin formula for the Laplace–Stieltjes transform of the virtual waiting time of the M/G/1 queue to the present model and the resulting Volterra system of integral equations. The analysis presented here serves as an example of the power of Markov renewal theory.

A general procedure is outlined for obtaining lower bounds and approximations to the amount of congestion in queues with low traffic. Some detailed formulae are given for a number of single-server systems and compared with exact solutions where available. Results are also given for a discrete time system in which departures clash with new arrivals.