A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

A Weighted Goodness-of-Fit Test for GARCH(1,1) Specification

Suppose that (j) is the lag-j autocorrelation of the squared residuals computed from a realization of length n under the assumption that the observations follow a GARCH(1,1) model. We study the asymptotic distribution of the statistics of the form , where the _j are nonnegative summable weights and the matrix , can be estimated from the data. We show that, under weak assumptions on model errors, the statistic Q _n converges in distribution to , where the N _i are iid standard normal. We discuss choices of the weights _j for which the distribution of Q is tabulated. Our results lead to and provide a rigorous justification for Portmanteau goodness-of-fit tests for GARCH(1,1) specification.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

On the estimation of ordered means of two exponential populations

Let random samples of equal sizes be drawn from two exponential distributions with ordered means _i . The maximum likelihood estimator _i ^* of _i is shown to have a smaller mean square error than that of the usual estimator X_i, for each i=1,2. The asymptotic efficiency of _i ^* relative to X_i has also been found.     

On the Gap between the First Eigenvalues of the Laplacian on Functions and p-Forms

We study the first positive eigenvalue ^(p) ₁(g) of the Laplacian on p-forms for a connected oriented closed Riemannianmanifold (M, g) of dimension m. We show that for 2 p m – 2 a connected oriented closed manifold M admits three metrics g _i (i = 1, 2, 3) such that ^(p) ₁(g ₁)> ⁽⁰⁾ ₁(g ₁),^(p) ₁(g ₂) < ⁽⁰⁾ ₁(g ₂) and^(p) ₁(g ₃)= ⁽⁰⁾ ₁(g ₃).Furthermore, if (M, g) admits a nontrivial parallel p-form,then ^(p) ₁ ⁽⁰⁾ ₁ always holds.     

An approximate analysis for a class of assembly-like queues

Assembly-like queues model assembly operations where separate input processes deliver different types of component (customer) and the service station assembles (serves) these input requests only when the correct mix of components (customers) is present at the input. In this work, we develop an effective approximate analytical solution for an assembly-like queueing system withN(N 2) classes of customers formingN independent Poisson arrival streams with rates {_i=1,...,N} The arrival of a class of customers is turned off whenever the number of customers of that class in the system exceeds the number for any of the other classes by a certain amount. The approximation is based on the decomposition of the originalN input stream stage into a cascade ofN-1 two-input stream stages. This allows one to refer to the theory of paired customer systems as a foundation of the analysis, and makes the problem computationally tractable. Performance measures such as server utilization, throughput, average delays, etc., can then be easily computed. For illustrative purposes, the theory and techniques presented are applied to the approximate analysis of a system withN = 3. Numerical examples show that the approximation is very accurate over a wide range of parameters of interest.     

A critically loaded multiclass Erlang loss system

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 requireM _j 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 toM _j . 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 toM _j , 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 forji. Finally, we compare two simple control policies for this system under critical loading.     

A note on products of Relative Difference Sets

Relative Difference Sets with the parameters k = n have been constructed many ways (see (Davis, forthcoming; Elliot and Butson 1966; and Jungnickel 1982)). This paper proves a result on building new RDS by taking products of others (much like (Dillon 1985)), and this is applied to several new examples (primarily involving (p ⁱ, p ^j, p ⁱ, p ^i–j)).     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

Über Mittelwerte aus Potenzproduktsummen

Using symmetric forms A(n)=number of terms of the sum,a >0,k _i0,i=1,...,n) the meansm _{k 1},...,k_p:=(M_{k 1},...,k_p1/(k₁+...+k_p)(k₁+...+k_p0) are formed and investigated as to monotonicity under the hypothesis that the exponentsk ₁,...,k _p are certain linear functions of only one parameterk(k _i = _i k+ ₁, _i >0, ₁+... _p =0). (The means , e. g., are increasing ifk is increasing.) The proofs are elementary and use the known method of positive logarithmically convex (or concave) sequences and certain generalizations of Muirhead's theorem.     

Independence of Likelihood Ratio Criteria for Homogeneity of Several Populations

Let _i be an i-tb population with a probability density function f(· | _i ) with one dimensional unknown parameter _i = 1, 2, ... , k. Let n _i sample be drawn from each _i . The likelihood ratio criteria _j|(j–1) for testing hypothesis that the first j parameters are equal against alternative hypothesis that the first (j – 1) parameters are equal and the j-th parameter is different with the previous ones are defined, j = 2, 3, ... , k. The paper shows the asymptotic independence of _j|(j–1)'s up to the order 1/n under a hypothesis of equality of k parameters, where n is a number of total samples.     

Divisible designs and groups

We study (s, k, ₁, ₂)-translation divisible designs with ₁0 in the singular and semi-regular case. Precisely, we describe singular (s, k, ₁, ₂)-TDD's by quasi-partitions of suitable quotient groups or subgroups of their translation groups. For semi-regular (s, k, ₁, ₂)-TDD's (and, more general, for the case ₂>₁) we prove that their translation groups are either Frobenius groups or p-groups of exponent p. Some examples are given for the singular, semi-regular and regular case.     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

On graphical partitions

An integer partition {₁,₂,..., _v } is said to be graphical if there exists a graph with degree sequence _i . We give some results corcerning the problem of deciding whether or not almost all partitions of even integer are non-graphical. We also give asymptotic estimates for the number of partitions with given rank.     

Non-parametric Estimation for the M/G/∞ Queue

Given an M/G/ queue with input rate and service-time distribution G, we consider the problem of estimating and G from data on the queue-length process Q = (Q_t). Our motivation is to study departures of G from exponentiality, following recent work of Bingham and Dunham (1997, Ann. Inst. Statist. Math., 49, 667–679).     

Departures from queues with changeover times

We consider the M/M ^ij /1 queue as a model of queues with changeover times, i.e., the service is exponential with parameter _ij depending on the previous job type (i) and the current job type (j). It is shown that the departure process is renewal and Poisson iff _ij = (constant). In this case, types of departures are dependent renewal processes. Crosscovariance and crosscorrelations are given.     

Approximate computation of the positive eigenvalue of a positive operator with a nonlinear occurrence of a parameter

A method is indicated for the approximate determination of the positive eigenvalue of the problem x–Qx=0, >0, xK, x0, whereK is a cone in Banach space and Q is an operator-valued function positive relative toK.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 37–39, 1976.     

Continuous Singularity of the Weak Limit of Convolution Powers of a Discrete Probability Measure on 2 × 2 Stochastic Matrices

Let be a probability measure on n 2 × 2 stochastic matrices, n an arbitrary positive integer, and = (w) lim _n ⁿ , such that the support of consists of 2 × 2 stochastic matrices of rank one, and as such, can be regarded as a probability measure on [0, 1]. We present simple sufficient conditions for to be continuous singular w.r.t. the Lebesgue measure on [0, 1]. We also determine , given .     

All Lambda-Designs With λ = 2 p are Type-1

A-design is a family B ₁,B ₂,...,B _v of subsets of X={1, 2,..., v} such that B _i B _j = for all i jand not all B _i are of the same size. Ryser's andWoodall's -design conjecture states thateach -design can be obtained from a symmetricblock design by a certain complementation procedure. Our mainresult is that the conjecture is true when is twice a prime number.     

The birth and death processes with zero as their absorbing barrier

LetE=(0, 1,...), Q ^b=(q_ij), i, j=0, 1, ..., whereq _{i, i–1}=a_i, q_{i, i+1}=b_i, q_ii=–(a_i+b_i), q_ij=0, when|i–j|>1. a ₀=0, b₀=b>0, a_i, b_i>0 (i>0). Lettingb=0 inQ ^b, we get the matrixQ ⁰.The time homogeneous Markov processX ^b ={x ^b (t,w), 0t< ^b (w)} (X ⁰={x⁰(t,w), 0t<⁰(w)}), withQ ^b (Q ⁰, respectively) as its density matrix and withE as its state space, is calledQ ^b (Q ⁰, respectively) process in this paper.Q ^b andQ ⁰ processes are all called the birth and death processes, with zero being the reflecting barrier ofQ ^b processes, the absorbing barrier ofQ ⁰ processes.AllQ ^b processes have been constructed by both probability and analytical methods (Wang [2], Yang [1]). In this paper, theQ ⁰ processes are imbedded intoQ ^b processes and all theQ ⁰ processes are directly constructed from theQ ^b processes. The main results are:Letb>0 be arbitrarily fixed, then there is a one to one correspondence between theQ ⁰ processes and theQ ^b processes (in the sense of transition probability).TheQ ⁰ process is unique iffR ^*=. SupposingR<, then:IfX ⁰={x⁰(t,w), 0t<⁰(w)} is a non-minimalQ ⁰ process, then its eigensequence (p, q, r _n, n–1) satisfies § 4(7).Conversely, let a non-negative number sequence (p, q, r _n, n–1) satisfying § 4(7) be arbitrarily given, then there exists a unique non-minimalQ ⁰ processX ⁰ with eigensequence (p, q, r _n, n–1). The Laplace transform of the transition probability (p _ij ⁰ (t)) ofX ⁰ is determined by § 4(15). X ⁰ is honest iffr _–1=0.X ⁰ satisfies the forward equation iffp=0.