Geometric equilibrium distributions for queues with interactive batch departures

Gelenbe et al. [1, 2] consider single server Jackson networks of queues which contain both positive and negative customers. A negative customer arriving to a nonempty queue causes the number of customers in that queue to decrease by one, and has no effect on an empty queue, whereas a positive customer arriving at a queue will always increase the queue length by one. Gelenbe et al. show that a geometric product form equilibrium distribution prevails for this network. Applications for these types of networks can be found in systems incorporating resource allocations and in the modelling of decision making algorithms, neural networks and communications protocols.In this paper we extend the results of [1, 2] by allowing customer arrivals to the network, or the transfer between queues of a single positive customer in the network to trigger the creation of a batch of negative customers at the destination queue. This causes the length of the queue to decrease by the size of the created batch or the size of the queue, whichever is the smallest. The probability of creating a batch of negative customers of a particular size due to the transfer of a positive customer can depend on both the source and destination queue.We give a criterion for the validity of a geometric product form equilibrium distribution for these extended networks. When such a distribution holds it satisfies partial balance equations which are enforced by the boundaries of the state space. Furthermore it will be shown that these partial balance equations relate to traffic equations for the throughputs of the individual queues.     

G-networks with multiple classes of signals and positive customers

G-networks are queueing models in which the types of customers one usually deals with in queues are enriched in several ways. In Gnetworks, positive customers are those that are ordinarily found in queueing systems; they queue up and wait for service, obtain service and then leave or go to some other queue. Negative customers have the specific function of destroying ordinary or positive customers. Finally triggers simply move an ordinary customer from one queue to the other. The term “signal” is used to cover negative customers and triggers. G-networks contain these three type of entities with certain restrictions; positive customers can move from one queue to another, and they can change into negative customers or into triggers when they leave a queue. On the other hand, signals (i.e. negative customers and triggers) do not queue up for service and simply disappear after having joined a queue and having destroyed or moved a negative customer. This paper considers this class of networks with multiple classes of positive customers and of signals. We show that with appropriate assumptions on service times, service disciplines, and triggering or destruction rules on the part of signals, these networks have a product form solution, extending earlier results.     

Product form solution for exponential G-networks with dependent service and completion of service of killed customers

Queueing networks with negative customers (G-networks), Poisson flow of positive customers, multi-server exponential nodes, and dependent service at the different nodes are studied. Every customer arriving at the network is defined by a set of random parameters: customer route, the length of customer route, customer volume and his service time at each route stage as well. A killed positive customer is removed at the last place in the queue and quits the network just after his remaining service time will be elaborated. For such G-networks, the multidimensional stationary distribution of the network state probabilities is shown to be representable in product form.     

On Stochastic Bounds for Monotonic Processor Sharing Networks

We consider a network of processor sharing nodes with independent Poisson arrival processes. Nodes are coupled through their service capacity in that the speed of each node depends on the number of customers present at this and any other node. We assume the network is monotonic in the sense that removing a customer from any node increases the service rate of all customers. Under this assumption, we give stochastic bounds on the number of customers present at any node. We also identify limiting regimes that allow to test the tightness of these bounds. The bounds and the limiting regimes are insensitive to the service time distribution. We apply these results to a number of practically interesting systems, including the discriminatory processor sharing queue, the generalized processor sharing queue, and data networks whose resources are shared according to max–min fairness.     

Delay analysis of a two-class batch-service queue with class-dependent variable server capacity

In this paper, we analyse the delay of a random customer in a two-class batch-service queueing model with variable server capacity, where all customers are accommodated in a common single-server first-come-first-served queue. The server can only process customers that belong to the same class, so that the size of a batch is determined by the length of a sequence of same-class customers. This type of batch server can be found in telecommunications systems and production environments. We first determine the steady state partial probability generating function of the queue occupancy at customer arrival epochs. Using a spectral decomposition technique, we obtain the steady state probability generating function of the delay of a random customer. We also show that the distribution of the delay of a random customer corresponds to a phase-type distribution. Finally, some numerical examples are given that provide further insight in the impact of asymmetry and variance in the arrival process on the number of customers in the system and the delay of a random customer.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

Questionnaire design improvement and missing item scores estimation for rapid and efficient decision making

In this paper we consider a single-server, cyclic polling system with switch-over times and Poisson arrivals. The service disciplines that are discussed, are exhaustive and gated service. The novel contribution of the present paper is that we consider the reneging of customers at polling instants. In more detail, whenever the server starts or ends a visit to a queue, some of the customers waiting in each queue leave the system before having received service. The probability that a certain customer leaves the queue, depends on the queue in which the customer is waiting, and on the location of the server. We show that this system can be analysed by introducing customer subtypes, depending on their arrival periods, and keeping track of the moment when they abandon the system. In order to determine waiting time distributions, we regard the system as a polling model with varying arrival rates, and apply a generalised version of the distributional form of Little??s law. The marginal queue length distribution can be found by conditioning on the state of the system (position of the server, and whether it is serving or switching).     

The MM CPP/GE/c G-Queue: Sojourn Time Distribution

We obtain the sojourn time probability distribution function at equilibrium for a Markov modulated, multi-server, single queue with generalised exponential (GE) service time distribution and compound Poisson arrivals of both positive and negative customers. Such arrival processes can model both burstiness and correlated traffic and are well suited to models of ATM and other telecommunication networks. Negative customers remove (ordinary) customers in the queue and are similarly correlated and bursty. We consider both the cases where negative customers remove positive customers from the front and the end of the queue and, in the latter case, where a customer currently being served can and cannot be killed by a negative customer. These cases can model an unreliable server or load balancing respectively. The results are obtained as Laplace transforms and can be inverted numerically. The MM CPP/GE/c G-Queue therefore holds the promise of being a viable building block for the analysis of queues and queueing networks with bursty, correlated traffic, incorporating load balancing and node-failures, since the equilibrium behaviour of both queue lengths and response times can be determined in a tractable way.     

Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the beginning of a visit of the server to such a queue, a gate is set behind all customers. High priority customers receive priority in the sense that they are always served before any low priority customers. But high priority customers have a second advantage over low priority customers. Low priority customers are served according to the gated service discipline, i.e. only customers standing in front of the gate are served during this visit. In contrast, high priority customers arriving during the visit period of the queue are allowed to pass the gate and all low priority customers before the gate. We study the cycle time distribution, the waiting time distributions for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type. Through numerical examples we illustrate that the mixed gated/exhaustive service discipline can significantly decrease waiting times of high priority jobs. In many cases there is a minimal negative impact on the waiting times of low priority customers but, remarkably, it turns out that in polling systems with larger switch-over times there can be even a positive impact on the waiting times of low priority customers.     

Economies of scale,competitiveness, and trade patterns within the European community: Clarendon Press,Oxford, 1983, 193 pages, £20.00

We consider two queues in series with input to each queue, which can be controlled by accepting or rejecting arriving customers. The objective is to maximize the discounted or average expected net benefit over a finite or infinite horizon, where net benefit is composed of (random) rewards for entering customers minus holding costs assessed against the customers at each queue. Provided that it costs more to hold a customer at the first queue than at the second, we show that an optimal policy is monotonic in the following senses: Adding a customer to either queue makes it less likely that we will accept a new customer into either queue; moreover moving a customer from the first queue to the second makes it more (less) likely that we will accept a new customer into the first (second) queue. Our model has policy implications for flow control in communication systems, industrial job shops, and traffic-flow systems. We comment on the relation between the control policies implied by our model and those proposed in the communicationa literature.     

On the M/G/1 queue with feedback and optional server vacations based on a single vacation policy

We study a single server queue with batch arrivals and general (arbitrary) service time distribution. The server provides service to customers, one by one, on a first come, first served basis. Just after completion of his service, a customer may leave the system or may opt to repeat his service, in which case this customer rejoins the queue. Further, just after completion of a customer's service the server may take a vacation of random length or may opt to continue staying in the system to serve the next customer. We obtain steady state results in explicit and closed form in terms of the probability generating functions for the number of customers in the queue, the average number of customers and the average waiting time in the queue. Some special cases of interest are discussed and some known results have been derived. A numerical illustration is provided.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

Heavy-traffic analysis of the sojourn time in a three node Jackson network with overtaking

We consider a Jackson network consisting of three first-in-first-out (FIFO)M/M/1 queues. When customers leave the first queue they can be routed to either the second or third queue. Thus, a customer that traverses the network by going from the first to the second to the third queue, can be overtaken by another customer that is routed from the first queue directly to the third. We study the distribution of the sojourn time of a customer through the three node network, in the heavy traffic limit. A three term heavy traffic asymptotic approximation to the sojourn time density is derived. The leading term shows that the nodes decouple in the heavy traffic limit. The next two terms, however, do show the dependence of the sojourn times at the individual nodes and give quantitative measures of the effects of overtaking.     

Convergence to equilibria for fluid models of FIFO queueing networks

The qualitative behavior of open multiclass queueing networks is currently a topic of considerable activity. An important goal is to formulate general criteria for when such networks possess equilibria, and to characterize these equilibria when possible. Fluid models have recently become an important tool for such purposes. We are interested here in a family of such models, FIFO fluid models of Kelly type. That is, the discipline is first-in, first-out, and the service rate depends only on the station. To study such models, we introduce an entropy function associated with the state of the system. The corresponding estimates show that if the traffic intensity function is at most 1, then such fluid models converge exponentially fast to equilibria with fixed concentrations of customer types throughout each queue. When the traffic intensity function is strictly less than 1, the limit is always the empty state and occurs after a finite time. A consequence is that generalized Kelly networks with traffic intensity strictly less than 1 are positive Harris recurrent, and hence possess unique equilibria.1991Mathematics Subject Classification, 60K25, 68M20, 90B10. Partially supported by NSF Grant DMS-93-00612.     

Analysis of M/M/S queues with 1-limited service

In this paper, a multiple server queue, in which each server takes a vacation after serving one customer is studied. The arrival process is Poisson, service times are exponentially distributed and the duration of a vacation follows a phase distribution of order 2. Servers returning from vacation immediately take another vacation if no customers are waiting. A matrix geometric method is used to find the steady state joint probability of number of customers in the system and busy servers, and the mean and the second moment of number of customers and mean waiting time for this model. This queuing model can be used for the analysis of different kinds of communication networks, such as multi-slotted networks, multiple token rings, multiple server polling systems and mobile communication systems.     

A retrial queue with structured batch arrivals,priorities and server vacations

A retrial queue accepting two types of customers with correlated batch arrivals and preemptive resume priorities is studied. The service times are arbitrarily distributed with a different distribution for each type of customer and the server takes a single vacation each time he becomes free. For such a model the state probabilities are obtained both in a transient and in a steady state. Finally, the virtual waiting time of an arbitrary ordinary customer in a steady state is analysed.     

Bibliography on G-networks,negative customers and applications

The idea of G-networks with negative arrivals, as well as of the relevant product form solution including non-linear traffic equations, was first published by Erol Gelenbe in 1989. In contrast to classical queues and queueing networks, the arrivals of negative customers which remove customers from a non-empty queue upon their arrival are possible in G-networks. Negative customers with appropriate killing discipline can be used to model breakdowns and to model packet losses, etc., while triggered customer movement can represent control processes in networks. This work presents a bibliography¹ on G-networks, negative customers and the use of G-networks, negative customers and triggers to various performance analysis problems. We hope that we can include a majority of publications on G-networks. This bibliography in the BibTex format and a grouping by various themes is available online from http://www.hit.bme.hu/~do/G-networks/. We would encourage readers and researchers to send information to the author in order to make this bibliography as complete as possible.     

An assignment problem for a parallel queueing system with two heterogeneous servers

In this paper, we consider an optimization problem for a parallel queueing system with two heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Each service time is independent and exponentially distributed. When a customer arrives at queue 1, the customers in queue 1 can be transferred to queue 2 by paying an assignment cost which is proportional to the number of moved customers. Holding cost is a function of the pair of queue lengths of the two servers. Our objective is to minimize the expected total discounted cost. We use the dynamic programming approach for this problem. Considering the pair of queue lengths as a state space, we show that the optimal policy has a switch over structure under some conditions on the holding cost.     

A GI/Geo/1 queue with negative and positive customers

The arrival of a negative customer to a queueing system causes one positive customer to be removed if any is present. Continuous-time queues with negative and positive customers have been thoroughly investigated over the last two decades. On the other hand, a discrete-time Geo/Geo/1 queue with negative and positive customers appeared only recently in the literature. We extend this Geo/Geo/1 queue to a corresponding GI/Geo/1 queue. We present both the stationary queue length distribution and the sojourn time distribution.