Search

We consider the Erlang A model, or $M/M/m+M$ queue, with Poisson arrivals, exponential service times, and $m$ parallel servers, and the property that waiting customers abandon the queue after an exponential time. The queue length process is in this case a birth-death process, for which we obtain explicit expressions for the Laplace transforms of the time-dependent distribution and the first passage time. These two transient characteristics were generally presumed to be intractable. Solving for the Laplace transforms involves using Green's functions and contour integrals related to hypergeometric functions. Our results are specialized to the $M/M/\infty$ queue, the $M/M/m$ queue, and the $M/M/m/m$ loss model. We also obtain some corresponding results for diffusion approximations to these models.

We consider the Halfin-Whitt diffusion process $X_d(t)$, which is used, for example, as an approximation to the $m$-server $M/M/m$ queue. We use recently obtained integral representations for the transient density $p(x,t)$ of this diffusion process, and obtain various asymptotic results for the density. The asymptotic limit assumes that a drift parameter $\beta$ in the model is large, and the state variable $x$ and the initial condition $x_0$ (with $X_d(0)=x_0>0$) are also large. We obtain some alternate representations for the density, which involve sums and/or contour integrals, and expand these using a combination of the saddle point method, Laplace method and singularity analysis. The results give some insight into how steady state is achieved, and how if $x_0>0$ the probability mass migrates from $X_d(t)>0$ to the range $X_d(t)<0$, which is where it concentrates as $t\to\infty$, in the limit we consider. We also discuss an alternate approach to the asymptotics, based on geometrical optics and singular perturbation techniques., Comment: 43 pages and 8 figures

We consider a finite population processor-sharing (PS) queue, with Markovian arrivals and an exponential server. Such a queue can model an interactive computer system consisting of a bank of terminals in series with a central processing unit (CPU). For systems with a large population $N$ and a commensurately rapid service rate, or infrequent arrivals, we obtain various asymptotic results. We analyze the conditional sojourn time distribution of a tagged customer, conditioned on the number $n$ of others in the system at the tagged customer's arrival instant, and also the unconditional distribution. The asymptotics are obtained by a combination of singular perturbation methods and spectral methods. We consider several space/time scales and parameter ranges, which lead to different asymptotic behaviors. We also identify precisely when the finite population model can be approximated by the standard infinite population $M/M/1$-PS queue., Comment: 60 pages and 3 figures

We consider sojourn (or response) times in processor-shared queues that have a finite customer capacity. Computing the response time of a tagged customer involves solving a finite system of linear ODEs. Writing the system in matrix form, we study the eigenvectors and eigenvalues in the limit as the size of the matrix becomes large. This corresponds to finite capacity models where the system can only hold a large number $K$ of customers. Using asymptotic methods we reduce the eigenvalue problem to that of a standard differential equation, such as the Airy equation. The dominant eigenvalue leads to the tail of a customer's sojourn time distribution. Some numerical results are given to assess the accuracy of the asymptotic results., Comment: 30 pages, 7 figures, and 3 tables

We consider sojourn or response times in processor-shared queues that have a finite population of potential users. Computing the response time of a tagged customer involves solving a finite system of linear ODEs. Writing the system in matrix form, we study the eigenvectors and eigenvalues in the limit as the size of the matrix becomes large. This corresponds to finite population models where the total population is $N\gg 1$. Using asymptotic methods we reduce the eigenvalue problem to that of a standard differential equation, such as the Hermite equation. The dominant eigenvalue leads to the tail of a customer's sojourn time distribution., Comment: 28 pages, 7 figures and 5 tables

We consider the heavy-traffic approximation to the $GI/M/s$ queueing system in the Halfin-Whitt regime, where both the number of servers $s$ and the arrival rate $\lambda$ grow large (taking the service rate as unity), with $\lambda=s-\beta\sqrt{s}$ and $\beta$ some constant. In this asymptotic regime, the queue length process can be approximated by a diffusion process that behaves like a Brownian motion with drift above zero and like an Ornstein-Uhlenbeck process below zero. We analyze the first passage times of this hybrid diffusion process to levels in the state space that represent congested states in the original queueing system.

We consider a hybrid diffusion process that is a combination of two Ornstein-Uhlenbeck processes with different restraining forces. This process serves as the heavy-traffic approximation to the Markovian many-server queue with abandonments in the critical Halfin-Whitt regime. We obtain an expression for the Laplace transform of the time-dependent probability distribution, from which the spectral gap is explicitly characterized. The spectral gap gives the exponential rate of convergence to equilibrium. We further give various asymptotic results for the spectral gap, in the limits of small and large abandonment effects. It turns out that convergence to equilibrium becomes extremely slow for overloaded systems with small abandonment effects., Comment: 48 pages

We consider the chessboard pebbling problem analyzed by Chung, Graham, Morrison and Odlyzko [3]. We study the number of reachable configurations $G(k)$ and a related double sequence $G(k,m)$. Exact expressions for these are derived, and we then consider various asymptotic limits., Comment: 12 pages, 7 references

We consider an American put option under the CEV process. This corresponds to a free boundary problem for a PDE. We show that this free bondary satisfies a nonlinear integral equation, and analyze it in the limit of small $\rho$ = $2r/ \sigma^2$, where $r$ is the interest rate and $\sigma$ is the volatility. We use perturbation methods to find that the free boundary behaves differently for five ranges of time to expiry., Comment: 14 pages, 0 figures

We consider a processor sharing storage allocation model, which has m primary holding spaces and infinitely many secondary ones, and a single processor servicing the stored items (customers). All of the spaces are numbered and ordered. An arriving customer takes the lowest available space. We define the traffic intensity rho to be lambda/mu where lambda is the customers' arrival rate and mu is the service rate of the processor. We study the joint probability distribution of the numbers of occupied primary and secondary spaces. For 0 < rho < 1, we obtain the exact solutions for m = 1 and m = 2. For arbitrary m we study the problem in the asymptotic limit rho -> 1 with m fixed. We also develop a semi-numerical semi-analytic method for computing the joint distribution., Comment: 40 pages, one figure, two tables

We consider a processor sharing storage allocation model, which has m primary holding spaces and infinitely many secondary ones, and a single processor servicing the stored items (customers). All of the spaces are numbered and ordered. An arriving customer takes the lowest available space. We define the traffic intensity rho to be lambda/mu where lambda is the customers' arrival rate and mu is the service rate of the processor. We study the joint probability distribution of the numbers of occupied primary and secondary spaces. We study the problem in two asymptotic limits: (1) m -> infinity with a fixed rho <1, and (2) rho -> 1, m -> infinity with m(1-rho)= O(1)., Comment: 103 pages, five figures, two tables

We consider a processor shared $M/M/1$ queue that can accommodate at most a finite number $K$ of customers. We give an exact expression for the sojourn time distribution in the finite capacity model, in terms of a Laplace transform. We then give the tail behavior, for the limit $K\to\infty$, by locating the dominant singularity of the Laplace transform., Comment: 10 pages

We consider the $M/M/1$ queue with processor sharing. We study the conditional sojourn time distribution, conditioned on the customer's service requirement, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. The asymptotic formulas relate to, and extend, some results of Morrison \cite{MO} and Flatto \cite{FL}., Comment: 30 pages, 3 figures and 1 table

We consider the processor sharing $M/M/1$-PS queue which also models balking. A customer that arrives and sees $n$ others in the system "balks" (i.e., decides not to enter) with probability $1-b_n$. If $b_n$ is inversely proportional to $n+1$, we obtain explicit expressions for a tagged customer's sojourn time distribution. We consider both the conditional distribution, conditioned on the number of other customers present when the tagged customer arrives, as well as the unconditional distribution. We then evaluate the results in various asymptotic limits. These include large time (tail behavior) and/or large $n$, lightly loaded systems where the arrival rate $\lambda\to 0$, and heavily loaded systems where $\lambda\to\infty$. We find that the asymptotic structure for the problem with balking is much different from the standard $M/M/1$-PS queue. We also discuss a perturbation method for deriving the asymptotics, which should apply to more general balking functions., Comment: 36 pages

We consider the $M/G/1$ queue with a processor sharing server. We study the conditional sojourn time distribution, conditioned on the customer's service requirement, as well as the unconditional distribution, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. Our results demonstrate the possible tail behaviors of the unconditional distribution, which was previously known in the cases $G=M$ and $G=D$ (where it is purely exponential). We assume that the service density decays at least exponentially fast. We use various methods for the asymptotic expansion of integrals, such as the Laplace and saddle point methods., Comment: 45 pages

We consider the $M/M/1$-PS queue with processor sharing. We study the conditional sojourn time distribution of an arriving customer, conditioned on the number of other customers present. A new formula is obtained for the conditional sojourn time distribution, using a discrete Green's function. This is shown to be equivalent to some classic results of Pollaczeck and Vaulot from 1946. Then various asymptotic limits are studied, including large time and/or large number of customers present, and heavy traffic, where the arrival rate is only slightly less than the service rate., Comment: 45 pages, 2 figures

We analyze the sequence of polynomials defined by the differential-difference equation $P_{n+1}(x)=P_{n}^{\prime}(x)+x(n+1)P_{n}(x)$ asymptotically as $n\to\infty$. The polynomials $P_{n}(x)$ arise in the computation of higher derivatives of the inverse error function $\operatorname{inverf}(x)$. We use singularity analysis and discrete versions of the WKB and ray methods and give numerical results showing the accuracy of our formulas., Comment: 26 pages, 7 figures

We analyze asymptotically a differential-difference equation, that arises in a Markov-modulated fluid model. We use singular perturbation methods to analyze the problem with appropriate scalings of the two state variables. In particular, the ray method and asymptotic matching are used., Comment: 37 pages, 5 figures

We analyze a second order, linear, elliptic PDE with mixed boundary conditions. This problem arose as a limiting case of a Markov-modulated queueing model for data handling switches in communications networks. We use singular perturbation methods to analyze the problem. In particular we use the ray method to solve the PDE in the limit where convection dominates diffusion. We show that there are both interior and boundary caustics, as well as a cusp point where two caustics meet, an internal layer, boundary layers and a corner layer. Our analysis leads to approximate formulas for the queue length (or buffer content) distribution at the switch., Comment: 38 pages, 3 figures

We consider a fluid queue where the input process consists of N identical sources that turn on and off at exponential waiting times. The server works at the constant rate c and an on source generates fluid at unit rate. This model was first formulated and analyzed by Anick, Mitra and Sondhi. We obtain an alternate representation of the joint steady state distribution of the buffer content and the number of on sources. This is given as a contour integral that we then analyze for large N. We give detailed asymptotic results for the joint distribution, as well as the associated marginal and conditional distributions. In particular, simple conditional limits laws are obtained. These shows how the buffer content behaves conditioned on the number of active sources and vice versa. Numerical comparisons show that our asymptotic results are very accurate even for N=20.

We consider an elliptic PDE in two variables. As one parameter approaches zero, this PDE collapses to a parabolic one, that is forward parabolic in a part of the domain and backward parabolic in the remainder. Such problems arise naturally in various stochastic models, such as fluid models for data-handling systems and Markov-modulated queues. We employ singular perturbation methods to study the problem for small values of the parameter.

We analyze asymptotically a differential-difference equation, that arises in a Markov-modulated fluid model. Here there are N identical sources that turn "on" and "off", and when "on" they generate fluid at unit rate into a buffer, which process the fluid at a rate c < N. In the steady state limit, the joint probability distribution of the buffer content and the number of active sources satisfies a system of N + 1 ODEs, that can also be viewed as a differential-difference equation analogous to a backward/forward parabolic PDE. We use singular perturbation methods to analyze the problem for N large with appropriate scalings of the two state variables. In particular, the ray method and asymptotic matching are used.