Monotonicity and supermodularity results for the Erlang loss system

For the Erlang loss system with s servers and offered load a, we show that: (i) the load carried by the last server is strictly increasing in a; (ii) the carried load of the whole system is strictly supermodular on {(s,a)|s=0,1,… and a>0}.     

Erlang loss bounds for OT–ICU systems

In hospitals, patients can be rejected at both the operating theater (OT) and the intensive care unit (ICU) due to limited ICU capacity. The corresponding ICU rejection probability is an important service factor for hospitals. Rejection of an ICU request may lead to health deterioration for patients, and for hospitals to costly actions and a loss of precious capacity when an operation is canceled. There is no simple expression available for this ICU rejection probability that takes the interaction with the OT into account. With c the ICU capacity (number of ICU beds), this paper proves and numerically illustrates a lower bound by an M|G|c|c system and an upper bound by an M|G|c-1|c-1 system, hence by simple Erlang loss expressions. The result is based on a product form modification for a special OT–ICU tandem formulation and proved by a technically complicated Markov reward comparison approach. The upper bound result is of particular practical interest for dimensioning an ICU to secure a prespecified service quality. The numerical results include a case study.     

Sharp and simple bounds for the Erlang delay and loss formulae

We prove some simple and sharp lower and upper bounds for the Erlang delay and loss formulae and for the number of servers that invert the Erlang delay and loss formulae. We also suggest simple and sharp approximations for the number of servers that invert the Erlang delay and loss formulae. We illustrate the importance of these bounds by using them to establish convexity proofs. We show that the probability that the M/M/s queue is empty is a decreasing and convex function of the traffic intensity. We also give a very short proof to show that the Erlang delay formula is convex in the traffic intensity when the number of servers is held constant. The complete proof of this classical result has never been published. We also give a very short proof to show that the Erlang delay formula is a convex function of the (positive integer) number of servers. One of our results is then used to get a sharp bound to the Flow Assignment Problem.     

Approximate analysis of non-stationary loss queues and networks of loss queues with general service time distributions

A Fixed Point Approximation (FPA) method has recently been suggested for non-stationary analysis of loss queues and networks of loss queues with Exponential service times. Deriving exact equations relating time-dependent mean numbers of busy servers to blocking probabilities, we generalize the FPA method to loss systems with general service time distributions. These equations are combined with associated formulae for stationary analysis of loss systems in steady state through a carried load to offered load transformation. The accuracy and speed of the generalized methods are illustrated through a wide set of examples.     

On bounds for bulk arrival queues

This paper gives a simple and effective approach pf deriving bounds for bulk arrival queues by making use of the bounds for single arrival queues. With this approach, upper bounds of mean actual/virtual waiting times and mean queue length at random epochs can be derived for the bulk arrival queues GI^X/G/1 and GI^X/G/c (lower bounds can be derived in a similar way). The merit of this approach is shown by comparing the bounds obtained with some existing results in the literature.     

Nonstationary analysis of the loss queue and of queueing networks of loss queues

We present an iterative scheme based on the fixed-point approximation method, for the numerical calculation of the time-dependent mean number of customers and blocking probability functions in a nonstationary queueing network with multi-rate loss queues. We first show how the proposed method can be used to analyze a single-class, multi-class, and multi-rate nonstationary loss queue. Subsequently, the proposed method is extended to the analysis of a nonstationary queueing network of multi-rate loss queues. Comparisons with exact and simulation results showed that the results are consistently close to the exact results and they are always within simulation confidence intervals.     

Monotonicity and bounds for convex stochastic control models

We consider a general convex stochastic control model. Our main interest concerns monotonicity results and bounds for the value functions and for optimal policies. In particular, we show how the value functions depend on the transition kernels and we present conditions for a lower bound of an optimal policy. Our approach is based on convex stochastic orderings of probability measures. We derive several interesting sufficient conditions of these ordering concepts, where we make also use of the Blackwell ordering. The structural results are illustrated by partially observed control models and Bayesian information models.     

Improved bounds for queues with delayed arrivals

Improved bounds are developed for a queue where arrivals are delayed by a fixed time. For moderate to heavy traffic, a simple improved upper bound is obtained which only uses the first two moments of the service time distribution. We show that our approach can be extended to obtain bounds for other types of delayed arrival queues. For very light traffic, asymptotically tight bounds can be obtained using more information about the service time distribution. While an improved upper bound can be obtained for light to moderate traffic it is not particularly easy to apply. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exponential bounds for queues with Markovian arrivals

Exponential bounds [queueb]e ^b are found for queues whose increments are described by Markov Additive Processes. This is done by application of maximal inequalities to exponential martingales for such processes. Through a thermodynamic approach the constant is shown to be the decay rate for an asymptotic lower bound for the queue length distribution. The class of arrival processes considered includes a wide variety of Markovian multiplexer models, and a general treatment of these is given, along with that of Markov modulated arrivals. Particular attention is paid to the calculation of the prefactor .     

Monotonicity properties in various retrial queues and their applications

We consider several multi-server retrial queueing models with exponential retrial times that arise in the literature of retrial queues. The effect of retrial rates on the behavior of the queue length process is investigated via sample path approach. We show that the number of customers in orbit and in the system as a whole are monotonically changed if the retrial rates in one system are bounded by the rates in second one. The monotonicity results are applied to show the convergence of generalized truncated systems that have been widely used for approximating the stationary queue length distribution in retrial queues. AMS subject classifications: Primary 60K25     

Perturbation bounds and truncations for a class of Markovian queues

We consider time-inhomogeneous Markovian queueing models with batch arrivals and group services. We study the mathematical expectation of the respective queue-length process and obtain the bounds on the rate of convergence and error of truncation of the process. Specific queueing models are shown as examples.     

Improved approximations for the Erlang loss model

Stochastic loss networks are often very effective models for studying the random dynamics of systems requiring simultaneous resource possession. Given a stochastic network and a multi-class customer workload, the classical Erlang model renders the stationary probability that a customer will be lost due to insufficient capacity for at least one required resource type. Recently a novel family of slice methods has been proposed by Jung et al. (Proceedings of ACM SIGMETRICS conference on measurement and modeling of computer systems, pp. 407–418, 2008) to approximate the stationary loss probabilities in the Erlang model, and has been shown to provide better performance than the classical Erlang fixed point approximation in many regimes of interest. In this paper, we propose some new methods for loss probability calculation. We propose a refinement of the 3-point slice method of Jung et al. (Proceedings of ACM SIGMETRICS conference on measurement and modeling of computer systems, pp. 407–418, 2008) which exhibits improved accuracy, especially when heavily loaded networks are considered, at comparable computational cost. Next we exploit the structure of the stationary distribution to propose randomized algorithms to approximate both the stationary distribution and the loss probabilities. Whereas our refined slice method is exact in a certain scaling regime and is therefore ideally suited to the asymptotic analysis of large networks, the latter algorithms borrow from volume computation methods for convex polytopes to provide approximations for the unscaled network with error bounds as a function of the computational costs.     

Towards an Erlang formula for multiclass networks

Consider a multiclass stochastic network with state-dependent service rates and arrival rates describing bandwidth-sharing mechanisms as well as admission control and/or load balancing schemes. Given Poisson arrival and exponential service requirements, the number of customers in the network evolves as a multi-dimensional birth-and-death process on a finite subset of ℕ ^k . We assume that the death (i.e., service) rates and the birth rates depending on the whole state of the system satisfy a local balance condition. This makes the resulting network a Whittle network, and the stochastic process describing the state of the network is reversible with an explicit stationary distribution that is in fact insensitive to the service time distribution. Given routing constraints, we are interested in the optimal performance of such networks. We first construct bounds for generic performance criteria that can be evaluated using recursive procedures, these bounds being attained in the case of a unique arrival process. We then study the case of several arrival processes, focusing in particular on the instance with admission control only. Building on convexity properties, we characterize the optimal policy, and give criteria on the service rates for which our bounds are again attained.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

Cones and error bounds for linear iterations

Consider an ordered Banach space with a cone of positive elementsK and a norm ∥·∥. Let [a,b] denote an order-interval; under mild conditions, ifx*∈[a,b] then $$||x * - \tfrac{1}{2}(a + b)|| \leqslant \tfrac{1}{2}||b - a||.$$ This inequality is used to generate error bounds in norm, which provide on-line exit criteria, for iterations of the type $$x_r = Ax_{r - 1} + a,A = A^ + + A^ - ,$$ whereA ⁺ andA ^? are bounded linear operators, withA ⁺ K ?K andA ^? K ? ?K. Under certain conditions, the error bounds have the form $$\begin{gathered} ||x * - x_r || \leqslant ||y_r ||,y_r = (A^ + - A^ - )y_{r - 1} , \hfill \\ ||x * - x_r || \leqslant \alpha ||\nabla x_r ||, \hfill \\ ||x * - \tfrac{1}{2}(x_r + x_{r - 1} )|| \leqslant \tfrac{1}{2}||\nabla x_r ||. \hfill \\ \end{gathered} $$ These bounds can be used on iterative methods which result from proper splittings of rectangular matrices. Specific applications with respect to certain polyhedral cones are given to the classical Jacobi and Gauss-Seidel splittings.     

Improved error bounds for near-minimax approximations

Givenf εC ⁽ⁿ⁺¹⁾[?1, 1], a polynomialp _n, of degree ≤n, is said to be near-minimax if (*) $$\left\| {f - p_n } \right\|_\infty = 2^{ - n} |f^{(n + 1)} (\xi )|/(n + 1)!,$$ for some ζ ε (?1,1). For three sets of near-minimax approximations, by considering the form of the error ∥f ?p _n∥_∞ in terms of divided differences, it is shown that better upper and lower bounds can be found than those given by (*).