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.     

Some properties of the delay probability inM/M/s/s +c systems

We look at an extension of the steady state delay probability inM/M/s/s + c systems to nonintegral number of serverss and queue capacityc, which we call GED function. We show that this function is increasing and concave in the queue capacity. We find that if c 1, the reciprocal of the GED function is convex in the traffic intensity and the GED function is increasing in the traffic intensity if is below some ^* _s,c, and decreasing if is greater than ^* _s,c, Moreover, ^* _s,c is increasing in the number of servers and, fors 1, ^* _i,c=1 p^* _s,c < 2.Research supported by Grant BD/645/90-RM from Junta Nacional de Investigação Científica e Tecnológica.On leave from: Departamento de Matemätica, Instituto Superior Técnico, Av. Rovisco Pais, 1096 Lisboa Codex, Portugal.     

Approximation of the viability kernel

We study recursive inclusionsx ⁿ⁺¹ G(x ⁿ ). For instance, such systems appear for discrete finite-difference inclusionsx ⁿ⁺¹ G (x ⁿ) whereG :=1+F. The discrete viability kernel ofG , i.e., the largest discrete viability domain, can be an internal approximation of the viability kernel ofK underF. We study discrete and finite dynamical systems. In the Lipschitz case we get a generalization to differential inclusions of the Euler and Runge-Kutta methods. We prove first that the viability kernel ofK underF can be approached by a sequence of discrete viability kernels associated withx ⁿ⁺¹ (xⁿ) where (x) =x + F(x) + (ML/2) ². Secondly, we show that it can be approached by finite viability kernels associated withx _h ⁿ⁺¹ ( (x _h ⁿ⁺¹ ) +(h) X _h .     

The broken sample problem

Suppose that (X_i,Y_i),i=1,2, ... ,n, are iid. random vectors with uniform marginals and a certain joint distribution F, where is a parameter with =_o corresponds to the independence case. However, the Xs and Ys are observed separately so that the pairing information is missing. Can be consistently estimated? This is an extension of a problem considered in (1980) which focused on the bivariate normal distribution with being the correlation. In this paper we show that consistent discrimination between two distinct parameter values ₁ and ₂ is impossible if the density f of F is square integrable and the second largest singular value of the linear operator is strictly less than 1 for =₁ and ₂. We also consider this result from the perspective of a bivariate empirical process which contains information equivalent to that of the broken sample.Dedicated to Professor Xiru Chen on His 70th BirthdayMathematics Subject Classification (2000): primary: 60F99, 62F12Research supported by NSFC Grant 201471000 and the NUS Grant R-155-000-040-112.Research supported by the Texas Advanced Research Program.     

Some inequalities about the covering radius of Reed-Muller codes

Let R(r, m) be the rth order Reed-Muller code of length 2 ^m , and let (r, m) be its covering radius. We prove that if 2 k m - r - 1, then (r + k, m + k) (r, m + 2(k - 1). We also prove that if m - r 4, 2 k m - r - 1, and R(r, m) has a coset with minimal weight (r, m) which does not contain any vector of weight (r, m) + 2, then (r + k, m + k) (r, m) + 2k(. These inequalities improve repeated use of the known result (r + 1, m + 1) (r, m).This work was supported by a grant from the Research Council of Wright State University.     

Deformations of homogeneous foliations

Let X be a simply connected compact homogeneous Kähler manifold, b₂(X) = 1, and let E be a homogeneous vector foliation on X. A complete effective family of deformations of a holomorphic vector foliation E , this family parametrized by a neighborhood of zero in H¹(X,o End ), is constructed.Translated from Matematicheskie Zametki, Vol. 3, No. 6, pp. 651–656, June, 1968.The author is indebted to A. L. Onishchik for his assistance and interest in the completion of the paper.     

A Load-Balanced Network with Two Servers

A load-balanced network with two queues Q ₁ and Q ₂ is considered. Each queue receives a Poisson stream of customers at rate _i , i=1,2. In addition, a Poisson stream of rate arrives to the system; the customers from this stream join the shorter of two queues. After being served in the ith queue, i=1,2, customers leave the system with probability 1–p _i ^*, join the jth queue with probability p(i,j), j=1,2, and choose the shortest of two queues with probability p(i,{1,2}). We establish necessary and sufficient conditions for stability of the system.     

Cyclic Bernoulli polling

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to move from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilityp _i , or moves on to the next queue (w.p. 1 —p _i ) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all parameterized cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thep _i 's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {p _i } _i ^N =1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalp _i 's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp ₁=1 is the best strategy, and derive conditions under which it is optimal to havep ₁ < 1.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant Number 3321190.     

Relationship between the Hadamard Theorem on Three Disks and Certain Problems of Polynomial Approximation of Analytic Functions

By using the classical Hadamard theorem, we obtain an exact (in a certain sense) inequality for the best polynomial approximations of an analytic function f(z) from the Hardy space H _p, p 1, in disks of radii , ₁, and ₂, 0 < ₁ < < ₂ < 1.     

A tandem Jackson network with feedback to the first node

AnN-node tandem queueing network with Bernoulli feedback to the end of the queue of thefirst node is considered. We first revisit the single-nodeM/G/1 queue with Bernoulli feedback, and derive a formula forEL(n), the expected queue length seen by a customer at his nth feedback. We show that, asn becomes large,EL(n) tends to /(l ), being the effective traffic intensity. We then treat the entire queueing network and calculate the mean value ofS, the total sojourn time of a customer in theN-node system. Based on these results we study the problem ofoptimally ordering the nodes so as to minimize ES. We show that this is a special case of a general sequencing problem and derive sufficient conditions for an optimal ordering. A few extensions of the serial queueing model are also analyzed. We conclude with an appendix in which we derive an explicit formula for the correlation coefficient between the number of customers seen by an arbitrary arrival to anM/G/1 queue, and the number of customers he leaves behind him upon departure. For theM/M/1 queue this coefficient simply equals the traffic intensity .     

A tandem of discrete-time queues with arrivals and departures at each stage

A discrete-time system of a tandem of queues with exogenous arrivals and departures at each stage is considered. A customer leaving queuek–1 departs the system with probability 1– ^[k] and continues to queuek with probability ^[k] . Exogenous arrivals to each stage are i.i.d. at each time slot. An approximate analysis of the occupancy and busy-period distributions of each stage based on a General Busy-period with batches and Memoryless (geometric) Idle period renewal Process (GBMIP) provides improved performance over two-state Markov approximations and gives exact results when there are no interstage departures.This research was supported in part by NSF grant NCR-8708282.     

Some observations on the distribution of values of continued fractions

Summary There have been many studies of the values taken on by continued fractionsK(a _n /1) when its elements are all in a prescribed setE. The set of all values taken on is the limit regionV(E). It has been conjectured that the values inV(E), are taken on with varying probabilities even when the elementsa _n are uniformly distributed overE. In this article, we present the first concrete evidence that this is indeed so. We consider two types of element regions: (A)E is an interval on the real axis. Our best results are for intervals [–(1–), (1–)], 0 <1/2. (B)E is a disk in the complex plane defined byE={z:|z|(1–)}., 0<1/2.     

Balanced ternary designs with block size three,any Λ and anyR

A balanced ternary design onV elements is a collection ofB blocks (which are multisets) of sizeK, such that each element occurs 0, 1 or 2 times per block andR times altogether, and such that each unordered pair of distinct elements occurs times. (For example, in the blockxxyyz, the pairxy is said to occur four times and the pairsxz, yz twice each.) It is straightforward to show that each element has to occur singly in a constant number of blocks, say ₁, and so each element also occurs twice in a constant number of blocks, say ₂, whereR= ₁+2 ₂. If ₂=0 the design is a balanced incomplete block design (binary design), so we assume ₂>0, andK<2V (corresponding to incompleteness in the binary case). Necessarily >1 if ₂>0 (andK>2).In 1980 and 1982 the author gave necessary and sufficient conditions for the existence of balanced ternary designs withK=3, =2 and ₂=1, 2 or 3. In this paper work on the existence of balanced ternary designs with block size three is concluded, in that necessary and sufficient conditions for the existence of a balanced ternary design withK=3, any >1 and any ₂ are given.     

Preprojective components of wild tilted algebras

If A is a finite dimensional, connected, hereditary wild k-algebra, k algebraically closed and T a tilting module without preinjective direct summands, then the preprojective componentP of the tilted algebra B=End_A (T) is the preprojective component of a concealed wild factoralgebra C of B. Our first result is, that the growth number (C) of C is always bigger or equal to the growth number (A). Moreover the growth number (C) can be arbitrarily large; more precise: if A has at least 3 simple modules and N is any positive integer, then there exists a natural number n>N such that C is the Kronecker-algebraK _n, that is the path-algebra of the quiver (n arrows).     

Spectral properties of cosine operator functions

LetA be the generator of a cosine functionC _t ,t R in a Banach spaceX; we shall connect the existence and uniqueness of aT-periodic mild solution of the equationu = Au + f with the spectral property 1 (C _T ) and, in caseX is a Hilbert space, also with spectral properties ofA. This research was supported in part by DAAD, West Germany.     

Identification of the Parameters of a Multivariate Normal Vector by the Distribution of the Maximum

This paper continues the work started by Basu and Ghosh (J. Mult. Anal. (1978), 8, 413–429), by Gilliland and Hannan (J. Amer. Stat. Assoc. (1980), 75, No. 371, 651–654), and then continued on by Mukherjea and Stephens (Prob. Theory and Rel. Fields (1990), 84, 289–296), and Elnaggar and Mukherjea (J. Stat. Planning and Inference (1990), 78, 23–37). Let (X₁, X₂,..., X_n) be a multivariate normal vector with zero means, a common correlation and variances ² ₁, ² ₂,..., ² _n such that the parameters , ² ₁, ² ₂,..., s² _n are unknown, but the distribution of the max{X_i: 1in} (or equivalently, the distribution of the min{X_i: 1in}) is known. The problem is whether the parameters are identifiable and then how to determine the (unknown) parameters in terms of the distribution of the maximum (or its density). Here, we solve this problem for general n. Earlier, this problem was considered only for n3. Identifiability problems in related contexts were considered earlier by numerous authors including: T. W. Anderson and S. G. Ghurye, A. A. Tsiatis, H. A. David, S. M. Berman, A. Nadas, and many others. We also consider here the case where the X_i's have a common covariance instead of a common correlation.     

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.     

Second-order properties of the loss probability inM/M/s/s +c systems

The Erlang loss function, which gives the steady state loss probability in anM/M/s/s system, has been extensively studied in the literature. In this paper, we look at the similar loss probability inM/M/s/s + c systems and an extension of it to nonintegral number of servers and queue capacity. We study its monotonicity properties. We show that the loss probability is convex in the queue capacity, and that it is convex in the traffic intensity if is below some ^* and concave if is greater that ^*, for a broad range of number of servers and queue capacities. We prove that the one-server loss system is the onlyM/M/s/s +c system for which the loss probability is concave in the traffic intensity in all its range.Research supported by Grant BD/645/90-RM from Junta Nacional de Investigação Científica e Tecnológica.On leave from: Departamento de Matemática, Instituto Superior Técnico, Av. Rovisco Pais, 1096 Lisboa Codex, Portugal.     

Lower types of δ-subharmonic functions of fractional order

It is proved that the lower types of functions T(r, u) and N(r, u)=N(r, u₁)+N(z, u₂) relative to the proximate order (r) of a function u=U₁–u₂ of fractional order -subharmonic in ^m, m>- 2, coincide, that is, are simultaneously minimal or mean. In the case of an arbitrary proximate order (r), the assertion is, in general, false.Translated from Ukrayins'kyy Matematychnyy Zhurnal, Vol. 44, No. 9, pp. 1280–1284, September, 1992.     

A characterization of plane Lorentz transformations

Denote (x_i,y_i=ct_i), i=1,2, by X_i and (x₂–x₁)²–(y₂–y₁)² by F(X₁,X₂). Then our result is the following: Given a fixed real number 0 and given a bijection of M=IR² such that F(X₁,X₂) = iff F(X _in1 ^su , _in2 ^su ) =p for all X₁, X₂ M. Then must be a Lorentz transformation (time reversal and inhomogeneity included).