Heavy-traffic limits for stationary network flows
- PDF / 361,917 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 47 Downloads / 214 Views
Heavy-traffic limits for stationary network flows Ward Whitt1
· Wei You2
Received: 26 January 2019 / Revised: 20 December 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper studies stationary customer flows in an open queueing network. The flows are the processes counting customers flowing from one queue to another or out of the network. We establish the existence of unique stationary flows in generalized Jackson networks and convergence to the stationary flows as time increases. We establish heavy-traffic limits for the stationary flows, allowing an arbitrary subset of the queues to be critically loaded. The heavy-traffic limit with a single bottleneck queue is especially tractable because it yields limit processes involving one-dimensional reflected Brownian motion. That limit plays an important role in our new nonparametric decomposition approximation of the steady-state performance using indices of dispersion and robust optimization. Keywords Generalized Jackson networks · Heavy traffic · Stationary point processes · Stability · Index of dispersion · Asymptotic methods Mathematics Subject Classification Primary 60F17; Secondary 60K25 · 90B22
1 Introduction In this paper, we establish heavy-traffic limits for the stationary flows in a non-Markov open queueing network (OQN). By flows, we mean the departure processes, flows from one queue to another, superpositions of such processes and thus the internal arrival processes. We consider an OQN with K single-server stations, unlimited waiting space, and the first-come first-served service discipline. We assume that we have mutually independent renewal external arrival processes, sequences of independent
B
Ward Whitt [email protected] Wei You [email protected]
1
Department of IEOR, Columbia University, New York, NY, USA
2
Department of IEDA, HKUST, Clear Water Bay, Hong Kong
123
Queueing Systems
and identically distributed (i.i.d.) service times and Markovian routing. Such a system is called a generalized Jackson network (GJN), because it generalizes the Markovian OQN analyzed by Jackson [18] in which all the interarrival times and service times have exponential distributions. Jackson OQNs are remarkably tractable because the vector of steady-state queue lengths (number in system) has a product-form distribution, just as if the queues were independent M/M/1 queues with the correct arrival rates. The major theoretical advance for GJNs more general than Jackson OQNs has no doubt been the heavy-traffic limit theory [8,20,24] (which did not consider the flows). However, the practical application of that theory remains challenging, largely because the different queues in an OQN may have widely varying traffic intensities, with only a few being bottlenecks. The heavy-traffic limits can be extended to that case, as shown by Chen and Mandelbaum [6,7], but there remains a need for effective numerical algorithms for computing performance measures which properly account for a range of traffic intensities. See [11,17] for pre
Data Loading...
