Search

We consider a multi-class multi-server retrial queueing system. Customers of each class arrive from outside the system according to a Poisson process. The service times for each class of customers are assumed to be exponentially distributed with service rates depending on both the customers’ class and the servers. We define the offered load and provide stability and instability conditions for this retrial queueing system. The stability result can be obtained by introducing artificial primitive processes and using the fluid limit approach.

When the boundary--the total number of servers-- in an Erlang loss system is a function of time, customers may also be lost due to boundary variations. On condition that these customers are selected independently of their history, we solve for the hitting-time distribution and transient distribution of busy servers. We derive concise asymptotic expressions in the time domain for normal loads in the heavy-traffic limit, i.e., when the offered load $$\rho $$ ? is high, and the number of servers scales as $$\rho +O\left( \sqrt{\rho }\right) $$ ? + O ? . The solutions are computationally efficient, and simulations confirm the theoretical results.

We present a cost model for splitting Internet dial-up traffic (which varies by time-of-day) between two large modem banks. One of the modem banks charges by the hour, the other charges for the peak number-in-system during the day. To study if the possible savings are enough to make the effort worthwhile, we formulate a clairvoyant ("perfect information") Integer Program that is equivalent to a network flow problem. This leads us to use a ceiling policy. In the stochastic control case, we use a Modified Offered Load (MOL) approximation to explore the properties of the system, and develop a square-root-type rule to set the ceiling in the homogeneous case. We also use simulation to determine an optimal ceiling when we cannot route individual calls precisely. We propose approximations that may be computed for any call duration distribution, and compare their answers to exact differential-equation procedures for Exponential call durations.

One of the classical models of queueing theory is the M/M/s queue or Erlang delay model. This model has s homogeneous servers working in parallel. Customers arrive according to a Poisson process with arrival rate λ, and the service times are independent and exponentially distributed with mean 1/μ. Let the offered load be a = λ/μ and assume a < s to have a proper steady-state distribution. The most important performance characteristic for this system is the probability that a customer is delayed when arriving at the system in steady state. This probability is known as the Erlang C formula, given by (with ρ = a/s)

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type i customers requiring A_i servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type i customer is accepted only if there are R_i \,(\geq A_i ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R_1,\ldots, R_{K-1} remain bounded, while R^N_K\to\infty and R^N_K/\sqrt{N}\to0 as N \to\infty. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation.

In this paper we consider the M_t /G/\infty queueing model with infinitely many servers and a nonhomogeneous Poisson arrival process. Our goal is to obtain useful insights and formulas for nonstationary finite-server systems that commonly arise in practice. Here we are primarily concerned with the peak congestion. For the infinite-server model, we focus on the maximum value of the mean number of busy servers and the time lag between when this maximum occurs and the time that the maximum arrival rate occurs. We describe the asymptotic behavior of these quantities as the arrival changes more slowly, obtaining refinements of previous simple approximations. In addition to providing improved approximations, these refinements indicate when the simple approximations should perform well. We obtain an approximate time-dependent distribution for the number of customers in service in associated finite-server models by using the modified-offered-load (MOL) approximation, which is the finite-server steady-state distribution with the infinite-server mean serving as the offered load. We compare the value and lag in peak congestion predicted by the MOL approximation with exact values for M_t/M/s delay models with sinusoidal arrival-rate functions obtained by numerically solving the Chapman–Kolmogorov forward equations. The MOL approximation is remarkably accurate when the delay probability is suitably small. To treat systems with slowly varying arrival rates, we suggest focusing on the form of the arrival-rate function near its peak, in particular, on its second and third derivatives at the peak. We suggest estimating these derivatives from data by fitting a quadratic or cubic polynomial in a suitable interval about the peak.

An M/M/N queue, where each of the processors is subject to independent random breakdowns and repairs, is analyzed in the steady state under two limiting regimes. The first is the usual heavy traffic limit where the offered load approaches the available processing capacity. The (suitably normalized) queue size is shown to be asymptotically exponentially distributed and independent of the number of operative processors. The second limiting regime involves increasing the average lengths of the operative and inoperative periods, while keeping their ratio constant. Again the asymptotic distribution of an appropriately normalized queue size is determined. This time it turns out to have a rational Laplace transform with simple poles. In both cases, the relevant parameters are easily computable.

We consider a generalization of the classical Erlang loss model to multiple classes of customers. Each of the J customer classes has an associated Poisson arrival process and an arbitrary holding time distribution. Classj customers requireMj servers simultaneously. We determine the asymptotic form of the blocking probabilities for all customer classes in the regime known as critical loading, where both the number of servers and offered load are large and almost equal. Asymptotically, the blocking probability of classj customers is proportional toMj. This asymptotic result provides an approximation for the blocking probabilities which is reasonably accurate. We also consider the behavior of the Erlang fixed point (reduced load approximation) for this model under critical loading. Although the blocking probability of classj customers given by the Erlang fixed point is again asymptotically proportional toMj, the Erlang fixed point typically gives the wrong limit. Next we show that under critical loading the throughputs have a pleasingly simple form of monotonicity with respect to arrival rates: the throughput of classi is increasing in the arrival rate of classi and decreasing in the arrival rate of classj forj≠i. Finally, we compare two simple control policies for this system under critical loading.