A 2-by-2 buffered switch is the basic element of certain parallel data-processing networks. For a switch fed by two independent Bernoulli input streams, we find the joint distribution of the number of messages waiting in the two buffers at equilibrium, in the form of a bivariate generating function. The derivation uses complex-variable techniques developed by Kingman and by Flatto and McKean for the “shortest queue problem.” A number of asymptotic results are given, the principal one being the variance of the total number of waiting messages in the heavy-traffic limit.

A stochastic process {Xt(s)} is viewed as a collection of random variables parameterized by time (t) and the initial state (s). {Xt(s)} is termed spatiotemporally increasing and convex if, in a sample-path sense, it is increasing in s and t and satisfies a directional convexity property, which implies that it is increasing and convex in s and in t (individually) and is supermodular in (s, t). Simple sufficient conditions are established for a uniforniizable Markov process to be spatiotemporally increasing and convex. The results are applied to study the convex orderings in GI/M(n)/l and M(n)/G/1 queues and to solve the optimal allocation of a joint setup among several production facilities. For a counting process that possesses a stochastic intensity, we show that its spatiotemporal behavior can be characterized by its conditional intensity via a birth process.

We prove necessary and sufficient conditions for the existence and uniqueness of the stationary solution of the queueing networks (G-networks) with negative and positive customers introduced in Gelenbe [3], which have been shown to have product form. First, the existence of the solution of the nonlinear customer flow equations is established using Brouwer's fixed-point theorem; this result is valid for stable and unstable systems, as well as for certain networks that may not have product form. Then, the result is used to establish general stability related to the usual “load factor less than 1” criterion of queueing systems for G-networks with product form.

We establish the quasireversibility of a certain exponential multiserver queue. The queuing discipline imposes restrictions on the numbers of customers of different classes and subclasses that can be served simultaneously. Customer loss is also allowed. Due to its quasireversibility the queue can be used as a node in a product form network. Our work generalizes work of Le Boudec, Krzesinski, and Crosby.

We characterize the probabilistic nature of the maximum queue length and the maximum waiting time in a multiserver G/G/c queue. We assume a general i.i.d. interarrival process and a general i.i.d. service time process for each server with the possibility of having different service time distributions for different servers. Under a weak additional condition, we will prove that the maximum queue length and waiting time grow asymptotically in probability as logωn−1 and log n1/θ, respectively, where ω < 1 and θ > 0 are parameters of the queuing system. Furthermore, it is shown that the maximum waiting time – when appropriately normalized – converges in distribution to the extreme distribution Λ(x) = exp(−e−x). The maximum queue length exhibits similar behavior, except that some oscillation caused by the discrete nature of the queue length must be taken into account. The first results of this type were obtained for the G/M/l queue by Heyde and for the G/G/l queue by Iglehart. Our analysis is similar to that of Heyde and Iglehart. The generalization to c > 1 servers is made possible due to the recent characterization of the tail of the stationary queue length and waiting time in a G/G/c queue (cf. Sadowsky and Szpankowski [17]).

This paper is divided into two distinct parts: the first considers a loss network, the second a queueing network. In each case, we consider a fully connected network consisting of a large number of links (queues) and operating under a dynamic routing policy known as least busy alternative routing. Using weak convergence results, we can examine the behavior of the networks as the number of links (queues) increases to infinity. We find that, despite the models having similarities and being amenable to the same analytical tools, they exhibit important differences in character.

Motivated by packetwise transmission of data in telecommunications, we introduce a fluid model with a continuous burst arrival process ψ = {(tn, Sn):n ≥ 0}. Each epoch, tn, begins a burst of length Sn that is, a continuous flow of fluid (work, information, etc.) at rate 1 to a system. The system processes fluid at rate 1. The model more generally can be used to approximate a storage system where fluid arrives over time due to many different (unrelated) sources. We analyze the model using sample path techniques (ψ is assumed deterministic, having arisen as a sample path from some underlying probability space) and by doing so obtain a variety of expressions for such quantities as average work inc system and average work in service as well as the empirical distribution for work in service. The expressions are given in terms of familiar quantities (such as customer delay) from the corresponding classic single- and infinite-channel queues that we construct from the same arrival sample path. In particular, we obtain an interesting decomposition of work in terms of the work in these two wellknown queueing models. In our final remarks, we also point out the optimality features of this model when compared to other models having different rules regulating the flow of burst work. In addition, we also give some stochastic ordering results when comparing two burst systems of the M/GI/1 or GI/M/1 type.

The approximation of the loss probability in finite-buffer queues is a practical problem of considerable interest. A new heuristic is given. This heuristic is based on the equilibrium distribution of the corresponding infinite-buffer queue. Numerical results show an excellent performance of the heuristic.

This paper presents Monte Carlo techniques for evaluating equilibrium availability and mean up and down periods of a renewable network for a wide class of network operational criteria. The suggested method is based on a graph evolution model that overcomes the main difficulty–hitting low-probability “border” states of the criterion. Theoretical efficiency of the method is briefly discussed and numerical results are presented.

We study a generalization of the GI/G/l queue in which the server is turned off at the end of each busy period and is reactivated only when the sum of the service times of all waiting customers exceeds a given threshold of size D. Using the concept of a “randomly selected” arriving customer, we obtain as our main result a relation that expresses the waiting-time distribution of customers in this model in terms of characteristics associated with a corresponding standard GI/G/1 queue, obtained by setting D = 0. If either the arrival process is Poisson or the service times are exponentially distributed, then this representation of the waiting-time distribution can be specialized to yield explicit, transform-free formulas; we also derive, in both of these cases, the expected customer waiting times. Our results are potentially useful, for example, for studying optimization models in which the threshold D can be controlled.

We analyze the optimal preemptive sequencing of n jobs on M + 1 parallel identical machines to minimize expected total flowtime. The running times of the jobs are independent samples from the distribution Pr(X = H) = p, Pr(X = H + T) = 1 − p, where H, T are random variables of general distribution. Preemption of a job is allowed when H is completed. This problem does not have a simple optimal solution. We show that the scheme of shortest expected remaining processing time first (SERPT) is close to optimal in two senses. The expected flowtime under SERPT and under the optimal policy differ by no more than a constant, independent of the number of jobs, and the expected number of optimal decisions that are not according to SERPT is bounded by a constant, independent of the number of jobs.

We consider the optimal scheduling of a finite capacity shuttle in a two-node network with imperfect information. When shuttle trips do not depend on the number of passengers carried, we prove optimality and monotonicity of threshold policies. We derive conditions for dispatching that reduce the computational effort required to compute an optimal threshold policy. We prove a counter-example to the optimality of threshold policies for finite horizon problems where trip lengths increase stochastically in the number of passengers carried.

We consider two nodes in tandem. At each node or service center, there are two exponential servers present with the same service rate μ and each with its own queue. Customers arrive at the first node according to a Poisson process with arrival rate λ. At their arrival, they have to be assigned to one of the servers, so they are routed to one of the queues at node 1. Customers leaving center 1 enter node 2 and are routed to one of the queues at node 2. In this paper, we consider the case with full information and the case with partial information.

This paper describes a procedure for computing tightest possible best-case and worst-case bounds on the coefficient of variation of a discrete, bounded random variable when lower and upper bounds are available for its unknown probability mass function. An example from the application of the Monte Carlo method to the estimation of network reliability illustrates the procedure and, in particular, reveals considerable tightening in the worst-case bound when compared to the trivial worst-case bound based exclusively on range.

We consider the problem of scheduling jobs on parallel machines to minimize flowtime, where all decisions about loading and sequencing must be made before any processing is done. We find policies that minimize flowtime stochastically or in the increasing convex sense under various assumptions.

In this paper, we exactly analyze the performance of the slotted ALOHA access scheme with capture in a multichannel packet radio communication environment for the IFT (immediate-first-transmission) protocol and the DFT (delayed-first-transmission) protocol. We derive four moment generating functions for the following performance measures: (1) the number of packet deparures in each group of capture level in any slot, (2) the interval time between wo consecutive slot ends with the same number of departures, (3) the interval time between two consecutive slot ends with at least one departure and the number of departures in each group in that slot, and (4) the packet delay for each group. We calculate the averages and higher moments of these performance measures by differentiating the moment generating functions and numerically compare the systems with and without ower capture. The system consists of a finite population of Nstations, both fixed and mobile, that are divided into L different capture groups and access a set of parallel M channels to transmit their packets. Capture effect means that a packet transmitted by a station with a highest capture level can be received accurately, even when other packets in lower capture levels are simultaneously transmitted on the same channel and in the same slot. Numerical comparison to a multichannel system without capture is made. Capture effects on channel utilization, mean packet delay, and coefficients of variation of packet delay and interdeparture time are examined.

We continue the study of our general cost structure for a maintained system. Here we focus on the optimization questions for an age or block policy. The notion of a marginal cost function is rigorously formulated and its utility investigated. Various applications are considered, including a new model in which minimal repairs are performed as long as the total accumulated repair costs do not exceed a fixed amount.

This paper considers routing to parallel queues in which each queue has its own single server and service times are exponential with nonidentical parameters. We give conditions on the cost function such that the optimal policy assigns customers to a faster queue when that server has a shorter queue. The queues may have finite buffers, and the arrival process can be controlled and can depend on the state and routing policy. Hence our results on the structure of the optimal policy are also true when the assigning control is in the “last” node of a network of service centers. Using dynamic programming we show that our optimality results are true in distribution.

We are concerned with a burst arrival single-server queue, where arrivals of cells in a burst are synchronized with a constant service time. The main concern is with the loss probability of cells for the queue with a finite buffer. We analyze an embedded Markov chain at departure instants of cells and get a kind of lumpability for its state space. Based on these results, this paper proposes a computation algorithm for its stationary distribution and the loss probability. Closed formulas are obtained for the first two moments of the numbers of cells and active bursts when the buffer size is infinite.

Loss networks with direct routing have a product-form solution for their equilibrium probabilities. The product-form solution typically involves a normalization constant calling for a multidimensional summation over an astronomical number of states. We propose the application of Monte Carlo summation in order to determine the normalization constant, the blocking probabilities, and the revenue sensitivities. We show that if the proper sampling technique is employed, then the computational effort of Monte Carlo summation is independent of link capacities. We also discuss the application of importance sampling, antithetic variates, and indirect estimation via Little's formula. The method is illustrated with a four-leaf star network supporting multirate traffic.