PPT

```Balancing Reduces Asymptotic
Variance of Outputs
Yoni Nazarathy*
EURANDOM, Eindhoven University of Technology,
The Netherlands.
Based on some joint works with
Gideon Weiss and Ward Whitt
QTNA 2010, Beijing,
July 26, 2010.
*Supported by NWO-VIDI Grant 639.072.072 of Erjen Lefeber
Overview
• GI/G/1/K Queue (with K
•
D (t ) 
or K


)
number of customers served during
• Asymptotic variance
V  lim
• Surprising results when
V ar  D ( t ) 
t
t
 1
Balancing Reduces
Asymptotic Variance of Outputs
[0, t ]
The GI/G/1/K Queue
 , ca
2
 , cs
2
D (t )
K
overflows
* Assume Q (0)  0


* Squared coefficient of variation:
ca , cs 
2
2
variance
m ean
2
Variance of Outputs
V ar  D ( t )   V t  o ( t )
Asymptotic Variance
V ar  D ( t ) 
V  lim
t
t
V ar  D (T )   V T
t
Simple Examples:
* Stationary stable M/M/1, D(t) is PoissonProcess( ): V a r  D ( t )    t
* Stationary M/M/1/1 with   .
1
1 1
D(t) is RenewalProcess(Erlang(2,  )): V ar  D ( t )    t   e  2  t
4
Notes:
1 2

c
3  m
* In general, for renewal process with m ,  : V 
m
2
2
* The output process of most queueing systems is NOT renewal
8
8
V 
V 
4
Asymptotic Variance for   1 (simple)
K  ,   1

D (t )
V ar  D ( t ) 
t
V   ca

A(t ) 
V ar  A ( t ) 
t

Q (t)
V ar  Q ( t ) 
2
C ov  A ( t ), Q ( t ) 
t
t
2
K  ,   1
After finite time, server busy forever…
V   cs
2
K 
V
is approximately the same as
K 
when 
1
or

1
Intermediate Summary
V
GI/G/1
GI/G/1/K
V
 ca
 ca
2
2
?
?
 cs
 cs
2
2

V


M/M/1
V


?



M/M/1/K
?


B
alancing
R A
educes
symptotic
V
ariance of
O
utputs
Theorem (Al Hanbali, Mandjes, N. , Whitt 2010):
For the GI/G/1 queue with  1 , under some further
technical conditions:
2

2
2
V    1   (ca  cs )
 

Theorem (N. , Weiss 2008):
For the M/M/1/K queue with   1 :
V 
2

3
3K  2
3( K  1)
2
Conjecture (N. , 2009):
For the GI/G/1/K queue with  1 , under further
technical conditions :
V 
1
3
( c a  c s )  o K (1)
2
2
BRAVO Summary for GI/G/1/K
For GI/G/1/K with   1 :

2
2
2 
   ca  cs   1  

 

V 
  1 c 2  c 2  o (1)

s 
K
 3 a
Proven:
• K   : M/M/1/K
• K  :
* M/M/1
* Assuming finite forth moments:
*M/G/1
*GI/NWU/1 (includes GI/M/1)
*Any GI/G/1 with
P (B  x)
L( x) x
 1/ 2
Numerically Conjectured: GI/G/1/K with light tails
K 
K 
Numerical Illustration: M/M/1/K


*
*
V
V

*
V

*
V
Numerical Illustration: M/M/1 (finite T)
Some (partial) intuition for M/M/1/K

0

V
 


K-1


M

1










 A sym ptotic variance of num ber of transitions
Easy to see: V  4V
M
K

References
• Yoni Nazarathy and Gideon Weiss, The asymptotic variance rate
of the output process of finite capacity birth-death queues.
Queueing Systems, 59(2):135-156, 2008.
• Yoni Nazarathy, 2009, The variance of departure processes:
Puzzling behavior and open problems. Preprint, EURANDOM
Technical Report Series, 2009-045.
• Ahmad Al-Hanbali, Michel Mandjes, Yoni Nazarathy and
Ward Whitt. Preprint. The asymptotic variance of departures in
critically loaded queues. Preprint, EURANDOM Technical Report
Series, 2010-001.
```