Skip to main content
main-content

Über dieses Buch

This is a revised and expanded version of the earlier edition. The new material is on Markov-modulated storage processes arising from queueing and data commu­ nication models. The analysis of these models is based on the fluctuation theory of Markov-additive processes and their discrete time analogues, Markov random walks. The workload and queue length processes, omitted from the earlier edition, are also presented. In addition, many sections have been rewritten, with new re­ sults and proofs, as well as further examples. The mathematical level and style of presentation, however, remain the same. Chapter I contains a comprefensive treatment of the waiting time and related quantities in a single server queue, combining Chapters 1 and 2 of the earlier edition. In Chapter 2 we treat the (continuous time) workload and queue length processes using their semiregenerative properties. Also included are bulk queues omitted from the earlier edition, but included in its Russian translation. The queue MIMIl is presented in Chapter 3. This is the so-called simple queue, but its treat­ ment in most of the literature is far from simple. Our analysis of the queue length process is elementary and yields explicit results for various distributions of interest. are treated in Chapter 4, combining Chapters 3 Continuous time storage models and 4 of the earlier edition. We present extensive new material, omitting much of the old Chapter 4. This has resulted in a streamlined account of this important class of models.

Inhaltsverzeichnis

Frontmatter

Introduction

Introduction

Abstract
The processes investigated in this book are those arising from stochastic models for queues, inventories, dams, insurance risk, and data communication. The following brief description of some of these models makes it clear that the common title "storage processes" is appropriate for these processes.
N. U. Prabhu

The Single Server Queue

Frontmatter

1. The Queue GI/G/1

Abstract
We consider the single-server queueing system where successive customers arrive at the epochs t0 (= 0), t1, t2,... and demand services times v1, v2,.... The interarrival times are then given by u n = t n t n-1 (n≥1). Let Xk = Vk — uk (k ≥ 1), and So = 0, S n = X 1 + X 2 + … + X n (n ≥ 1). We assume that the X kare mutually independent random variables with a common distribution; the basic process underlying this queueing model is the random walk {Sn}. To see this, let Wn be the waiting time of the nth customer and I n the idle period (if any) that just terminates upon the arrival of this customer. Then clearly for n≥ 0
$$ W_{n + 1} = \left( {X_{n + 1} + W_n } \right)^ + , I_{n + 1} = \left( {X_{n + 1} + W_n } \right)^ - $$
(1)
.
N. U. Prabhu

2. Further Results for the Queue GI/G/1

Abstract
The main topics of this chapter are the remaining workload and the queue length, defined as follows. At any time t ≥0 the remaining workload W(t) is the amount of work that the server has to do to serve all the customers present in the system at that time. The queue length Q(t) is the number of customers present, waiting, or being served at time t. The analysis of the processes {W (t), t ≥ 0} and {Q(t), t ≥ 0} calls for techniques different from those used in Chapter 1.
N. U. Prabhu

3. The Queue M/M/1

Abstract
Let A (t) be the number of arrivals during a time interval (0, t]. We characterize the service mechanism in terms of the maximum number D (t) of customers that can be served during (0, t]. Our assumptions imply that A (t) and D(t) are independent Poisson processes with parameters and &µ, respectively (0 <l < ∞, 0 < µ < ∞). The traffic intensity is given by ρ = λ/µ (0 < ρ < ∞). The properties of the queue length Q(t) can be expressed in terms of the net input
$$ X\left( t \right) = A\left( t \right) - D\left( t \right) $$
(1)
and the minimum functional m(t) of X(t). To see this, let T 0 =0 and T (n n ≥ 1) be the epochs of successive jumps in the process D(t). From the description of the model we obtain
$$ Q\left( t \right) = Q\left( {T_n } \right) + A\left( t \right) - A\left( {T_n } \right) for T_n \leqslant t < T_{n + 1} $$
(2)
and
$$ Q\left( {T_{n + 1} } \right) = \left[ {Q\left( {T_n } \right) + A\left( {T_{n + 1} } \right) - A\left( {T_n } \right) - 1} \right]^ + $$
(3)
for n ≥ 0. These relations yield the following expression for Q(t)(t≥0).
N. U. Prabhu

Continuous Time Storage Models

Frontmatter

4. The Basic Storage Model

Abstract
The models described in this chapter give rise to continuous time stochastic processes that are analogous to sums of independent and identically distributed random variables. We begin by describing models for two apparently different situations.
N. U. Prabhu

Markov-Modulated Storage Models

Frontmatter

5. The Markov-Modulated Single Server Queue

Abstract
We consider a single server queueing system whose customers belong to certain types indexed by jε (a countable space), the switching mechanism between different types of customers being governed by a Markov chain J = {J n , n ≥ 0} with the state space ε. Customers of each type have their own interarrival time and service time distributions determined by the state of J at the epoch of arrival. We assume that J is irreducible and persistent nonnull. The queue discipline is first come, first served.
N. U. Prabhu

6. A Fluid Model for Data Communication

Abstract
Example 1 (A Multiple Source Data Handling System). There are N sources of messages, which may be on or off from time to time. A switch receives these messages at a unit rate from each source and transmits them at a fixed maximum rate c (1 ≤ N < ∞, 0 < c < ∞), storing messages it cannot transmit in a buffer of infinite capacity. The sources act independently, the durations of on and off times being independent random variables with exponential densities. Denoting by J(t) the number of on sources at time t, these assumptions amount to the statement that J = {J(t), t ≥ 0} is a birth and death process on the state space {0, 1, 2, …, N}.
N. U. Prabhu

7. A Data Communication Model with Packets

Abstract
We consider a storage model for data communication in which (i) the input process (X, J) = {X(t), J(t),t ≥ 0} is a Markov-compound Poisson process on R+ x ε, ε being a countable state space; (ii) the demand for transmission arises at a rate d(j) when J is in state j; and (iii) the storage policy is to meet the demand if physically possible.
N. U. Prabhu

Backmatter

Weitere Informationen