Analysis of a finite-capacity M/G/1 queue with a resume level

In order to model the buffer pool behavior in a data communication component, an M/G/1/K queue where input is shut down when the queue size (number of messages) attains K until it decreases to a specified level is analyzed. By use of semi-Markov process approach, the queue length distribution at an arbitrary time is found, and the resultant performance measures (utilization, loss probability, and mean response time) are computed.     

Approximations for the waiting time distribution of the M/G/c queue

For the M/G/c queue we present an approximate analysis of the waiting time distribution. The result is given in the form of the defective renewal equation. This integral equation can be numerically solved by a simple recursion procedure. Also, asymptotic results for the waiting times are presented. Numerical results indicate that the approximations are sufficiently accurate for practical purposes.     

On the number of customers served in the M/G/1 retrial queue: first moments and maximum entropy approach

In this paper we present general results on the number of customers, I, served during the busy period in an M/G/1 retrial system. Its analysis in terms of Laplace transforms has been previously discussed in the literature. However, this solution presents important limitations in practice; in particular, the moments of I cannot be obtained by direct differentiation. We propose a direct method of computation for the second moment of I and also for the probability of k,k⩽4, customers being served in a busy period. Then, the maximum entropy principle approach is used to estimate the true distribution of I according to the available information.Scope and purposeWe consider an M/G/1 queue with retrials. Retrial queueing systems are characterized by the fact that, an arriving customer who finds the server busy is obliged to leave the service area and return later to repeat his request after some random time. We deal with I, the number of customers served during the busy period of a retrial queue, and obtain closed expressions for its main characteristics, which will be employed in order to estimate the true distribution of this random variable.     

The Geometry of M/D/1 Queues and Large Deviation

Since an M/D/1 queue is represented by a Markov chain, we can consider the set of all the M/D/1 queues as a subset of Markov chains. A geometric structure is induced from the geometric structure of the set of Markov chains, which forms an exponential family. In this paper, we show that in the large deviation of the tail probability of the queue length of an M/D/1, the rate function and a twisted Markov chain, etc., are represented in terms of the geometry. Moreover, in the importance sampling (IS) simulation for the M/D/1 queue, we elucidate the geometric relation between the underlying distribution and a simulation distribution, and evaluate the variance of an IS estimate by geometric quantities.     

An approximate transient analysis of the M(t)/M/1 queue

An approach, based on recent work by Stern [56], is described for obtaining the approximate transient behavior of both the M/M/1 and M(t)/M/1 queues, where the notation M(t) indicates an exponential arrival process with time-varying parameter λ(t). The basic technique employs an M/M/1K approximation to the M/M/1 queue to obtain a spectral representation of the time-dependent behavior for which the eigen values and eigenvectors are real.Following a general survey of transient analysis which has already been accomplished, Stern's M/M/1/K approximation technique is examined to determine how best to select a value for K which will yield both accurate and computationally efficient results. It is then shown how the approximation technique can be extended to analyze the M(t)/M/1 queue where we assume that the M(t) arrival process can be approximated by a discretely time-varying Poisson process.An approximate expression for the departure process of the M/M/1 queue is also proposed which implies that, for an M(t)/M/1 queue whose arrival process is discretely time-varying, the departure process can be approximated as discretely time-varying too (albeit with a different time-varying parameter).In all cases, the techniques and approximations are examined by comparison with exact analytic results, simulation or alternative discrete-time approaches.     

On a single server queue with two-stage heterogeneous service and deterministic server vacations

We analyse a single server queue with Poisson arrivals, two stages of heterogeneous service with different general (arbitrary) service time distributions and binomial schedule server vacations with deterministic (constant) vacation periods. After first-stage service the server must provide the second stage service. However, after the second stage service, he may take a vacation or may decide to stay on in the system. For convenience, we designate our model as M/G ₁, G ₂/D/1 queue. We obtain steady state probability generating function of the queue length for various states of the server. Results for some particular cases of interest such as M/E_{k 1} , E_{k 2} /D/1, M/M ₁, M ₂/D/1, M/E _k /D/1 and M/G ₁, G ₂/1 have been obtained from the main results and some known results including M/E_k /1 and M/G/1 have been derived as particular cases of our particular cases.     

Deciding k-colorability in expected polynomial time

For every fixed k?3 we describe an algorithm for deciding k-colorability, whose expected running time in polynomial in the probability space G(n,p) of random graphs as long as the edge probability p=p(n) satisfies p(n)?C/n, with C=C(k) being a sufficiently large constant.     

Transforming Curves on Surfaces

We describe an optimal algorithm to decide if one closed curve on a triangulated 2-manifold can be continuously transformed to another, i.e., if they are homotopic. SupposeC₁andC₂are two closed curves on a surfaceMof genusg. Further, supposeTis a triangulation ofMof sizensuch thatC₁andC₂are represented as edge–vertex sequences of lengthsk₁andk₂inT, respectively. Then, our algorithm decides ifC₁andC₂are homotopic inO(n+k₁+k₂) time and space, providedg≠2 ifMis orientable, andg≠3, 4 ifMis nonorientable. This implies as well an optimal algorithm to decide if a closed curve on a surface can be continuously contracted to a point. Except for three low genus cases, our algorithm completes an investigation into the computational complexity of two classical problems for surfaces posed by the mathematician Max Dehn at the beginning of this century. The novelty of our approach is in the application of methods from modern combinatorial group theory.     

Distribution of busy period for the bulk-service queueing system Ek/Ma,b/1

Using the Erlangian technique the busy-period equations for the single-server bulkservice system E_k/M^a,b/1. are solved to obtain the Laplace transform of the probability density function (pdf) of the busy period. The Laplace transform is expressed in terms of an easily computable real root of the characteristic equation. Expressions for the mean and variance of the busy-period distribution are given. Explicit results for the pdf of the busy period are obtained for the special systems M/M^a,b/1 and E_k/M^a,a/1.     

Steady state analysis of the GI/M/1/N queue with a variant of multiple working vacations

This paper studies the GI/M/1/N queue with a variant of multiple working vacations, where the server leaves for a working vacation as soon as the system becomes empty. The server takes at most H consecutive working vacations if the system remains empty after the end of a working vacation. Employing the supplementary variable and embedded Markov chain methods, we obtain the queue length distribution at different time epochs. Based on the various system length distribution, the probability of blocking, mean waiting times and mean system lengths have been derived. Finally, numerical results are discussed.     

Bandwidth packing

We model a server that allocates varying amounts of bandwidth to “customers” during service. Customers could be computer jobs with demands for storage bandwidth or they could be calls with demands for transmission bandwidth on a network link. Service times are constants, each normalized to 1 time unit, and the system operates in discrete time, with packing (scheduling) decisions made only at integer times. Demands for bandwidths are for fractions of the total available and are limited to the discrete set {1/k, 2/k, …, 1} wherek is a given parameter. More than one customer can be served at a time, but the total bandwidth allocated to the customers in service must be at most the total available. Customers arrive ink flows and join a queue. Thejth flow has rate λ _j and contains just those customers with bandwidth demandsj/k. We study the performance of the two packing algorithms First Fit and Best Fit, both allocating bandwidth by a greedy rule, the first scanning the queue in arrival order and the second scanning the queue in decreasing order of bandwidth demand. We determine necessary and sufficient conditions for stability of the system under the two packing rules. The average total bandwidth demand of the arrivals in a time slot must be less than 1 for stability under any packing rule, i.e., the condition $$\rho {\text{ : = }}\sum\limits_i {\lambda i\left( {i/k} \right)} {\text{< 1}}$$ must hold. We prove that if the arrival rates λ₁, …, λ _k?1 are symmetric, i.e., λ _i =λ _k?i for alli, 1 ≤i ≤k ? 1, theρ<1 is also sufficient for stability under both rules. Our Best Fit result strengthens an earlier result confined to Poisson flows and equal rates λ₁=…=λ _{k ? 1}, and does so using a far simper proof. Our First Fit result is completely new. The work here extends earlier results on bandwidth packing in multimedia communication systems, on storage allocation in computer systems, and on message transmission along slotted communication channels. It is not surprising thatρ<1 is sufficient under Best Fit, since in a congested system, Best Fit tends to serve two complementary (matched) customers in each time slot, with bandwidth demands beingi/k and (k ? i)/k for somei, 1 ≤i ≤k ? 1. It is not so obvious, however, thatρ<1 is also sufficient under First Fit. Interestingly, when the system becomes congested, First Fit exhibits a “self-organizing” property whereby an ordering of the queue by time of arrival becomes approximately the same as an ordering by decreasing bandwidth demand.     

Determination of a general economic location constant by monte carlo simulation

The problem of estimating the number of markets (or plants) to serve a set of sources in a given geographical area was considered. Markets were located so as to minimize total assembly cost which was considered a linear function of the weighted Euclidean distances between sources and markets. The following predictive function C_m was proposed for estimating the minimum total assembly cost for a given number of markets: $\text{C}{}_{\mathrm{m}}\text{= C}{}_1\text{?(}\text{m?1}\text{m}\text{)}{}^{\mathrm{k}}\text{(}\text{M}\text{M ? 1}\text{)}{}^{\mathrm{k}}\text{(C}{}_1\text{? C}{}_{\mathrm{M}}\text{),m = 1, 2, 3, …, M}$ where m = number of markets being located. M = maximum number of potential market sites. C₁ = minimum assembly cost when only one market is located. C_M = minimum assembly cost when all M markets are located. k = an undetermined constant which specifies the shape of the function.The validity of the C_m function and the range of the k constant were determined by computer Monte Carlo experimentation. The constant k, to a sufficient degree of approximation and ordinary use, was found independent of the number of sources and their distribution. A general economic location co     

Near-optimal bounded-degree spanning trees

Random costsC(i, j) are assigned to the arcs of a complete directed graph onn labeled vertices. Given the cost matrixC _n =(C(i, j)), letT* _k =T* _k (C _n ) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal tok. Since it is NP-hard to findT* _k , we instead consider an efficient algorithm that finds a near-optimal spanning treeT _k ^a . If the edge costs are independent, with a common exponential(I) distribution, then, asn → ∞, $$E(Cost(T_k^a {\text{)) = }}E(Cost(T_k^* {\text{)) + }}o\left( 1 \right).$$ Upper and lower bounds forE(Cost(T* _k )) are also obtained fork≥2.     

The M/G/1 processor-sharing queue with disasters

n this paper, the M/G/1 processor-sharing queue with disasters is given a detailed analysis by means of extending the supplementary variable method. The transient and steady-state distributions of the queue length are expressed as a simple and computable form, the Laplace-Stieltjes transform of the sojourn time is derived, and the Laplace transform of the busy period and its mean are obtained. Also, the approach developed in this paper is shown to be able to study more complicated M/G/1 processor-sharing models.     

Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.     

Profit analysis of the M/M/R machine repair problem with balking,reneging, and standby switching failures

We study the warm-standby M/M/R machine repair problem where standby machines have switching failure probability q  , and failed machines balk (do not enter) with a constant probability (1-b)$(1-b)$ and renege (leave the queue after entering) according to a negative exponential distribution. Failure and repair times of the machines are assumed to follow a negative exponential distribution. A profit model is developed in order to determine the optimal values of the number of spares and the number of repairmen simultaneously, while maintaining a minimum specified level of system availability. We use the two methods direct search method and steepest descent method to find the global maximum value until the availability, balking and reneging constraints are satisfied. Numerical results are provided in which various system performance measures are calculated under optimal operating conditions. Sensitivity analysis is also investigated.     

Analysis of the discrete-time Geo/G/1 working vacation queue and its application to network scheduling

In this paper we present an exact steady-state analysis of a discrete-time Geo/G/1 queueing system with working vacations, where the server can keep on working, but at a slower speed during the vacation period. The transition probability matrix describing this queuing model can be seen as an M/G/1-type matrix form. This allows us to derive the probability generating function (PGF) of the stationary queue length at the departure epochs by the M/G/1-type matrix analytic approach. To understand the stationary queue length better, by applying the stochastic decomposition theory of the standard M/G/1 queue with general vacations, another equivalent expression for the PGF is derived. We also show the different cases of the customer waiting to obtain the PGF of the waiting time, and the normal busy period and busy cycle analysis is provided. Finally, we discuss various performance measures and numerical results, and an application to network scheduling in the wavelength division-multiplexed (WDM) system illustrates the benefit of this model in real problems.     

On exact computational analysis of distributions of numbers in systems for M/G/1/N + 1 and GI/M/1/N + 1 queues using roots

In this paper, we obtain the distribution of number in system and other measures of efficiency for the M/G/1/N + 1 queuing system in terms of the roots of the associated characteristic equation (CE). Results for the GI/M/1/N + 1 queuing system have also been obtained from those of M/G/1/N + 1. Numerical results in the form of tables and graphs have been presented for a variety of service-(interarrival-) time distributions, e.g. Erlang (E_k), generalized Erlang (GE_k) and hyperexponential (HE_k).     

Information theoretic approximations for theM/G/1 retrial queue

In this paper we present information theoretic approximations for theM/G/1 queue with retrials. Various approximations for this model are obtained according to the available information about the service time probability density and the steady-state distribution of the system state. The results are well-suited for numerical computation.     

The analysis of the M/M/1 queue with two vacation policies (M/M/1/SWV+MV)

We consider an M/M/1 queue with two vacation policies which comprise single working vacation and multiple vacations, denoted by M/M/1/SMV+MV. Using two methods (called R-matrix method and G-matrix method), we obtain the stationary distribution of queue length (including the customer being in service) and make further analysis on the stationary numbers of customers in the working vacation and vacation period, respectively. The stochastic decomposition results of stationary queue length and the sojourn time of a customer are also derived. Meanwhile, we show that a simple and direct method of decomposition developed in Liu et al. [Stochastic decompositions in the M/M/1 queue with working vacations, Oper. Res. Lett. 35 (2007), pp. 595–600] is also applicable to our model. Furthermore, busy period is analysed by the limiting theorem of alternative renewal process. Finally, some boundary properties and numerical analysis on performance measures are presented.