Prediction in Markovian bulk arrival queues

This paper deals with the statistical analysis of bulk arrival queues from a Bayesian point of view. The focus is on prediction of the usual measures of performance of the system in equilibrium. Posterior predictive distribution of the number of customers in the system is obtained through its probability generating function. Posterior distribution of the waiting time, in the queue and in the system, of the first customer of an arriving group is expressed in terms of their Laplace and Laplace–Stieltjes transform. Discussion of numerical inversion of these transforms is addressed.     

Asymptotic Expansions for the Congestion Period for the M/M/∞ Queue

We consider the M/M/ queue with arrival rate , service rate and traffic intensity =/. We analyze the first passage distribution of the time the number of customers N(t) reaches the level c, starting from N(0)=m>c. If m=c+1 we refer to this time period as the congestion period above the level c. We give detailed asymptotic expansions for the distribution of this first passage time for , various ranges of m and c, and several different time scales. Numerical studies back up the asymptotic results.     

Some Asymptotic Results for the M/M/∞ Queue with Ranked Servers

We consider an M/M/ model with m primary servers and infinitely many secondary ones. An arriving customer takes a primary server, if one is available. We derive integral representations for the joint steady state distribution of the number of occupied primary and secondary servers. Letting =/ be the ratio of arrival and service rates (all servers work at rate ), we study the joint distribution asymptotically for . We consider both m=O(1) and m scaled to be of the same order as . We also give results for the marginal distribution of the number of secondary servers that are occupied.     

M/G/∞ with alternating renewal breakdowns

We consider an M/G/ queue where the service station is subject to occasional interruptions which form an alternating renewal process ofup anddown periods. We show that under some natural conditions the random measure process associated with the residual service times of the customers is regenerative in the strict sense, and study its steady state characteristics. In particular we show that the steady state distribution of this random measure is a convolution of two distributions of (independent) random measures, one of which is associated with a standard M/G/ queue.     

Settling time bounds forM/G/1 queues

This paper addresses the question of how long it takes for anM/G/1 queue, starting empty, to approach steady state. A coupling technique is used to derive bounds on the variation distance between the distribution of number in the system at timet and its stationary distribution. The bounds are valid for allt. This research was supported in part by a grant from the AT&T Foundation and NSF grant DCR-8351757.     

Stability and queueing time analysis of a reader-writer queue with alternating exhaustive priorities

This paper considers a reader-writer queue with alternating exhaustive priorities. The system can process an unlimited number of readers simultaneously. However, writers have to be processed one at a time. Both readers and writers arrive according to Poisson processes. Writer and reader service times are general iid random variables. There is infinite waiting room for both. The alternating exhaustive priority policy operates as follows. Assume the system is initially idle. The first arriving customer initiates service for the class (readers or writers) to which it belongs. Once processing begins for a given class of customers, this class is served exhaustively, i.e. until no members of that class are left in the system. At this point, if customers of the other class are in the queue, priority switches to this class, and it is served exhaustively. This system is analyzed to produce a stability condition and Laplace-Stieltjes transforms (LSTs) for the steady state queueing times of readers and writers. An example is also given.     

A reader-writer queue with reader preference

This paper considers a reader-writer queue with reader preference. The system can process an unlimited number of readers simultaneously. However, writers have to be processed one at a time. Readers are given non-preemptive priority over writers. Both readers and writers arrive according to Poisson processes (PP) and have general independent service times. There is infinite waiting room for both. This system is analyzed to produce stability conditions. The analysis uses anM/G/ queue busy period to model readers, followed by a modifiedM/G/1 queue to model the entire system. Finally, results are presented for the expected wait-in-queue times for the readers and writers. The paper ends with an example.This work was done while the author was visiting the IBM Corporation, Networking Systems, RTP, NC 27709, USA.     

K-theory of braided tensor ring categories with higher commutativity

We show that theK-theory of a Waldhausen categoryC with anA-ring structure is anA ring spectrum. If theA structure onC supports anE _n structure, so thatBC group completes to ann-fold loop space, thenK (C) is anE _n ring spectrum. In particular, theK-theory of the category of crossedG-sets,G a finite group, is anE ₂ ring spectrum.     

Iterating the Bar Construction

For a 1-connected space X Adams's bar construction B(C*(X)) describes H*(X) only as a graded module and gives no information about the multiplicative structure. Thus it is not possible to iterate the bar construction in order to determine the cohomology of iterated loop spaces ⁱ X. In this paper for an n-connected pointed space X a sequence of A()-algebra structures , is constructed, such that for each there exists an isomorphism of graded algebras      

Some statistical problems in random translations of stochastic point processes

A random translation of a marked point process is considered. The distribution of random translation is assumed to be dependent upon the mark through a certain functionh(·). The main concern is to make inferences about the functionh(·) for different types of data. Complete identification and estimation are not possible in general, but some interesting particular solutions are presented.     

Relative K homology and C* algebras

Let A be a separable nuclear C ⁺ algebra with unit. Let be a closed two-sided ideal in A. A relative K homology group K ⁰(A,) is defined. Closely related are topological definitions of properly supported K homology and of compactly supported relative K homology. Applications are to indices of Toeplitz operators and existence of coercive boundary conditions for elliptic differential operators.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

A simple technique for computing theH ∞-norm of polynomials

In this note, computation of theH -norm of polynomials is considered. It is shown that direct computation of theH -norm of polynomials, based on the definition of the norm, results in a simple and inexpensive technique for computing the norm.     

Well-conditioned computation for H ∞ controller near the optimum

The present paper gives a procedure for determining a H optimal controller in the assumption that the game Riccati equations have stabilizing positive definite solutions at the optimum value. A specific feature of the construction is its first step consisting in balancing with respect to the positive definite stabilizing solutions of the Riccati equations. The justification is based on singular perturbations reduction.     

Robustness of minimax controllers to nonlinear perturbations

We study the robustness of minimax controllers, originally designed for nominal linear or nonlinear systems, to unknown static nonlinear perturbations in the state dynamics, measurement equation, and performance index. When the nominal system is linear, we consider both perfect state measurements and general imperfect state measurements; in the case of nominally nonlinear systems, we consider perfect state measurements only. Using a differential game theoretic approach, we show for the former class that, as the perturbation parameter (say, >0) approaches zero, the optimal disturbance attenuation level for the overall system converges to the optimal disturbance attenuation level for the nominal system if the nonlinear structural uncertainties satisfy certain prescribed growth conditions. We also show that anH -controller, designed based on a chosen performance level for the nominal linear system, achieves the same performance level when the parameter is smaller than a computable threshold, except for the finite-horizon imperfect state measurements case. For that case, we show that the design of the nominal controller must be based on a decreased confidence level of the initial data, and a controller thus designed again achieves a desired performance level in the face of nonlinear perturbations satisfying a computable norm bound. In the case of nominally nonlinear systems, and assuming that the nominal system is solvable, we obtain sufficient conditions such that the nominal controller achieves a desired performance in the face of perturbations satisfying computable norm bounds. In this way, we provide a characterization of the class of uncertainties that are tolerable for a controller designed based on the nominal system. The paper also presents two numerical examples; in one of these, the nominal system is linear; in the other one, it is nonlinear.This research was supported in part by the US Department of Energy, Grant DE-FG-02-88-ER-13939 and in part by the National Science Foundation, Grant ECS-91-13153.An abridged version was presented at the 32nd IEEE Conference on Decision and Control, San Antonio, Texas, December 15–17, 1993, and it appeared in the Conference Proceedings.     

Semicontinuous solutions for Hamilton-Jacobi equations and theL ∞control problem

We prove uniqueness for extended real-valued lower semicontinuous viscosity solutions of the Bellman equation forL -control problems. This result is then used to prove uniqueness for lsc solutions of Hamilton-Jacobi equations of the form –u _t +H(t, x, u, –Du)=0, whereH(t, x, r, p) is convex inp. The remaining assumptions onH in the variablesr andp extend the currently known results.Supported in part by Grant DMS-9300805 from the National Science Foundation.     

L ∞ Algebra Representations

It is shown that the direct sum of an L algebra and a module over it has a natural L algebra structure.     

On the gi/m/∞ service system with batch arrivals and different types of service distributions

We study the infinite-server system with batch arrivals ands different types of customers. With probabilityp _i an arriving customer is of typei (i=1,..., s) and requires an exponentially distributed service time with parameter _i (G ^GI /M ₁ ...M _s /). For theGI ^GI /M ₁...M _s / system it is shown that the binomial moments of thes-variate distribution of the number of type-i customers in the system at batch arrival epochs are determined by a recurrence relation and, in steady state, can be computed recursively. Furthermore, forG ^GI /M ₁...M _s /, relations between the distributions (and their binomial moments) of the system size vector at batch arrival and random epochs are given. Thus, earlier results by Takács [14], Gastwirth [9], Holman et al. [11], Brandt et al. [3] and Franken [6] are generalized.     

Transfer Function Optimization Procedure for the H 2/H ∞ Problem

In this paper, the H ₂/H problem is considered in a transfer-function setting, i.e., without a priori chosen bounds on the controller order. An optimization procedure is described which is based on a parametrization of all feasible descending directions stemming from a given point of the feasible transfer-function set. A search direction at each such point can be obtained on the basis of the solution of a convex finite-dimensional problem which can be converted into a LMI problem. Moving along the chosen direction in each step, the procedure in question generates a sequence of feasible points whose cost functional values converge to the optimal value of the H ₂/H problem. Moreover, this sequence of feasible points is shown to converge in the sense of a weighted H ₂ norm; and it does so to the solution of the H ₂/H problem whenever such a solution exists.     

H ∞-Control for Markovian Jumping Linear Systems with Parametric Uncertainty

This paper studies the problem of H -control for linear systems with Markovian jumping parameters. The jumping parameters considered here are two separable continuous-time, discrete-state Markov processes, one appearing in the system matrices and one appearing in the control variable. Our attention is focused on the design of linear state feedback controllers such that both stochastic stability and a prescribed H -performance are achieved. We also deal with the robust H -control problem for linear systems with both Markovian jumping parameters and parameter uncertainties. The parameter uncertainties are assumed to be real, time-varying, norm-bounded, appearing in the state matrix. Both the finite-horizon and infinite-horizon cases are analyzed. We show that the control problems for linear Markovian jumping systems with and without parameter uncertainties can be solved in terms of the solutions to a set of coupled differential Riccati equations for the finite-horizon case or algebraic Riccati equations for the infinite-horizon case. Particularly, robust H -controllers are also designed when the jumping rates have parameter uncertainties.