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.     

Analysis of a finite buffer model with two servers and two nonpreemptive priority classes

In this paper, we analyze a finite buffer queueing model with two servers and two nonpreemptive priority service classes. The arrival streams are independent Poisson processes, and the service times of the two classes are exponentially distributed with different means. One of the two servers is reserved exclusively for one class with high priority and the other server serves the two classes according to a nonpreemptive priority service schedule. For the model, we describe its dynamic behavior by a four-dimensional continuous-time Markov process. Applying recursive approaches we present the explicit representation for the steady-state distribution of this Markov process. Then, we calculate the Laplace–Stieltjes Transform and the steady-state distribution of the actual waiting times of two classes of customers. We also give some numerical comparison results with other queueing models.     

State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

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.     

Markov-modulated queueing systems

Markov-modulated queueing systems are those in which the primary arrival and service mechanisms are influenced by changes of phase in a secondary Markov process. This influence may be external or internal, and may represent factors such as changes in environment or service interruptions. An important example of such a model arises in packet switching, where the calls generating packets are identified as customers being served at an infinite server system. In this paper we first survey a number of different models for Markov-modulated queueing systems. We then analyze a model in which the workload process and the secondary process together constitute a Markov compound Poisson process. We derive the properties of the waiting time, idle time and busy period, using techniques based on infinitesimal generators. This model was first investigated by G.J.K. Regterschot and J.H.A. de Smit using Wiener-Hopf techniques, their primary interest being the queue-length and waiting time.     

Some notes on the reduction of network dimensionality in nested open queueing networks

In this paper, we study an open and nested tandem queueing network, where the population constraint within each subnetwork is controlled by a semaphore queue. The total number of customers that may be present in the subnetwork can not exceed a given value. Each node has a constant service time and the arrival process to the queueing network follows an arbitrary distribution.A major characteristic of this queueing network is that the low layer flow is halted by the state of the high layer. We develop a simple and equivalent queueing network that has the same performance characteristics as the original queueing network. Using this model, the waiting time on the queueing network can be easily derived. It is interesting to see how the simplification process can be applied to multi-layered queueing network.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

The 1-Center and 1-Highway problem revisited

We consider a two-queue polling model in which customers upon arrival join the shorter of two queues. Customers arrive according to a Poisson process and the service times in both queues are independent and identically distributed random variables having the exponential distribution. The two-dimensional process of the numbers of customers at the queue where the server is and at the other queue is a two-dimensional Markov process. We derive its equilibrium distribution using two methodologies: the compensation approach and a reduction to a boundary value problem.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

The Infinite Server Queue with Arrivals Generated by a Non-Homogeneous Compound Poisson Process

This paper considers the infinite server queue with arrivals generated by a non-homogeneous compound Poisson process. In such a system, customers arrive in groups of variable size, the arrival epochs of groups being points of a non-homogeneous Poisson process, and they are served without delay. The service times of customers who belong to the same group need not be independent nor identically distributed. Assuming that the system is initially empty, the transient distribution of the queue size and of the counting departure process is obtained. Also the limiting queue size distribution (when it exists) is determined and it is found to be insensitive to the form the service time distribution functions.     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

THE MATCHED QUEUEING SYSTEM GI。PH/PH/1

ＴＨＥＭＡＴＣＨＥＤＱＵＥＵＥＩＮＧＳＹＳＴＥＭＧＩ。ＰＨ／ＰＨ／１ＸＵＧＵＡＮＣＨＵＩ（ＧＵＡＮＧ－ＨＵＩＨＳＶ）（徐光煇）；ＨＥＱＩＭＩＮＧ（何启明）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙ...     

Exponential Queues with Server Vacations

In this paper, we analyse a queueing system where the server may take a vacation. The customers arrive at the service facility according to a Poisson process, and are served if the server is available (not on vacation). We consider two models: when the server vacation cycle is independent of and dependent on the number of customers in the system. The infinitesimal generators of the underlying Markov processes have a block tri-diagonal structure, and we provide a matrix geometric solution. When the vacation cycle is independent of the customer queue length, we present a simple load-dependent approximation that is fairly accurate.     

Transient and stationary waiting times in (max,+)-linear systems with Poisson input

We consider a certain class of vectorial evolution equations, which are linear in the (max,+) semi-field. They can be used to model several Types of discrete event systems, in particular queueing networks where we assume that the arrival process of customers (tokens, jobs, etc.) is Poisson. Under natural Cramér Type conditions on certain variables, we show that the expected waiting time which the nth customer has to spend in a given subarea of such a system can be expanded analytically in an infinite power series with respect to the arrival intensity λ. Furthermore, we state an algorithm for computing all coefficients of this series expansion and derive an explicit finite representation formula for the remainder term. We also give an explicit finite expansion for expected stationary waiting times in (max,+)-linear systems with deterministic queueing services. This revised version was published online in June 2006 with corrections to the Cover Date.     

The matched queueing system GIoPh/Ph/1

We study the matched queueing system GIoPH/PH/1, where the type-I input is a renewal process, the type-II input is a PH renewal process, and the service times are i.i.d. random variables with PH-distributions. First, a condition is given for the stationarity of the system. Then the distributions of the number of type-I customers at the arrival epoches of type-I customers and the number of type-I customers at an arbitrary epoch are derived. We also discuss the occupation time and the waiting time. Their L.S. transforms are derived. Finally, we discuss some problems in numerical computation.This research is supported by the National Natural Science Foundation of China and partially by the Institute of Mathematics, the Chinese Academy of Sciences.     

A preferential attachment model with Poisson growth for scale-free networks

We propose a scale-free network model with a tunable power-law exponent. The Poisson growth model, as we call it, is an offshoot of the celebrated model of Barabási and Albert where a network is generated iteratively from a small seed network; at each step a node is added together with a number of incident edges preferentially attached to nodes already in the network. A key feature of our model is that the number of edges added at each step is a random variable with Poisson distribution, and, unlike the Barabási–Albert model where this quantity is fixed, it can generate any network. Our model is motivated by an application in Bayesian inference implemented as Markov chain Monte Carlo to estimate a network; for this purpose, we also give a formula for the probability of a network under our model.     

A two-stage queueing network with MAP inputs and buffer sharing

In this paper, we study a two-stage tandem queueing network with MAP inputs and buffer sharing. The two stages share the same buffer. By using Markov process, we give an exact analysis of the queueing network. Since the customer arrival is not a Poisson process, the PASTA (Poisson Arrivals See Time Averages) property does not hold. A matrix filtration technique is proposed to derive the probability distribution of queue length at arrivals. Our objective is to investigate how the buffer sharing policy is mitigate the tradeoff between the probability that an arriving customer is lost and the probability that the first-stage server is blocked. The numerical results show that buffer sharing policy is more flexible, especially when the inputs have large variant and are correlated.     

The state-dependent <Emphasis Type="Italic">M</Emphasis> / <Emphasis Type="Italic">G</Emphasis> / 1 queue with orbit

We consider a state-dependent single-server queue with orbit. This is a versatile model for the study of service systems, where the server needs a non-negligible time to retrieve waiting customers every time he completes a service. This situation arises typically when the customers are not physically present at a system, but they have a remote access to it, as in a call center station, a communication node, etc. We introduce a probabilistic approach for the performance evaluation of this queueing system, that we refer to as the queueing and Markov chain decomposition approach. Moreover, we discuss the applicability of this approach for the performance evaluation of other non-Markovian service systems with state dependencies.     

Analysis of stationary discrete-time GI/D-MSP/1 queue with finite and infinite buffers

This paper considers a single-server queueing model with finite and infinite buffers in which customers arrive according to a discrete-time renewal process. The customers are served one at a time under discrete-time Markovian service process (D-MSP). This service process is similar to the discrete-time Markovian arrival process (D-MAP), where arrivals are replaced with service completions. Using the imbedded Markov chain technique and the matrix-geometric method, we obtain the system-length distribution at a prearrival epoch. We also provide the steady-state system-length distribution at an arbitrary epoch by using the supplementary variable technique and the classical argument based on renewal-theory. The analysis of actual-waiting-time (in the queue) distribution (measured in slots) has also been investigated. Further, we derive the coefficient of correlation of the lagged interdeparture intervals. Moreover, computational experiences with a variety of numerical results in the form of tables and graphs are discussed.