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 number of full levels in tries

We study the asymptotic distribution of the fill‐up level in a binary trie built over n independent strings generated by a biased memoryless source. The fill‐up level is the number of full levels in a tree. A level is full if it contains the maximum allowable number of nodes (e.g., in a binary tree level k can have up to 2^k nodes). The fill‐up level finds many interesting applications, e.g., in the internet IP lookup problem and in the analysis of level compressed tries (LC tries). In this paper, we present a complete asymptotic characterization of the fill‐up distribution. In particular, we prove that this distribution concentrates on one or two points around the most probably value k = ?log_1/qn ? log log log n + 1 + log log(p/q)?, where p > q = 1 ? p is the probability of generating the more likely symbol (while q = 1 ? p is the probability of the less likely symbol). We derive our results by analytic methods such as generating functions, Mellin transform, the saddle point method, and analytic depoissonization. We also present some numerical verification of our results. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

An Exact Solution for an M(t)/M(t)/1 Queue with Time-Dependent Arrivals and Service

We consider an M/M/1 queue with a time dependent arrival rate (t) and service rate (t). For a special form of the traffic intensity, we obtain an exact, explicit expression for the probability p _n (t) that there are n customers at time t. If the service rate is constant (=), this corresponds to (t)=(t)/=(b–at)^–2. We also discuss the heavy traffic diffusion approximation to this model. We evaluate our results numerically.     

A Variational Approach to Nonlinear Singularly Perturbed Boundary-Value Problems

Carrier and Pearson introduced a nonlinear singularly perturbed boundary value problem that has served as a paradigm for problems where the method of matched asymptotic expansions (MAE) apparently fails. The “failure” of MAE is its inability to select the location of possible internal layers, though their structure is determined. Thus, a straightforward application of MAE leaves the positions of any internal layers arbitrary, though the asymptotic expansion of the exact solution to the problem exhibits internal layers only at specific locations. For this reason the solutions produced by MAE have been referred to as spurious solutions. We resolve the question of finding the positions of the interior layers by employing the variational approach of Grasman and Matkowsky. In addition, we show that this method tells how solutions bifurcate as the boundary values are varied, and give an alternative motivation for the variational approach via Newton”s method.     

Geometrical Optics Approach to Markov-Modulated Fluid Models

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 processes 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 →∞  , with appropriate scalings of the two state variables. In particular, the ray method and asymptotic matching are used.     

Asymptotic Analysis of Spectral Properties of Finite Capacity Processor Shared Queues

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.     

Boundary behavior of diffusion approximations to Markov jump processes

We show that diffusion approximations, including modified diffusion approximations, can be problematic since the proper choice of local boundary conditions (if any exist) is not obvious. For a class of Markov processes in one dimension, we show that to leading order it is proper to use a diffusion (Fokker-Planck) approximation to compute mean exit times with a simple absorbing boundary condition. However, this is only true for the leading term in the asymptotic expansion of the mean exit time. Higher order correction terms do not, in general, satisfy simple absorbing boundary conditions. In addition, the diffusion approximation for the calculation of mean exit times is shown to break down as the initial point approaches the boundary, and leads to an increasing relative error. By introducing a boundary layer, we show how to correct the diffusion approximation to obtain a uniform approximation of the mean exit time. We illustrate these considerations with a number of examples, including a jump process which leads to Kramers' diffusion model. This example represents an extension to a multivariate process.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic Expansions for the Congestion Period for the M/M/∞ Queue

We consider the M/M/ queue with arrival rate , service rate and traffic intensity =/. We analyze the first passage distribution of the time the number of customers N(t) reaches the level c, starting from N(0)=m>c. If m=c+1 we refer to this time period as the congestion period above the level c. We give detailed asymptotic expansions for the distribution of this first passage time for , various ranges of m and c, and several different time scales. Numerical studies back up the asymptotic results.