This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
k).
= p ( z k 6 6, z k
Therefore, since fi is assumed to be finite, we obtain the coupling inequality lFx,k
- FZ,kl < ~
( > k) 8
3
0 as k
-+ 00.
In particular, if (2,) is @-stationary,
4 : N -+ I$ then
<
4 ( n ) ~ ( 8> n ) = 0. This'and (4.1.2) give the 0
We shall need later the notion of coupling of point processes. The two point processes on the real line, M and N , defined on the probability space ( R , 7 ,P ) , are said to couple if there exists a finite random variable T such that M ( A n [T,oo)) = N(A n [T,a ) ) , for all Borel sets A. This definition is easily extended to marked point processes by requiring that M(A n [T,oo) x B ) = N(A n [T,co) x B ) for all Borel sets A on the line and all measurable sets B of the mark space. The reader interested in coupling is advised t o read the book by T . Lindvall (1992) Lectures on the Coupling Method, Wiley. 4.2 Coupling of Stochastic Recurrent Sequences *C
The following framework contains all the systems considered so far. Consider a dynamical system where the quantities of interest are described by an Evalued sequence { W z ) , n 2 0, generated by the stochastic recurrence
, d
5
where h is some measurable function. The driving sequence {&,I, n E Z, is F-valued ( E and F are two Polish spaces) and Y is the initial condition (W: = Y). All these random variables are defined on the same probability space. Observe that if two solutions {W:) and (WT} of (4.2.1) couple, they couple a t the first epoch when they meet; a necessary and sufficient condition for coupling is therefore that
.I Convergence in variation implies convergence in distribution. cl
be a.s. finite.
r
:
2 Stationarity and Coupling
90
4 Coupling
Consider the case when the reference probability space is ( O P T Po, , where ( P o , @ )is ergodic, and assume that the sequence (&,I is compatible with thct shift 8. T h e basic questions concerning the solutions of (4.2.1) are tileu the existence of a stationary solution which is compatible with the shift, the uniqueness of the stationary regimes, and the nature of the convergence of the non-stationary process { W z ) towards the stationary regime(s). ernark 4.2.1 Consider the case when E is (R+)Kand the mapping h is nonnegative, non-decreasing and continuous in- its first argument. The method which was used in 5 2 and $ 3 leads t o simple answers to the first of these questions. Indeed, we can then find a stationary solution M, o On t o (4.2.1), where M, E BK is defined by
91
type (4.2.1) holds for both {fl) and {w:) with the same driving sequence, and {W:) couple. So do the processes {w$-) = {M,o the processes On\ and { W : } by specializing Y to Mm This in turn implies that { W $ - ),-I U and {w:} couple. The associated non-stationary inter-departure sequence also couples with a compatible sequence, a t least for reasonable service disciplines. For instance, in the FIFO case, let Dn denote the n-th departure time. T h e coupling property of {D,+l - D,) with a sequence compatible with the shift is immediate from the relation
{c)
and from the coupling property of {W,). Note that in this case, the stationary inter-departure times are integrable. This follows from the relation
and (4.2.4) M , = lirn f Mn. n-00
It is natural t o call M , the Loynes' variable associated with the stochastic recurrence. This solution can be finite or infinite. In case it is a.s. finite, it is the smallest stationary solution of (4.2.1). However, there may be several other finite soiutions compatible with 0 (e.g. the G / G / s / m queue).
0
Coupling can then be used to answer the second type of question and t o show that the distribution under Poof a given solution converges in variation to a stationary limit distribution, for instance that of {M, o Bn}nzo under P o .
,
ling in the G / G / l / w plieplie. In this subsection, besides the f ( p o l8 ) , the stability condition p < 1 is assumed to hold. Then, there exists an infinity of negative (resp. positive) indices n such that Z o On = 0, where Z = M, is the unique non-negative solution of (2.1.1). (4.2.5) For any finite initial condition Y, {w;) couples with the 6-compatible workload process (Mm 0 On). Therefore, the process { q + k ) n 2 0 under Po converges i n variation to { M , o On)nlo under Po when k tends to oo.
Prwf Since W z = Y 2 0 = W:, W z 2 W: for all n 2 0. In addition, { W z } eventually becomes null. Indeed, W z > 0 for all n >_ 0, implies Y + Cy=o(uk - r k ) 2 0 , for all n 1 0 , which implies that I
lim SUP - x ( u k - r k ) LO n k=0
a.s.
for all n
Similar constructions are possible for other secondary processes like for instance the congestion processes using the construction points (see $ 1). Remark 4.2.2 T h e coupling properties of the G / G / l / w queue can be slightly extended as follows: consider a queue with arrival times 0 = T o < T I , .. . and service times uo, a l , . .., all defined on the probability space shift which is Po-stationary and ergodic. Here, ( O , p , P o , @ ) ,where 6 is a dzf the sequences {on}and { T , - Tn+l- T n ) are not assumed to be 6 compatible, and in particular (R,36, P 0 , 8 ) is not assumed to be the Palm space of the arrival process. Denote W z the workload sequence in this queue for an initial workload Y. (4.2.6) Assume that the sequences (7,) and { o n } couple with 0-compatible sequences {roOn) and { a 0 0 ~ )respectively, , where T and cr are Po-integrable. If EO[o]< @[TI, then W z couples with the stationary sequence { M , 0 On), where M, is the Loynes' variable associated with the sequences { a 0 On) and { T O 6") (see $ 2.2). Proof: Let N denote the coupling time of the inter-arrival and service times with the stationary sequences. On {w; 2 M , o O N } (resp. {w: < M, 0 ON)), w;+, 2 h/i, oONtn (resp. {W;+n M, oBN+*)), for all n 2 0. Let I( (resp. L) be the first n such that M, o oN+" = 0 (resp. w;+, = 0). T h e random variables Ii and L are finite (provided Y is finite). This implies that
<
tV,Y = M ,
>
0
On,
a
-
This contradicts the fact that limndm C;=,(uk r k )= EO[o] - Eo[r]< 0, P o - a s . . Thus, for any finite initial condition Y, there exists a finite N such that = W,O = 0, and therefore since a recurrence equation of the
forn>N+h'VL. A typical example is studied in $ 7.1, where we use the property that the output process of a FIFO queue couples with a 0-compatible sequence, where 8 is the (discrete) shift associated with the input process of this queue.
Convergence in Variation of t e Continuous-Time Workload in ueues. It was shown above that for a G/G/l/oo queue with p < 1, for all finite initial conditions, the sequence describing workload a t arrival times couples with the unique customer stationary workload sequence. This coupling was established under Po. A similar coupling property holds in continuous time, under P. (4.2.7) For any finite initial condition Y , the stochastic process {WY(t)), defined in 5 1.2, couples P-almost surely to the stochastic process { W o &),
used. Thus, i i arrival process
denotes the probability associated with the delayed renewal
Can we say something similar concerning the continuous time workload process? That is, does the relation
defined i n (2.1.3). Therefore, (4.2.8)
lim sup J P( { w Y ( t
TTm A
+ T ) ) ~ ~E A) o - P ({w et)t>oE A)I 0
= 0,
where the supremum is over all Bore1 sets with respect to the Skorokhod's topology for instance.
0 Proof: The proof is similar to that of (4.2.5). e 4.2.1 Coupling in the G / G / l / o o queue with priorit9 classes. Let be two &compatible &-marked point processes defined on the same space ( R , 3 , P , B t ) , where { B t ) is ergodic. It is assumed that the superposition of N1 and N2 is simple. Let p,, i = 1,2, denote the traffic intensity of N , , and assume that pi + pz < 1. Consider this superposition of point processes t o be the input of a G/G/l/co queue with the following discipline: customers of class 1 (corresponding to Nl) have preemptive priority over those of class 2; within each class, customers are served on a FIFO basis. Then the workload processes { W l ( t ) )and fWz(t)), representing the workload of customers of class 1 and 2 respectively, couple P-a.s. with uniquely defined &-compatible workload processes, regardless of the initial conditions. Indeed, the total workload W ( t )%if W l ( t ) W z ( t ) couples with a uniquely defined stationary process, in view of (4.2.7) (this discipline leads to the same total workload as global FIFO for instance). The same holds for Wl(t), since customers of class 1 are not affected by those of class 2. Therefore, (t)) couples with a uniquely defined stochastic process too. a
+
We now look a t the case when the arrival point process is not in its stationary state. To state the problem in simple terms, consider a G I / G I / l / c o " queue with p < 1, where the arrival process is arbitrarily delayed (and therefore a delayed renewal process, however not assumed stationary) and where the workload a t time 0 is also arbitrary. T h e distribution of the sequence (Wk+n)n>O, where Wn = W(Tn-), converges in variation, as k 4 co, to the distribution under Po of ( 2 o On) = {M, o On). This is because of the coupling occurring, under P o , when we start with an arbitrary workload, and because in the delayed renewal case, the sequence (T,, has the same istribution as if the governing probability were Po,and so (4.2.1) can be
hold, where P is the stationary probability corresponding to a stationary delayed renewal arrival process? This is obviously possible if the renewal process, arbitrarily delayed, couples with the stationary delayed renewal process, that is if we can construct on the same probability space two renewal processes with the same given inter-arrival distribution and arbitrary distribution of the first point after the origin of times, such that after a finite random time, their points coincide. A necessary and sufficient condition for this is that the inter-arrival probability distribution be spread-out. In the general non-lattice case, convergence in variation is not available, only convergence in distribution is true (for a study of these aspects concerning G I / G I / l / m queues, the reference is section 3 of chapter VIII of the book of S. Asmussen, Applied Probability and Queues, Wiley, N Y , 1987). T h e question stated in (4.2.10) has not yet received a complete answer for the G/G/l/oo queue. In this case, (4.2.10) may well not be true. However, in the case when coupling exists, convergence in variation does hold. More precisely, let M and N be two arrival marked point processes defined on the same probability space ( R , 3 , P,Ot), where Bt is ergodic. Assume that N is Ot-compatible. Let Po the Palm probability of N and let a and T denote the service time and the inter-arrival time associated with point To of N , respectively. Let W$(t) denote the workload a t time t, for the arrival point process Q (either N or M) and the initial condition Y. (4.2.11) If M and N couple and if EO[u]< E0[7], then the workload process { W L ( t ) )couples with the stationary workload process { W o Bt) associated with N (see (1.2.3) and (2.1.3)).
Proof: Let T 2 0 be the coupling time between N and M. By the same arguments as in the proof of (4.2.5), it follows that any solution finite a t time T couples with the workload process starting with the value 0 a t time T (all what is needed t o carry 'on the argument is that
and this is true for any finite random variable T).
2 Stationarity and Coupling
94
Example 4.2.2 Example 4.2.1. continued. If we replace the assumption that and NZ are &-compatible by the assumption that Ni couples with a Becompatible point process, i = 1,2, the conclusion of Example 4.2.1 remains unchanged in view of (4.2.11). C) N1
We now give an example of non-renewal point process for which the coupling property assumed in (4.2.11) holds. Example 4.2.3 Construction and Coupling of Lindvall's (A,m)-Point Processes. The present example is 'devoted to the construction of a s i m ~ l e~ o i n t process N , which is stationary and admits a (PIFp)-intensity {X(t)}, t E $ of the form:
where cp is a given functional on the canonical space of point processes , M ) , measurable w.r.t. the a-field generated by the random variables m 4 m(C), C Borelian of (-w, 0) (recall that m is the notation for generic elements of (MI&), not to be confused with the integer of the (A,m) process). This construction is not always possible, or if possible, it may not be unique for two main reasons: there could'be explosions, or there could be extinctions. The explosive case (forbidding existence) occurs for instance for a functional cp of the form
where ?(I : N -r R is strictly positive and increases to w sufficiently fast. The extinction case (forbidding uniqueness), would occur for instance for a functional of the same form with $ ( O ) = 0 and sup $(n)< oo
.
n>O
One must therefore impose conditions on the functional cp in order to make a construction based on regenerative events possible.
tion: There exists an integer m 2 0 and a real number A > Q cp(Nf) whenever both conditions below hold (a) N ( C n ( - A , 01) = N'(C n A,01)for all Borelians of R (b) T-j(N) = 2'-j(N1) for j = 1, . . . ,m - 1, where {T,(N)) is the sequence of points of N with a similar definition for Tn(N1). This assumption tells us that at a given time t , the future probabilistic behavior of the point process only depends on the last rn points and/or on the past at depth A (the points in ( t - A, 11).
4 Coupling
95
We shall now prove uniqueness of the point processes defined there in the sense of coupling. More precisely: given an arbitrary "initial distribution", that is to say a probability distribution P- on ( M - , M e ) , the restriction of (M, M ) to (-oo,01, then we can construct two point processes, N and N', on the same probability space ( 0 , T ,P ) such that (a)N is stationary with the (P, Ff)-intensity cp(StN). (@)Therestriction of N' to M - has the distribution P-. (7)On R+ , i\l' admits the (P, T;t" )-intensity p(St N'), and moreover, there exist two non-negative times U and V with P(U < co) = 1, P ( V <'m) = 1, such that (6) N(C n [U,oo)) = N'(C n [U, oo))for all Borelians C of & ( E ) cp(StN) = cp(StN1)for all t 2 V. Besides the (A, m ) assumption, we shall impose that
for some XI, X2, and for all N (see the bibliographical comments for less restrictive assTmptions). For our construction, we'need a stationary framework ( 0 , 3 , P,O t ) on which are defined two Poisson processes Nl and N1,2 compatible with the shift independent, and of respective intensities XI and Xl,2 = A2 - XI. ' For each n E Z, define
and call rn a regeneration point if
It is easy to see that, with probability 1, there are an infinite number of such regeneration points, both to the right and to the left of the time origin. We shall denote (R,,), n E Z , the ordeied sequence of regeneration points, with & 5 0 < R1as usual. The process N is constructed between Rk and Rk+l as follows: in any case, all the points of Nl will be counted as points of N. Now a point of N1.2 will be accepted as a point of N with the probability
The only problem is whether we can compute X(Tl,2,,) for a given T1,2,n. This is indeed possible if we start from Rk (for any Ic) because there will be no point of N1,2 for some time, and when we meet one, all the points of Nl provide all the past history necessary to compute X(TIt2,,) (see the (A,m)-assumption, and use (4.2.14)).
with acceptation probability T h e random acceptance rule (take P, &) framework if we given by (4.2.15)) can be translated inside the (f2,3, slightly modify it as follows: We are given a marked point process N2 with marks {Y,), compatible with &, N2 being Poisson with intensity X2 and {Y,) being i.i.d., independent of N2, uniformly distributed on [0, X2]. Define Nl and N1,2 by
Suppose the arrival process of a G/GI/l/m queue is of the type described above, and suppose that the stability condition p < 1 holds true. Let P be the probability corresponding to a version of the point process with arbitrary distribution of the past a t time 0. Then (4.2.9) and (4.2.10) are true, where Po and P represent the Palm and the stationary version, respectively, of the point process. This is due to the coupIing of all versions of the point process with the same intensity, and t o the fact that the Palm version has the same stochastic intensity on IW+ as the stationary version (see Chapter 1, 3 9.1). 0
with the obvious meaning for Tz,n the acceptance rule reads: accept if the correHere, for a given sponding mark falls in (XI, X(T1,2,,)]. With this framework, it is obvious that N constructed above is compatible with the shift {Of), and therefore stationary. Also it has the required stochastic intensity: indeed
4.3 Strong Coupling and Borovkov's Theory of Renovating Events Strong coupling is said to occur between the stochastic recurrent sequence {W,) = {w:) and the stationary sequence { Z o On), where Z o 0 = h(Z,[), if the random variable
is P o - a s . finite. For k
and therefore since the marked point process (N2,{Yn)) has the intensity kernel (see Chapter 1, 5 8.2)
3,N2'Y-
> 0, let
and let N(k) = {inf n
> -k 1 Wn(k) = Z o 6").
Strong coupling admits the following equivalent definition: '&
for any A E
e l Y
(4.3.3)Let N * '%f { Z o 8") if and only if
N(k). Strong coupling occurs between {W,)
n*is Po-a.s. finite.
and
Proof: T h e random variables N o and N * have the same Po-distribution. Indeed where we have used the fact that (w,t,y) -+ 1A(w)l(a,b1(t)~ ( o , x ( Q , , ) ) (isY ) p ( j r P t Y )Qg B measurable (observe that X(t,w) = X(0, Otw) where X(0, w) is ~ ~ ' ~ - m e a s u r a b lTherefore e). {X(t)) is the ~ , " 1 ' ~ - i n t e n s iof t ~N. But C " 7,"2l and Y X(t) is F'p-measurable, therefore {X(t)) is the 3:-intensity of
pO(N"
3 n) = PO(%(k)
= Z o o n , for all k
= PO(kVn+k(0)= Z, for all k
> 0)
> 0)
= PO(wn+ko 6-n-k = Z, for all k 2 0) = P'(NO
< n).
N. As for the announced coupIing construction, it uses the same ( R , 3 , P, Ot) framework, with N defined as above, and N' defined in a similar way, using the same marked point process (N2, {Y,)), only starting the construction from time 0 on, with a fixed history of N ' a t time 0. At the first regeneration point R1,N and N' will share the same points up to a time where they have a common history which makes their intensities equal (v;l(StN) = p(StNt)). From that time on they will have the same points and the same intensity.
0
(4.3.4) Strong coupling of: {W,) and { Z 06") implies their coupling. Proof: If strong coupling holds, then
98
4 Coupling
2 Stationarity and Coupling
(4.3.5)
99
Wn+,n= @(En$- . . + tn+m-~).
For instance, events of the type An = {Wn = 0 ) are renovating events of length 1 since, on An, Wn+1 = h(O,&). Borovkov's result gives a sufficient condition for a finite stationary regime of (4.2.1) t o exist and for strong coupling t o occur: (4.3.6) If the stochastic recurrent sequence {Wn) admits a sequence of reaovating events { A n ) ,n 2 0, alE with the same length m 2 1 and the same . associated function Qi, and if
then Wno9-" converges a.s. to afinite limit Z as n tends to co.The sequence { Z o 0") iatisfies (4.2. I ) , and {Wn) strongly couples with {Z 0 8"). Proof: We first prove that for all n (4.3.8) with initial condition Wo = 0 and with associated sequence (I,} i.i.d. and such that E E 3 , . . .), EOII]= m. It is easily checked that {W,) couples with the constant sequence equal to 1. However, strong coupling does not
PA,-^ n 8n+"A,+k-1 c
> I > m, and k L: 0, we have the inclusion
{w, o t ) v n
= Wn+k 0
-%
Indeed, on PAn-I
= Qi(tJb0-I,.
.. , ern-'-' 0
1 9
and similarly, on On+kAA,+k-~
O Q - " -= ~ SP(Eo8-I,. .. , < O B ~ - ' - ~ ) . Therefore, on the intersection of these events, Wn-r+m o F n= Wn+k-l+m0 . In view of the recurrence defining W n ,this implies
05Ml I...IM,
liY,-l+m+l
Thus, when denoting N the coupling timeof (W,) and { M , oOn), we obtain
pO(N _< n ) = P O ( W , '
= M,
= P'(w~+,
o
an) = po(Wno 8-"
@-n-k
0
<
= M,)
= M,, for aIl k 2: 0 ) = P'(N" 5 n).
= Wn+k-l+m+~ 0 9-n-k9
Since N 5 No a.s., the last relation implies that N = No a.s. Thus, in this case, not only coupling and strong coupling are equivalent, but in addition the coupling and strong coupling times coincide. We are now in a position to present the theory of renovating events for stochastic recurrences. Let m be a positive integer and @ be a measurable function, rP
<,
:
Fm-t E
( E and F are the spaces in which TiV, and take their values respectively). The event A, is said t o be a renovating event of length m and associated function @, for the stochastic recurrent sequence {W,), if on A,
9-" = h(Wn-l+m 0 Own, t n - ~ + m0 e-") = h(Wn-c+m o V n , o ) 0-n-k = h(Wn+k-lfm 0 9-n-k,
and by iterating the above calculation, we see that 0
.
8-" = Wn+k-(+m+j 0 e-n-k,
for all j 2 0.Taking j = l - m 2 0, gives (4.3.8). The inclusion (4.3.8) implies
We have B c Q B ,so that B is of probability zero or one (recall the assumption that (P0,6') is ergodic). Since P O ( B )> Po(A), we iilust have P o ( B ) = 1. 0 Let y be a set of random variables, and consider the sequences {w:), for all possible initial conditions Y in y. (4.3.15) If there exists a sequence of events {A,} compatible with the shift and satisfying the condition P O ( A o ) > 0 , a function @ and an integer m, such that, on A,, W: = @(<,, . . . ,&,+m-l), for all Y E Y , then there exists a stationary sequence ( 2 o e n ) , solution of (4.2.1), and such that for all Y E Y , the sequence ( W r ) converges with strong coupling to { Z 0 8").
and 00
k=O From (4.3.71, the quantity w
[n w
00
B-"B,,~] = PO k=O
n-m
k=O 1=0
tends to 1when n goes to m, and therefore, by (4.3.9), the increasing sequence of events 1% of?-" = W,+k o B - " - ~ , V k 2 0 ) tends to an event of probability 1 when n goes to oo.That is
Proof: Following the same lines as in the proof of (4.3.6), under the preceding assumptions, we obtain that (4.3.9) can be replaced by the stronger statement that
We see that with probability one, the sequence WqoB-q is eventually constant in q. In other words, there exists a finite random variable Z such that = Z PO-as. 4.31) lim WII o
where Y * is an arbitrary element of
y. The conclusion that
n-OD
Iim W: o Q-"
and
n-w
where Z does not depend on Y, follows immediately. The rest of the proof is as in that of (4.3.6). 0 emark 4.3.3 The last theorem can be used to prove the uniqueness of the solutions of (4.3.13) as follows: if X and X' are two finite solutions such that W: and w:' admit the same sequence of renovating events {A,} and the same associated function @, then in view of (4.3.15)
By letting n go t o oo in -n
= h(W,
0
8-", (5),
and by using (4.3.11) gives (4.3.13) 2 o 8 = h(Z, 0,
=Z
*.
since h is continuous in its first argument. This concludes the proof that { Z o On) is a finite solution of (4.2.1). This solution is reached with strong 0 coupling in view of (4.3.12). A sequence of events is said to be compatible with the shift if A, = P n A for all n 2 0. (4.3.14) If the sequence of events ( A , ) is compatible with the shift, the condition (4.3.7) is equivalent to P O ( A )> 0. Proof: Since BkAl+k = A,,
and therefore (4.3.7) implies Po(A) > 0. Conversely, let
B be the event
n The following converse to (4.3.15) holds: (4.3.17) Let {W:) be a (iR+)K-valued stochastic recurrent sequence with constant initial condition. If {W:) strongly couples to { Z o On}, where Z is a finite stationary solution of Z o o = h(Z,(5), then {W,") admits a 0-compatible sequence of renovating events of positive probability.
-
Proof: In view of (4.3.2), N o Po-a.s. finite implies that there exists a finite rn such that the event A = A. = { N * = m + 1) is of positive Po-measure. On this event, we have
:
for some deterministic function g obtained by iterating h. More generally, on the set A , = @-"A, we have
,"
102
2 Stationarity and ~ o " ~ l i ~ ~
4 Coupling
103
In particular, for k = n,
Wm+l(n)
en = WnO+m+l = g(tn,. .. ,(;nSm).
Thus { A n ) is a's-compatible sequence of renovating events.
Proof: Let 2 be the set of finite solutions of (3.1.2). For all Z E 2 , A,(v$) C A,(Z), since V E 2 2. Therefore, (4.3.15) can be applied with A, = A,(VZ) and y = 2. This in turn implies that for all Z , the stationary sequence {w:) couples with the sequence {Wflm) = { M , 0 On), so that MW = a.8. 0 In the renewal case, the condition (4.3.18) takes the simpler form: (4.3.20) If the stability condition E O [ ~ <]s E O [ r ]is, satisfied and if the R2valued variables (r,,,an) are i.i.d., then the condition P'[AO(VZ)] > 0 is satisfied if the random variable TO has an infinite support.
Proof: From (3.3.11), we know that PO[(V,")' = 0) > 0. This plus the finiteness of V," imply that there exists some finite x E R such that Po[(V2)l = 0 , ( V 2 ) j x, j = 2,. . . ,s] > 0. Using the independence assumption, we obtain
<
j-2
p0[(v:)' =g,(
v , )_< ~2:n , j = 2,. . .,sl k=O
2 p0[r0~ X ] P O [ ( V Z=) '0 ,
( v z <) x~, j = 2 ,...,s] > O . 0
Observe that if Y is an initial condition satisfying the condition Y 5 V z a.s. (for instance Y = 0 ) , then under the assumptions of (4.3.18), the convergence of the sequence (W,(Y)) to the unique stationary regime { M , 0 On) takes phce with coupling. Indeed, denoting by An(Y) the renovating events (4.3.17) associated with the sequence {W,(Y)),we obtain by induction so that that the sequence { V g oBn) is a stationary upper bound of {w,(Y)), A,(V:) c A n ( Y ) . This inclusion in turn implies that the renovating events A,(Y) satisfy condition (4.3.7). This result extends to more general initial conditions (see the bibliographical notes), using the same method, though with more elaborate stationary upper bounds.
. .
Let A , ( V s ) be the renovating events (4.3.18) associated with the maximal solution W n = Vz o 8" (see •˜ 3.3).
with the shift
The setting for the G/G/1/0 queue is that of 5 1.1 (the G / G / l / m queue) except that there is no waiting room, and therefore any customer who finds a busy server upon arrival is lost (i.e. he is rejected and disappear). Therefore there is a t most one customer in the system, and the equation for the workload process is
whereas the workload sequence satisfies the equation
Within the Palm framework, Loynes' problem consists in finding a Po-a.s. finite non-negative random variable Z such that
where Po = Pf;:and 8 = OT,. A typical trajectory of the workload process is illustrated in Figure 5.1.1, where the tagged arrivals are not accepted in the system.
We immediately check that ( P o , @ )is ergodic, and that Po is &invariant. Define the random variable u and T by
so that, when adopting the notation
the basic equation (5.1.3) reads
Example 5.1.1 Take ol = 1 , 02 > 2. There is no solution of (5.1.4). Indeed if Z1 = 0, then from (5.1.4b), Z2 = ( q - 1)+ = 0, and therefore, going back to (5.1.4a), Z1 = (a2 - 1)+ > 0, a contradiction. If Z2 = 0, (5.1.4a) gives 21 = (u2 - 1)+ = u2 - 1, therefore, from (5.1.4b), Zz = (uz - 1)+ > 0, another contradiction. Thus, necessarily Z1 > 0 and Z2 > 0 (This means that all customers are rejected). But then, from (5.1.4.b), Z2 = (Z1 - l ) + , and taking the latter expression in (5.1.4a), Z1 = ((Z1 - I ) + - 1)+ which is not possible if Z1 > 0. 0 Example 5.1.2 Take both 0-1 and in the open interval (1,2). Then the system (5.1.4) does not have a unique solution. Indeed
and
.I A typical trajectory of the G/G/1/0 workload It is intuitively clear that no problem should arise for proving the finiteness of 2.However a new problem arises, as demonstrated by the following examples. We have situations where ( a ): Z does not exist, and (p) : Z is not unique. These examples are constructed on the following space
are both solutions (they correspond to rejecting every even customer and 0 every odd customer respectively). In 5 5.2, we simultaneously address the existence and the uniqueness problems, by finding sufficient conditions for renovating events to exist. In 5 5.3, we then show that existence is always granted if we accept t o work on an enriched sample space containing more than just the input process {(on, T~)).
106
2 Stationatity and Coupling
5 Stability of the G/G/1/0 Queue
Renovating events of length 1 are provided by sets of the type (5.2.1) A, C (W, = 0). (5.2.2) If the condition
This shows that sequence {W:) admits {S, = 0) as renovating events of length 1, where S,, = S o On. Therefore, from (4.3.6),W,"o 8-" tends to a finite limit 2 , which is a solution of (5.1.3), and {W:) couples with ( 2 oBn). 0 Uniqueness was obtained in (5.2.2).
Remark 5.2 .I Consider the case when the random variables {on,-7,) are Po-associated (see 5 3.1, Chapter 4, for the definition of association). This is .for instance the case if each of the sequences {a,) and (7,) is i.i.d. and if these two sequences are independent. Under this assumption, the condition (5.2.3) can be further simplified using Property (3.1.5), Chapter 4, which implies that .
holds, then (5.1.3) admits at most one solution. Proof: Let
The random variable S is finite if EO[a]< oo and 0 < EO[r]< CQ (see 5 6.1 below). Let us prove that if Z is a finite stationary solution of (5.1.3), then Z 5 S a s . For this, we show that the event (2 S) is $-contracting and of positive probability. To obtain S , we take the largest (for I -1) among the workloads left S o 6 and since by customer I at time 0. Therefore, dearly (S - T ) + . ( a - r ) + 5 S o @ ,we find that on { Z < S ) ,
<
<
107
Therefore, in view of classical results on infinite products, (5.2.3) is satisfied if
<
and which completes the proof of the 9-contraction. For proving that POIZ <_ S ] > 0, it is enough to show that FOIZ = 01 > 0. Since Z satisfies (5.1.3), the assumption P o [ Z = O] = 0 implies
which in turn implies E " [ Z 0 6 - Z] < , a contradiction with Lemma 2.3.1. Therefore, for any finite solution Z of (5.1.3), the sequence {w: = Z o o n ) admits A , = ( S o 9" - 0) as a stationary sequence of renovating events of length 1 (since on A,, W: = 0). From (4.3.15), it suffices to show that P O ( S= 0) > 0, in order to prove the uniqueness property. But this is a direct consequence of (5.2.3). C1 (5.2.5) Under the condition (5.2.3), (5.1.2) admits a unique solution which is compatible with the shift and which is reached with strong coupling by the
Proof: For all n
2 0,
In the renewal case (i.e. under P o , the sequences {a,) and (7,) are independent and each sequence is i.i.d), the last condition will be satisfied whenever the random variable a is integrable. Indeed, in this case
zz,
Po[% < tl = E0 [N(O,t ) ]. where R(t) is the renewal function R(t) = We obtain (5.2.7) when using the fact that R(t)/t tends to X as t goes to oo (Renewal Theorem). Therefore, under the above stated renewal and integrability assumptions, if PO[a<_ T ] > 0, then (5.2.6) is satisfied and (5.2.3) holds. 0
110
5 Stability of the G/G/I/O Queue
2 Stationarity and Coupling
n > -m, and when letting i vary over N. y construction H ~ ( #~ 0.) In addition, C w ( N ) E [ O , n ] i f w E B,, so that H,,,(w) is a finite set owing to (5.3.3).Using the relation
we also obtain that H,+l(w) C H,(o).
Since L B - ~iswa bijection from H ( F 1 ( w ) ) into H(w), the event ( i E H(w)) is equal to the event (3 j E N I L e - ~ , ( j )= i , j E H(fP1w)), which completes -0 the proof of the 8 invariance of P . Construction of a Stationary Solution. Define
Hence
(5.3.11) v ( w , i ) = . . Since Lmf' oB = GoLm, Hm+loB = L(N,), and therefore card (&+I 08) 5 card (If,,,).Letting m 1 m, we see that card ( H o e ) _< card (H). Therefore, since (Po,8) is ergodic
111
Since a o 8-i
- ci=l itoFi
- x;=,T
0
T
o oak)+,
Pk> 0 when i
E H(w),
v on 3 by if i # 0, otherwise.
i # 0,
(5.3.8) card H(w) = constant, Po-a.s.
--
-0
-
Let us check that
We are now in a position to construct the enriched space (W, F, P ,8) defined by .f2 = {(w,i) E 0 x
--
N 1 i E N(w)),
-
First case : Lw(i)= i + l , i # 0. Then, Wo6 = W(B(w),L,(z)) = w(B(w),i+ I ) = TOO-' -xizo Since Lw(i) = i + l , a06-'-C;=~ r0Pk> 0 and a fortiori uoO-'-C~=, T O B - ~ > 0. i.e. W(w,i) > 0. Hence, ~ + U . ~ ~ ~ = = ~ ) - - T W - T = T O ~ - ~ - ~ ~ = ; T O $ - ~ - T = w -o ~- .
F = trace on z o f F@P(I??), where P(N) denotes the set of subsets of N, and -0
(5.3.10)
P (A, i) = EO[~A~~;)(W)], B(w, 1:) = (B(w), 13, (i)).
--
--
is a o-finite measure. on (f2.F).3 is an automorphism on ( 0 , F ' ) . To show this, it is enough to prove that Lw : H ( w ) --, W ( B ( w ) )is bijective. Lw is clearly surjective. It is also injective since card (ff(w)) = card H(B(w)). Define the mapping f : 4 0 by f (w, i) = w. We have Po = --0 P o f-I - - P ,-B) is an enrichment of (0,F, and f 030f = 8. Therefore, ($2,P,-0 P o , 6). Let us show that 7 is g invariant i.e. :
-'
l ~ ~ ~ i ) ( w , j ) @ ( w ,=j )
Second case : L,(i) = d , i # 0. Then, IT08 = ~ ( o ( w ) , o )Since . Lw(i) --= O , ~ O B - ~ ~ ~ = 5 0. ~ Since = , O i E&H -( w ~ ) ,= ~ o08-~-~~., TOP' > 0. 6-i 6-k 5 0. ~ h u s , Therefore, W + r . l ~ ~T-- = ~ ) w - T = + ~ . l -~T)+, =~0 = W 0 6.
3-
(v
zLzo
+ l , i = 0. We have L,(i) = 1 and w(8(w), L,(i)) = W($(w), 1) = (a o B-I - T o 8-I) o B = a - T. Since i = ~ , W ( w , i )= 0. Therefore w + 0.1 {v=Ol - T = a - T . Now L, (0) = 1 also implies that u > T, and therefore (W+ 0.1 {F,,) - r ) + = W o 8.
-
case : Lw(i) = i
1 ~ ~ { ~ ) ( 8 (G,(j))d~O(w, w), j}.
Indeed, the right-hand side is by definition
or, in view of the Q-invariance of Po :
F o u r t h case : C,(i) = 0 , i = 0. ~hereforeV(e(w), t,(i)) - = ~ ( B ( w ) , o=) 0. But C,(O) = 0,a - T < 0 and w ( w , i ) = 0, so that W a . l { ~ , ~- )7 - = a-T<0. 0
+
eing Systems ,
.
This section contains a few important examples. In the first subsection we elay system G / G / m , which is rather atypical in stability theory. In the second one, we show how the 'raw' G / G / l / m model can be augmented so as to represent priorities.
The input (a,,~,) , n E Z is defined as in 5 1.1.The system has an infinite reservoir of servers, so that any customer is immediately attended. Therefore, customer n arriving a t time T, leaves a t time T, +a, (service is provided a t unit rate). The state of the system is described by the random element R, E R*, where R, = (Rk,R i , R:, . . .) is an ordering in decreasing order
of the residual service times a t time T,. In view of the assumptions on the input, we have
where R has the following entries properly reordered
Fig. 6.1.3 The pure delay system
where f ( t ,o ) is 1 if t < 0 and o > -t, and 0 otherwise. By Campbell's formula ((3.3.2) of Chapter I), and formula (3.1.4) of Chapter 1,
i.e., since X = l / E O [ r ] ,
(6.1.3) ( ( ao Bi - /Ti/)+; z _< -1). The number of non-null coordinates of R is the number X o of customers in the system just before the arrival of customer 0 (see Figure 6.1.1). (6.1.4) If T and o are integrable,
and therefore (6.1.6) holds. More generally, denoting X,(t) the number of busy servers a t time t with a load larger or equal t o r > 0, we obtain 00
and therefore, i n this sense, the G / G / m system is 'stable'
(6.1.8)
E[X,(O)]= X
(1
- pO(o5 t ) ) d t .
roof: We prove that
where P is the Bt- stationary probability associated to Po aid where.X(t) is the number of customers in the system a t time 1. Indeed (6.1.6) implies (6.1.5) in view of the results of $ 7.1 of Chapter 1. ut
0
isciplines in G / G / l / m : the Vector of Residual Services This section focuses on service disciplines in the general G/G/l/oo model of 5 1. The stability condition EO[cl-] < EO[r]is supposed t o hold, and therefore there exists a unique finite stationary load W. We construct a state richer in information than W , which features in particular the service discipline (LIFO, FIFO, SRPT, . . .).
114
6 Other Queueing Systems
2 Stationarity and Coupling
115
Let S be an infinite vector of non-negative numbers, i.e. S E Ry, and only the I first coordinates of S are non-null, where I is random. S is the vector of residual service times of the I customers present in the system just before time 0. In position I , we find the customer being presently served, in position I - 1, the next customer to be served, etc. When customer O arrives, this possibly changes the priorities. The priority vector a t time O+ is S f , where
In the general case, the random permutation 4, is used at time T,, and for all S E Ry , (pn(w,S) = do(Onw,S). For the last two disciplines, the arrival of a new customer creates a modification of the order of service which depends at most upon a and S. There exist more complex disciplines for which 6 depends upon the whole sequence (a o Pn, S o OPn, n 2 0). We shall only consider disciplines which depend upon
where e; is the i-th vector of the canonical base of RN,and 4(w) is a permutation on RN involving only the I ( w ) f 1 first coordinates. The function q5 describes service disciplines in a way which is best explained through examples.
where
First-In-First-Out,
Such disciplines will be said to be admissible. For each admissible discipline 6, there corresponds a unique stationary state S = Sd. The actual construction uses the construction points as follows : (6.2.8a)
S&,,= 0, if n is a construction point (W o 8-" = 0),
Last-In-First-Out wit
There is no preemption i.e. the last customer arriving does not interrupt the service of customer being serviced. n-First-Out with Preem (6.2.4) $(S1, S 2 , . . . ,s',s'+~) = (S',S~,. . .,s',s'+')
= identity.
aining-processing-~ime. SRPT is a priority discipline with preemption, where 5' = ( 9 , S , s f , , , ...) always satisfies the relation SQ S2 2 . . . 2 S I . We define (u, S1,S2,.. .,s'), (6.2.5) (S(S f t r e ~ + l )=
identity, (S',
.. . ,Sj-l,
a, S j , . . . ,S')
< <
if S t a, ifSr>u, if Sj u < Sj-1,
o r t e s t - P r o c e s s i n g - T h e . It is the same discipline a s SRPT, but without preemption. The only change with respect to S where, for SPT, 4 = (S1, S2,.. . ,s'-' ,0, S').
A discipline is said to use no information on the service times if the permutation 4 does not depend on the actual value of the coordinates of S , as it is the case for the first three disciplines. r all the above disciplines, the permutation 4 is 'deterministic'. The RANDOM discipline provides an example where 4 is a function of both S and w.
The last equality expresses that the residual service times are consumed at unity rate, in the order of the customers (see Figure 6.2.2). We are now in a position to construct the time-stationary state. Let P be the stationary probability associated with Po. Let 4 be an admissible service discipline. From the sequence of marks (S6,,,n E Z) and (S&,n E Z ) we can construct the process of residual service times (S+(t),t E R) by and for 1 E [Tn,Tn+l), n E Z
This construction must be shown to be P-consistent, i.e. we must show that the evolution dynamics are respected, i.e. But S4(T;) = S*,, in view of (6.2.9b) and (6.2.8c), and S4(Tn) = ,,s: definition (6.2.9a) and therefore (6.2.10) can be reduced to
by
Since this is Po-as. true, (6.2.10) is verified in view of the invariance results of •˜ 7.1, Chapter 1.
vacation
vacation
starts
Fig.6.2.2
(~:,+)j=
O
for j = 4 , 5 , 6 ,...; s;,, = O for j =4,5,6,
u e u e s with Vacations
,
The corresponding system. is a G / G / l / m queue in which the server takes vacations (during which no customers are served) in the following two situations: (a) the queue just became empty; (b) upon return from vacation, the server finds the queue still empty. T h e sequence of vacation times is assumed to be independent of the input sequence; we denote it { V k ) k > l ; the queue starts with an arbitrary workload a t time 0. efore considering this queue, we shall consider the following abstract construction, which is closely related to the original problem but must be interpreted, as we shall do later. We suppose that the G / G input is stationary ergodic, with traffic intensity p < 1, and we let (W(t))tE* be the associated stationary workload for a system with one server and infinite capacity of the waiting room). Let now fi be a s t a t i o ~ a r ypoint process with finite intensity "X We shall "distribute the points of N in the idle periods of the queue" as Figure 6.3.1 shows. The point process so obtained is now called N v . Each point of N v will be taken to be the start of a vacation, the length of the vacation being the .% .
..
Fig. 6.3.1 Distributing the points of
ends
5
time separating this point from the next point minus the length of the busy period in between, if any. Now, we construct the process {Wl(t)), t E I$ as indicated in Figure 6.3.1, by considering that a start of vacation represents the arrival of a virtual customer, with virtual required service equal to the duration of the vacation, and then defining (Wl(t)) as the workload process relative to the superposition of the streams of the original customers and of the virtual customers. The reader is invited to prove formally that {W(t)), {Wl(t)) and N v are jointly stationary. Consider now the case when the input process is not stationary but couples t o a stationary ergodic i 9 u t process, so that, in particular, the non stationary workload process. {W(t)) couples after a finite stopping time to the stationary workload { W ( t ) )above (see 3 4.2). If in a addition, the point process with time sequence {Vl . . . Vn)n21 couples strongly to the stationary point process fi above, then clearly, the total workload process (WI (t)) taking into account the original customers and the virtual customers; couples after a h i t e time t o {Wl(t)) above. In this sense, we can say that this G / G / l / m queue with multiple vacations has a unique asymptotic stationary regime.
+ +
118
2 Stationarity and Coupling
The above assumptions of coupling are satisfied in the 6 1 / 6 1 case if the arrival process is a renewal process with spreadout distribution (see S. Asmussen, already quoted), and the vacation sequence also. a
ernark 6.3.2 For the FIFO discipline, the workload process receives the following interpretation: M.i(Tn-) is the waiting time of the customer arriving at time T,. 17
7 Stability o f Queueing Networks via Coupling
119
from the dominated convergence theorem. When using Neveu's exchange formula, this condition rewrites:
or equivalently, if pl = XEL (a)denotes the traffic intensity of the first arrival process and pz = PEL(@)>- 1 that of the second one, pl + pz 2 1.
+
In this system, there are two streams of customers arriving to a single server queue with infinite waiting room. Customers of both classes are served under a global FIFO discipline. An additional rule states that a customer of one class can only be served if there is at least one customer of the other class in the waiting room. If not, he has to wait till the arrival of the next customer of the other class. Let M and N be two 6 / 6 input type marked point processes defined P, &), with the usual ergodicity and integrability assumptions. The oh (Q,3, points of M are denoted {T,) and those of N {S,). Similarly, a will denote the service time of customer To of M and fl that of SOin N. Let Wn be the waiting time experienced by customer T,,that is the total time between its arrival and the time it starts being served. One easiIy checks that {W,) satisfies the stochastic recurrence
where 7, = Tn+1 - T,. AS it is easily checked, the technique of Remark 4.2.1 applies, when taking the Palm space of M as ieference probability space. Let M , (resp. M,) denote the associated Loynes' sequence (resp. variable). The relation
follows from the non-decreasingness of (M,). Assuming that M, is P& a.s. infinite (it is necessarily either a.s. finite or a.s. infinite because of the ergodic assumption on the G / G inputs), when letting n go to infinity in this relation, we obtain that
Thus the.queue is stable if p = pl pz < 1. One easily checks that it is unstable if p > 1. So the stability region is the same a t that of a queue with two input streams but where customers do not have to wait for customers of the other class!
7 Stability of
ueueing Networks via Coupling
7.1 G / G / l / m Queues in T a n d e m Consider a network of J G / G / l / m FIFO queues in tandem, that is, B The first queue is fed by'some external input stream, which is assumed to form a stationary point process N on the probability space (52,FlP o , & ) , where ( B t ) is ergodic; e The output of queue j is the input of queue j f 1, j = 1,J - 1. The point process N = C ST, is assumed to be simple and to have a finite intensity. The service time of eustomer 0 in queue j, is a lW+-valued mark a3 associated with To.It is assumed that these marks are all Po integrable. Let (0,P ,Po,8) be the Palm space of the external input point process. Let W, = (WA, . . . ,W:), where W i is the waiting times of the n-th customer to be served in queues j E (1,. . . ,J). (7.1.1) If E [ a j ]< E [ T ] ,j = 1,. ..,J , then (W,) couples with a uniquely defined and finite stationary sequence {W 00") which does not depend on the initial condition.
Proof: The proof is by induction on j. The induction hypothesis states that { W i )couples with a stationary sequence (WJo8")which does not depend on the initial condition, and that the inter-event times of the output process of queue j couple with a 8-compatible and integrable sequence. The induction assumption holds true for j = 1, in view of Remark 4.2.2. The stationary sequence with which (Wh) couples is merely the Loynes' sequence associated with the external input stream and the marks o i . Assume the property holds for queue j. Then the inter-event times of the input process to queue j + 1 couples with a 0-compatible and integrable sequence, and the hypothesis cl holds true for queue j + 1 in view of Remark 4.2.2.
Consider a network of J single server queues with infinite waiting room capacity. Customers arrive t o this network following a stationary point process N, defined on the probability space ( R , F , P , O t ) , where (Bt) is ergodic. This point process admits the marks (r,) = {roBr, ) and (0,) = (00 BT, ), where r = ( r 1 , r 2 , . . .) is a (1,. . . ,J) U {O)-valued sequence which describes the route of customer 0 through the network. Each r is of the form r = ( r l , r2,. . . , T ' , O,O,. . .), where the 1 first coordinates belong t o (1,. . . ,J). This sequence describes the sequence of queues to be visited by customer 0: first r q s visited; when customer 0 completes his service there, he is routed t o queue r2 an so on; after he has completed in queue r', customer O leaves the network. T h e random variable 1, which describes the total number of queues along the route of customer 0, is assumed to be finite. a = (a1, u2, . ..) is a &-valued sequence which describes the service requirements of customer 0 a t the successive queues of his route. The general question is the following: if we specify the service discipline (for instance FIFO a t each queue), under what condition does the network reach a stationary regime? There are no general answers t o this question. Known results are relative to specific probabilistic assumptions (e.g. independence) or specific service disciplines. The aim of this section is to study a particular discipline for which coupling arguments can be used under the preceding general statistical assumptions. This discipline is based on priority class$s. A customer who visits the mt h queue of his route is said t o be of class m 2 1. The priority rule in each queue is the following: o Customers of class m have a preemptive priority o y r customers of class m + l , m + 2 , ...; D Within each class, customers are served on a FIFO basis. We denote pk the mean value of the workload brought to queue k per unit a t is, (see Example 3.1.1, Chapter 1)
enotes expectation with respect to the Palm measure of N, and X is the intensity of N. Let Wklm(t) denote the workload of customers of class rn in queue k at time t. T h e main result of this section is the following property: for all k = 1,.. . ,J, then for all m 2 1, the random process Lm, . . .,W Jim)) couples with a stationary process {WmoOt), - W m ( f ) ) admits a finite stationary and the total workload ( ( t ) ) gf regime (W o &), W E RJ.
Proof; In the proof, P denotes the stationary probability of N. If A is a Btcompatible point process, Elk denotes expectation with respect to the Palm probability of A. All point processes t o be used are defined on ( R , F , P,Bt), and admit marks in ((1,. . . , J } U {0)lNx ( & l N . If A denotes such a marked point process, its points and marks will be denoted T(A), ,r(A), and a(A), respectively, or simply T,,r, and a, when no ambiguity is possible. Let Aklm (resp. ~ ~denote 1 the~ arrival ) (resp. departure) point process of customers of class m t o queue k. For all k, the marked point process A k l is defined by
This point process is &-compatible. Its intensity is
and
E ~ [a'] u = EO[al1 r1 = k]. In view of the preemptive nature of the service discipline, customers of class 1 are not affected by customers of other classes, so that if the traffic intensity
is less than 1, then the workload process {WkJ(t)) couples with a uniquely defined 0t-compatible workload process P-a.s. Since the condition pk < 1 implies pkl < 1, we see that the above coupling property is satisfied, so that the departure process Dkll defined by
couples with a uniquely defined &-compatible point process ZkJ.In this last definition, we take Vn = Wk~l(T(Ak*l)n+), the workload just after the arrival of the n-th customer of Akpl, which coincides with the sojourn time of this customer since the dgcipline is FIFO within each class. In view of the results of •˜ 5.4, Chapter 1, Dkll has the same intensity as AkJ. Similarly, in view of the results on delayed point processes of (5.4.3), Chapter 1,
The point processes Ak,2 are then defined as the superposition
122
Thus, sity of
2 Stationarity and Coupling
.Zkp2
8 Stability of Queueing Networks via Recurrence Equations
P-a.s. The intencouples with a Bt-compatible point process 2k*2 is
In addition, the traffic intensity
pkv2
of this point process is
123
are independent, i.i.d. and with a distribution that is absolutely continuous D with respect to the Lebesgue measure. Remark 7.2.2 Because p k = pklm < 1, queue k with an arrival pro+ cess equal to the superposition of the point processes ( A k ~ m ) , 2admits ~ a stationary regime, which is characterized by the workload process (Wk o Bt). If the random variable 1, defining the maximal number of queues visited by customer O is bounded, we easily chek that the total workload process 0 { W k ( t ) )= { C r n L 1W k t m ( t ) couples ) with { W k0 &).
8 Stability of Equations
ueueing Networks via Recurrence
8.1 Finite Capacity Queues in Tandem with Blocking
Consider a network of 3 FIFO servers in tandem. The first server has a waiting rooms of infinite capacity and is fed by an external arrival stream, which forms a stationary and ergodic point process with the usual properties. The basic probability space is the Palm space of this point process. There are no intermediate waiting rooms between server j and j 1, 1 5 j J - 1, and a customer having compjeted its service in server j is blocked there as long as server j + 1 is not empky (this is the so-called manufacturing blocking mechanism). Note that in this finite capacity queueing system, no customers are lost, as it was the case in the system considered in 5 5. More generally, finite capacity queues fall into two categories depending on whether a lack of space provokes a loss or a blocking. The J-dimensional mark a , = (a:, . . . ,a:) is supposed to be associated with the n-th point, denoted T,, of the external input process. The mark a: is the service time of the n-th customer to enter server j (who is also the customer who entered the first queue at time T, in view of the FIFO assumptions). Let Y J E R denote the time when server j gets free of all its initial workload. For n >_ O and 1 5 j, k <_ J , let
+
The induction assumption is now that for all k = I,. ,: J, the point processes A k ~ m couples with a f&compatible point processes Akbm,with intensity
and with traffic intensity brought to queue rE equal to
Using the results of Examples 4.2.1 and 4.2.2, together with the fact that
we obtain that PVklm(t)couples with a uniquely defined Bt-compatible workload process. This allows us to construct a Bt-compatible departure point process 6 k l m , with which Dksm couples. This and the same arguments as above allow us to prove that the property holds for m 1. 0 emark 7.2.1 In what precedes, we should check that the involved superpositions have no common points so as to get simple input point processes at each step. This property will for instance be satisfied if the service times
with the convention that
Xik
<
= 0 for all j > k, and
+
Denote by quantity
D; the time when customer n leaves server j, and by W i the
which represents the total amount of waiting time of customer n between its arrival time in queue 1 and its departure time from server j. (8.1.1) The variables Wn satisfg the recurrence equation
-
(8.1.2)
max ( y j - $ , ~ j - ~ ) + , {lljlk+l) max ( w ~ - ~ + I ~ {l<.j
for n = 0;
- ~ - f-oTr n~> 0- ,~ ) + ,
8.2 Existence of a Stationary Solution T h e stochastic recurrence (8.1.3) falls in the class (4.2.1), i.e. Wn+l = h(Wn, I,), where the function h is non-negative, continuous and coordinatewise non-decreasing in its first argument. Therefore the sequences {Mk), 1 < k < J, defined by
where w ~ +YJ+l G = -co by convention. Proof: Since server 1 gets free of customer n , n 2 0 (resp. its initial workload) a t DA 0, (resp. DLl = Y'), customer n + 1, n 2 -1 starts its service in server 1 a t time Tn+lV D; and completes it a t time (T,+l v DA) + Since server 2 gets free of customer n (resp. its initial workload) a t D: (resp. 05, = Y 2 ) ,customer n + 1 , n 2 -1 will hence leave server 1 and start its service in 2 a t time
>
More generally, if customer n -t 1 leaves server k - 1, k < J a t D;+:, then it + a:+,) and leave server k at will complete its service in server k a t (0:;:
whereas for server J ,
are non-decreasing in n, and if we denote by M,!& the limiting value (that is, the Loynes' variable associated with (8.1.3)), then { M , o On) is a stationary solution of (8.1.3) (see $ 4.2). it is easily shown that M, is the minimal stationary solution of
T h e derivation of the stability region requires a few technical lemmas. (8.2.3) For all j = 1,.. . , J , the event {M& = co) is 6 invariant.
Proof: For all j , we have j E ? r j = { k s.t l k s j# -03). 0 (8.2.4) Either PO[nj=l ,...,J{M& = co)] equals 1 or PO[nj=l ,...,J I M & < oo)] equals 1. Proof: Both events are obviously @-invariant.If P O [ n j = l.,. . , J { M L < oo)] is not 1, it is hence 0, so that POIM& = co] = 1 for a t least one j = 1,. . . , J , in view of (8.2.3). But since {j- 1,j , j + I) C d (at least for j # 1,J),
+ d+J Dn+t = (~nJ7: J
Simple substitutions based on the last three relations imply
+
k
Dn+l = (Tnj-1 A::;:,) V
+
*_
max (DA ~3,':~),n 2 -1, (lS3Sktll
with the conventions D;+' = -oo, DL, = Y3. Equation (8.1.2) follows by 0 + from both sides of the last relation. subtracting Let
x::~
1;
{ML+~
where the undefined events like = oo) are R by convention. Therefore P O I M i = co] = 1 implies POIMg" co] = 1 and pOIM&-l = oo] = 1. T h e property that PO[nj,l,...,J{M& = co)] = 1 follows immediately. 0 T h e following expression of M, will also be needed later on: (8.2.5) For every n 2 1 and j = 1 , . . . , J ,
ifl<jlk+1;
-oo otherwise.
(8.2.6)
Equation (8.1.2) rewrites (8.1.3)
w:+,
= max(M',: 3
+ itk- T~)',
n 2 0, k = 1 , . . . , J ,
M:. = rnax ( H A l$m j n
-
r o (7' p=l
where
where the maximum now bears on all j = 1,.. . ,J .
Proof: T h e proof is by induction on n. For n = 1, (8.2.6) is obvious. Suppose it holds for some n 2 1. Then, we obtain from equation (8.2.1) that
9 The Saturation Rule
131
<
For all m n E N, let Xlrntnl(N)be the time of the last activity in the network, when this one starts empty and is fed by the [m,n] restriction of N, namely the point process ( ~ ) , g < , . We assume t o b e given a set of -+ E, such that: functions {f)), fi : R' x KK'
for all n , m and N . We assume that the functions lowing properties hold for all N: '(1) (causality): For ail m 5 n,
This 'engineering rule', which we will refer t o as the saturation a l e , does not hold for all systems (see the examples below). The aim of the present section is t o set a natural framework, which involves two main properties called separability and external monotonicity in which this rule can be rigorously proved when dropping the Markovian assumptions and replacing them by standard stationary ergodic assumptions, namely the arrival point process is a stationary ergodic marked point process of finite intensity. For any queueing system within this framework (to be defined below), we will denote Xn the time of the last activity t o take place in the system, whenever one starts with n customers, all arrived a t time 0 in an empty system. This notion of time to inactivity, turns out to be the adequate way of implementing the saturation idea for non-Markov systems. The main result is then: (9.1.1) The sequence (Xn) satisfies a S U N : (9.1.2)
xn = $0) lim n n
a.s.,
for some non-negative constant y(0); this constant will also be finite if the input marked process satisfies natural integrability conditions. Whenever the intensity of the input process satisfies the condition X < 7-l(0), then the system is stable, whereas it is unstable i f X > y-q(O). . . Stability her6 means that the time t o inactivity when the system is fed by the restriction of the point process on ( - m , t ) admits a finite steady state regime. This usually implies most standard acceptations of stability. e Barnework. Let N be a marked point process with points {TnInEZ and marks ( [ n ) n E ~ , where tn E (K,K). This point process is not assumed t o b e simple (nor t o be stationary a t this stage). We only assume that Tn j Tn+l, for all n. We shall use the notations rn for T,+l - T,, c N for the point process {Tn c) and cN for the point process (cTn), where c E R In what follows, we shall not adopt the usual rule of renumbering, so that the n-th point of N % c will be T, c by definition.
+
+
+
(2) (external monotonicity): For all m
fn
are such that the fol-
i: n ,
whenever N ' %f (TA) is such that TA >_ Tnfor all n; (3) (homogeneity): Vc ~c E, V m _< n
-.
X[m,n](c f N ) = X[m,n] + C; (4) (separability): If, fpr all m
< 1 < n , XIm,ll(N)5 x+l,then
+
1 In words, property (4) simply states that if the arrival of customer I takes place later than the last activity for the arrival process [m,El, then the evolution of the network after time is the same as in the network which 'starts empty' a t this time.
The Sub-additive Property. Let
only. In particular, Note t h a t Z[,,,](N) is a function of (tn)and {71)m51sn-1 Zn(N) %f ZL,,nl(N) is not a function of {h). (9.1.5) Under the above conditions, the variables Xi,,,] and Z[m,nlsatisfy the internal monotonicity property: for all N
Proof: Consider the point process N' with points:
Tjl =
{
Tj-2,-,(N) Tj
for j < m - 1; for j 2 m .
Since the [m,oo]restrictions of N and N' coincide, X'[,,,](N) = X'[m,nI(N'). The separability assumption implies that Xim-l,nl(N') = Xlm,nl(N').Finally, the external monotonicity implies that X[rn-l,nI(N') X[rn-l,nl(N).
Note that we then have
<
(9.1.7) Under the above condition?, (Z~m,,l) satisfies the following subadditive property: for all r n 1 < n, for all N
Let A be the event A = {Iim ZI-n,O1= m). (9.2.3) Under the foregoing assumptions, PO(A)E (0,l).
Proof: Introduce two auxiliary point processes N1 = {T)) and N2 = {Tf) defined by
Proof: Note that BA = (lim Z[-n,-ll = m). But owing to the sub-additive property, Z[-,,-I] ZI-n,ol - Zo. This and the integrability of Zo imply that @ A2 A. 0 For all O 5 c < oo,the sequences
<
>
Tj Tj
+ Z[,,I~(N)
for j for j
< E;
>l . and
and
T; = Tj - Zim,[](N) for j 5 1; for j > I . Tj SO T: = Tj framework
- ZLrn,rl(N),for all j. Then, using assumptions
(1)-(4) of our
satisfy all the monotonicity and sub-additive properties mentioned above. In addition, for all n (a) ZI-n,-ll(cN) is decreasing in c; (b) X[l,nl(cN)is increasing in c. We have (9.2.4) For all c 2 0, there exists a non-negative constant y(c) such that lim Z[-n,-l]fcN) = y(c) a.s.; n y(c) is decreasing in c while y ( c ) f cA-' is increasing i n c. The main result on the stability region is: (9.2.5) If limZ~-n,ol -+ m a.s., then Xy(0) 2 1. If Xy(0) > 1 , then lim Z[-n,o~-+ co a.s.
Assume that the point process N is stationary and ergodic, and take its Palm space (R, 3,P o , 0 ) as reference probability space. Assume that: def
EOT, - A-%
w,
EOZn< w.
Then Kingman's sub-additive ergodic theorem (already quoted) gives: (9.2.1) There exists a finite and positive constant y such that the a.s. Limits
old Po-a.s.
Proof: We first prove the second assertion. Let Q be the point process with a31 its points equal to 0: Tn(Q) = 0 for all n. For n fixed, let Nn be the point process with points Ty = T-n - To, for all j. Then
+
and Iim inf Z[-ntO1(N)2 y(0) - A-' > 0, n hich concludes the proof of the second assertion.
2 Slationarily and Coupling
134
9 The Saturation Rule
now prove the first one. For each integer 1
16 = min(n 2 1 :
> 1, let Kt be the random
Z[-n,O~(N) 2 Z -To},
which will be Po a.s. finite if ZI-n,ol tends to oo. Rom the sub-additive property, for all n, 1 2 1
z[-a,(]< 2,-n,o] + ~ [ I J 5] Zi-n:~] +
c
135
is Po-integrable. By making use of the relations Z[-,,q =* Zl-n-l,O1 ZI-n-,,ol I.Zf-n,ol and E"Z[-n-~,ol < oo,we obtain from (9.2.6) that
0
el,
1
Zi,
i=l
is a a . finite 'fdi all I, the right-hand side of the last equation tends to Il;ll(Q) - IX-' as n -t oo.Therefore
where the random variables Zi = Zo 0 Qi do nzt depend on the inter-arrival times and are integrable. For all n 2 1, let N n be the point process with points
... Tj"= Tj - To
for j _< 0; Z[-n,o](W for j 2 1
for all I. Finally, when letting 1 go to infinity and when making use of (9.2.4),
and let .@" be defined by
-
Tj" = Z[-n,ol, for all j. Thus if X$O)
Then (2)
<
(X[-n,f](N)- T o ) l n > ~ , X[-n,9(Nn)lnZ~I
'(5)
~ [ l , s ( f i ~ ) 1 n >=Kx[,Jl(fin)ln2K, ~
-
(Z[-n,~](N)+ XIIJ~(Q)) L ~ K ~ = ( Z [ - n , ~ ] (+ ~ )Z[l,l](&))1 n 2 ~ 1 .
Therefore
< 1, the random variable
Z-def = lim Z[-nbol a.s. n
is Po-a.s. finite and it provides a minimal stationary regime for the time to inactivity, which is defined as the time to the last activity in the system when subject to the [-oo,01 restriction of N. .3 Examples
We start with a few examples which all fall within the monotone separable framework. Example 9.3.1 The G/G/l/oo queue. Here, X[m,nlis the departure time of customer n, when there are n + 1 - m customers with arrival times Tl and service times q ,m 5 I n; Zim,nl i s then the sojourn time of customer n. The computation of $0) is trivial, by the strong law of large numbers. 0
<
Example 9.3.2 The G/G/s/oo queue. Here, XImtn1is the last departure time from the queue with customers arriving at Tl, m 5 1 5 n, that is (9.3.1) Z[m.n](N) = max(W&,,](N) where
. ..
+ an,WfmVnI(N)),
where Wtrn+](N) = (WLrnl(N), ,WL,,] (N)) is the ordered workload vector (see 5 3.1) at time Tn-, for this arrival process (we assume that the queue is initially empty). We have
with initial condition .
Posing CL
=
Dk = A[,is such that
Ar,+l
( DL
for all k and i.
DL - s U ( ~ - ~ ) we~ +see~ ,that (Ck}satisfies the Lindley equation
as a consequence of (9.2. ). The computation of the constant $0) is immediate from the'relation
Indeed since a
n
the relation y(0) = E O ( o ) / s follows by an immediate limiting argument. roof of (9.3.2) The property for j = s follows from the relation Zil,nl(Q) = 9,,,+,](Q). In order t o prove the property for all j, it is enough to show
is such that d n / n tends t o 0 a.s. Let def Un
= max(un,. . . ,on+,-I),
and
def
Un - min(on,.
+
..,an+,-1).
By comparing the original queue and the queue with workload (Wii,nl(Q),* . . t wii,nl(Q)) a t time Tn- and with constant service time nn over the interval n , n \.. 1,.. . , n + s - 1, we see that
and so CL/k tends to 0 a.s. for all I (use Remark 2.3.2 plus a coupling argu0 ment, in the case when O3 is ergodic). Example 9.3.3 Finite capacity tandem queues with Blocking. We take X[,,,] equal to the time to empty the network with the same arrival process as above. The constant y(0) is the same one as obtained in (8.2.11). There is no simple analytical characterization of the stability region in this case. 0 Example 9.3.4 A queueing system which does neither satisfy the separability condition nor the saturation rule. Consider an assembly queue with two independent Poisson arrival streams with the same intensity ,412. The system starts empty. Whenever there are customers of both classes in the queue, service is provided a t rate p. The completion of a service consumes one customer of each class. Whenever the queue has no customers of either class, it is blocked. Let us consider as input stream the superposition of the two Poisson processes properly marked. If one saturates the system with an infinite customer population, the (Markov) departure rate is y. Similarly, if one takes the viewpoint of letting n customers of this input stream arrive a t time 0, the last activity of the system takes place a t time p-In12 o(n). A rough application of the saturation rule would suggest that if X < p, the system is stable. However, such queues are always unstable (see the bibliographical notes), whatever the values of X and y. Note that this system does not satisfy the separability property. 0
+
hical Comments Similarly, when considering the queue with workload
a t time
Tn- and with constant service time Un, we obtain
The solution
(DL)of the equation
The historical paper concerning the stability of queueing systems within a stationary ergodic framework is that of Loynes [87]. This basic construction, hich is given in $ 1-2, is of wide applicability. In particular, it extends t o queueing systems amenable to a representation in terms of a stochastic urrence with certain monotonicity properties (see •˜ 4.2 and Remark 4.2.1). e interpretation of Garsia's proof of Hopf's lemma ([49]) and the queueingeoretic proof of the ergodic theorem which are given in •˜ 2.5. are due to u [103]. The proof of the existence of stationary states for G/G/s/oo G/G/1/0 queues (•˜ 3. and 5 5. respectively) are borrowed from Neveu and from Flipo [44]. The first construction of the steady state of the /1/0 loss system in the general case is due t o Lisek [85]. The ideas leadg to the maximal solution of $ 3.3 come from Foss [45] and Brandt (231 ee also the book by Brandt, Franken and Lisek (241 which contains several
138
2 Stationarity and Coupling
other results on the matter) . The coupling method and its relation t o vergence in variation (3 4.1-4.2) are the object of the book [83j by Lind This book also contains a very complete survey on the applications of method. In particular, coupling properties of various classes of processes 1 cluding renewal processes and Harris Markov chains are analyzed. The stud of coupling of point processes with a stochastic intensity was initiated Lindvall (823 who introduced the ( R , m ) point process. His result is m general than that of Example 4.2.3, and is obtained by introducing a Harris chain. A review of imbedding and coupling techniques for point processe is given in [30], where an extension of the ( A , m ) process t o finite random memory is considered. The notion of strong coupling and the method of renovating events are due t o Borovkov [20], where more other sufficient conditions for uniqueness of the stationary regimes of G/G/s/oo and G/G/1/0 queues can be found. This method is also of wide applicability since it applies t o all stochastic recurrences, regardless of their monotonicity properties. More results on the relationship between coupling and renovating events can be found in the survey paper 1211 by Borovkov and Foss, which also contains detailed comments on the relation between Harris recurrence and renovating events. New applications of renovating events theory 'to the uniqueness of the stationary regimes of closed queueing networks were recently proposed by Mairesse [88]. The construction of the stationary regime for acyclic queueing networks via coupling which is described in 5 7.1 was used by several authors. See in particular the paper of Konstantopoulos and Walrand [77], and the book [63] of Kalashnikov and ev. The priority discipline analyzed in 5 7.2 is borrowed from Dumas [41]. The results on finite capacity blocking queues considered in $ 8 are taken from Baccelli and Liu [9]. The basic reference concerning sub-additive ergodic theory is Kingman [73]. The method developed in 3 8 extends t o the class of discrete event systems which can be represented as a ( m a ,+)-linear stochastic recurrence like Equation (8.1.3) (for more details on this see 161). Subadditive ergodic theory is known to be a key mathematical tool in percolation theory, among others. The saturation rule of fc 9, which was given in BaccelIi and Foss [8],suggests that it also provides a central tool for stability issues in queueing theory. We conclude with a short survey of recent developments on the stability of queueing networks within the stationary ergodic framework; amson [22] has shown that the condition requiring that the traffic intensi be less than one at each queue (that is, condition pk < 1, for all k, where pk is defined in (7.2.1)) is not sufficient for stability in Kelly-type networks with FIFO discipline (that is, the networks of 3 7.2, but with a FIFO discipline). The counter-example involves a two-queue Kelly-type network with a single class of customers (that is, all customers have the same route). FIFO Kelly-type networks do not satisfy the external monotonicity property of the monotone separable framework of 5 9. On the other hand, Jackson-type networks, where the service times and the routing decisions are sequences attached to nodes and not t o customers,
Bibliographical Comments
139
1 within this framework; in addition the constant ~ ( 0 can ) be computed d it was &own in 171 that the stability region is pr, < 1 for all k using the uration rule. Other network$ for which the construction of the stationary mes is still an open question are polling systems. A construction of a -Markovian polling system was given in hfassoulii. [go]-
."
.
Chapter 1 introduced the &-framework, a convenient formalism for the study of point processes and stochastic processes which are jointly stationary. In Chapter 2, it was shown that the house is not empty but shelters a number of stationary queueing systems. In the stable case, coupling arguments often show convergence in variation of an initially non-stationary state t o the stationary state obtained by a construction of Loynes' type. Thanks to the existence of construction points, from which secondary processes (as the congestion process in G / G / l / m ) can be obtained from the stationary state (the workload process in G/G/l/oo), the convergence in variation of the secondary processes is a consequence of the same phenomenon for the stationary state. This state of things allows one to obtain the basic formulas of queueing theory concerning limit processes directly on the stationary system, in the Ot-framework. This separates the task of obtaining formulas from that of obtaining limit distributions, and enables one t o give short and elementary proofs of the classical formulas and results of queueing theory. In this chapter, some consequences of the main formulas of Chapter 1, namely Mecke's formula, the stochastic intensity integration formula, the rate conservation law and Papangelou's formula, will be harvested. All these formulas are given in terms of the stationary probability and of the Palm probability associated with certain point processes. In the ergodic context, averages under a Palm probability receive an interpretation as empirical averages under the stationary probability, as explained in $ 7 of Chapter 1 (cross-ergodic theorems). The objective of the present chapter is t o present in a unified manner few classical results and formulas of queueing theory. Special systems will considered only when they are interesting from a pedagogical point of ew, and therefore no attempt a t exhaustivity should be expected. However, ost of the fundamental formulas and results which intervene in the mathatical study of particular systems will be reviewed. This includes Little's rmula, the formula of Poliaczek and Khinchin and its consequences, Kleinrock's conservation law, Cobham's priority formulas, the PASTA property, the busy cycle formula, insensitivity properties, etc.
142
3 Formulas
1 Little's Formula
T h e presentation is made in the &-framework, which is recalled in 5 1.1, and the derivations are based on the Palm-martingale calculus, that is t o say the combined use of Mecke's formula in its more general form (the function space Campbell-Little-Mecke formula (2.1.1)), of the notion of stochastic intensity kernels and of the associated stochastic intensity integration formula.
143
In the &-framework, this input stream is compatible with a flow (8t) in the sense that A(w,C t) = A(Btw,C) and a,(w) = ao(B~,,w).The canonical process {u(t)) associated with the sequence of required services {a,) is defined by u ( t )= a, if t E [Tn,Tn+l).
+
In the Bt-framework, stationarity is implied by the Bt-invariance of the underlying probability P. E x a m p l e l.l.l.,, (cont'd): G / G / l / m queue. T h e arrival rate
k for Stationary Let us recall the &-framework of Chapter 1 , • ˜1.3. There is a probability space (0,F,P ) , on which a measurable flow {Ot), t E $ is defined. Probability P is &-invariant for all t E II& Also there are a number of point processes and stochastic processes which are compatible with the flow {&). Recall that the point process N and the stochastic process { Z ( t ) )are called compatible with the flow {& ) if N(8,w, 6)= N(w, C + t ) and Z(t1w) = Z(%@LW), for all t E IW, w E $2 and C E D. The preceding chapter was partly devoted t o the construction of such frameworks in a queueing context. In the &-framework, a sequence {Z,), n E Z, of marks of N has the canonical form
zn = Z(Tn), where (Z(t)) is defined by z(1) = Zn
if 1 E
[Tn, Tn+l)+
T h e stochastic process {Z(t)) is therefore coppatible with the flow (8,). It is called the canonical process associated with the mark sequence (2,) and the process N. A sequence with the above property is called &-compatible. bserve that { Z ( t ) ) and N, being compatible with the same flow {&), are jointly stationary, since P is Bt-invariant.
le 1.1.1 6/6 input stream. Let {(Tn,an)), n E Z , be a 616 input and let A be the arrival point process defined by (1.1.1) A(C) =
1.1.2) X = E[A((O, I])], assumed positive and finite, in which case the Palm probability P: associed with ( A ,P) is well defined. Under the stability condition (1.1.3) p s f X ~ $ [ a o ] < 1, the existence of a finite G/G/l/oo workload process {W(t)), compatible with the flow {&) and satisfying the evolution equation (1.1.4) W ( t ) = i W ( T n - )
+ a, - ( t - tn))+
was proved in Chapter 2,
3
Tn
It < Tn+~t
2, when (P,Ot)is ergodic.
.. Define a construction PO@ to be an arrival time T, for which W(T,-) = 0. It was shown in Chapter 2 that, under the stability condition, there are an infinite'number of such construction points, both on the right and on the left of the origin of times. T h e existence of an infinity of construction points on the left allowed us t o construct a number of point processes, mark sequences and stochastic processes, all compatible with the flow {&I.For instance (see
The system congestion process { X ( t ) ) , where X ( t ) is the number of customers present in the system (waiting or being served) a t time t. r T h e waiting room congestion process {Q(t)), where Q ( t ) is the number of customers in the waiting room a t time t. The' sojourn time sequence {V,}, where V, is the sojourn time in the system of customer n. where Qn is the amount of time spent in e The waiting time sequence the waiting room by customer n. r T h e residual service time process { R ( t ) } ,where R(t) is the amount of service remaining t o be done a t time t for the customer being served a t time t ; R(t) = O if the system is empty. r D,the departure point process counting the departures from the system: if T A is the departure time of customer n, D(C) = CnEZ 1c(T;). The construction of the above objects is possible for all 'reasonable' service 0 disciplines (see Chapter 2, 3 6.2).
{v,),
2 616 input stream with priority classes. Consider a G/G input stream ((T,, an,U,),n E Z, where a;, is the amount of service required by customer n and Un is its priority class : U, E {1,2, ...,M}. Define
and the point processes A and Ai (1
< i < M ) by
Let (Ti,,} be the sequence associated with the arrival process Ai of customers of class i, with the usual convention Ti,o 0 < Ti,l. The quantity
<
is the amount of service required by customer n of type i arriving a t time Ti,,. Assume that X = E[A((O, I])] < oo and therefore A; = E[A,((Q, l])]< oo. This allows us t o define the Palm probabilities Pj and P j , . We have seen in Chapter 1, Example 5.2.1, that
Consider the traffic intensities pi = X&ii [d= X;E.;[ c ~ ,Recall ~ ] . that Pii(Ti,o = 0) = 1 and therefore vi,o = 00,Pji-a.s. The traffic intensities and p XE; [go] are linked by
sf
(see Chapter 1, Example 5.2.1). le 1,1,2 (cont'd) G/G/s/w queueing system with pIYonty classes. In Chapter 2 ($ 31, we have seen that under the stability condition . .-
there exists a t least one workload process {W(t)), t E IR, with values in IW; (and in particular finite), compatible with the flow {&} and satisfying the evolution equation
( t ) = R(W(T,-)
+ a(T,)e - (t - T,)i)+,
for t E [Tn,Tn+l), where R,i and e were defined in Chapter 2, 5 3.1. I t was shown that the cardinal of the set of indices n 2 1 (resp. n 5 0) such that U/l(Tn-) = 0 was P - a s . infinite. As in Example 1.1.1, for 'reasonable' service disciplines and priority assignments, the existence of an infinity of construction points t o the left allows us to construct the following point processes, stochastic processes and mark sequences, all compatible with the flow {&): r The workload process for class i , {W,(t)). r The system congestion process for class i, {X,(t)}. e The waiting room congestion process for class i , {Q,(t)}. r T h e sojourn time sequence for class i, {V,,,}. e The waiting time sequence for class z, {c,,). r T h e departure (point) process for class i, D,. 0 e The residual service time process for class z, {R,(t)}. We now proceed to the derivation of a basic result of queueing theory linking the time average congestion of a given system, the rate of arrival into this system, and the customer average sojourn time in the system.
The Campbell-Little-Mecke formula (3.3.3) of Chapter 1 is the source of a number of interesting queueing relations, including the Pollaczek-Khinchin formula, the formula of residual service times, Little's formula and Kleinrock's conservation law. For easy reference we reproduce it below
In this formula, N is a stationary point process of finite intensity A, {T,} is the sequence of its 'points', (2,) is a sequence of marks with values in K , P$ is the Palm probability associated with N, and f ( t ,z ) is an arbitrary non-negative measurable function from R x K into I[B T h e ingredients a Little type formula are the following: We need a stationary &framework with r an arrival process A, represented by the sequence {T,),with finite intensity A. r a sojourn time sequence {V,), where both A and {V,) are compatible with the flow {&I. The interpretation is that T, is the arrival time, into some system, of a customer who remains in the system for the time Vn and then leaves the system. Therefore, the number of customers present in the system a t time t is
146
3 Formulas
1. Little's Formula
Indeed a customer arriving a t time T, is in the system a t time t if and only if he arrived before t (T, < t ) and departed strictly after t (Tn + Vn > 1). Application of the Campbell-Little-Mecke formula (1.2.1) t o the function f ( s , t ) = l(-,,t](s)l~t,+,)(s f z ) and to the mark sequence (2,) = {V,) implies, in view of Identity (1.2.2)
(1.2.6)
i ~ ( ~ (=t i))
1
+ s P ( X ( t ) 2 S) = X n-a, lim n
~k
147
= XE~[LT~],
k=O
i= 1
since all incoming customers eventually reach a ticket booth (and therefore the rate of arrivals into the 'system' is the rate of arrivals into the queue), and the sojourn time a t a booth is the required service time. In the G/G/l/oo case, recalling the definition of the traffic intensity p = XEi[ao], we find that
Therefore E [ X ( t ) ]= E[X(O)], which is expected since (X(t)} is compatible with the flow ( O , ) , and
E x a m p l e 1.2.2 (cont'd). G/G/s/c with loss. Instead of a G/G/s/co queue, we consider a queue with limited waiting room capacity G/G/s/c where c < m. Equality (1.2.6) holds with X being replaced by the rate of accepted arrivals, i.e. X = X P j ( X ( 0 - ) < s c). For instance, in a G/G/s/O queue, since X ( t ) cannot exceed the number of servers, the left-hand side of (1.2.6) is E[X(t)], and therefore taking into account the above remark concerning the rate of arri;bl X, we find
When (P,Bi) is ergodic (see Chapter 1, 5 7), This formula can be read
(1.2.8)
(1.2.4)
E[X(O)] = X lim k=l
It has been customary among the queueing theory community to call L = XW a formula such as (1.2.3). I t is however a rather imprecise terminology that we shall always make precise as in (1.2.3) or (1.2.4). Ie 1.2.1 Little's waiting room f o n u l a . If the 'system' is the waiting room of a queueing system, and if the service of a customer is never interrupted, then take X ( t ) = Q(t), Vn = (the waiting time before service), and X is the rate of arrivals into the waiting room and hence into the queueing system. Little's formula (1.2.3) reads
vn
+
E [ X ( t ) ]= p(1 - P ~ ( x ( o - ) = s)).
E x a m p l e 1.2.3 Busy cycles via Little's formula. Consider a GIG queue in equilibrium and let N be the point process counting the construction points, that is the arrival times a t which a customer finds an empty queue
Let (R,) be the sequence of points of N, and define C, n-th cycle, by
the length of the
It is the sum of an idle period Inand of a busy period B, (see Figure 1.2.1)
If service interruptions are allowed, things become more complicated and it is better to use Formula (1.2.3),where the 'system' is the whole service station (waiting room plus servers), and use whatever relation there may exist between Q ( t ) and X ( t ) , for instance, in a G/G/s/oo queue, (X(t) - s)+ =
17 Example 1.2.2 Little's server formula. The system to which (1.2.3) now applies consists of the ticket booth. In a G/G/s/m queue, Little's formula (1.2.3) becomes
(1.2.10)
+
Cn = In B,.
Consider the following system: the arrival process is N, a customer arriving a t time Rn requires the service time Bn,and is served a t unit speed by a single server. Little's formula (1.2.3) can be applied to this system with the following identifications
Campbell-Little-Mecke formula gives
If we introduce the function r ( t ) defined by
where X * ( t ) = X ( t ) if t 5 Wo (the sojourn time of customer 0) and X * X ( t ) + 1 if t Wo, we have
>
(1.2.16) r ( a o ) = W o and r ( t ) receives the interpretation of the sojourn time of customer 0 if its re~ ?response ~ time process quired service is t. We shall therefore call { ~ ( t ) ) the of customer 0. Also
ig. 1.2.1 Busy cycle
Therefore (1.2.11)
1 - P ( X ( O )= 0) = XP;(X(O-) = o ) E ; ( B ~ ) . Now, the service sequence is i.i.d. and independent of the arrival process, and ~ ( tdepends ) on the input process except ao. Therefore
On the other hand, the intensity is the inverse of the mean inter-arrival time (1.2.12) X P ~ ( X -) ( = 0)E%[Co]= 1
E$~T(C-JO A a ) ]= E;
and therefore
[la
ja
+
o r ( t ) d ~ ( t )=] o F ( t ) d ~ ( t ) i ( a ) ( l - ~ ( a ) ) ,
where
Example 1.2.4 Attained service in G I / G l / l / w Processor Sharing. In this example, the arrival process is of a general nature, and the service time sequence is i.i.d., independent of the arrival process. The queueing discipline is of the processor sharing type (PS):all customers present in the system receive service, at a rate inversely proportional to their number. Thus a customer arriving at time T, < O and requiring service a , will be pes-ent at time 0 . and will have attained service not greater than a if and only if
is the average response time to required service t. But
so that finally
t
rO
i
where X ( t ) is the number of customers present at time t . Denoting by X,(t) the number of customers present at time t with attained service not greater than a
Example 1.2.5 Response time of M / G I / l / o o PS. Let the state a t time t of a M / G I / l / o o PS system consist of (1) the number X ( t ) of customers in the system, and ( 2 ) the elapsed and residual service times of these customers. The stationary distribution of the state under P (of course we assume p < 1 )
150
3 Formulas
1 Little's Formula
can be computed by general methods of Palm theory (see the bibliographical comments). It is obtained as follows: First select the number of customers present in the system to be n with probability pn(I - p). Then select n independent pairs of elapsed-residual service times distributed as a pair of backward-forward recurrence times of a renewal process with c.d.f. G, the c.d.f. of the service times. In particular the residual service times and the elapsed service times have the c.d.f. G.(x) = p S r ( 1 - G ( x ) ) d x ,where pW1 is the mean service time. We shall use this result to obtain the average response time. Indeed the probability for a given customer to have attained service no greater than a is G, ( a ) , and therefore 1
(1.2.19) E(Xa(Q)]= E[X(O)]G,(a) = -G,(a) I-P Comparing with (1.2.18) gives
151
It extends the classical L = XW formula as well as the exchange formula. It finally collapses into Mecke's definition of Palm probability ( B = A ) and this is of course a tautology since the Swiss Army formula is derived from Mecke's definition of Palm probability. Let IT,} and (7,) be two simple point processes on R and let A and D be the associated counting measures, assumed to put finite masses on bounded sets. The sequence {T,} is supposed to be ordered, with the convention To 5 0 < T I , and such that A ( & ) = A ( B - & ) = m, so that in particular T, E $ for all n E iZ. The sequence (7,) is also supposed to satisfy D(& = D(R - &) = op, but it need not be ordered. However, it is required that for each n E Z
. On could imagine that Tn is the arrival time of customer n in a system, and that T, is its departure time. With this interpretation, any process { X ( t ) } satisfying X ( t ) 2 0 and
and therefore, since ~ ( 0=)0
1.3 The Swiss Army Formula epending on which blade is selected, a Swiss Army knife transforms itself into various useful tools. The general formula obtained in this subsection is called the Swiss Army formula of Palm calculus because it contains wellknown formulas of this theory as well as some new ones. The main formulas of Palm theory are not just derived from the Swiss Army formula, they are in fact avatars of it' in following sense : the Swiss Army formula features a "queueing' process { X ( t ) ) = X , with its arrival and departure point processes A and D respectively; a random measure B , and o a non-negative stochastic process ( Z ( t ) ) = 2. The objects X , B and Z can be considered as 'dummy variables' which, when assigned a 'value', give a classical formula. For instance, with Z ( t ) I , B ( d s ) r ds, we obtain Little's L = XW formula, and with X ( t ) r 1, B a point process, we obtain Neveu's exchange formula between A and B . The Swiss Army formula has also the following avatars : Palm inversion formula ( X ( t ) z 1, B ( d s ) = d s ) , as well as an ordinal version of Little's formula.
=
is a queueing process associated with the a r r i d and departure processes A and D respectively. Howeve? such an interpretation is not required. The processes A and D can have common points, and as a matter of fact we shall consider the situation where r, = Tn+*,that is W n= Tn+l-T, and therefore X ( t ) r constant. Let now { B ( t ) ) be a right continuous with left limits (corlol), nondecreasing real-valued process. Denote S(a,bl h(s)dB(s)the Stieltjes-Lebesgue integral of function h with respect to the measure canonically associated with { B ( t ) } . For the consistency of the notational system, we shall write dA(t), dD(t) instead of A(dt),D(dt). Finally, let { Z ( t ) ) be a non-negative real-valued stochastic process. Recall the Stieltjes-Lebesgue formula of integration by parts for two corlol real-valued functions f and g of locally finite variation
We shall use Formula (1.3.3)in a way that generalizes the argument used in textbooks to explain Little's formula. This argument is based on the graph of the arrival and departure counting processes of the queue, and on the computation of the areain between in two different manners (see R.W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice *dl, 1989, p. 235).
'This picturesque proof is eq (1.3.3), which gives, if X ( 0 )
ent to the following argument, using Formula
that is
and therefore, after elementary computations, the left hand side of (1.3.4) is
Z(u)dB(u))1(0,t~(Tn) + R(O) - R ( t ) , Therefore, if t is such that X ( t ) = 0 (this is a simplifying assumption; we shall go through the complete argument later), t
or
A ((0,tI) ------1 X (8)ds = ------t A ((%tI)
w n
and iz/(t) is the set of indices n corresponding to customers still in the system at time t (that is, such that.Tn 5 t and 7, > t ) . Finally
.
Z ( u ) d B ( u ) ) l ~ , , ~ ( of, tR(O) l
Such an argument can be significantly generalized. Indeed, when applying (1.3.3) with
f (4 - f (0)= X ( t ) - X(O),
g(t) =
we obtain
(X(s-) -X ( O ) ~ Z ( S ) ~ B ( S )
All the above objects are now supposed to be given in the stationary &framework, and in particular, we assume that ( Z ( t ) ) and A and D (and therefore X ( t ) ) are Bt compatible, and that the intensity XA of A is non-null and finite. We then have:
Z(u)dB(u))dX( 8 ) . Rewriting the left- and side of the last equality as
Z(s)dB(s))dX(s) gives
Proof: First suppose that ) Z ( s ) d B ( s ) ]< m,
E:[
1
Z ( s ) d B ( s ) ]< m.
(0,Wol
R(0) - R(t) E L1(P) and since R(t) = R(0) o 8,, it follows from Lemma 2.3.1, Chapter 2, that E[R(O)- R(t)]= 0,and this suffices to prove (1.3.8), taking expectations in
3 Formulas
154
1 Little's Formula
For the general case, we need to introduce the following notation T - ( t ) = inf{Tn; T,
:
< t and 7, > t )
(thus T-(t) is the arrival date of the oldest customer in the system a t time t ) . For any c > 0, we define
T h e process {ZC(t)) satisfies condition (1.3.9) and moreover lim
clm
t Z c ( t ,w) = Z(t,w).
Thus (1.3.9) holds true for {Zc(t)), and the general case follows by monotone R convergence.
ittle's Formula. Under the above assumptions, the following formula is true
155
according t o whether they descend from the Extended Little's formula or from the Extended Exchange formula. We start with the descendents of the Extended Little's formula: (a1)Little's L = XW formula. Letting Z(t) E 1 in (1.3.10), we have
(PI) Palm Inversion Formula. Defining D
from A by
(1.3.12) rn = T n + l , "we have Wo = 7-0 -To = Tt - T o = (1AlO) becoines
T,,Pj- a . s . , and X ( t ) z 1, so that
We now list the descendents of the Extended Exchange formula.
( a z )An Ordinal't = XW Formula. Taking Z(t) r 1 and B
E
A in
(1.3.11), we obtain
Proof: Let B(ds) = d s in the Swiss Army formula and observe that ~E[J,'X(s-)Z(s)ds] = $ E ( J X(s)Z(s)dsj ~ = E[X(O)Z(Q)]. 0 emark 1.3.1 Formula (1.3.10) has a very simple interpretation. Suppose that when some item is stocked in a warehouse, its owner has t o pay Z(t) money units per time unit. In view of Formula (1.3.10)' the average income of the warehouse owner per time unit is equal to the average fee paid by the owner of the items multiplied by X A , the number of customers entering the 0 warehouse per unit time. ange Formula. Under the a eve assumptions, and if moreover B is a point process with positive and finite intensity X B , the following formula is true
Proof: Just observe that when B is a point process with intensity XB, the right hand sides of (1.3.9) and (1.3.11) are equal by definition of Palm probability. 0
By further specifications of the 'dummy variables' of the Swiss Army formula we obtain the classical formulas, which can be classified in two types,
Similarly, with Z(t)
that is, since XA
5
1 and B = D,
AD,
emark 1.3.2 A formula like (1.3.13) is called an ordinal L = XW formula for the following reason: time is counted in terms of units, one unit being the (random) time separating two arrivals. Therefore the left-hand-side of (1.3.13) is the sojourn time counted in terms of these new units, that is the number of arrivals during the usual sojourn time. T h e intensity is 1 since there is one arrival per new unit time. The Swiss Army formula also gives an ordinal formula for a stable G / G / l / c c queue, with the sequence of arrival times a t which the system is empty (we denote {R,), N the associated counting process, see Example 1.2.3). Here Tn = Rn, rn = (Tn+l = R,+l. T h e corresponding queueing process is X(t) r 1. Applying the Swiss Army formula with B = A, we have
umber of customers served in a busy
shall call Formula (2.1.1) or (2.1.1') the junction space Campbell-LittleMecke formula.
ourse, this can be obtained as a dir ula between A and N.
(Pz) Neveu's Exchange obtain from (1.3.11)
0
rmula. By specializing D as in (1.3.12), we
The formula L = XW has been extended by Brumelle and the extension is known as N = XG. It rests upon the function space Campbell-LittleMecke formula which is just another look a t the usual Campbell-Little-Mecke formula, only with marks that are functions; taking Z,(t) = h,(a - t), where (h,) is a sequence marks taking values in a function space, we obtain
nition. Taking B s A, we obtain the definition of Palm probability
ernark 2.1.1 We can associate a formula of the type H = XG with every ! which depends upon the past a t time 0. More precisely: functional @ Let 7% = T,,+l - T,. Consider now a functional
which takes us back where we started. ernark 1.3.3 The Swiss Army formula can be given the simpler form
called the H-functional. Using the notation
since an increment Z(s)dB(s) is a particular case of an increment dB(s). The latter formula is a natural extension of L = XW and it receives an interpretation similar t o that given in Remark 1.3.1. 0
define the G-functional:
Suppose that
*-
ace Campbell-Little ecke Formula and the
= X G Formula shall take another look a t the Campbell-Little-Mecke Formula (1.2.1) and erve that 2, can take its values in an arbitrary measurable space (K,X). This fact can be usefully exploited. Indeed, take K = D ( R R) the set of corlol functions from R into W wi a suitable topology (Skorokh~d'stopology for orel field associated with this topology. Define ~ ( 2 ) .The Campbell-Little-Mecke formula then takes the form
Campbell's formula
c:=-,
and assumption (2.1.5) imply that I g(Tn, Z,, U-,) I< oo P - a . ~ . , and therefore h(T,, Z,, Un-l) has a finite limit as n goes to -m. We shall assume that (2.1.6)
n+-ca lim
h(Tn,Z n , Un-l) = O
and therefore
Also, applying Campbell's formula once more gives
158
3 Formulas
2 0
(2.1.7)
E[@]= X
E & [ ~ ( cZo, , U-l)]dt.
This is again a N = XG formula, which can be considered as an extension of Little's formula. 0 Example 2.1.1 Light traffic derivative. Formula (2.1.7) is the key to light traffic analysis and to a method of perturbation analysis. We shall consider a simple case which contains the basic ingredients of the method and the reader is referred to the bibliographical comments a t the end of the chapter for further information. Suppose that N is a Poisson process of intensity X and that (2,) is independent of N, and that conditions (2.1.5) and (2.1.6) are verified, so that
Since the r,'s are the inter-arrival times of a Poisson process of intensity X
Therefore
(2.n.m) E~[s] = The following result then holds: under assumption (2.1.5) and (2.1.10), an if there exists a function go(t, 2 ) such that
the derivative a t X = 0 of Ex[@J exists and is given by
10
EABJX -0
=
,[g(t,
Zor~ i l J d t .
f we go back to the definition (2.1.4) of g, we see that . .. 1 1 g(t, Z O , U ? ~=h(t, ) 2 0 , 1 ~ - ~2-1, , x ~ - 2 2, - 2 , ...)-
In reasonable situations I
lim h(t - -~-1,2-1,-T 2,Z-2, ...) = 0 A10 X X and therefore a reasonable guess is that
with the interpretation that go(t; Zo) is equal to the functional 9 when there is just one customer a t time t with the random mark Zo. However this interpretation is not needed in .the theory, although in all applications it is the right one.
An E x t e n s i o n of N = XG. We now give one further generalization of the Swiss Army formula (1.3.8). Instead of taking a classical queueing process {X(t)), t E IR, we shall consider a process of the form (2.13) X(t) =
We also suppose that
159
in the right-hand side, the index 1has been suppressed since the distribution Zo is independent of the intensity X of the basic point process N). The oof of (2.1.12) is immediate since, in view of (2.1.10), (2.1.9) gives
I
where we have written down (2.1.7) using the fact that since N is Poisson P$ and P agree on ( 2 0 ,U-I), and where we have appended an index X to the expectation symbol E in order to emphasize dependency on the intensity of N. Define
H = XG
1
R
{h(t - s ) 0 B.)dA(s),
where h(t,w) is a non-negative function such that E i S [, h(s)ds] < oo. In view of the generalized Campbell's formula and of the latter integrability condition, {X(t)} is a finite process. Arguments, similar to those leading to formula (1.3.8) give the extended H = XG formula 21.14)
X~E;
[
h(s)Z(l.d~(s)] = j i
[/
(0,tI X(s-)Z(s)dB(s)]
,
which reduces to (1.3.8) with the choice h(t) = l(To,w+wal. This formula is therefore an extension of (1.3.8) and with the choice B(ds) = ds, Z(t) = 1, it gives H = XG:
(T,-). We will see in •˜ 3 that, due to the Poisson nature of the arrival (point) process, the 'PASTA' property holds, that is Consider a G / G / s / c system, with a non-preemptive service discipline, that is, once started, the service of a customer cannot be interrupted. The contribution of customer n,n 5 0, t o the workload W ( 0 )a t time 0 is of the form Zn(-T,), where 2, is the function depicted in Figure 2.2.1. In this figure, V, is the waiting time of customer n.
and therefore, using (2.2.4) and the previous remarks
or equivalently
By Little's formula, X E : [ ~= ~ E[Q(O)]. ] Also, E[Q(O)]= E[(X(O)- l ) + ] = E[X(O)]- 1 + P ( X ( 0 ) = 0). Therefore in view of (1.2.7), E[Q(O)]= E[X(O)]- p. Combining all the above remarks, we find the expected number of customers in the system M / G I / l / o o FIFO: Fig. 2.2.1 The 2, function
The workload a t time 0 is the sum
Writing
X 2 ~ [ u ;=] X 2 ( ~ a r ( u o+) ( ~ [ c r o ] = ) ~A) 2 ~ a r ( u o+) p2
x. .
formula (2.1.1) and therefore, by the function space,Carnpbell-Little~eck
in the previous equality, we obtain
In view of the shape of Zo(t)and using the fact that Pj(To = 0) = 1,
This shows that for a fixed traffic intensity p, constant service times (such that Var(cro)= 0) give the smallest congestion in the M / G I / l / o o FIFO 0 queue. We will come back t o this in Chapter 4, 5 1.
Zo(t)dt]= E$[aov0+
1
esidual Service Time. The function space Campbell-Little-Mecke formula can be applied t o obtain the residual service time f o n u l a
This results in Pollaczek-Khinchin's mean value formula:
hen a. and VOare independent, for instance in a G I / G I / l / o o FIFO or LIFO non-preewtive queue (but not for S P T for instance)-- -
Example 2.2.1 The M / G I / l / o o FIFO queue. ecause of the FIFO disciof customer n pline and since there is only one server, the waiting time is equal t o the system load that he sees in front of him upon arrival, i.e.
vn
valid for a G/G/s/oo system with a non-preemptive discipline. Indeed defining Z,(t) as in Figure 2.2.2,'we see that
and therefore, by (2.1.1), E[R(O)]= XEA[JRZo(t)dt],that is (2.2.9) since = $a:.
& Z,(t)dt
162
3 Formulas M
X ~ E[;U ~~ , O C =,constant. ~]
(2.3.4) i=l
Of course, if for each class i, ai,o and Pito are independent (under P or P i i , this is equivalent), (2.3.3) takes the form
This formula holds for instance in a M / G I / l / w system with priority classes, no preemption, and FIFO discipline among the members of a given class (see also 5 5.2).
Fig. 2.2.2
2.3 Kleinrock's Conservation Law
This conservation formula is obtained exactly in the same way as Pollaczek
Remark 2.3.1 Another derivation of Formula (2.3.1) from Pollaczek-Khinchin's formula (2.2.3) is as follows, using the results of 5.1, Chapter I:
- Khinchin's mean value formula in the preceding subsection. It concerns the G/G/s/oo queueing system with M priority classes of Example 1.1.2. If we apply Pollaczek-Khinchin's formula to each of the priority classes, we obtain, with the notations of Example 1.1.2
This formula applies when the service of a customer of any type cannot be interrupted and the speed of service is one. The only requirement for the discipline service among customers of the same class and for the priority assignment between the M classes is that all the objects considered fit the Btframework. The simplest case would be a FIFO discipline among the members of the same class, and a non-preemptive priority rule with given order of priority, say 1 >> 2 >> ... >> M, where i >> j means that i has riority over j. Summing up the M equations (2.3.1) and observing that R W;(t) is the total workload, and that
xi=,
Example 2.3.2 A continuous version of Kleinrock's conservation law. This version is an immediate consequence of Pollaczek-Khinchin's (2.2.3). It is obtained by conditioning with respect to uo:
Therefore A. 0 (since XiEZ, [a;,,] = ATE,; [ug]= XPi(Uo = i)E;[u; [ Uo = i], see Chapter 1, Example 5.2.11, we obtain
Defining p(dx) = XxP~(roE dx), the traffic intensity measure, this equation takes the form e right-hand side does not depend upon service disciplines among members of the same class, and priority assignment, as long as the conditions stated just after Formula (2.3.1) are in force. This constitutes Kleinrock's conservation law
We recall the conditions of validity of (2.3.7): a service is not interrupted when started, and the speed of service is one for a given customer. However, no condition of independence of uo and VOis needed. For instance, Formula
(2.3.7) is valid for a non-preemptive SPT discipline (where the servers choose in the waiting room the customer with shortest processing time on,and no preemption is allowed). 0 A n o t h e r C o n s e r v a t i o n F o r m u l a for P r e e m p t i v e s u m e Disciplines. We consider a system in equilibrium, with a stationary G I G input. Other hypotheses will be introduced as need arises. T h e first one is:
Since the workload a t time 0 is
the functional Campbell-Little-Mecke formula (2.1.1) implies E[W(O)] = E~[J,"Zo(t)dt], that is M
E: [TO(Z)]P; (a0
> X ) ~ =X E[W(O)].
(2.3.8) Hypothesis: the discipline is non-preemptive, or preemptive resume. T h e contribution of customer n, arriving a t T, 5 0, to the workload W(0) is Zn(O - T,), where, according to the above hypotheses, Z,(t) has the form exhibited in Figure 2.3.1.
In a number of interesting cases
and (2.3.10) then becomes
Example 2.3.3 G I / G I / l / c o Processor Sharing (PS). For this system, a t equilibrium, hypotheses (2.3.8), (2.3.9) and (2.3.11) hold. Only (2.3.9) requires a proof. This assumption is verified because {Zo(t)),t 0, depends on a0 and on the congestion process { X ( t ) )in the interval [0, VO).But in this interval, { X ( t ) ) depends only on the sequence of arrivals {T,), n E .Z, and on the sequence of services {a,) except a0 (for t VO,X ( t ) actually depends cl on 00).
>
time Fig. 2.3.1 The function Z,(t)
T h e slopes of the decreasing parts of ~ , ( t )may be different. Also, in the non-preemptive case, there may be just one flat region (the first one), or no a t region a t all. For 0 5 x 5 a,, rn(x) is defined as in Figure 2.3.1 and can be interpreted as the response time to a load x brought into the system at time T,. We introduce the second hypothesis. It is a technical hypothesis, but it is not difficult t o check (see the examples below). (2.3.9) I-lypothesis: the random variables lo<,<,, dent for all x. Under the assumptions (2.3.8) and (2.3.9)
and T ~ ( Xare ) P i indepen-
>
Example 2.3.4 G I / G I / s / c SRPT. Here we assume that we are a t equilibrium in the &-framework. The same argument as in Example 2.3.2 gives the cl same conclusions.
Event and
This classical result of queueing theory states, in rough terms, that if the arrival point process is Poissonian, operational characteristics of the system computed just before arrival times and a t arbitrary times are the same (Poisson Arrivals See Time Averages). Some care must be exercised in the application of this principl.e, and we now give a precise statement, in the &-framework. Let A be a point process, compatible with a flow {Ot), and with finite intensity X (we use the notation A because the PASTA theorem is mostly applied t o arrival point processes). Let {Fi}be a history of A that is compatible with the flow {Oc) and with a predictable structure adapted t o {&) (see 5 8.1 of Chapter 1). Let { Z ( t ) ) be a Fi-predictable process compatible with the flow {Ot), with values in a
166
3 Event and Time Averages
3 Formulas
measurable space (K,K ) , and let f : K -4 I be a non-negative measurable function. Then if A admits the constant &-intensity X
167
Example 3.1.2 Busy cycle in M/GI/l/oo. In a G I / G I / l / m queue, we have P(X(0) = 0) = 1 - p , where p is the traffic intensity XEi[ao]= XEiao], and if moreover the arrival point process is Poisson, Pi[X(O-) = 0) = P[X(O) = 01. Using these remarks and Formula (1.2.11), we obtain
In the case when (P, B t ) is ergodic, (3.1.1) becomes
(recall that for this formula, N counts the arrival times into an empty system; . see Example 1.2.3).
(see 5 7, Chapter 1 ) . emark 3.1.1 By Watanabe's theorem, A admits a Ft-intensity X if and only if it is a Poisson process with rate X and for all (a, b] C $ N(a, b] is independent of 7,. In particular N(a, b] is independent of Z(a) : this is the 0 so-called lack-of-bias assumption. Proof of (3.1.1):
3.2 Applications o f Papangelou's Formula Necessary and Sufficient Condition for ESTA. ESTA means Events See Time Averages. It is the same property as PASTA, only without reference to an arrival process. The ESTA property is said to hold for the process {Z(t)} and the point process N, both compatible with the flow {&), if [f(Z(@)] = E[f (Z(O))], for d l non-negative measurable functions f : E -+&I where E is the state space of {Z(t)}. Let {Ft} be a history of N and {Z(t)}, that is compatible with the flow {&). Suppose that N admits a &-intensity {X(t)} (which can be assumed compatible with the flow'{Bt); see Chapter 1, 5 8). Recall that E[X(O)] = A. If (Z(0)) is Fa--measurable, Papangelou's formula
EL
where the first equality is Mecke's definition of Palm probability, the second equality is the definition of stochastic intensity plus the stochastic intensity integration formula, and the last equality is the stationarity of {Z(t)) under probability P. 0 emark 3.1,2 Of course, as will be explicited in 5 3.2, PASTA can be viewed as a consequence of Papangelou's Radon-Nikodfm derivative theorem. However, we preferred to give the more elementary proof above, because PASTA is indeed a very elementary result. C)
i
t
holds true for all bounded f . This shows that ESTA holds for N and {Z(t)) if and only if the lack of bias condition
In the usual applications Lo queueing theory, Z(t) has the form is satisfied. where (Y(1)) is a corlol process adapted to (FtTt)and moreover, (Y(t)} is . In this case, (3.1.1) becomes
hen ESTA Does not Hold '33ue. The basic formula to use is of course Papangelou's formula (3.2.1).
Example 3.1.1 The point process A is the input of a M/GI/s/oo queue in equilibrium ( p < s), and Y ( t )= Ix(t),,, where X ( t ) is the number of customers in the system a t time t. The PASTA property then shows that
Example 3.2.1 This example is the same as Example 3.1.1 except that the waiting room has limited capacity: c < oo, and therefore X(t) s + c. The arrival process into the system has the Ft-intensity A ( t ) = XIX(t-)js+c-~ and (average) intensity XP(X(0) < s c 1 ) = X ( l - P(X(0) = s c)). Papangelou's formula immediately implies
<
+ -
(3.2.3) P$(x(o-)
= n)=
P(X(0) = n )
(1
- P(X(0) = 8 + c)) '
+
O
.,
3 Event and Time Averages
Proof: In view of what precedes, the only property to prove is the 'only if' part. Assume that ESTA holds, then for any bounded f : E -+ &I we have
171
In view of the general results concerning conditional Palm probabilities (Chapter 1, 5 5.2), for any 3t-predictable process {X(t)) of the form X(t,w) = X(O,Otw), where X(0) is 30--measurable and for all bounded functions f
that is
and the conclusion follows from Watanabe's theorem.
0
Example 3.2.3 ANTIPASTA for Markov chains. The setting is the one described in Example 1.3.3 and 5 5.3 of Chapter 1. We consider a Markov chain ( X ( t ) ) with state space E, and we suppose that it is at equilibrium. Let N H be the point process counting the transitions from state i to state j for all (i,j ) belonging to a given set H C E x E - diag(E x E). As was shown in Example 8.2.2 of Chapter 1, the F?-intensity of N H is
where { q i j ) is the infinitesimal generator of {Kt). According to the ANTIPASTA theorem, ESTA holds for ( X ( t ) ) and NH if and only if NH is -Poisson. 0
Conditional PASTA. We consider a point process predictable intensity { X ( t ) ) of the form
N with the (P,&)-
where ( Y ( t ) ) is some Ft-predictable process taking its values in a denumerable set E, of the form Y(t,w) = Y(0,Otw). For fixed i E El we consider the point process Ni defined by
The intensity of
Ni(C)is
From Papangelou's formula
and
and therefore
Ot) is ergodic, thd. above equality reads If (P,
Example 3.2.4 Insensitivity of M / G I / 1l o o LIFO preemptive. The service time sequence {an) is i.i.d. with c.d.f. G ( x ) and mean j~-%nd the input process N is Poisson with intensity A. Assume that p = Ap-I < 1 and that the system is in equilibrium. Call X ( t ) the number of customers in the system at time t. For fixed k 1, denote Nk the point process counting the arrivals that make the congestion process {X(t)} reach level k, i.e.
>
Let {Tik)}be the sequence of points N k , with the usual convention ~ o ( " 5 0 < Tik). A customer arriving at time ~ ! i requires ~ ) the service uik). The following fact is true: {aik)) is i.i.d. with the same distribution as {u,} (we shall admit this, although it requires a proof). receives all his service Because of the LIFO preemptive rule, customer when the queue is at level k (Figure 3.2.1). Since k is recurrent (under the stability hypothesis), the law of large numbers give
TA~)
that is
showing in particular the insensitivity of the M / G I / 1/m LIFO preemptive queue, i.e. n depends on G only through its mean. The proof of insensitivity can be extended to the situation where the input process N admits the (P,F t ) intensity
where {Ft}is the history recording the past of N a t time t and the whole sequence {a,). Now, we have t o use Papangelou's version of PASTA
showing insensitivity.
0
P A S W and the Martingale SLLN. The following result can be considered a s a non-stationary version of the classical PASTA result (3.1.2). The framework is that of !j 9.3 of Chapter 1 and in particular no stationarity is assumed for {Z(t)). Assume that (3.2.14)
3 lim
t-roo
Nt = A, t
where 0 < X
< m.
St X ( s ) d s
= X (from the results in the examples of $ 9.3 Therefore 3 limt,, of Chapter 1). Assume moreover that f is bounded, so that condition (9.3.7) of Chapter 1 is verified. Then, if either limit involved exists, the other exists, and (3.2.15)
lim "t'
-
1
Nt (O,t]
f ( ~ ( s ) ) ~ ( d= s ) lim t-oo
I t
This result immediately follows from the general theory of !j 9.3, Chapter 1.
174
3 Formulas
4 Formulas Derived from Conservation Equations
175
Taking for instance f (x) = l { , ) ( x ) , where n 2 1, and denoting 0 rA ( n )= P ~ ( x ( o - )= n ) , &(n) = P;(x(o-)
rder Equivalence Congestion at Arrivals and at Departures. There are a number of formulas which follow directly from the definition of Palm probability, which we recall here under its expectation form
where N and { Z ( t ) ) are compatible with the flow { B L ) , X is the intensity T,) is the sequence of times associated with (finite and non-null) of N, and I ~.
= n),
we obtain
As for n = 0 , taking into account the fact that X ( 0 - ) 3 0 , and that X ( 0 - ) 0 if 0 is a departure time (which it is under P:) :
>
Summing u p t h e last two equalities, we obtain for all i 2 0
A'.
For instance, take the situation described in Example 1.1.1 or Example 1.1.2. More generally consider a 0t-framework with two simple point processes A and D and a stochastic process { X ( t ) } ,all compatible with the flow (41, and linked by the relations
(4.1.3) A((O,tl) 2 D((O,tl). Moreover, X ( 0 ) 2 0, so that X ( t ) '1 0. Also assume that A and D have no common points. Let us write down the evolution equation of a stochastic process of the form { f ( X ( t ) ) } .Since a change occurs only a t a point of A or D
First Order Equivalent of a Queue and Norton's Theorem. Suppose that A and D admit the Ft-intensities { X ( t ) }and { ~ ( t )respectively, ) where {Ff} is a history of { X ( t ) )that is compatible with the flow {fit}. In particular, the stoch&tic processes { X ( t ) } and {,u(t))can be chosen compatible with { & ) . By Papangelou's formula
where we have used the fact that a t point 0 there are no arrivals or departures under P . Defining
ii = E[X(O)I X ( 0 ) = i], fii = E[p(O)I X (0) = i], ~ ( i=)P ( X ( 0 ) = i), oint of A, f(X(t)) = f(X(t-) - 1 ) . Therefore
+ 1) and at a point of D, f(X(t))=
f( X ( t - )
we obtain
(4.1.7) Xn%(i)= ii?r(i), ~ n g ( i=) jigr(i) and therefore, in view of (4.1.4) and (4.1.4')
07,-(0)- fi1r(1) = 0,
+
Ai-~*(i - 1) - (A, -4- bi)*(i)+ ji,+l~(i1 ) = 0. Dividing by At, taking expectations with respect to P , observing that E [ f (X( t ) ) ]= E [ f ( X ( O ) ) ]and , using (4.1.1), we find that
G [ f (X(O-) + 1 ) - f (X(O-))I = E o I f (X(O-) - 1) - f (*(O-))I.
Therefore n is the stationary distribution of a birth and death process with parameters {A,) and (ji,}, called the first order equivalent birth and death process of { X ( t ) ) . If (P,& ) is ergodic, Equalities (4.1.7) become
178
3 Formulas
4 Formulas Derived from Conservation Equations
We can check that &, .-
ai
Cj=lQ j
iO = A-, 1-c: (4.1.17)
, (l<j
1-P Ai
= A-I
P
is the unique probability distribution solution of the traffic equations (4.1.11). Therefore, for any n with the last coordinate fixed equal to n K , we obtain 1 --
sf
n(n 1 n ~ )
Crn/mK=nK
179
~ ( m )
c
(&p ,
for some C depending only upon M , K , ~ K and the routing probabilities. The constant C must be equal to G(K - 1, M - n ~ since ) C n ( n I n ~ =)1 and ni = M - n ~ . 0
c&'
Example 4.1.2 Equivalent birth and death process for GI/M/l/ca FIFO. Let U ( x )= Pi(Tl x) be the inter-arrival cumulative distribution function. From the classical theory of queues (see N.V. Prabhu, Queues and Inventories, Wiley, 1965, p. 43-44), we know that
<
where [ is the unique solution in ]0,1[ of
(i 2 1). 0
Remark 4.1.1 Observe that since PZ(X(0-) > 0) = [, the parameter can be estimated by
I
. .
(4.1.18) [ = lim
-
Ix(~-),oA(ds). 0
Remark 4.1.2 F'rom (4.1.15) we see that iff = p, then n;
n. In this case, we have the ESTA property without the arrival process being Poisson. 4.2 Brill and'posner's Formula
Let {Z(tJl be a corlol, real-valued stochastic process compatible with the flow { O t } , and let N contain all the discontinuity points of {Z(t)), in the sense that
N(C)2
C 1~(3)%z(s-)~ s EC
(recall that we are considering a system in equilibrium, and in particular
p = XEi[a] < 1). We shall now compute ~ ( i = ) P(X(0) = i) using the
extension of PASTA theorem and the relation ai(i)= &(i + 1) (Formula of D is pl{x(t),o), and therefore (4.1.6)). Indeed, the F:-intensity
That is to say
and therefore
for all Borel sets C. Assume that N has a finite non-null intensity A. Call (T,) the sequence of points of N and suppose that there exists a stochastic process { Z i ( t ) )compatible with (&) and such that for all n E Z, rt
Let now
f : B -+ IR be a function such that
for some function f' : If% -+ If% which is to be interpreted as the derivative of f . Therefore, for all t 2 0
and, as we already know from (1.2.1)
Finally, from the extended PASTA theorem, Xn:(i) = & x ( i ) , SO that
for all n E Z
We assume that
for some function g :
R -r R satisfying, for all a , b, E i[&t
We also suppose that for some a and b (4.24 d a )
# 0,d b ) # Q, implies
so that (Z(t)} does not stick t o the boundaries a and b. The function
P(Z(0) E [a,b]) = -
(A; - A,)Ld~, g(y)
where A$ is the intensity 'of admits the density
is well defined and in (4.2.3) we can take
Df.In
particular the P-distribution of Z(0)
From a simulation point of view, it is preferable t o give the following ergodic form t o the above identity, which of course requires the ergodicity of (P,Bt) :
T h e evolution equation (4.2.3) then takes the special form
(4.2.12)
1 g(y).fz(y) = - t-w lim t
x
{IZ(T,)>Y - ~Z(T,-)>Y}1Tn5t .
rill
Example 4.2.1 The workload level crossing formula. If Z(t) = W(t), where W(t) is the load a t time t of a single server queue, g(y) SE -1 and
Taking expectations in (4.2.8) leads to P(Z(Q) E Ia, bl) =
<
y t o > y) a t arrival instants or counts the number of upcrossings (from equivalently, the number of downcrossings of level y (from > y t o y). Thus For each y E R, define the point processes
Dj and D;
<
by More generally, if g is strictly negative and if the jumps of {Z(t)) are all upwards
<
T h e point process D$ counts the upcrossings of level y (from y t o > y) by (Z(t)} which are located at a discontinuity of {Z(t)). A similar interpretation holds for D;. Using (4.2.9), the observation that
0
'
ernark 4.2.1 Defining the Palm c.d.f.'s of Z(Tn-) and Z(Tn) respectively by F,TZ and F&, and the stationary c.d.f. of Z(t) by FZ , Equation (4.2.9) can be written
182
3 Formulas
4 Formulas Derived from Conservation Equations
183
This formula is due to Taka&. In the special case when the arrival process is Poissonian ( M / G I / l / o o ) ,the PASTA property gives E;[eiuW(O-) 1 = E[~"'~(O)] and therefore
xample 4.2.2 If we apply (4.2.15) to the case when Z ( t ) = W(t), the workload of a G I / G l / l / c a FIFO queue, we obtain where P,,(u) is the characteristic function of cro. This formula is referred to as Pollaczek-Khinchin's characteristic function formula where Fw is the stationary c.d.f. of W(t), I;va is the Palm c.d.f. of the sojourn time V, and F- is the Palm c.d.f. of the waiting time Vn. a: w
Vo
TakaEs' Formula an
System without Vacations. Let ( W ( t ) ) be the workload process of a stationary G/G/l/ca stationary queue. The evolution equation of X ( t ) = e"W(t) is
Taking expectations, observing that in the stationary regime ~ [ ~ " " w ( t= ) ] E[~"W(O)
System with Multiple Vacations :Cooper's Formula. Let now { W ( t ) ) be the workload process of a M / G I / l / w stationary queue with multiple server vacations : as soon as the queue becomes empty, the server takes a vacation. The sequence of vacation times {Vn) is assumed i.i.d. and independent of the arrival process. It is supposed that if at the end of a vacation, the server finds the queue still empty, he takes another vacation ; and so on, as long as the queue remains empty. Call Nv the point process counting the starting times tk of vacations. The workloa,$ process verifies the evolution equation
If equilibrium is assumed, E(W(t)] = E[W(O)], and therefore, denoting by Xv the intensity of the vacation process N v ,we have
1 which gives
we obtain
The evolution equation of (expfiu W ( t ) ) }is
Suppose that a, is independent of W(Tn-) (this is the case in a G I / G I / l / m queue). Then
In a G l / G I / l / c o queue, E ~ [ e i u b o= ] E[eiuuOj,and therefore, taking into account P ( X ( 0 )= 0) = 1- p
+
(4.3.3) iu~[e~"*(')]= X E ~ [ ~ ~ ~ ~ ( ~ -- 1) ) ] (iu(1 E [-~p).~ ~ ~ ~ ]
Observing that W ( t k - ) = 0 and that the Lebesgue measure of {t 1 W ( t )= 0) is a.s. null, we obtain the following formula after computations similar to those performed in the derivation of TakaEs' formula, and when assuming the existence of a stationary state :
where tPV(u)and !Pg(u) are the characteristic functions of Vo and ao respecerefore, using the expression (4.3.6) for the intensity of vacation process
ernark 4.3.1 Observing that
where F v ( x ) is the c.d.f. of Vo, we see, from formulas (4.2.4a) and (4.2.4b) of Chapter 1, that the above expression is that of the characteristic function of the forward (or equivalently : of the backward) recurrence time of a stationary (delayed) renewal process corresponding to the c.d.f. Fv. C1
k 4.3.2 From expressions (4.3.8), (4.3.9) and the previous remark, and also observing t h a t in the vacation system as well as in the original sysTn-)= V, is the waiting time before service when a FIFO discipline is assumed, we find that, with obvious notations d .
where Y is a random variable having the same distribution as the forward recurrence time of a stationary renewal process carresponding t o the c.d.f. Fv. In words : (4.3.11) The waiting time of a M / G I / l / o o FIFO system with multiple independent vacations of c.d.f. Fv is distributed as the sum of two independent random variables X and Y , where
end of vacation
beglnlng of ~Ca!hl
Fig. 4.3.1. A vacation queue
where F ( t ) is the forward recurrence time a t time t of the point process with time sequence {Vl + . . .+ V,), n 2 1. Call p p (u) the characteristic function of the stationary forward recurrence time, assumed to exist. In other words, we assume that
'&
o
X is distributed as the waiting time in the same M / G I / l / o o FIFO system without vacations; Y is distributed as the forward recurrence time of a stationary renewal process corresponding to the c.d.j. Fv.
(4.3.15)
lim E [eiuF ( t ) ] = $F* (u),
trm
for a characteristic function c p p . In view of the FW1-measurability of U, and of the independence of the 3%and {Vk), k 2 1, we have:
0
.,.
L
A General Case. Let us go back t o the general situation described in Chapter 2, $ 6.3, with the same notation. In the FIFO discipline, the waiting time of the customer arriving a t time Tnis
where +F(u, t ) is the characteristic function of F ( t ) . Therefore, by bounded convergence,
defined by this relation; see d s o Figure 4.3.1. Therefore provided limttm E [eiu W " T n - ) ]
exists. In other words, under the conditions
186
5 Queueing Applications of the Stochastic Intensity Integration Formula
3 Formulas
187
we have
where X and Y are independent and are distributed as XI and Yt respectively. This clearly generalizes (4.3.11). emark 4.3.3 If we do not wish to make an assumption such as (4.3.17), we can instead consider the stationary system constructed in 3 6.3 of Chapter 2, and obtain the relation .
ueueing Applications of the Stochastic Intensity Integration Formula 5.1 Reminder In this section, we shall demonstrate how the stochastic intensity integration formula can be useful in obtaining queueing relations. For instance, we shall provide a proof of Cobham's formulas in $ 5.2. First recall the notion of a Ft-intensity kernel for a marked point process ( N , ( L ) ) . Defining ( Z ( t ) ) , t E R by Z(t) = C n E Z Z n l [ ~ n , ~ n + , )it( tis) , assumed that (FL} is a history of (N, (2,)) that is to say
This relation is obtained by first observing that
(since W ( 0 )= Wl(0) +F(O)), and then by taking expectation in (4.3.7), and 0 using (4.3.6).
4.4 Backward and Forwar Recurrence Times Let N be a stationary simple point process with finite intensity X > 0. Another way of obtaining the joint distribution of the stationary distribution of the backward and forward recurrence time at time 0, B(0) and F(0) respectively is the following: Write the evolution equation
A s t o c w t i c Ft-intensity kernel of (N, {Z,)) is a function X : R x R x E (where (E, E) is the measurable state space of {Z(t))) such that
--t
&I
(a) ( t ,w ) -+ X(t, w , C) is Ft- progressively measurable for all C E E, (b) C -+ X(t,w, C) 3s a measure on ( E , E) for all (t,w) E R x 0, (c) J: X(t, E)dt < co, P-a.s for dl [a,b] c BB, and for all C E E,(X(t,C)) is a Ft-intensity of Nc, where Nc(A) = CnEZ lA(Tn)Ic(Z,) (see Chapter 1, 5 8, for the definition of stochastic intensity). Denoting
the stochastic intensity integration formula states that
( 5 . 1 E[ R E
bservifig that B(Tn-) = Tn - TnW1 , B(T,) = 0 , F(Tn-) = 0 , F(Tn) =
T,+l- Tn and taking expectations, we obtain
ut TIand -T-l
have the same distribution under
with obvious notations. In particular, with v = O
Pi. Therefore
11
H ( t , r)N(dt x dr)] = E[
R
E
~(t,z)~(t,dz)dt],
for all non-negative functions (t,w,z) -4 H(t,w,t) from IR x R x E into 3 that are P ( 3 ; ) @I E-measurable, where P ( F t ) is the Ft-predictable a-field on R x R (see Chapter 1, 8). Recall that the left-hand side of (5.1.1) is by H(Tn,Z,)]. definition equal to E[CnEZ
Example 5.1.1 Mean busy period in M/GI/l/co. Let {(T,, on)), n E N, be an M / G I input flow with To = 0, and let { W ( t ) ) , tE EX+, be the nonstationary workload process, with W(0-) = 0 and W(O) = ao. Let R1 be the first strictly positive time at which the system is empty (oo if the system never empties). Assuming that there is a unique server working at unit speed, we have, for any I{ > 0,
type. There is one server operating at unit speed, the service discipline is non-preemptive, FIFO for the customers of the same class, and priority is given t o customers of class i over customers of class j if i < j. Equilibrium is assumed, and in particular Clearly R1 is a 3 : v FF-stopping time, where A is the arrival process (with associated arrival sequence {T,)): indeed (R1 t ) only depends on the variables Tk,ak, where k is such that Tk t. Therefore
<
<
Recall the definition
verifies the assumptions for (5.1.1) with respect to Ft = Fe V 3f.Since the Fe-intensity kernel of (A, (a,)) is XG(dz) where X is the intensity of A and G is the common c.d.f. of the service times, we obtain from (5.1.1) and (5.1.2)
Define the history (F,,t) by
Defining Ni(A x 6 ) = ~ n E Z 1 ~ ( T i , n ) l ~ ( ~then i , n )(see , Example 8.2.3 of Chapter 1) the marked point process, (Ai, {aj,,)) admits the 3+-intensity kernel X,G,(da), that is to say
for all non-negative functions H : R x R x iR+ -+ R that is P(3;,t)@ B(I$.)measurable. Define the virtual i-customer a t time t as follows: it is a customer arriving a t time t with the required service
and therefore ER1 is finite and given by
(set K = oo in (5.1.2) and (5.1.3), with an equality instead &an inequality). Thus p < 1 is a sufficient condition for E[Rl] to be finite in a M / G I / l / c c queue. I t is also a necessary condition, in view of E[R1] = E[ao] pEIRl]
+
a
Although, the above proof does not teach us anything new, it shows how martingale calculus can be used. The next application contains a more elaborate usage of the stochastic intensity integration theorem.
Thus, if t = T,,,,+,(T,,,) = a,,,. Call c ( t ) the waiting time of the virtual i-customer a t time t (all priority rules being respected), C,(t) the time required t o clear all customers of class 1,2, ...,i present in the waiting room (therefore excluding the customer presently served) a t time t and D,(t) the additional delay incurred by the virtual 2-customer due to those customers of class 1, ..., i - 1, arriving during the time interval ( t ,t %it)] (such customers with higher priority than z arrive in the system whereas the virtual i-customer a t time t is still waiting, and pass in front of him in the line). Accounting gives
+
Non-Preemptive Case: Gobham's rmula. cobham's formulas the average waiting time of a customer of a given type in a M/GI/l/oo . More precisely, we consider the situation of Example 1.1.2, with t itional feature that the M input flows corresponding t o the M classes of priority are independent and of the M / G I
where R(t) is the residual service a t time t. The residual service time formula (2.2.9) gives
190
5 Queueing Applications of the Stochastic Intensity Integration Formula
3 Formulas
191
Recall that (see Chapter 1, •˜ 5.2)
The clearing time Ci(t) has the following expression
(5.2.9) where where g,, is the waiting time of the customer of type i arriving at time Ti,,. Taking expectation and observing that u~,, is independent of and G,,, and also that
x,,
Eii[fi,o]= E:[V~ I customer arriving at To = 0 is of type i],
vn is the waiting time of a customer arriving at time T,.
0
emark 5.2.1 In order to show that E[G(o)] = E;,[G,~], using the PASTA property, some care must be exercised. Indeed Al is a 31,t-Poisson process with intensity Xi and G,o = G(%,o) = G(0) Pi,-a.s. . However (G(t)} is not a Fttt-predictable process, when 3 t P t is defined by (5.2.1). This problem is easily circumvented by introducing the u-field
the number of type 1 customers in the waiting room, we obtain (we add to 3 1 t t the future of the service process). The point process is a Pl,t-Poisson process of intensity Xi, and this time { f i ( t ) ) is a left-continuous process adapted to h , t , and therefore BIBt-predictable. 0 The additional delay Di(t)has the following expression
Example 5.2.1 M / G I / l / m SPT non-preemptive. In this discipline the customer with smallest required service (Smallest Processing Time) has nonpreemptivepriority over the others. Calling G(x) the c.d.f. of the required service time, we have .
Now, the process (l~,,,+G(,)l(u),uE R] is adapted to {Ti,,)(in order to and leftcheck whether u E. ( t , t f %(t)]or not, it suffices to observe Fit,) continuous. Therefore, from the above expression of Dj(t) and the stochastic intensity integration formula,
Proof: Consider 3 priority classes: in class 1, put all customers with required service less than or equal to x - h, in class 2 those with required service in (x - h, x],and in class 3 the rest of the customers. Thus (ignoring class 3)
Little's formula and the PASTA property (see the remark after the proof) give
Combining equations (5.2.2) to (5.2.6), we obtain Cobham's formula (nonpreemptive case):
From the PASTA property, we obtain as above
Applying (5.2.7)-(5.2.9), we obtain (5.2.10). In the case when x is not a discontinuity point of G(x), letting h go to 0 in (5.2.10), we obtain
..
rmula. In the preemptive case, the e of a customer of class i arriving a t time t is where Ijl(t) is the time between t and the first time the customer receives attention from the server, and G,(t) is the sum of the service cT,(t) and of the service of all customers of class 1,..,i - 1 arriving in the system in the interval ( t F,(t), t F,(t) G,(t)]. Clearly in the computation of E[F,(t)], the customers of class i c 1, ...,K do not play a role, and therefore E[F'(t)] is the average waiting time of a class i virtual customer arriving a t time t in a system with only customers of type 1,...,i, in the non-preemptive case
+
+
+
The term Gi(t) can be expressed as
Application: the c / p Rule. Consider the M / G I / l / o o system with M priority classes with non-preemptive priority as de~cribedat-the beginning of e present subsection. For simplicity, denote E[K(O)] by V,. Our objective is to minimize the functional
where c, > 0, among all possible rankings (in terms of priority) of the M classes. We will show that the classes should be ranked according to the value of c / p , that is non-preemptive priority is given to class i over class j if and only if > $ (in the case of equality = give highest priority t o i or j indifferently). To prove this result, compare two rankings A and B differing only in two adjacent classes. More precisely, suppose (for convenience) that ranking A corresponds to
z,
2
where i > j means that class i has (non-preemptive) priority over class j, and suppose that ranking B exchanges classes i and i 1
+
and arguing as in the non-preemptive case, we obtain
qA d
Call and the average waiting time for a customer of class j under the rankings A and B respectively. Also denote Therefore, observing that E[bi(t)]= E[ai] (PASTA), we obtain (5.2.14)
E[Gi(t)] =
E[ai] 1-
~ i z6%'\
From the expression (5.2.7), we see that
Combining (5.2.12)-(5.2.14), we obtain
pk = p?, for all k,
i, k # i + l , s o that
Kleinrock's conservation law
(5 2.3) gives
Mere also, in view of PASTA
EIV,(t)J= Ei' IV;,ol = E ~ [ V OI the customer arriving a t To = 0 is of type i], e sojourn time of the customer of type i arriving a t time Ti,n and V, is the sojourn time of the customer (of any type) arriving a t time (5.2.16)
T,.
n
that is, in view of the previous remark (5.2.19)
pi(qA - q B ) = - p , + l ( t $ ,
From (5.2.18) and (5.2.19), we obtain
-KT,).
15 k
< M, k #
194
3 Formulas
cA cB
Bibliographical Comments
-
Now - < 0 (think, or use Formula (5.2.7)) and therefore cA C B < 0 > if and only in This proves the result since, for any ranking not satisfying the $ condition, we can find two adjacent classes i and i + 1 violating the condition, and exchanging these two classes would give a better ranking.
2 E.
Example 5.2.2 The pc rule. Suppose we wish to minimize
where Qi = E[Q;(t)], the average number of customers of class i in the waiting room a t time t. From Little's formula
and therefore, from the previous results, we see that priority should be given to class i over class j if pic; > p j c j . 0
Example 5.2.3 Optimality of SPT non-preemptive. Consider a M / G I / l / w queueing system. Then among all the non-preemptive service disciplines based on the required service time, S P T non-preemptive minimizes the average number of customers in the system. This result follows from the pc rule of Example 5.2.2 which c; 1 (minimizing the average number of customers E[Q(t)] in the waiting room is same a s minimizing the average number EIX(t)] of customers in the system, when there is one server). Thus in Example 5.2.2, in order to minimize E[Q(t)j, we must give highest priority t o the class with smallest average service time. A limiting argument (with class i formed of those customers with required service between i h and (i + 1)h) gives the optimality of S P T non-preemptive. 0
Little's formula (1.2.3), or (1.2.4), seems to have been well known by practitioners before a proof appeared in Little [861. A number of proofs with varying degrees of generality and rigor followed this article, the history of which is recorded in the review article [133]. The proof given in fj 1.2 follows the general ideas expressed in [47], were the reader will find abundant historical comments. The derivation of the response time for M/Gl/l/co P S in Example 1.2.5 is borrowed from Wolff [I361 which contains many other examples of this type. Formula (1.2.18) of Example 1.2.4 is sometimes proved by a statement like: "it follows from L = XW that ..." and this is why we presented it in the section devoted to Little's formula. The Swiss Army Formula
195
(1.3.15) was given in [28]; considering the obvious interpretation of Remark 1.3.1, and the numerous formulas that it generates, it is only surprising that it was not discovered earlier. The ordinal L = XW Formula (1.3.13) is due to.. Halfin and Whitt [Sl]. The insensitivity problem has a long history recorded in the monograph [47] (see also [115], [116], [117]). The theory of insensitivity by Palm calculus can be found in the paper of Jensen, Konig and Nawrotzki (591; (see also the monograph [4]). The H = XG formula was discovered by Brumelle 1321. It is equivalent to the generalized Campbell's formula (Equation (3.3.1) of Chapter l, due to Mecke [93], Satz 2-3 thereof). The light traffic analysis of Example 2.1.1 comes from [5]; more complete results using analytical methods are given in [lo81 (see also [18]). The treatment of the conservation formulas of 5 2.2 and 5 2.3 is inspired by Kaliihne I621 and Chapter 11 of the book by Heyman and Sobel 1551 (see also (331). A fundamental article in the area of work conservation is that of Wolff [134]. For applications and references concerning the conservation formula (2.3.5), see Kleinrock [75]. As mentioned in [27], the ESTA results when there exists a stochastic intensity are implicit in the work of Papangelou [105]. An ESTA result not contained in Papangelou's work and containing PASTA as special case can-be found in the article by Konig and Schmidt [76], which contains the first Agorous proof of PASTA in the general case. The proof of PASTA in the non-stationary case is an extension, in the martingale parlance, of the proof of Wolff [135]. As is now well known, the result of [I351 is a consequence of the martingale stiong law of large numbers, and in this respect, Theorem 8.3.22, p. 250, of Dacunha-Castelle and Duflo [36] gives all the details without mention of PASTA. For the job observer property of fi 3 we refer for bibliographical comments and additional information to the book of Mitrani, [95]. More details and references concerning PASTA can be found in the review article [29]. The first order equivalence result of 5 4 first appeared in the monograph 1261 and was used in the proof of Norton's theorem by Lazar and Hsiao, (811. For Norton's theorem of 5 4, we refer t o the monograph of Walrand [129], which contains additional details, bibliographical comments, and also a nice heuristic proof. The result of 4.2 are those of Brill and Posner, [31]. The proof presented in the present monograph only slightly differs from that of Lazar and Ferrandiz [81]. The proof of TakaEs formula (4.3.4) using evolution equations comes from Bremaud and Jacod [25]. This proof was extended by Kella and Whitt [68] t o cover the case with vacations. The basic decomposition (4.3.11) for the M/GI/l/oo queue with multiple vacations is due to Fuhrmann and Cooper 1481. A review of systems with vacations is given by Doshi 1391, the general spirit of which inspires our treatment. In the non-preemptive case, the priority formulas of 5 5 can be found in Cobham [35]. For the preemptive case, see the paper by Phipps, [106]. The proof presented in the present monograph is new. For applications, see [75] and P51
.
Since many queueing systems are analytically untractable, one often has to resort t o more qualitative properties such as the monotonicity of the waiting or sojourn times with respect to the service or inter-arrival times. This often leads to the derivation of bounds which may give useful information on the behavior of a system which cannot be exactly computed. Another application of stochastic comparison is optimal design, where one does not necessarily want t o compute the performance of a particular system, but one only wishes to show that the system is the best, for some criteria, among a given class of systems. Such optimality results are collected in 5 1. A systematic approach t o the comparison of queues goes through the study of stochastic ordering of random variables or of their cumulative distribution functions (c.d.f.). A stochastic order can first be seen as a partial order on a set of c.d.f., like for instance the integral orderings defined in 5 2.1. T h e simplest example on R is the increasing stochastic order Si defined as follows: two c.d.f. F and G on R are such that F
sic,,
sic,
sic,
<
A 4-non-decreasing (resp. non-increasing) function is also called Schurconvex (resp. Schur-concave). Example 1.1.1 The functions f ( x ) = C x i or f ( x ) = maxxi are Schurconvex functions. More generally, for all 1 < k < n, the function
Taking a = O , in the last relation allows us to conclude the proof. (b) + (c). If x lies in the convex hull of {y,, y E r), then
is Schur-convex (use Remark 1.1 .I). 0 Equivalent definitions of the majorization partial order are given below. Let r be the collection of permutations of (1,. . . ,n,), and for y E r,z E Rn, denote 2, = (z,(~),. .. ,z,(,)). Also call 4 : Rn -+ R symmetric if +(x) = 4(x,) for all y E r and all x E Rn.
where the real numbers p, are non-negative and sum up t o one. If metric and convex, we then have
(1.1.3) The following properties are equivalent ("13: 4 Y ; (b) x lies in the convex hull of the set {y,, y E r); (c) 4 ( x ) < +(y) for all convex symmetric functions 4.
(c)
4 is sym-
* (a). It suffices to observe that the functions
Proof: ( a ) =$ ( b ) . The point x lies in the convex hull C of the points {y,, y E are all symmetric and convex.
I') if and only if
1.2 Optimality of the SRPT Discipline in G/G/l/oo or equivalently if
ithout loss of generality, take y such that yl 5 yn. Let ,O be a permutation of I' such that cp(l) . . . 5 CP(~).The maximum in the right-hand e of (1.1.4) is reached for y = 0-l (see the proof of (3.3.7), Chapter 2). om Remark (1.1.1), we obtain that for all a E
<
+ . .
r,
and that for all I = 2,. . . ,n and a E r , n
n
Multiplying (1.1.5) (resp. the I-th inequality of (1.1.6)) by cp(l) (resp. cp(l)summing up the n resulting inequalities, we obtain that for all a! E I',
In •˜ 4.2 of Chapter 2, we constructed a state representation which features the most common service disciplines including FIFO, LIFO and SRPT. We now show how elementary sample path arguments can be used in order to compare these disciplines using the partial orderings introduced above. The notations and definitions of this section are those of $ 6.2, Chapter 2. (1.2.1) If $J denotes the SRPT discipline, then for any other admissible discipline 4, S+ S*, Po a.s. emark 1.2.1 We only defined majorization for finite dimensional vectors. The property S4 4 S+ should be understood as the comparison of two vectors of dimension J, where J is the smallest integer such that S$ = S> = 0, for !J all i > J. Proof of (1.2.1) We want to prove that the event { S 4 4 S+)is of probability one. For this, it is enough to prove that this event is 8-contracting, since on (W =0), O = S+ 4 S+ = 0 and PO(W= 0 ) > 0. Let .? be &_reorderingof S E RN in decreaing order, i.e. g1 2 2 . . .. Observe that S+ = S+ by definition of $J=SRPT. On the event {g4 g+), by definition of 4 ,
s2
4 Stochastic Ordering and Comparison of Queues
202
for all k > 1 , and
1 Comparison of Service Disciplines
(1.2.5)
X+(t) < X+(t), t E $
203
P-as..
A direct application of Little's formula shows that (1.2.6)
From Equation (6.2.8), Chapter 2, for all k 2 1, and all disciplines 4,
EOIV$]<_ E'[v+],
for all admissible disciplines 4, where V ,denotes the stationary sojourn time under discipline 4. These optimality results should be stated together with their counterpart that for all Schur-convex functions f ,
where
From the definition of the S relations that for all k > 1
T discipline $, we obtain from the last two 1.3 Optimality of the FIFO Discipline
whereas for
4,
R e o r d e r i n g of Vectors and Majorization. We start with two technical lemmas on majorization (1.3.1) Let X I $2 . . . x, and y, 5 yz . . . 5 y, be real numbers. For any permutation y on (1,2,. . . , n ) , such that there exist some i, j , 1 5 i < j 2 n, with ~ ( i >) y(j), let 7' be the permutation of (1,2,. . . ,n) which is obtained from 7 b y interchanging the values of y on i and j :
<
When using this together with (1.2.2), we obtain that 8. For iE = 1 , we have
C z kZ i o 2~ C g , 3;o
<
<
<
Then (1.3.2) 0 Therefore {S+ 4 S+) C {S+ 0 0 4 S+ o 8). Since {&,, -: S+,,, n E Z) r {S+(t) 4 S+(t), t E R), another application of the invariance results of •˜ 7.2, Chapter 1, implies the following result, in view of (1.2.1): (1.2.4) If @ is the SRPT discipline and 4 is any other admissibk disciplane
(y,~ - X ) 4 (y,
Proof: Since Yy(i) - Yy(j) 1 0 and xi - X j 0 5 E < 1 such that E(Y~(;)
(
+S
t )
t E
I$ P-as.
- s).
< 0, there exists a real number
- ~ 7 ( 3 ) )f (1 - €)(xi - x j ) = 0.
This relation can be rewritten under the two equivalent forms
In particular let {X4(t), t E R ) be the process counting the number of customers present in the system a t time t under discipline 4. Since for all k 2 1
we see that I+
< I+. Since I+ = X4
which imply that (y,~ - x ) lies in the convex hull of the points {(y, - x), ,v E This in turn implies that (y,, - x) 4 (y, - x ) in view of (1.1.3). D
r).
As an immediate application of the preceding lemma, we obtain (1.3.3) Let XI 5 $2 5 . .. < z n and y l 5 yz < . . . < yn be real numbers. Then, for all y E I"
where y- is defined by y- = (y,, %
.
Example 1.3.2 LIFO non-preemptive. The random variables {Un), denoting the successive jump times of {It), are Bt-stopping times. We prove by induction on n that
. .. ,y,).
rgumed. Consider a GI/GI/l/oo queue with an admissible discipline 4, for which we use the same type of notations as in •˜ 6.2, Chapter 2. In particular, (It) denotes the corlol congestion process whereas
(s:;,
. .. ,S&-)
and
. . . ,):,s:
(s,:
denote the non-zero part of the residual service time vector at time t- and t respectively, when starting with an empty queue at To- = 0 (the first subscript Q, will be omitted when possible). We assume that 4 is non-preemptive and uses no i n f o n a t i o n on the service times (like for instance FIFO, LIFO or RANDOM), and we denote II, iscipline. Let A denote the 61/61 input of the queue; we show below that there exists a point process A', equivalent in law to A , and such that S*,t(A) = 2&(A') for all t. The proof of this property (from this point to Lemma (1.3.10) below) may be skipped on the first reading. Let Vu be the characteristic function of
G', = o(A(u),
u
2 0)
D
(s:,
o
a0
18,"-1
(1.3.6) E [exp (iuis;:
+ . .. + iur,,,-l~$-~+) I QU.]
=
t=1
with the' convention that both sides are zero on Iu, _< 1. Assume that the proQerty holds for n. On I",+, = Iu, 1 > 1 (that is, Un+1 is an arrival time, say Un+, = T,), we have Gun+, = Bun and since Q, is LIFO non-preemptive
+
and so by the induction assumption
and let Bt be the o-field
In words, this is the a-field generated by the arrival process and by the history of the residual service times of the customers who started their service before time t. The key property of non-preemptive policies using no information on service times, which we will need below, is that conditionally on GTn, the required service times of the 'fresh' customers (those who have not yet started their service) are i.i.d. and with the same c.d.f. as oo: (1.3.5) For all sequence,$ of real numbers ( w r ) , on the event I,,;, = j > 1, wlziclr, belongs lo &-,, ,
1% is the number of customers at time Tn+. 1 FII"O. In the FIFO case, (1.3.5) is a direct consequence of ral~~>l,OnIT = nj > 1 ,
and
where we also used the fact that om is then independent of So, V V(S& ). Similarly, if Un+l is a departure time such that Iu,,, > 1, then Bun+, = Bv, ~ ( $ -'+I 2 and using the induction assumption,
v
0 We obtain (1.3.5) by restricting (1.3.6) to arrival times. Let A be the following counting measure on R x ifB associated with the G I / G I input:
4 Stochastic Ordering and Comparison of Queues
206
*f
1 Comparison of Service Disciplines
Let S i n - S<&. (1.3.7) There exists a sequence o j random permutations yn : N -+ M, n 2 1, where y, diflers from identity on {O,1,. . . ,n - 1) only, and such that for all n, the counting measure +
+
is such that (a) S z k ( A ) = S&(An) for all k = (b) A and An are equivalent in law.
where of
fi
and for j
f2
207
are appropriate product functions. In view of the definition
> 1, the right hand side of the last expression is also
where the last factorization comes from (1.3.5). From (b) of the induction assumption, for all values of j
Proof: The proof is by induction. For n = 1, Sit0(A)= SJ,,o(A)= 0, so that we can take 71 equal to the identity and (a) and (b) trivially hold. Assume the property holds true for n. Then in particular SZn(A) = S&,(An). Define
where j = I+,,(A) = I+,n(An) kfInand
Therefore, the right hand side of (1.3.8) is simply E [f(r0,r1,. . . , Q , u ~ , .. .)] and the proof is concluded from the monotone class theorem. 0 Let A'
% ' ?Ck2,6Tk,,; be the point process defined by
A1(Cx K) = 11-00 lim An(C x K) Since 4 is non-preemptive, B & ~ +=~ Piif j > 0. Let y n + ~be a permutation which differs from the identityon (0,1,. .., n ) only, and which is such that: r
e
If In= 1, then yn+l = yn; IfIn>l,thenyn+l(l)=yn(l),forO
with 7n+1(1) = 1 elsewhere. Then by construction, Sgk(A) = SG,~(A"+'), for all 0 k n 1, which completes the proof of (a). In order to complete the proof of (b), we now show that for all bounded f : 1WbO x IWOO -+ $ .
< < +
Taking J of t'he form
we obtain
for C and 'h Bore1 sets of R If p < 1, this a s . limit is well defined since the permutations yn are then such that yn(k) does not depend on n after a finite rank (indeed, yn only permute indices within a busy period). Using this and (1.3.7) (b), we obtain: (1.3.10) The point process A' is equivalent in law to A, and such that for all t, &&(A) = S+,t(A1). Let T, be the first positive construction point of the queue. Then, the process {S+,t}, 0 5 t T,,fully determines the time B+,, a t which customer n, 0 5 n 5 p - 1, begins its service (see (6.2.9), Chapter 2.). Let B+ denote the vector (B+,,, n = 0,. . . ,p - 1) and let V+ be the waiting time vector V+ = (B+,, - Tn, n = 0 , . . . ,p - 1). In the particular case of policy 4, the waiting time of the n-th customer is also the workload a t the arrival of customer n, that is V*,, = VV,. We shall add a 'prime' to denote a variable associated with A'. For instance, {W,!,) will be the stationary workload sequence, B;,, the time at which the service of customer n begins under policy +, all for the arrival point process A' etc. Let T,t be the the first positive construction point of {W,!,). We have p(w) = p'(w) and more generally, all construction points of {Wn) are construction points of {WA) and conversely. By construction
<
(see Figure 1.3.1, for the particular case when I#C if LIFO non-preemptive). Thus, it follows from (1.3.3) that (with obvious notations)
Owing to the fact that A and A' are equivalent in law, we also have
The last two relations and the cycle formula allow us to conclude that the stationary sojourn time V+,O satisfy the following optimality property: (1.3.12) Eo[f(V+,o)]5 Eo[f(V+,o)], for all convex functions f such that the expectations exist. Let R+,0 and R+,o be the stationary sojourn times of customer 0 under disciplines qj and 4 respectively. (1.3.13)- E O [ f ( R + , o ) ] E O [ f ( R + , o ) for ] , all convex functions f, such that the expectations exist.
<
+
Proof: We have R+,o = V+,O a , where Example 2.2.1 below).
and a are independent (see 0
emark 1.3.1 We can define the same service disciplines in G I / G I / s / c o queues, and prove that within the class of disciplines which use no information on service times, FIFO is optimal in the same sense as in (1.3.12)-(1.3.13). 0
2 Comparison of 2.1 Integral Stochastic Orderings
Let V ( W )denote the set of c.d.f. on DiB" and C be a set of Borel mappings from Rn onto R. Consider the binary relation 5~ on V ( P )defined by the integral relation Comparison of FIFO and LIFO (1.3.11) V $ = ( B k - T ) - C ( B + - T ) = V + . From (1.1.3), this in particular implies that
for all convex functions f : R
-+
$ so that
F SL G if and only if
f ( x f ~ ( & )5
1
R"
f(~)~(dx).
for all f E C such that the integrals are well defined. The binary relation Sc is clearly reflexive and transitive, so that it always defines a partial semi-ordering on V(Rn) (if the set L is rich enough to imply the anti-symmetry property, <_cdefines a partial ordering). Such an order will be referred to as an integral order on V(gn).It will also be understood as a partial order on the set of Rn-valued random variables via the usual definition: X <e Y if P [ X 5 .] < L P[Y5 .]. Three basic instances of sets C are first considered. The set {i) = { f : Rn 4 R 1 f non - decreasing ) generates the increasing (partial) integral order on V ( R n ) .
290
4 Stochastic Ordering and Comparison of Queues
2 Comparison of Queues
The set {cx) = {f : Rn -+ B If convex ) generates the convex integral order on D(E; ), and is closely related to the projection stochastic order associated with <, alluded to in the introduction. The set {scx) = {f : Rn --, R If Schur -convex ) defines the Schurconvex integral order, which will be seen to be c'losely related to the pathwise stochastic order associated with +). Remark 2.1.1 Traditionally, the initials 'st' (for stochastic) are used in place of 'i' (increasing). We will see that the Si order is in some sense equivalent to the pathwise stochastic order associated with <; we will thus often refer 0 to it as the strong ordering. The following subsets of the above sets will also be used: s The set {icx) = {i) ~ { c x )which , generates the increasing convex ordering on D(Rn), and which coincides with the projection stochastic order associated with the partial ordering s The set {cxs) = { f : Rn -+R f convex symmetric), generates the convex symmetn'c ordering and coincides with the projection stochastic order associated with the partial ordering < on Rn. * The set {ip} = {f : Rn --t R+ If = : R 3 lW+ E {i)) generates the increasing product form xample 2.1.1 Exponential and Erlang Distrib~utions.Let G,,,(X) be the Gamma c.d.f. of parameters X and n, and Ex(%) be the exponential c.d.f. with parameter A. If n E N, we have
211
e
<.
Indeed let YI,. . . ,Yn be i.i.d. random variables, with c.d.f. Ex,and let X = Yl $. . . . C Y,.Then if f, is convex,
so that that Elf (Xln)] 5 Elf (Y)]. n e r e f o r e X l n
<,,
.'1
0
Example 2.1.2 Optimality of the FIFO disciphe. The setting is that of 3 1.3. From (1.3.10), for all Schur-convex functions f (like for instance the maximum of the coordinates), f (V;)5 f (V+), and therefore, in view of the equivalence in law between A and A', for all increasing functions g : R -+ Hg, E[g o f (V*)] E[g o f (&)I. Thus, for all Schur convex functions, f (V*) <_i f (%). 0
In addition, the fact that convex symmetric functions are Schur-convex (see (1.1.3)) implies
In general, these implications have no converse. ernark 2.1.2 For non-negative random variables, each of the inequalities F 5i G, F Sex G, F s i c , G and F l i p G implies the corresponding inequality between the moments (of any order) of the coordinates of F and G. For the ordering, we have the stronger property that, for all i = 1,. . . , n
provided these moments exist (indeed, both functions x xi and x -, -xi are convex). Thus, we will say that the variability of F is smaller than the variability of G since their mean values coincide and any even moment of F is smaller that the corresponding moment of G. 0 The preceding definitions will naturally extend to random vectors: the random vector X = (XI, .. . , X n ) is +dominated by Y = (Yl,. . . ,Yn) if F(x) = P[Xo 5 50,. - . ,Xn 5 xn] and G(x) = P[& 5 XO,. . . ,Yn x,], satisfy the ordering relation F S r G, or equivalently if
<
for all f : Rn 4 R E L. This definition does not require that the random vectors X and Y be defined on the same probability space. If we replace increasing functions by decreasing functions and/or convex functions by concave functions in the above definitions, we obtain the decreasing concave, concave symmetric, increasing concave, decreasing convex, etc.
<,,
<,
<
Some obvious relations between these (semi)orderings are quoted below for future reference: ( 2 . 1 and
=
+
and _<;=+<;,
For all the integral orders considered above, if f : Rn -i R is in C,so is f o 7 , where ;lis any permutations of (1,. . . , n ) . Therefore X
r
efinitions can then be extetde Let X < . . . , X n be Rk valued random vectors, all defined on the same probability space. Let Y < . . . , Yn in IWk be another sequence, possibly de. . ,X n ) , fined on a different probability space. Let X be the matrix (X1,. with a similar notation for Y. We will say that X < L Y if
x:,x;,
( X i , . . ., . . . ,XZ, . . . ,x;, . .. ,X;) < L (Y?). . . ,Y;,Y;,.. .Y&. . .,Y;, . .. ,Y;).
r
<
In this definition, the elements of the matrices were ordered in columns. Any other order would lead t o an equivalent definition. Let {Xn), n 2 1 and (Yn), n 2 1 be Rk-valued stochastic sequences, possibly defined on different probability spaces. The sequence {Yn) is said to dominate ( X n ) for the < L ordering (which will be denoted (X" X 2 , . . .) <_c(Y1, Y2,. . .)) if for all n 1 1, the following matrix comparison property holds: (XI,.
where g(s) : R 4 1I$ is non-decreasing and continuous and the functions un(x) are step functions of the form
. . ,x n ) Lr. (Y1)... ,Vn).
<
with 0 a b b. Thus in view of the monotone convergence theorem, it is enough t o check (2.2.2) for all continuous functions and all step functions in this class. A step function in this class is left-continuous if a = 0, right-continuous if a = 1. If a E (0, l ) , this function admits a representation as the sum of a right-continuous function and a left-continuous one within this class via the relation v,J,,, = v,,,b,l + ~ , , ( 1 - ~ p , O . The proof is now completed if we observe that each step function with 'either a = 0 or (Y = 1 is the monotone limit of 0 a sequence of non-decreasing continuous functions. Let F and G be in D(R) and P denote the function E(x) = 1- F(x), x E R. (2.2.3) F < i G if and only if P ( x ) 6 ( x ) for all x E R.
<
2.2 Analytical G
An integral ordering property can be checked directly through the definition of Ij 2.1, but this is rarely the most efficient way. On V(R), there are simple analytical characterizations for the three integral orderings < i , I,, and sic, of interest in dimension 1, which boil down to simple tests on the distribution functions. The following result shows that we can restrict the set of test functions for the strong order: (2.2.1) If the relation
Proof: The necessary part is obvious since the indicator function t -, l ( t > x ) is non-decreasing. Conversely, each right-continuous (and a fortiori continuous) non-decreasing func4on f : R -+ JR such that f (-oo) > -co admits the ~tieltjes-Lebesgueintegral representation
and so
<
holds for all functions f then F
:R
-+
IW+ which are non-decreasing and continuous,
ces t o prove (2.2.2) for f non-decreasing, continuous and nonis satisfied by fn(x) = (-n) V f (x) n, which is positive, by f ( x ) as can be seen when letting n tend to oo). Any ecreasing function f : R -+ can be re
The fact that E ( t ) c ( t ) for all t 2 0 implies E(t-) 2 6(t-) for all t > 0. Therefore, the last relation implies that (2.2.2) holds for all f as above, which 0 concludes the proof in view of (2.2.1). (2.2.4) Assume that F and G have a finite first moment. Then F Sic, G if and only if
+
IW+
sum
Proof: The identity JsW p(u)du = SR(u- x)+ F(du), (obtained from (1.3.3), Chapter 3 and the integrability assumption) establishes the necessary part since u -+ ( u - x)+ is non-decreasing and convex. To prove the converse, it is enough to consider f bounded from below (otherwise take f V (-n) and let n go t o oo). We have
214
4 Stochastic Ordering and Comparison of Queues
2 Comparison of Queues
where g , the right-derivative of j , is a non-decreasing function which can be assumed right-continuous without loss of generality. Thus, by Fubini's Theorem
Therefore
SF p ( u ) d u 5 JZwG(u)du, for all x implies
&
In view of (2.2.4): (2.2.5) If X and Y are integrable, X
<
Example 2.2.1 Stability of integral crders b x convoluthon If the real-valued random variables X I , . .. ,Xn (resp. XI,. . . ,X,) are mutually independent, then for any of the above orders, Xi < L 2;for all i implies
-
xl+:..+xn
2.3 Strassen's Pointwise
imbedded sequences in various queueing systems by simple induction arguments, which replace the usual analytical proofs, based on stability properties of the integral order with respect to convolutions or products of c.d.f. The first result, already mentioned in the introduction, is that the ordering corresponds to the pathwise stochastic order associated with (2.3.1) For F and G two c.d.f. i n V(Rn), F
si<:
0 Proof: See 3 5. emark 2.3.1 In dimension 1, the proof boils down to the following classical construction: take U to be a random variable uniformly distributed on the interval [O, 11, defined on some probability space ( R , F ,P). Let X = F - ' ( U ) , Y = G-'(U), where the inverse of the non-decreasing function F is defined by
cl
so that in particular
215
F - ' ( u ) = inf { x IF(%)> u ) . It follows from the assumption F Si G that F-l(U) 5 G-'(U). Conversely, if X L Y as., then P ( X x ) = F ( x ) 2 G ( x ) = P(Y 5 X ) for all x 2 0, which is equivalent to F Si 6 . 0 Similarly, the Schur-convex ordering corresponds to the pathwise ordering associated with +: F S,,, G if and only if there exist two Rn-valued random variables X and Y defined on the same probability space, with c.d.f. F and G respectively, and such that X + Y a s . The proof is similar to that of (2.3.1). The following characterizations of and Sic,in terms of the projection stochastic order associated with _< are also proved in 3 5: (2.3.2) Let F and G be two integrable c.d.f. i n D(1W"); F G (resp. F Sic,G) if and only if there exist two Rn-valued random variables X and Y defined on the same probability space with c.d.f. F and G respectively, and such that E [ Y I X] = X (resp. E[Y [ XI 2 X ) a.s.
<
<,
.
<,
Example 2.3.1 Exponential and Erlang Distributions. We give a second proof of the comparison of Example 2.1.1, based on the construction of the variables of the last theorem: by symmetry, we have E[K I X] = P(X) a s . , E [ x I X]= X , for some function 9 independent of i. Therefore n 9 ( X ) = so that
xi
epresentation T
The pointwise representations which are discussed in this subsection provide a natural way for handling integral ordering in higher dimension, at least whenever the independence assumptions of (2.2.6) are not satisfied. These representations are particularly useful to establish comparison properties of
Since X is rA,,, the proof is concluded from (2.3.2). 0 These results have the following immediate coro&i.ries: (2.3.3) If F
F = G.
-
roof: Use (2.3.1) whic allows us t o chose X and Y distributed according Y a s . This and E [ X ) = E [ Y ] to F and G respectively and such that X C1 imply X = Y a.s. (2.3.4) If F sic, G and F and G have the same finite first moment, then F 5cx 6.
<
Proof: From (2.3.2), we can chose X and Y distributed according t o F and G respectively and such that E [ Y I X ]1 X a.s. If in addition E [ X ]= E[Y], then the random variables EIVlXj and Y have the same mean, so that necessarily, 0 E[YIX] = X as., which concludes the proof in view of (2.3.2). 2.4 Comparison of Stoc
The ideas developed in $5 2.1-2.3 provide the underpinings of various bounding techniques. Before specializing them to queues, we describe these techniques within the framework of stochastic recurrences introduced in •˜ 4.2 of Chapter 2. T h e quantities of interest are described by IRK-valued sequences y,), n 0, generated by the recurrence equation
2.5 Bounds Based o Integral Orderings Strong Bounds. (2.5.1) - Assume that (y,E) 4 h(y,[) is non-decreasing. If (g,(o, t l , . .) (%to, (1,. . .), then yo,^^,. . .)
-
Proof: From Strassen's Theorem (2.3.1), for all n, we can find random variables (f,(~,(;,.. . ,I;)and ( q , . .. ,$) defined on the same probability space and such that a) The distribution of (g, to,(1 ,. . .,En) (resp to, tiL. . &)) coincides (resp. (7,(A, ti,.. . ,c;)); with the distributio? of (gl, [b, ti,.. . ,[;) a s . for all i = 0 , 1 , . . . ,n. 8) g' $ a s . and [i The property yk %.as. is now established by induction as follows: y&< gh as. since g1 7 a s . Assume that the property holds up to rank i < n. Since h is non-decreasing, we obtain
cb,c,
--
(T,
<
<
<
<
>
where we successively used the induction assumption and the pathwise or0 dering between [' and ('. The IRM -valued driving sequence ((,), n 2 0, and the initial condition yo = g are defined on the probability space (R, I;: P). Consider another stochastic recurrence, say
e same dynamics h, and which only-differs from the first one by its initial condition @ a n dits driving sequence {[,I, n 1 0, (all the tilde variables possibly defined on another probability space). Under what conditions on oes the ordering relation
Bounds by ~rojection.- he following result generalizes the example considered in the introduction: (2.5.2) Assume that the random variables (7, to, El,. . .) are integrable, and that (a) The function y -+ h(y, () is non-decreasing; (b) The function (y, () 4 h(y, [) is convex (resp. convex and non-decreasing);
-
imply that
Assuming in addition that the sequences y, and fin converge in some sense to the stationary limits y, and y", respectively,'when does the relation
Proof: From Strassen's theorem (2.3.2), - for all n, we can find random variables ( q l ,[h, J;, . . . ,[k) and (q,E&,[;, . . . , defined on the same probability space, and such that if we denote G, the a-field generated by the variables (77',€6, EI,...,FIf,then a) T h e distribution of (g, t o , (1 ,. . . ,En) (resp. (ij, . (,) coincides with the distribution of (g', I;, J; ,. . . ,[A) (resp. (7,[h , 5: , . . . ,EL));
TO,?I-,.
-
P - C X ) ~=' E[TI G,] a s . and (, = E[[, I P-icx) 7' E[q 1 g,] a.s. and We now prove that the relation
<
hold? These questions can be addressed directly from Strassen's Theorems by constructing the two sequences on the same probability space.
pn)
-
for all i = 0,1,. . . , n . Q,], for all i = O , l , . . . , n .
P,],
[: < E[Z
-
218
4 Stochastic Ordering and Comparison of Queues
2 Comparison of Queues
<
E[q' I G,] as.), (2.5.3) holds for i = 0. Since Q' = E[G I Gnl a.s. (resp. Take as induction hypothesis that (2.5.3) holds true for some i < n. Jensen's inequdiity gives
= i t o represent equality in distribution) for all n 2 0, and such that z, is non-decreasing in n. Let {Z,) be the sequence obtained in the same way from (2). Therefore, (2.6.1) is equivalent to
(2.6-3) EO[f(zn)] since the function h : IRK+M -+ IRK is convex. Thus using the induction hypothesis and the fact that the function y -+ h(y, E ) is non-decreasing
E[Z
Using now the property that E[$ I Gn] = ti a.s. (resp. ( En] >_ ti a s . together with the assumption that the function (y,() -, h ( y , t ) is nondecreasing), we obtain that
and the property that ( y o , ~ ~. .,,yn) . Jensen's inequality.
(i70,?1,.
. ., & )
follows from 0
Let
for all n
1 0, implies
may be obtained analytically for most of the orders defined in this chapter (cf. D. Stoyan (1984) Comparison Methods for Queues and Other Stochastic Models). .IIf the c.8.f. F, and 6, on R converge weakly to Fb, and 6, respectively, and if F, Li G, for all n, then Fb, 6, (use (2.2.1)). Thus, is preserved by weak limits. 0 Consider now the case when the driving sequences {&), and are stationary and ergodic, and defined on the Palm space of some point process, (a,?, Po,@).Since the systems considered in (2.5.1) and (2.5.2) are such that the mapping y 4 h(y, () is non-decreasing, Loynes' technique applies, provided this mapping is also continuous (see Remark 4.2.1, Chapter 2). Let jy:), n 2 0, be the state variable sequence when the initial condition is 0. From Remark 4.1.1, Chapter 2, it is possible to define a sequence {z,), n >_ 0 , such that z, =; &, (in what follows, we will often use the notation
si
<
(r,}
< EO[f(zn)] vf E L-
Equation (2.6.3) provides another way of addressing the question. For instance, if C = {icx), when letting n go to CCI in (2.6.3), a direct application of the monotone convergence theorem implies
for all f E {icx) such that the expectations exist, which is equivalent to (2.6.2), for C = {icx). Remark 2.6.1 Under the conditions of (2.5.1) (resp. (2.5.2)-icx), the existence of the monotone sequences {zn) and (2%)implies the stronger property that for all n 2 1, under P o , (2.6.4)
(z,,
provided z,
Stability of Stochastic Orders by Limits
219
z , o 01,
. . . ,zoo o 0") li (resp.
-
,2, o 81, . .. ,2b,o en),
and Z, are finite (resp. integrable).
2.7 Comparison of Basic Queues We use the notations of Chapter 2. In what follows, the case when the initial condition Wo and the vectors of service and inter-arrival times (a,, r,), n 0, are mutually independent will be referred to as Assumption HI (thus H I allows a, and T, to be correlated); the case when, in addition to H I , for all n, a, and T, are independent, will be referred to as Assumption H2; if in addition the service times are all identically distributed, as well as the inter-arrival times, we will say that we have renewal assumptions. emark 2.7.1 From Remark 2.2.2, for C = {i), {icx) or {cx), under H I ,
>
(2.7.1)
(wo, (TO,-TO)*(01, -TI),
. . .) 5r. (Fo,(zo, -70)~( 6 , -71)).. .)
is equivalent to WO
sc -
Similarly, (2.2.6) shows that under H2, (2.7.1) holds if and only if Wo Wo, ui S L 2% and .-T, -?2 for a11 i 2 0. go,a0 sc Zo and Under renewal assumptions (2.7.1) reduces to Wo
sI:
-7-0
a
-70.
a) T h e G/G/l/cw, Queue. The workload sequence in the G / G / l / m queue, {W,), satisfies the recurrence equation
with initial condition Wo. Take I, = (a,, -7,) h(W,E ) = [W a - 7-1'.
+
and denote by h the function
<
city. The function ( W , [ ) -+ h(W,[) being non-decreasing, i it (2.5.1) and from the fact that Loynes' technique applies to (2.7.2) that both the transient and the stationary distributions of W, are <_i-non-decreasingfunctions of the sequence (Wo, to, 61, . . -). Example 2.7.1 Consider the following two G.l/GI/l/oo queues. Both queues have 0 initial workload. Queue 1 has its inter-arrival times (7,) exponentially distributed with parameter 1, and its service times {a,) are distributed according to a Gamma distribution of parameters X = 114, n = 2. ueue 2 has its service times (7,) uniformly distributed on [0, l] and its rvice times (2,) are I' of parameter X = 114, n = 3. We immediately check from t h e analytical criteria of $ 2.2 that TO ibi TO a;nd a0 20. Let (W,) and (W,) denote the workload sequences in queue 1and 2 respectively. e wLare under renewal assumptions, we conclude from Remark 2.7.1 that Ci W, for a11 n. This results extends to the steady state regimes in-view xample 2.6.1. In particular, the steady state dis-tributions W and W satisfy the tail comparison property P ( W > x) P ( W > x) for all x E &. 5 E x a m p l e 2.7.2 Consider the following two G / G / l / w queues. Both queues have 0 initial workload. The sequence (a,, r,) of queue 1satisfies Assumption 1, and the same property holds for the sequence (Z,, Fn) of queue 2. We f (7,) (resp. ?, = G, f (F,)), where or, and T, have in addition an = or, (resp. 6, and 7,) are independent and f : & -+ R+ is non-increasing. Then an < i 6, and Fn sli T, for all n imply that (a,, -7,) Si (Z,, -?,I, for all n, so that Wn
<;
<
+
+
otonicity. The function (W,J) -+ h(W,J) in (2.7.2) is nonand convex. The transient and the stationary distribution~of W, are hence sic,-non-decreasing functions of the sequence (Wo, {,), as a conseence of (2.5.2). In other words, any decrease of the variability of the initial the sequence a, - T, results in an increased variability of stationary workload. (continuation of Example 2.3.1) Queue 1 and queue 2 are ues, with zero initial workload and with the same interarrival time c.d.f. The service times a, of queue 1 are Erlang k and those of queue 2 are exponentially distributed with the same mean as those of queue der renewal assumptions, the fact that a0 I,, So implies r all n. In particular E[WA) E[WA] for all n >_ 0 and E 2 O such that the expectations are finite. 0 g l e 2.7.4 Under renewal assumptions, we obtain from (2.5.2) that TO Sex 70 and 00 Scx50 imply 1"V, SicxUI',, for all n. 0
<
-
r o p e r t i e s of G/G/l/ca ueues. This subsection is a continuation of the example of the introduction and shows more precisely in what sense determinism is desirable. Let {W,) be workload sequence in a
G/G/1 queue, where (a,), (7,) and the initial condition Wo are mutually independent. Let W: (resp. W:), n = 0,1,.. ., be the workload in the D/G/1 (resp. G / D / l ) queue obtained by keeping the same service (resp. inter-arrival) time sequence and the same initial condition, and by replacing the inter-arrival (resp. service) times by their mean value. The following property holds.
[A
-
= (a,, -EO[r]) and [: = (EO[a],T,), n 2 0. If ( R , F ,P o ) denotes the probability space on which these variables are defined-let G1 and G2 denote the sub a-field of 3 generated by the sequences {T,,), n 2 0, and {an), n >_ 0, respectively. It is clear from the independence assumptions that f o i all n 2 0,
Proof: Let J, = (a,,
-r,),
E O [ ( ~ O , ~ . . , { ~ )..., ] S{i), ~ ] =i(= $l ,~2 ,, so that
which completes the proof in view of (2.5.2).
-
0
The G/G/s/coQueue. The notatidns are those of Chapter 2. Take I;, = (a,, -T,). The ordered workload vector satisfies the recurrence relation Wn+l = h(W,, J,), where
(2.7.4)
h(W, J) = R ( W
+ ue - Ti)+,
e = (1,0, ...,0),i = (1, ...,I), and R is the operator arranging vectors of Rs in increasing order. < i Monotonicity. The function h : IW" x R2 -+ RP is non-decreasing, and it follows from (2.5.1) that the transient and the stationary distributions of W , are 5;- nondecreasing functions of the sequence (Wo,€0, El,. ..). Whenever Assumptions HI or .Hz are satisfied, this property translates into the same monotonicity properties with respect to Wo, (uo, -TO), . . . as in the G / G / l / w case.
222
4 Stochastic Ordering and Comparison of'~ueues
-
F i n i t e Capacity Queues in Tandem with Blocking. This section focuses on the queueing network defined in 5 8 of Chapter 2. Let tn = (un, on+l,rn),where a, is the vector of service times of customer n . (2.8.1) If {Jo,J1, . . .) Scx . ..), then the sequences of waiting times (W;)O associated with the initial condition 0, are such that (Wn)O (??')o, for all n 2 0.
{&,g,
-+
Wn+, = (Wn
ueueing Systems
2 Comparison of Queues
223
a n - Fn)+.
As we saw in C h a p t z 2 , a sufficient condition for the existence of a finite stationary worMoad W is EO[u]< EO[?-). In addition EO[o]> E O [ qimplies that there exists no such finite stationary workload. Observe that
sic,
and therefore, by the inversion formula (4.1.2~)of Chapter 1,
Proof: The recurrence relation (7.2.3) of Chapter 2, that is,
with
is of the form Wn+l = h(W,,&), where the mapping h satisfies the assump111 tions of (2.5.2)-cx. Under renewal type assumptions, namely the ( J + 1 ) random sequences j u i ) , n 2 0 and {r,) are independent and each of them is an i.i.d. sequence, the condition {.(0,&, . . .) Fcx{[o,&, . . .) xeduces to the two conditio-ns7-iF, F0 and a 0 Scx(TO. Assume that the driving sequences itn)and {&) are stationary and ergodic, and that the system is stable for both sequenceq (see 5 8 of Chapter 2 for the stability condition). Since the unique stationary regimes are a s . limits of the increasing sequences (Wn)O o 8-" and (Fn)O o Pn,respectively, the comparison result on the stationary regimes follows from the considerations of 5 2.6. n In this model, a <;,,-increase of the service times does not necessary result in an F:ic,-increase of the vector of waiting times Wn.
-
--
andom Environment. The setting is as in G / G / l / m queues except 'now that the service is not given at unit rate, but at a random rate At. More precisely (A,, t E I[$) is a non-negative process being compatible with the shift 8~ in the sense that Ato8, = A,+,, s, t E R The maximum amount of service which can be provided during the interval [Tn,Tn+l] is
and Fn = ?08,, n E Z on {To= 0). The evolution equation for the worklaad process is hence
where
= E0[rj.Thus
(2.8.5)
EO[q= E[A~]E~[T].
Therefore if
- -
there exists a finite stationary workload W = M,, Mn and
-
where M, = limn,,
t
We wish to compare @ to W , the stationary workload corresponding to a Mn, where constant service rate a = E[Ao]. We have W = M, = limn,, Mn is given by
Notice that W will also be finite under condition (2.8.6). (2.8.8) If (At, t E R) is independent of (a,,~,, n E Z) (under Po or equivalently under P), then E n >icx W,, for all n. I f i n addition (2.8.6) is satisfied, then @ >icx W .
Proof: In view of the results of 2.7, it suffices to prove that for all n ,
Let Gn be the u-field generated by { u , , ~ ; ) ,0 that E0[5lGn]= ari a.s. But
< i 5 n. It suffices to show
u t , using the meas rability of Ti, Ti+l with respect to Q, and the independence assumption, we obtain the a s . equalities
where we have also used that P = Po on a{(Atl t E R)).
roof: Properties (c) and (d) follow immediately from the definition. Proof of (a). Let X be a real-valued random variable. We have to prove that for all pairs of non-decreasing functions f and g : R 4 $
0
at least whenever the involved expectations exist. This last reIation is called Harris' Inequality. Let X' and X" be two random variables defined on the same probability space and such that X' and X" are independent and both variables are distributed like X . For all x' and x" in R and for all f and g as above
andom Variables The R-valued random vector X = (XI,. . . ,X,) is said to be associated if the inequality
holds for all non-decreasing mappings f , g : Rn --+ R, for which the involved expectations exist. Thus, in particular, for all n-tuples of non-negative nondecreasing functions fi : R EX.+
Let y be any permutation of (1,.. . ,n); since the association of the vector
(XI,.. . ,X,) is equivalent to that of (X,(l), . . .,X,(,)), we wiIl also speak of the association property of the set of random variables {XI,. .. ,X,).
The sequence of R-valued random variabIes {X,), n 2 1, is said to be associated if the random variables ( X I , ..., X,) are associated for all n 1. This notion is extended to Rk valued sequences by requiring that the set of all coordinates be associated. The association property can often be established without computing explicitly the joint distribution of the variables. This can be done for instance by using the following 'calculus' ( a ) The set consisting of n ~ i n g i erandom variable is associated; (b) The union of independent sets of associated random variables forms a set of associated random variables; (6) Any subset of a set of associated random variables forms a set of associated random variables; (d) For any non-decreasing function 63 : iWn -+ R, and any set of associated random variables {XI,. . . ,X,), the set of random variables (44x1,. . .,Xn), XI,. . . , X,) is associated.
>
As a direct consequence of (a) and (b), any set of mutually independent random variables is associated.
Therefore
which implies Harris' inequality in view of the statistical assumptions on X' and XI1, provided the expectations on both sides of this inequality exist. 0
Proof of (b) Let X = (XI,. . . ,X,) a d Y = (YI,. . . ,Y,) be associated and X and Y be independent. Let f and g : Rmfn -+ R be two non-decreasing functions. Writing f (resp. g) for f (XI,. . . ,Xn, Yl, . . . ,Y,) (resp. g(X1,. . . ,Y,)), we have
In view of the assumption that X is a set of associated random variables, E [ f g l Y ]- EV[Y]E[gIY] 2 0 and hence
The functions Y
-+
E[fIY] and Y
-+
E [ g ( Y ]are non-decreasing, so that
0 since Y is associated. The R-valued random variables {XI, ..., X,) are said to form an independent vemion of the random variables (XI, - ..., X,) if (a) The random variables (XI,...,X,) are mutually independent, and (b)For every 1 i n the random variables X, and W,have the same probability distribution. In view of the definition of association (3.1.3) If the random variables {XI, ...,X,) are associated, then 5? <;, X .
< <
4 Stochastic Ordering and Comparison of Queues
226
=;,
3 Association Properties of Queues
.1.1 Let {XI,...,X,) be associated. The fact that jt(x> = L i > t belongs to (ip) implies the ordering relation
(3.1.4)
min
{ i = l , ...,n}
Xi
li rnin
{ k l , ...,n}
Xi.
max
{ k l , ...,n}
XiSi max { i = l , ...,n}
Besides the characterization of the type of correlation of the workload process {W,}, n 2 0, the association property can also be used to obtain bounds on the solution of certain vectorial recurrences of the form (2.4.1).
Example 3.2.2 Coupled G / G / l / c o queues. Consider a network made of K G / G / l / o o FIFO queues which are coupled in that they share the same
In the same vein, if the random variables {XI, ..., X,} are associated,
(3.1.5)
227
xi. a
These two relations suggest a natural way .of generating product form bounds on extremal statistics, whenever the association property holds (see Example 3.2.2 below).
arrival process. Namely, at the arrival time Tn of some stationary and ergodic point process N, each of the K queues receives its n-th customer. Let a, dlf (a:, . . . , ,):a where a: is the service time of the n-th customer of queue k E (1,. . . ,K). The waiting times of customer n in queue k satisfy the recurrence relations
w,".+,= rnax(~,k+ U: - ~ n ) + , where rn = Tn+l -Tn. The global sojourn time of the n-th customer is defined as the duration between Tn and the time when all the customers arrived at Tn have completed their service times, that is,
3.2 B o u n d s by Association
We now outline how the association properties can be established for the solutions of (2.4.1) and point out some instances where this property has interesting practical implications. (3.2,1) Assume that the function (y,S) --+ h(y,[) is non-decreasing. If the driving sequence {&), n L 0 and the iqitial condition 17 forms a set of associated random variables , then the sequence {y,}, n 2 0, is also aisociated.
Proof: The proof is based on the association calculus given in 5 3.1 and on (2.4.1). Take as induction hypothesis that the random variables {yk, 0 k < n, tk, k 2 0) be associated for some n 2 0. Then rule (d) of the association calculus implies the association of the random variables {yk, 0 _< k 5 n 1,
<
+
Bn = max R:, k=1,
where
If the initial condition, the inter-arrival times and the service times are associated (for instance independent), then W* = (W:, . . .,W c ) is also associated in view of (3.2.1). This association property extends to R, = (RX,. . . ,R z ) , so that by (3.1.5) Bn
0
The G / G / s / c o queue. A direct consequence of (3.2.1) above and of (3.1.1) of Chapter 2, is that the workload process {Wn), in G I / G I / s / o o queues is associated, provided the hitial condition is independent of the service and inter-arrival times. In particulak, the components of W,, that is, the workload of the servers at the n-th arrival time are associated. A similar property also holds when the sequence .
for all t l , . . . ,t , in IW+. Using the associated Loynes' sequence, we obtain that this property also extends to the stationary workload. U
k=1, max ...,K
x:,
(n > O ) ,
zn
where denotes the product form version of R,,.For instance, assume that the arrival process is Poisson of intensity X and that the marks a: are independent of the arrival process, i.i.d. and exponentially distributed with parameter p. Then, whenever X < p, En couples in finite time with a stationary and ergodic sequence B d n (because W, couples with a stationary sequence). Therefore
B has associated rather than independent components. Thus
...,K
rnax Ak,
k=1, ....K
where the random variables Ak are i.i.d. and exponentially distributed with parameter p - X (recall that the stationary sojourn times in queue k are exponentially distributed with parameter ,u - A). In particular 1
(3.2.4) EOPI5 x H ( K ) , with H ( k ) = 1
+ 1/2 + . . . + l / k .
0
.
arison of Time-Stationary Queues
le 3.2.3 Bounds for G I / G i / l / o o queues. Due to the renewal asn = - T-i), n 2 1, are associated.
sumption, the random variables From (2.2.3) of Chapter 2
xy=f=l(~-;
.I Comparison of Point Processes
and using (3.1.5)plus a limit argument
P(bn<x), ( ~ 2 0 ) . n>l
Now for all s 2 0,
Thus whenever the function Po = E(exp(sa)) is finite in a right neighbourood of 0 (for instance it is rational in s ) (3.2.5)
B(bn > x) < inf (!Pu(s)!PT(-s))nexp(-sx) $20
kFK ( n , x ) .
Thus
be two stationary point processes, possibly defined on different Let N and p-robabiljty spaces, both with finite intensity and no double points. Let P , Po, P and Po denote t h e corresponding stationary and Pdmgrobabilities. The points of N and N will respectively be denoted Tn and Tn, with the usual convention. Let X [P]denote the c.d.f. of the random variable X under probability P. [FO].It is not true in general that this comAssume that Tl [Po]S r parison pr;operty is preserved when passing from the Palm t_o th_e stationary probabilities; that is, it. is not always true that TI [PI ic Tl [PI, as shown by the following example, where t = {i). Example 4.1.1 Feller's paragox revisited. Assume that N is a Poisson process of intensity 1 and that N is a renewal process with inter-arrival time def c.d.f. equal to that of the random variable Xu = X V u , where X is exponentially distributed _with parameter 1, and u is a real and positive constant. Thus TI [Po] TI [Po].However, we can check after some calculations that
si
Note that this bound is non-degenerate since the infinite product converges t o a non-zero limit if p < 1. Indeed the infinimum in (3.2.5) is reached for sn such that
and thus, when n tends to co sn tends t o s*, solution of
+
for 0 _< u < u*, where u* is the positive root of the equation u 2exp(-u) 2 = 0. Thus, -for u in this interval, we citnnot have TI [PI Fl[PI. 0
<;
The preceding example shows that the property for all n 2 1, (a) Tn [Po]< i ;T, [FO], does not imply that [F]],for all n 2 1; (b) Tn [PI < i note that for n 2 0, the property N([O,x)) > n is equivalent to T n + ~ <x P-a.s.; so (b) is equivalent t o
F,,
ut
$*
is such that
s gf?Ii,(s*)Pr(-s*) < 1 because the function !Pa"b()!Pr(-s)is convex in the domain where !Pu(s) is finite, decreasing in s = 0 and tends to co when we reach the first singularity. Thus
(c) N[0,x ) [PI l i S[O,X) [PI,for all x E &. However, for <, we have: (4.1.1) The following two properties are equhalent: (d) Tn [Po] Fn [Po],for all n 1;
<,
(e) N[O, x ) [PI <, fi[0, z) om which we obtain that the infinite product of (3.2.6) is strictly positive. Note that the same type of arguments can be used to prove instability in 0 the case p > 1.
>
[2], for all x E R+..
The proof of (4.1.1) is based on the following lemma: (4.1.2) Let N be a stationay point process with finite intensity. For all functions f : R+ -+ R with f (0)= 0 , and for all x > 0
4 Stochastic Comparison of Time-Stationary Queues
231
(4.1.4) For all non-decreasing convex functions f : & 4 P, the function d(x) = Epf (N(0, XI) is non-decreasing and convex on It+. Proof: When adopting the convention N[a, b) = 0 for a 2 b, Mecke's formula ((3.3.1), Chapter 1) applied to the function
gives
since v(&w, t) = f (Nit, x)) that
- f (NITl,3)). From
this, it suffices to observe
00
(J(n+1)-2J(n)+
Proofi Formula (4.1.3) shows that $(x) is the sum of convex non-decreasing functions. U Example 4.1.2 Number of customers in the M/GI/l/oo queue. Let X(t) and z ( t ) denote the corlol congestion processes in two FIFO M/GI/l/co queues, with t h e same arrivalstensity A, and with respective service time c.d.f. G and 6 . Let W ( t ) and W ( t )denote the corresponding workload processes. We show that 6 implies X(0) I;,,z ( 0 ) under P. (4.1.5) G Sicr We first prove the following equality in distribution:
f((n-I)~))(x-T,)+,
PO-as.
n=O
-
a
Proof of (4.1.1). Assume that (d) holds. This implies that A = A. In addition, E p ( ( 2-?',)+I <_ EF0[(x Tn)'], for all x > O,?d n 2 1, since the function t -+ (x - t)+ is convex. If f is a non-decreasing convex function I[gt -t I$ with f (0) = 0, the coefficients of the sum in the right-hand side of (4.1.3) are non-negative, and so Ep[f(N[O,x))] ~ ~ [ f ( f i [ ~ , x ) ) ] .
-
<
where Pi denotes the Palm probability with respect to the arrival process. Due to the PASTA property (see Formula (3.1.5) in Chapter 3), X(0) [PI = X(0-) [Pi]. But X(0-) [Pj]= X(O+) [Pi], where Pi denotes the Palm distribution of the departure process (see (4.1.5), Chapter 3). Therefore X(0) [PI = X(O+) [Pi]. Now, due to the FIFO assumption, the number of customers left by a departing customer coincides with the number of arrivals during its sojourn time. That is X ( 0 f ) = N(S,O] P&a.s., where S denotes the (negative) arrival time of the customer which leaves at time 0. The proof of (4.1.6) is concluded from the fact that N(S,O] [POD] = N(0, W(O+)] [Pj], which follows from a direct pathwise identification and from the cross ergodic theorem of 5 7.3, Chapter 1. For proving (4.1.5), it is thus sufficient to show that
-
For the converse implication, we first observe that ( e ) also implies X = A. The functions fk(x) = (x - k)", k = 0,. . ., are non-decreasing convex and null at the origin. For dl n 2 1,
Since the arrival process is Poisson, N(0, t] is Pi-independent of W(0-) for all t > 0, with a similar property for the other queue. Therefore the proof will be concluded if we show that EP
Therefore,
E p [fk(N[O,z))]
< EF(fk(E[0, x))], for dl x implies that
om (2.2.5), this implies that -Tk [Po] Scx-;?;k
EP
[ ~ ( N ( O , X dI )?]; ( ~ o + )
21%
for all f non-decreasing and convex (in the last equation, we used the fact = that both arrival processes have the same law, and that Ep2 [f (N(0, E p [f (N(0, XI)].Under the foregoing assumptions,
XI)]
[FO], which is equivalent 0
rk 4.1.1 If N is a renewal process, then (d) is equivalent to TO < , 70. The preceding result also gives the following corollary:
VW(O,XI)Id ~ j ( w o + 2 ) 2) 5
(0-) [P;]
Scx
E(0-1
[F:],
provided both queues are stable (see W(O+) [Pj]Sic, E ( o + )
$5 2.6-2.7). This implies that
[F~I,
(0-) and a are Pi-independent. Thus 0 ues with blocking. Let ( X ( t ) ) denote the total number of customers in the tandem queueing system of 5 8, Chapter 2. Using the FIFO property of the system, whenever the input process is Poisson and service times are independent and i.i.d., with c.d.f. Gi a t queue i, arguments similar t o those used in the preceding example show that (with z ( 0 ) under P , obvious notations) Gi SCxGifor all i implies X(0) D provided both systems are stable. For p_oin_tprocesses, determinism is also extremal: let fi be a point process on ($2,F ,P ) , with intensity A. Let N X be a deterministic stationary point process with intensity A, defined on (R, F,P ) , that is, a point process with all its inter-arrival times equal to 1 / A (either under the Palm or the stationary probability). (4.1.7) For fl and N X as above, NX([O,s ) ) [PI <,,fi([0, x)) [3],Vx > 0.
sic,
Proof: The proof follows from (4.1.1) and from the fact that the deterministic distribution with mean n/A is a <,,-lower bound for T,, [Po]. So in particular, for all stationary point processes N with intensity A, for all increasing convex functions f : R --,I$
for some mapping f in &. We will also use the notation I - L+ for the set of functions 4 which admit the representation (4.2.1), with f 1 0. For n = 0 (or equivalently for the T-marginal), the set I - i coincides with the set of cx functions on IW+ which vanish a t the origin. Similarly I - i+ is just the set of icx functions which vanish a t the origin. (4.2.2) F
sr F if and only if for
(4.2.3)
Epo [$(T,X)] < EF0[4imd78 11 EPO[TI E+ I?] .
all d, i n I - C
F
<
z)],
Proof: Frrom the very definition, F
s),
or equivalently
where [a1 is the smallest integer larger than or equal to a. 4.2 S t o c h a s t i c C o parison under Time-Stationary B r o b a
- -
Let N and fi be two point processes as above. Let T dsf TI (resp. T = TI) denote the first positive point of N (resp. f i ) and X (resp -f)be some Rn-valued mark associated with To(resp. Po). Let be one of the integral orderings defined in 5 2.1. T h e aim of the present subsection is to analytically characterize the stochastic c_om_pari_sonproperties which should hold bekwep the c.d.f. ( T , X ) (Po] and (T,X) [Po] in order to have (T,X) [PI < L ( T , X ) [PI. def
For the marginal distributions FT(t) = F ( t , co) and F$ = F O ( t ,co), in view of Formula (4.2.4b) of Chapter 1, (4.2.2) takes the following simplified form: (4.2.4) FT
FT i f and
only if for all x
> 0,
sr
(4.2.5) FT sic,FT if and only i f f o r all x 2 0,
emark 4.2.1 Inequality (4.2.4) is equivalent t o
Let {I - L) be the set of functions d, : Rn+l 4 R which admit an integral representation of the form
EPo[(T - x)'] Epo [TI
< E~~[(F- $)+I EjSo
and (4.2.5) is equivalent to
Fl
7
(~201,
234
4 Stochastic Ordering and Comparison of Queues
4 Stochastic Comparison of Time-Stationary Queues
235
We now prove the properties stated in (4.2.7). (4.2.9) F0 51-1@ + F0 5s-i Po. U
Similarly, for marks, let Fx (s)= F ( w ,x) and F i = FO(oo,x).
Proof: FO51-i Po implies F$ Sc, F$, which in turn implies Epo[T]= E+[?]. I?rom the very definition, FO S I - ~ go reads
(4.2.6) Fx 51: gx if and only if for all f :1W" -,IW in L
EPo [Tf ( X ) ] EF0F f (X)I, L E P [TI ~ E;;,
Fl
ernark 4.2.2 If X and T are P-indepe_nd?nt, and 2 and ? are Findependent, then obviously (T,X) [PI
n+l
f ( t ,x)F"(dt,dx) <
-4-1
f ( t ,x)FO(dt,dx),
for all f E I - i. Dividing both terms by Epo [TJ= EFo[i?;l, we obtain Fo 5s-i
FO. (4.2.10) F0 5s-;
F0 =+ F0
-
n -
FO.
Proof: If f f I - i", then
[F]
elations with Integral Orders. For C any set of functions as in k2.1, let < s - ~ be the partial semi-order on 2)(Rn+l) defined by F0 5s-r F0 if, for all 9 in I - L.
where the last inequality follows from (4.2.8). The remaining implications of (4.2.7) follow from
-
F0 +-F0 <_I-i+ FO. Proof: Use the inclusion I - i+ C i.
(4.2.11) F0 < i -
.
or equivalently if F 5~ F. Unlike the integral orders defined in 5 2, 5s-1: daes not apply to any c,d.f., but only to those of the form ( T , X ) [Po], as defined above. In particular, T [Po]should have its support on EL+ and be such that PO(T= 0) = 0. The relationships between the < s - ~orders and the integral orders of fc 2.1 are summarized below:
The proof of (4.2.7) uses the following result: (4.2.8) FQ <sdi 3' implies Epo[T]5 EF0[?;).
0
When restricting the above relations to the marginal c.d.f. FT, we obtain the following relations (for c.d.f. in 'D(IW)):
In words, for FT Si 3~to hold, it is enough to have F$ <,, F$. However, it is possible t o have F$ Sicx F$ and not FT Si &, as exemplified below. Example 4.2.1 Example of c.d.f. in D(IW+)such that F0 SicxFO, but F0 and F0 do not compare for 5s-i. Let @ be a c.d.f. in D(&) and let uo be a defined by real number such that @(uQ-)> 0. Let !P be the c.d.f. in ).,&fI(?
i rl, and hence @
Proof: The assumption implies F$ < _ s - ~F$?.Elom (4.2.4) for all x. But this is not possible for x 2 uo since (1- Qr(u)) du = J," (1 - 9 ( u ) )du, whereas 0 ( 1 - P ( u ) )du > Som ( 1 - @ ( u )du. )
We conclude the proof by letting x tend to zero and by using the assumption cl
Example 4.2.2 Example of c.d.f. i n V(&) such that F0 5sWiFO, but F0 and 3' do not compare for < ., Take F0 = F$ deterministic with mean A - I
.
F0 = .@ exponential
ith mean p-" and assume that X > p. The last
perty F0 i,, FO.FT is uniform on [O, A-", assumption precludes the & is exponential with parameter p. Thus
and
xarnple 4.3.2 The workload in the G / G / l / m queue (see r( 1.2, Chapter 2), is obtained when taking q = (a, T) E R2,and h(y, q) = (y + a - T)+, where on is the n-th service time and T,, the n-th inter-arrival time. The sequence {y,) is imbedded in the continuous time workload process which is obtained 0 when taking E = a E IR, and g(t, y,<) = (y + o - t ) + , 0 t < T .
<
p
Let b_e a_se_condpoint process defined on a possibly different probability space (Q, 7 ,P , Bt), on which are also defined a stationary sequence {Fn} satisfying the relation
Comparison of
The results which are proved in $5 2.4-2.8, on the stochastic monotonicity of queues, are mainly based on the recurrence relations satisfied by imbedded sequences. Typically, we used these recurrences to show how a 'stochastic increase' of the Palm distribution of the driving sequence leads t o an increase of the Palm distribution of the imbedded sequence. The latter is usually imbedded in a continuous time process like for instance the workload process in the G / G / l / m queue. The aim of the present section is t o investigate the conditions which guarantee a similar stochastic increase for this continuous time process. (t) and E(t)denote the workload processes in two G / G / l / m queues, with associated arrival point process (N, P ) and ( E ,F ) , respectively. I t is not true in general that W(0) [Po] Si %(o) [PO] implies a t W(O) [PI %(o) [F],as shown by the following counter-example: the iving sequence of the first queue is {T,,u,), with a, = T,, and that of second queue is (?, Z,), also with 5, = Fn. We have W ( 0 )= TI and ) = ?I, so that a simple counter-example is obtained from Example 4.1.1.
<;
0
with the same function h as in (4.3.1), and a stochastic process {fj(t)) such that
also with the same function g as in (4.3.2). All the objects initially defined for the first processes are also supposed t o exist for the second ones, and will be denoted by the same symbol with a tilde.
Strong Bounds. If ( t ,y, I )
-,g(-t,
y, () is non-decreasing, and if
then since y(0) = g(-To, y, I ) , ~ ( 0 [P]5i ) G(O) [PI. If To and (y,c). (resp. Yo and (G,r)) are ? (resp. P)-independent, from Remark 4.2.2, (4.3.3) is equivalent to (4.3.4)
(y, E ) [Po] < i (q, f ) [Po] and
Tt [Po]2s-i
?I
[Po].
Let y E IRK be a finite solution of the equation Exarnple 4.3.2 (cont'd) The function g involved in the workload process W(t), t E lR, of the G / G / l / m queue, satisfies the above assumptions with associated with a stochastic recurrence defined as in (2.4.1). This solution is efined on the Palm space ( R , 3 , P o , 8) of a stationary point process N. Let y(t), t E R be the IRK-valued stochastic process on ( R , 3 , P o ) defined by
ere J is some integra e IR"-valued random variable, and where g is assumed to admit left-h limits with respect t o the variable t. I t is assumed that the consistency relation
so that the ordering of the workload a t arrival times extends t o the continuous time stationary workload provided (4.3.3) holds. Under renewal assumptions (see $ 2.7), if the relations
and (4.3.6)
holds, or equivalently that y(Tn-) = y o On, P o - a s . The stochastic process y(C), initially defined on the Palm space of N, also admits a time stationary a t y(w, t ) = y(Qt(w),0)) P - a s .
(a)
TO
[Po] 2i 70 [FO] and
(b)
70 [PO]
2s-i
si
6 [Po]
[[fio], provided the hold, then in view of (4.3.5) and (4.3.6a), W [Po] stationary regimes exist (see $3 2.6-2.7). Since in addition, To and (W, a) are
continuous, !inear functional from D(Rn) x D ( F ) to R is represented by
+
(f,g ) , where f and g are in C and where ( f , g ) .( F ,G ) gfJRV1f dF JR.. g dG. Then, owing to the Hahn-Banach Theorem, ( F , G ) belongs to closed the convex set M A , if and only for all (f, g ) a s above,
roof' of (2.3.2). The sufficient part follows immediately from Jensen's inequality for conditional expectations. In order to prove the converse implication, it is enough to prove that if two distribution functions F and G on Rn satisfy the relation
for all convex functions f , then there is a distribution function H in V ( R 2 " ) , with marginals F and G, and such that the conditional expectation of the last n coordinates given the first n is the first n coordinates. Let Proof of (2.3.1). The sufficient part is obvious. Let F and G be distribution functions on V ( R n ) ,such that F Si G. For any open set U E Rn, let U+ = 1s E R ( 3 t E U ,t < 3). For all such sets, we have where PF and Pc respectively denote the probability measures on Rn associated with F and G. The second inequality in (5.3) comes from the fact that the set U+ has a non-decreasing indicator function. Let
.
A = {N E V ( B z n) I This integral relation ii no more than the martingale relation which was mentioned above, written in a form which makes it transparent that A is closed. Since A is also convex, the preceding theorem shows that it is enough to prove that (5.2) holds for all f and g in C. Let go(t) be the smallest concave function such that go(t) 2 g(t), where go(t)= oo if no such function exists. Then
The set A is closed and convex, so that it is enough to prove that (5.2) holds for all f and g in C in order to conclude the proof of (2.3.2) (in view of the above theorem). There is no loss of generality in assuming that f and g are non-negative. In view of (5.3), we have sup f
J(t)F(dt)= f
L
P F ( { I~f ( t ) > ~ ) ) d r Pct{3 I 3
< 3, f (4> r ) W
+
<,
G. Let T < suptER.(f ( t ) go(t)). where we used our assumption that F Then for some t*, T < f (t*)+ go(t*).Let us show that
(f O P(t) + 9
9 ( t ) ) H(dt).
For t in Rn, let Bt be the set of distribution functions of V ( B n )with first moment equal to t . The function gl : Rn -,R defined by where fo(s) %f suptsr f ( l ) is bounded and non-negative. Therefore
+
>
is concave and gl g, so that gl >_ go and hence T < f ( t * ) gl(t*). By definition of gl, there exists a distribution function Ga in Bt. with * g(u)G'(du)
=
with N ( t ) = l,(tllt.G*(q(t)) E A.
L-m
( f P(t) + 9 O d t ) )H(dt)l
242
4 Stochastic Ordering and Comparison of ,Queues
The notion of majorization of 3 1 was introduced by Muirhead IlOOj and Schur [118]. A recent survey on the matter together with bibliographical notes can be found in the monograph of Arnold [I] and in the comprehensive book of Marshall and Olkin 1891. Besides the connection with Schur-convexity, most of the results of $ 1.2 on the SRPT discipline are taken from Flipo [43]; this reference also contains many more interesting details and historical references. The optimality of the FIFO discipline in GIIGI-input queues was addressed by several authors, including Kingman [72] and, more recently, Foss [45],Berg and Posner [15], and Shanthikumar and Sumita 11191; we found it useful to prove that the interchange argument of 5 1.3 preserves the law of the point process, although this is intuitively clear. Here also, the expression of optimality in terms of majorization was chosen because it leads to the strongest results. Basic analytical and stability properties of the integral stochastic orders of •˜ 2, mainly in dimension 1, and bibliographical notes are collected in the first chapter of the book of Stoyan 11251. The key paper on the pointwise representation of integral orders (5 2.3) is due to Strassen (1261. The proofs of 5 5 are borrowed from this reference. Extensions of this type of pointwise representation can be found in a paper of Riischendorf [113],where the pathwise and projection orders associated with majorization are considered. Such pointwise representations are often r6ferred to as couplings (like for instance in the book of Lindvall [83]). The comparison results of $ 2.4-6 on stochastic recurrences were given by Baccelli and Makowski in [Ill. The results of 5 2.7 were obtained with different levels of generality by several authors, including Rogozin [109], Humblet 1561, Bajek [52] and Whitt [131], to name a few. The example given in the introduction is taken from [56]. The book of Stoyan [I251 contains a review of the literature on the comparison of queues. The approach of this book is mainly based on stability properties of orders by convolution, maximization etc., which only apply t o the renewal case. The analysis of the G/G/l/co queue in random environment is related t o Ross9 conjecture (1121, which states that a G / G / l / c o queue in a random environment should be bounded from below by the corresponding queue where the environment process is 'frozen' t o its mean values. A first proof of this conjecture was given by Rolski (1111; the proof for the stationary ergodic case given in 2.8 is that of [lo]. The notion of association, also known as Positive Correlation, was introduced by Esary, Proschan, and Walkup 1421. T h e two basic references on association are the book of Barlow and Proschan (141, and that of Marshall and Olkin [89].The relation between association and integral E {i,-icx, cx), orders was studied in [12]. It is shown in particular that, for 13 one cannot have X = (XI,. . . ,X,) associated and X
1
Bibliographical Comments
243
on the matter. Property (4.1.4) was proved analytically by Jean-Marie and Liu [60], for renewal processes. The equivalence stated in Lemma (4.1.1) is new. Property (4.1.7)is due t o Hajek [53], where more general results based on multimodular functions are given. The stochastic order <s-i of 5 4.2 was first considered by Whitt in 11321. The results of 5 4.2-3 are mainly taken from Baccelli and Makowski [13].
Arnold, B. C. (1987) Majorization and the Lorenr Order: A Brief Introduction,Jecture Notes in Statistics, Springer-Verlag, New York.
a,
Asmussen, S. (1987) Applied Probability and Queues, Wiley, New York. Asmussen, S. (1992) O n Coupling and Weak Convergence to Stationarity, Ann. Appl. Proba., 2,3, pp. 739-751. Baccelli, F. and Brdmaud, P. (1987) Palm probabilities and stationary queueing systems, Lect. Notes in Stat. 41, Springer-Verlag, New York. Baccelli, F. and Brkmaud, P. (1993) Virtual Customer in Sensitivity Analysis via Campbell's Formula for Point Processes, Adv. App. Proba., 25, pp. 221234. Baccelli, F., Cohen, G.,.qlsder, G.J. and Quadrat, J.P. (1992) Synchronization and Linearity, Wiley, New York. Baccelli, F. and Foss, S. (1993) Stability of Jackson-Type Queueing Networks, INRIA Report 1945,to appear in QUESTA. Baccelli, F. and Foss, S. (1993) O n l'he Saturntion Rule for the Stability of Queues, INRIA Report 2015. Baccelli F. and Liu, Z. (1992) O n a Class of Stochastic Recursive Equations Arising in Queuing Theory, Ann. of Prob., %,I, pp. 350-374. Baccelli, F. and Makowski, A.M. (1986) Queues in Random Environment, Stability and Bounds, Commun. Statist. Stoch. Models, 2. Baccelli, F. and Makowski, A.M. (1989) Queueing Models for Systems with Synchronization Constraints, Proceedings of the IEEE, a,1,pp. 138-161. Baccelli, F. and Makowaki, A.M. (1989) Multidimensional Stochastic Ordering and Associated Random Variables, Oper. Res. a,3,pp. 478-487. Baccelli, F. and Makowski A.M. (1992) Stochastic Orders Related with Renewal Processes, University of Maryland, SRC-TR-92-3. Barlow, R.E. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing, Holt Rinehart and Winston, New York. Berg, M. and Posner, M.J.M. (1986) O n the Regulation of Queues, Oper. Res. Letters, 4,5, pp. 221-224. Billingsley, P. (1965) Ergodic Theory and Information, Wiley, New York. Billingsley, P. (1968) Convergence of Probability Measures, Wiley, New York.
References
References
247
Blaszczyszyn, B. (1993) Factorial Moment Expansion for Stochastic Systems, preprint, Math. Inst., University of Wroclaw.
Daley, D.S. and Vere-Jones, D. (1988) A n Introduction to the Theory of Point Processes, Springer-Verlag, New York.
Borovkov, A.A. (1976) Stochastic Processes in Queueing Theory, SpringerVerlag, New York.
Delasnerie, M. (1977) Flots mtlangeants et mesures de Palm, Ann. Inst. H. PoincarB, Section B 8, pp. 357-369.
Borovkov, A.A. (1984) Asymptotic Methods i n Queueing Theory, Wiley, New York.
Doshi, B.T. (1986) Queueing Systems with Vacations - A survey, Queueing Systems 5, pp. 99-112.
Borovkov, A.A. and Foss, S. (1992) Stochastic Recursive Sequences and their Applications, Siberian Advances in Mathematics, 2,1, pp. 16-81.
Doshi, B.T. (1990) Single Server Queues with Vacations, in Stoch. Anal. of Comp. and Comm. Systems, H. Takagi editor, North-Holland, pp. 217-265.
Bramson, M. (1993) Instability of FIFO Queueing Networks, preprint Mathematics Department, University of Wisconsin.
Dumas, V. (1992) Stabilite' des rbeaux de Jackson, Mimoire de DEA, CMAP, Ecole Polytechnique, Paris.
Brandt, A. (1985) O n Stationary Waiting Times and Limiting Behavior of Queues with Many Servers I: the General G/G/m/m Case, Elektron. Inform. u. Kybernet., pp 47-64.
Esary, J. D., Proschan, F. and Walkup, D. W. (1967) Association of Random pp. 1466-1474. Variables, with Applications, Ann. Math. Stat.
a,
Brandt, A., Franken, P. and Lisek B. (1992) Stationary Stochastic Models, Wiley, New York. BrBmaud, P. and Jacod, J. (1977) Processus ponctuels et martingales : rtsultats re'cenls sur la mod8isation et le filtmge, Adv. Appl. Proba., & pp. 362-416. Brkmaud, P. (1981) Point Processes and Queues Springer-Verlag, New York.
: Martingale
Dynamics,
BrBmaud, P. (1989) Characteristies of Queueing Systems O b s e ~ e dat Events and the Connection Between Stochastic Intensity and Palm Probabilities, Queueing Systems, 5, pp. 99-112. BrBmaud, P. (1993) A Swiss Army F o m u b b of Palm Calculus, J. Appl. Proba., 30, pp. 40-51. Brimaud, P. and Kannurpatti, R. Mazumdar, R. (1992) Events And T i m e Averages: A review, Adv. Appl. Proba., '&, pp. 377-411.
a,
Flipo, D. (1981) Compamison des disciplines de service des files d'attente G/G/l, Annales de I'IBP, Paris, 1 , 2 , pp. 191-212. Flipo, D. (1983) Steady State of Loss Systems, Comptes rendus de I'AcadBmie des Sciences, 297,6, Paris. Foss, S. (1981) Comparison of Multi-Server Queues, Sibirsk. Math. J . 22, pp. 190-197 (in Russian). Franken, P. and Streller, A. (1979) Cenemlized Stationary Renewal Processes (in Russian), Probability Theory and its Applications, 2, pp. 78-80. Franken, P., Konig, D., Arndt, U. and Schmidt, V. (1981) Queues and poir.: processes, Akademie-Verlag, Berlin (American edition: Wiley, New York, 1982). Fuhrmann, S.W. and Cooper, R.B. (1985) Stochastic Decomposition i n the M / G I / l queue with generalized vacations, Oper. Res., pp. 1117-1129.
a,
Garsia, A. (1965) A Simple Proof of Eberhard Hopf's Maximal Ergodic Theorem, J . Math. and Mech. & pp. 381-382.
BrBmaud, P. and MassouliB, L. (1993) Imbedding and Coupling i n the Construction of Stationary Point Processes, preprint, Laboratoire des Signaux et Systkmes, CNRS.
Geman, D. and Horowitz, J. (1973) Remarks on Palm Mensures, Ann. Inst. H. PoincarB, Section B. 9, pp. 215-232.
Brill, P.H. and Posner, M.3.M (1977) Level-Crossings i n Point Procps Applied to Queues: Single Server Case, Oper. Res., 25, pp. 662-674.
Halfin, S. and Whitt, W. (1989) A n Extremal Property of the FIFO Discipltne via and Ordinal Version of L = XW, Commun. Statist. Stoch. Models, 5, pp. 515-529.
Brurnelle, D. (1971) O n the Relation Between Customer and Time Avemge in Queues, J . Appl. Proba. 2,pp. 508-520. rumelle, D. (1972) A Generalization of L = XW to Moments of Queue Length and Waiting Times, Oper. Res., 20, pp. 1127-1136. Campbell, N.R. (1909) The Study of Discontinuous Phenomena, Proc. Cambridge Philos. Soc. E, pp. 117-136. Cobharn, A. (1954) Priority Assignment i n Waiting Line Problems, Oper. Res., 2,p p 470-76. Dacunha-Castelle, D. and Dufio, M.(1982) Probabilitds et Statistiques: I1 Problkmes d temps mobile, Masson, Paris.
Hajek, B. (1983) The Proof of a Folk Theorem on Queueing Delay with Applications to Routing i n Networks, Journal Assoc. Comp. Mach. 30, pp. 834-851. a
Hajek, B. (1985) Eztremal Splittings of Point Processes, Math. of Operations Research u , 4 , pp. 543-556. Weyman, D.P. and Stidham, S. (1980) The Relation Between Customer and T i m e Averages in Queues, Oper. Res., 28, pp. 983-994. Heyman, D. and Sobel, M (1982) Stochastic Models i n Opemtions Research (I,II), Mc Graw Hill, New York.
Numblet, P. (1982) e t e m i n i s m Minimizes Waiting Times i n Queues, Tech-
-
nical Report, LIDS Department of EIectricaI Engineering and Computer Science, MIT, (MA). Jacod, J . (1975) Multivariate Point Processes : Predictable Projections, Radon-Nikoddm Derivatives, Repmsentation of Martingales, Z. Wahrs. 31, pp. 235-253. Jaibi, M.R. (1984) Charges stationnaires d'une file d'attente avec blocages, preprint. Jansen, U., Konig, D., Nawrotzki, K. (1979). A Criterion of Insensitivity for a Class of Queueing Systems with Random Marked Point Processes, Math. Operationsforsch. Stat., Ser. Optimization, 10,pp. 379-403, Jean-Marie, A. and Liu, 2. (1992) Stochastic Comparisons for Queueing Models via Random Sums and Intervals, Adv. Appl. Proba., 24, pp. 960985. Jewel], W.S. (1967) A Simple Proof of L = XW, Oper. Res., 1116.
&, pp.
1109-
Kalahne, U. (1976) Existence, Uniqueness and some Invariance Properties of Stationary Distributions for General Single Server Queues, Math. Operationsforsch. Stat. 7, pp. 557-575.
Kleinrock, L. (1975,1976) Queueing Systems (I, 11), John Wiley & Sons, New York. Konig, D. and Schmidt, V. (1980) Imbedded and Non-imbedded Stationary Characteristics of Queueing Systems with Varying Service Rate and Point Process, J . Appl. Proba., 17,pp. 753-767. I
.a,
Lindvall, T. (1988) Ergodicity and Inequalities i n a Class of Point Processes, Stoch. Process. Appl., 3,pp. 121-131. Lindvall, T . (1992) Lectures on the Coupling Method, Wiley, New York.
Kalashnikov, V.V., and Rachev, S.T. (1990) Mathematical Methods for Construction of Queueing Models, Wadsworth & Brooks, Pacific Grove, Cal.
Liptser, R.S. and Shiryayev, A.N. (1978) Statistics of Random Processes, II : Applications, Springer Verlag, New York.
Kallenberg, 0. (1983) Random Measures, 3rd ed. Akademie-Verlag, Berlin, and Academic Press, London. (first. ed., 1975).
Lisek, B. (1982) A Method for Solving a Class of Recursive Stochastic Equation, Zeitschrift fur Wahr3ch. 60, pp. 151-162.
Kallenberg, 0. (1984) A n Informal Guide to the Theory of Conditioning i n Point Processes, Int. Statist. Review pp. 151-164.
Little, J. (1961) A Proof for the Queueing Formula L = XW, Oper. Res., 9, pp. 383-387.
Karr, A.F. (1986) Point Processes and their Statistical Inference, Marcel Dekker, New Uork.
Loynes, R. M. (1962) The Stability o'f Queues with non Independent Intera m v a l and Service Times, Proc. Camb. Ph. Soc. 58, pp. 497-520.
Marr, A.F. (1988) Palm Distributions of Point Processes and their Application to Statistical Inference, Contemporary Mathematics, 80, pp. 331-358.
Mairesse, J. (1993) Products of Random Matrices i n the (max,+) Algebra, INRIA Report 1939.
Kella, 0. and Whitt, W. (1991) Queues wilh Server Vacations and Livy Processes with Secondary Jump Input., The Annals of Appl. Proba., 1,pp. 104-117.
Marshall, A.W. and Olkin, I. (1979) Inequalities: Theory of Majorization and its Applications, Academic Press, New York.
a,
Kelly, F. (1979) Reversibility and Stochastic Networks, Wiley, New York.
MassouliB, L. (1993) Stability of a non-Markovian Polling System, Preprint, Laboratoire des Signaux e t Systkmes, CNRS.
Mhinchin, A.Ua. (1955) Mathematical Methods i n the Theory o j Queueing (in Russian), Trudy Mat. Inst. Steklov 49, [Translated (1960) Griffin, London].
Matthes, K. (1962) Zur Theorie des Bedienungsprozesses, Trans. 3-rd Prague Conf. Information Theory, Prague 1964, pp. 513-528.
Khinchin, A. Ua. (1932) Mathematical Theory of Stationary Queues (in Russian), Mat. Sbornik 39, pp. 73-84.
Matthes, K., Kerstan, J. and Mecke, J. (1978) Infinitely Divisible Point Processes, 2nd ed. Wiley, New York.
Kingman, J.F.C. (1970) Inequalities in the Theory of Queues, Journal Roy. Stat. Soc. B ;22, pp. 102-110.
Mecke, J . (1967) Stationare zuf6Llige Masse auf lokal kompakten Abelschen Gruppen, 2. Wahrs. 9, pp. 36-58.
1,pp.
Mecke, J. (1968) Eine charakten'stische Eigenschaft der doppelt stochastischen Poissonschen Prozesse, Zeitschrift fiir Wahrs. ll,pp. 74-81.
Kingman, J.F.C. (1976) Subadditive Processes, Ecole d'EtB de Probabilitk de Saint-Flour, Springer-Verlag, New Vork.
Mitrani, I. (1987) Modeling of Computer and Communications Systems, Cambridge Univ. Press.
Kingman, J.F.C. (1973) Subadditive Ergodic Theory, Annals of Proba. 883-909.
References
References
251
Miyazawa, M. (1977) T i m e and Customer Processes i n Queues with Stationary Inputs, J. Appl. Proba., 14,pp. 349-357.
[I151 Schassberger, R. (1977) Insensitivity of Steady State Distribution of Generalized semi-Markov Processes I, Ann. Proba. 5, pp. 87-99.
Miyazawa, M. (1979) A Formal Approach to Queueing Processes i n the Steady State and their Applications, J . Appl. Proba., 16,pp. 332-346.
[I161 Schassberger, R. (1978) Insensitivity of Steady State Distribution of Generalized semi-Markov Processes II, Ann. Proba. 6, pp. 85-93.
Miyazawa, M. (1983) The Derivation of Invariance Relations i n Complex Queueing Systems with Stationary Inputs, Adv. Appl. Proba., 15,pp. 874885.
[I171 Schassberger, R. (1978) Insensitivity of Steady State Distribution of Generalized semi-Markov Processes with Speeds, Adv. Appl. Proba., @, pp. 836-851.
Miyazawa, M. (1985) The Intensity Conservation Law for Queues with Randomly Changed Service Rate, J . Appl. Proba, 22, pp. 408-418. Muirhead, R.F. (1903) Some Methods Applicable to Identities and Inequalities of Symmetric Algebraic Functions of n Letters, Proceedings of Edimburgh Mathematical Society 21, pp. 144-157.
r Klasse won Mittelbildungen mit Anwendungen der (1181 Schur, I. (1923) ~ b e eine Determinanten, Theorie Sitzung. Berlin Math. Gesellschaft, 22, pp. 9-20. [I191 Shanthikumar, G.J. and Sumita, U. (1987) Convex Ordering of Sojourn Times i n Single Server Queues: Extremal Properties of FIFO and LIFO Disciplines, J. Appl. Probability, 2.
Neveu, J. (1976) Processus ponctuels, in Ecole d'EtB de St. Flour, SpringerVerlag Lect. Notes in Math. =,pp. 249-445.
[I201 Shanthikumar, G.J. (1988) O n Stochastic Decomposition i n M / G I / l Type Queues with Generalized Server Vacations, Oper. Res., 36, pp. 566-569.
Neveu, 3. (1976). Sur les mesures de Palm de deux processus ponctuels stationnaires, Zeitschrift fiir Wahrsch. 34, pp. 199-203.
[I211 Shanthikumar, G.J. (1989) Level Crossing Analysis of Priority Queues and Conservation Identity for Vacation Models, Naval. Res. Logist. Quart., 36, pp. 797-806.
Neveu. J. (1983) Construction de files d'attente stationnaires, in Lecture Notes in Control and Information Sciences Springer-Verlag, Berlin Neidelberg, pp. 31-41.
11221 Slivnyak, I.M. (1962) Some Properties of Stationary Flows of Homogeneous Random Events, Theory Proba. Appl.. 1,pp. 347-352.
Palm, C. (1943) Intensitatsschwankungen i m Fernsprechverkehr, Ericsson Techniks 44, pp. 1-189.
(1231 Slivnyak, I.M. (1966) Stationary Streams of Homogeneous Random Euents, Vest. Harkov. Gos. Univ. Ser. Mech. Math. pp. 73-116.
Papangelou, F. (1972) Integrability of Expected Increments and a Related Random Change of Time Scale, Trans. Amer. Math. Soc. 165,pp. 483-506.
(1241 Smith, W.L. (1955) Regenerative Stochastic Processes, Proc. Roy. Soc., Ser. A 232, pp. 66-31.
Phipps, T. (1956) Machine Repair as a Priorip Waiting Line Problem, Oper. Res., 4, pp. 76-85.
11251 Stoyan, D. (1983) Comparison Methods for Queues and Other Stochastic Models, English Edition, Wiley, New York.
Pollaczek, F. (1930) Ueber Aufgabe der Warscheinlichkeitstheorie (I,II), Math. Zeitschr., 32, pp. 65-99 and 729-750.
11261
Reiman, M.I. and Simon, B. (1989) Open Queueing Systems i n Light Tkafic, Mathematics of Oper. Res., & 1 , pp. 26-59.
[I271 Thorisson, H. (1992) O n T i m e and Cycle Stalionarity , Stoch. Proc. Appl., to appear.
Rogozin, B.A. (1966) Some Extremal Problems in Queueing T h w r y , Theor. Prob. Appl. and its Appl. jJ, pp. 144-151. -
[I281 Totoki, H. (1966) T i m e Changes of Flows, Mem. Fac. Sci. Kyushu Univ., Ser. A, 20, pp. 27-55.
Rolski, T. (1981) Stationary Random Processes Associated with Point Processes, Springer-Verlag Lecture Notes Statist. 5, Springer-Verlag, Berlin Heidelberg. '
(1291 Walrand, 3. (1988) A n Introduction lo Queueing Networks, Prentice-Hall, Englewood Cliffs, N. J.
a,
.
Rolski, T. (1983) Compan'son Theorems for Queues with Dependent InterArnval Times, in Springer Verlag, Lecture Notes in Control and Information Sciences 60, pp. 42-71.
a,
Strassen, V. (1965) The Existence of Probability Measures with Given Margznals, Ann. Math. Statist. pp. 423-439.
s,
11301 Watanabe, S. (1964) O n Discontinuous Additive Functionals and Lkvy Measures of a Markov Process, Japan J. Math. pp. 53-70.
a,
[I311 Whitt, W. (1984) Minimizing Delays i n the GI/GI/I Queue, Oper. Res., 2, pp. 41-51.
Ross, S.M. (1978) Average Delay i n Queues with non-stationary Poisson Arrivals, J . Appl. Proba., 15,pp. 602-609.
[I321 Whitt, W. (1985) The Renewal-Process Stationary Excess Operator, J.A.P. 22, pp. 156-167. -
Riischendorf, L. (1981) Ordering of Distributions and Rearrangement of Functions, The Annals of Probability, 2,pp. 276-283.
[I331 Whitt, W. (1991) A Review of L = XW and Extensions, Queueing Systems, 9, pp. 235-268.
Ryll-Nardzeweki, C. (1961) Remarks on Processes of Calls, Proc. Fourth Berkeley Symp. Math. Statist. Probab. 2,pp. 455-465.
(1341 Wolff, R.W. (1970) Work Conserving Priorities, J. Appl. Proba., 337.
-
1,pp. 327-
'
. (1982) Poisson Arrivals See
Time Average, Oper.
I1361 Wolff, R.W. (1989) Stochastic Modeling and the Theory of Queues, PrenticeHall, Englewood Cliffs, N.J.
o-field - Predictable, 7 - ~ r o ~ r e s s h46 e, &-Framework, 14 Adapted, 45 ANTIPASTA, 169, 170 Association, 107, 224, 226, 238 Busy period, 72, 147, 167, 187 Campbell measure, 15 Canonical t-process, 13 Canonical space - of marked point process, 9, 12 - of point process, 6 Compatibility,. 14, 46 Congestion process, 145 Conservation principle, 23 Construction point, 71, 79, 83, 143, 147 Convergence - in distribution, 77, 88, 93, 218 - in variation, 87, 88, 90, 93 - Rate, 89 Corlol, 151 Counting measure, 6 Coupled queues, 227 Coupling, 89, 90 - in continuous time, 92 - Inequality, 88 - of point processes, 89 - of stochastic processes, 87 - Strong, 97, 99, 106 - Time, 87 Critical value, 77 Customer-average, 18 Cycles, 71, 147 Discipline, 72, 113 Admissible, 115, 201
-
- Non-preemptive, 160, 161, 164, 188, 204 - Preemptive, 171, 192 - Preemptive resume, 164 - Reasonable, 73 - with no information on service times, 114, 204 Distribution - Lattice, 93 - Spread-out, 93
.
Ergodic theorem, 79 - Cross, 42 - Sub-additive, 127, 132 ESTA, 167, 169, 179 Feller's paradox, 26, 229 FIFO, 72, 73, 91, 114, 118-120, 160, 178, 182, 184, 189, 204, 231 Flow, 7, 8 Formula - H = XG, 156, 159 -- Extended, 159 - L = XW, 146, 150, 155 -- Ordinal, 155 - Brill and Posner's, 179 - Campbell's, 19, 20, 157 - Campbell's original, 19 - Campbell-Little-Mecke's, 20 -- Ihnctional, 156, 160, 161, 165 - Cobham's, 188 - - Non-preemptive, 190 - Cooper's, 183 - Cross Ergodic, 43 - Exchange, 21, 119, 150, 156 - Inversion, 23, 28, 150, 155 - Job-observer, 168 - Kleinrock's conservation, 162, 163, 193 - LBvy's, 36, 48 - Little's, 43, 190, 203
254
Index
Index
---
Extended, 154 Server, 146 -- Waiting room, 146 - Mean value, 27 - Mecke's, 19 - Miyazawa's, 23 - Palm-Khinchin's, 20 - Papangelou's, 54, 171, 175 - Phipps', 192 - Pollaczek-Khinchin's - - Characteristic function, 183 -- Mean value, 160, 162, 163, 198 - Residual service time, 161 - Swiss army, 150, 153, 156 - Taka&', 183
Lack of bias, 166, 167 Level crossing, 180, 181 LIFO, 72, 160, 171, 205 - Non-preemptive, 114 - Preemptive, 114 Light traffic, 158 Lindley's equation, 70, 74, 137 Loynes Sequence, 76, 119, 218 - Theorem, 70 - Variable, 76, 90, 91, 98, 228
-
Harris inequality, 225 History, 45 - Compatible, 46 - Internal, 45 Hopf's lemma, 79 Idle period, 72, 147 Imbedded thinning, 63 Independent version, 225 Infinitesimal estimate - Dobrushin's, 39 - Korolyuk's, 39 Input - GIG, 69, 118, 142, 144, 164 - M I G I , 48, 187 Insensitivity, 171 Integral order, 209, 234 - Concave, 211 - convex, 210, 211 - convex symmetric, 210 - Decreasing, 211 - Increasing, 209, 211 - Increasing convex, 210 - Increasing product form, 210 - Pointwise representation of, 214 - Schur convex, 215 - Stability by convolution of, 214 - Strong, 210, 217 Intensity, 15 Intensity measure, 15 Inter-arrival time, 68 Inter-departure time, 91 Interchange argument, 204 Invariant event, 40 Joint stationarity, 14, 142
-
Kendall's terminology, 69
'
Majorization, 199, 203 Markov chain, 48, 170 - Macrostate description of, 59 - Transitions of, 11, 36 Marks, 10 - Comparison of, 234 - Selected, 34 - Shadowing property of, 10 - Universal, 11 Martingale, 50 - Kolmogorov's, 61 - Mvy's, 62 - Local, 50 - Square integrable, 50 - Strong l$w of large numbers, 58 Monotone s'eparable framework, 130 Monotonicity - External, 130, 131 - Internal, 131 Norton's theorem, 175, 176 Palm probability Discrete time, 43 Invariance of, 1 8 Local interpretation of, 18, 39 Matthes' definition of. 16 Mecke's definition of, 19, 151, 156, 166 Papangelon's theorem, 54, 166, 170 Partial order, 199 Partial semi-order, 199, 209 PASTA, 54, 161, 165, 166, 172, 183, 190, 192 - Conditional, 170 - Extended, 178 Perturbation analysis, 158 Point process, 8 - (Am), 94
-
Common points of, 14 - Delayed, 37, 121 - Departure, 143, 145 Ergodic, 42 - Extremal, 232 Intensity of, 15 - Simple, 7 - Stationary, 8 - Superposition of, 10, 32, 35, 92 Poisson process, 47, 59, 158, 165 - Mecke's characterization of, 56 on product space, 62 Strong Markov property of, 52 - Watanabe's characterization of, 50, 166 Predictable, 46 Predictable structure, 46 Priority, 114 - Class, 5, 92, 120, 144, 162, 163, 188, 191, 193, 194 - Non-preemptive, 193 - Preemptive, 92, 120, 121 Probability space - Canonical, 12 - Enriched, 110 Process - Congestion, 72, 74 - at arrivals, 174 -- a t departures, 174 -- System, 143, 145 -- Waiting room, 143, 145 - Equivalent birth and death, 175, 178 - Sub-additive, 126, 131 - Workload, 70, 104, 145, 181, 237 Product form bounds, 226 Progressively measurable, 46 PS, 148, 165
-
-
-
Queue
-
-
G~/GI)S)C, 165 GI/M/l/oo, 178 M / G I / l / m , 166, 167, 187, 188, 191, 193, 231 - Arrival rate of, 15 - Assembly, 137
-
255
Blocking, 123
- Extremal properties of, 220
- Finite capacity -- Blocking, 123, 137, 222, 232
-- Loss, 104, 123, 147 - First order equivalent, 175
-
in random environment, 222 Mutual service, 118 Pure delay, 112 - Stochastic comparison of, 219, 236 Vacation, 116, 183 Queueing network - Gordon-Newell, 168, 176 - Jackson, 138 - Kelly, 120 - Route of, 120 - Tandem, 119,123
-
Radon-Nikodfm derivative, 26, 54, 166, 170 RANDOM, 73 Recurrence time, 24, 184-186, 233 Renewal - Assumption, 219 - Function, 107 - Process, 25, 184, 230 Renovating event, 98, 102, 103, 106 - Compatible, 100 Reordering of vectors, 203 Residual service time, 143 Rule - PC, 194 - clp, 193 Saturation rule, 130 Schur-convexity, 200, 203 Semi-Markov process, 29 Separability, 130, 131 Service - Discipline, 72 - Residual, 113, 143, 145, 161, 189 - Time, 69 Shadowing property, 10 Shift - Invariance, 16 - Operator, 7 Short circuit, 176 Sojourn time, 143, 145, 182, 203 - Virtual, 192 SPT, 73, 114, 160, 191, 194 SRPT, 73, 114, 165, 201 Stability, 70 - Region, 77, 125, 127, 130, 133, 143
Stationary solution Maximal, 83 - Minimal, 76, 78, 84, 90, 125 - Uniqueness of, 77, 128 Stieltjes-Lebesgue - Integral, 151 - Integration by parts, 151 Stochastic intensity, 45, 49, 94, 166 - Invariance of, 53 - Kernel, 48, 96, 187 Stochastic kernel, 48 Stochastic order, I97 - Analytical characterization of, 212, 234 - Convex, 229, 231, 238 - Convex increasing, 233 - of point process, 229 - Pathwise, 197, 215 - Projection, 197, 215 - Stability by limit of, 218 - Strong, 229, 233, 237 - under stationary probability, 232
-
Stochastic recurrence, 89, 216 Stopping time, 46 Strassen's theorem, 214, 239 System-average, 18 Time t o inactivity, 130 Traffic intensity, 17, 34, 69, 121, 144 Translation operator, 7 Uniqueness, 71, 78, 79, 92, 101, 103-106, 121, 122, 129 Variability, 211 Waiting time, 118, 143, 145, 182 Wald's identity, 22 Workload - Compatible, 71 - Convergence of, 77 - Ordered vector, 81 - Stationary, 77 Workload process, 70