Transcript Document

Traffic Modelling and
Related Queueing Problems
Presenter: Moshe Zukerman
ARC Centre for Ultra Broadband Information Networks
EEE Dept., The University of Melbourne
Presented at EE Dept., City University of Hong Kong, 11 April, 2002
Credit: R. Addie (USQ), T. Neame (EEE, Melbourne)
OUTLINE
1.
2.
3.
4.
5.
6.
7.
8.
9.
The big picture
Stream traffic modelling – ground rules
Growth and efficiency
Long Range Dependence (LRD) and LRD vs.
SRD + traffic models review
Poisson Pareto Burst Process (PPBP)
PPBP queueing performance
PPBP fitting
Fundamentals and ideas
The Resurrection of the MMPP
The Big Picture
Link and Network Design
and Dimensioning
Traffic
Modelling
Performance
Evaluation
Traffic
Queueing
Measurements Theory
Formulae in
Closed Form
Traffic
Prediction
Simulations and
Fast Simulations
Numerical
Solutions
Of Course, there are short cuts:
Just Do It! and then see …
Pros and Cons
But let’s forget about these
short cuts for now …
Research in Performance Evaluation
1. Exact analytical results (models)
2. Exact numerical results (models)
3. Approximations
4. Simulations (slow and fast)
5. Experiments
6. Testbeds
7. Deployment and measurements
8. Typically, 4-7 validate 1-3.
Performance evaluation tool
Parameters
Black
Box
Performance
The black box, can have:
Traffic (model or trace), and
a system or a network model, and
(1) Performance Formulae, or
(2) Numerical solution, or
(3) Fast Simulation, or
(4) Simulation
How fast should the black box be?
Parameters
Black
Box
Performance
• Very Fast (micro-millisecond) for
congestion control
• Fast (100s milliseconds) for
Connection Admission Control
• Slow (days) for network design and
dimensioning
Traffic Modelling
Traffic
Trace (TT)
Stochastic
Process (SP)
S
Ground Rules: For a given TT, S finds an SP defined
by a small number of parameters such that:
(1)TT and SP give the same performance when fed
into an SSQ for any buffer size and service rate.
(2)TT and SP have the same mean and autocorr.
(3)Preferably, SP SSQ is amenable to analysis.
“Do Not” Rules
• We Do not take retransmissions into
account.
• We ignore TCP dynamics.
• The aim is to dimension network so that
retransmissions will normally not be
needed.
• This will be efficient as traffic, capacity and
number of users increase. (why??)
Why does efficiency increase
with growth?
• If load and capacity increases service rate is
better- Scaling (Frank Kelly).
• Convergence to Gaussian - Central Limit
Theorem (Addie) – but the convergence is
slow.
Scaling
Q(t) = queue size at time t
A(s,t)=Work arrive between s and t
S(s,t)=Service capacity between s and t
Reich’s Formula:
Q(t )  maxA(t  t , t )  S (t  t , t )
t
Consider two scenarios (1 and 2). Let:
A1(s,t)= A2(bs,bt)
S1(t-t,t)=b S2(t-t,t)= S2(b(t-t),bt)
Q1 (t )  maxA1 (t  t , t )  S1 (t  t , t )
t
 maxA2 (b(t  t ), bt)  S 2 (b(t  t ), bt)
t
 maxA2 (bt  bt , bt)  S 2 ((bt  bt ), bt)
t
 Q2 (bt)
Thus, queue size is the same
but served much faster!
LRD Convergence to Gaussian
Buffer size, x
1
0
500
0.1
Pr(Q > x)
0.01
0.001
0.0001
0.00001
0.000001
0.0000001




Gaussian
1000
1500
2000
Why does LRD traffic
converge to Gaussian slowly?
I will tell you later.
First, let me explain the meaning of
LRD traffic and the difference
between LRD and SRD.
Background
• Modelling packet traffic is difficult because of its
properties
• Long Range Dependence (LRD) is a widespread
phenomenon
• LRD has been found in
–
–
–
–
–
–
Ethernet traffic
VBR video traffic
Internet traffic
MAN traffic
ATM cell traffic
CCS Signalling Traffic
(Leland, et al. 94)
(Garrett & Whitt 94)
(Paxson 95)
(Zukerman, et al. 95)
(Jerkins & Wang 97)
(Duffy, et al. 94)
• Possible causes for LRD
– Distribution of file sizes
– Human behaviour
– VBR video
Long Range Dependence
• A process is defined to be Long Range Dependent
if its autocorrelation function R(t) decays slower
than exponentially.
• LRD need only exist in the limit t  
– LRD implies nothing about its short term correlations
which affect performance in small buffers
• Traditional traffic model processes are Short
Range Dependent (SRD)
• In practice, LRD is difficult to distinguish from
non-stationarity
Traffic Modeling:
Historical Highlights
•1986 Heffes and Lucantoni IEEE JSAC
IEEE Best Paper Award (MMPP)
•1994 Leland et al. ACM/IEEE TON
IEEE Best Paper Award (LRD)
•1995 Likhanov et al. INFOCOM
Best Paper Award – proposed a model
equivalent to the one we call Poisson
Pareto Burst Process (PPBP)
Arrival Process Autocovariance (IID)
The Variance
v=Autocovariance Sum = The variance
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
Arrival Process Autocovariance SRD
The Variance
v=Autocovariance Sum
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
For SRD
v = limn VAR [A(n)]/n
That is, for large n,
VAR [A(n)] grows linearly
with n.
Arrival Process Autocovariance (LRD)
The Variance
V = Autocovariance Sum = 
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
For LRD

VAR[ A(n)]  Cn
wit h  > 1,
Queueing Performance Comparison
BUFFER SIZE
LOSS PROBABILITY
LRD
SRD
IID
Self Similar Traffic (Ethernet)
1 Second Intervals
10 Second Intervals
60 Second Intervals
100 Second Intervals
Half Hour Intervals
1 Hour Intervals
Arrivals Poisson
Interval = 10
Interval = 1
700
80
70
600
60
500
50
400
40
300
30
0
50
100
0
150
Interval = 100
70000
6000
60000
5000
50000
4000
40000
3000
30000
50
100
100
150
Interval = 1000
7000
0
50
150
0
50
100
150
For Poisson (IID) or SRD

VAR[ A( t )]  t
For Poisson  = 1,
SD[ A( t )]
t
Burstiness =

E[ A( t )]
t
For LRD

VAR[ A(t )]  t
with  > 1,
SD[ A(t )]
t
Burstiness =

E[ A(t )]
t

LRD vs. SRD
Slope>1: Fractal (LRD)
Slope=1: Non-fractal (SRD)
Log V(A(t))
Log (t)
The Hurst Parameter

limt  VAR[ A(t )]  t
with, 2 >   0 (LRD: 2 >  > 1)
The Hurst Parameter ( H ):
H =  / 2, (LRD: 1 > H > 1 / 2)
Burstiness on ALL scales?
Not Really.

VAR[ A(t )]  t
wit h 2 >  > 1
SD [ A(t )]
(  / 2)  1
 Ct
E [ A(t )]
Still approaches zero as t grows because

<2
Queueing Performance
State of the art
MMPP SRD Gaussian LRD
PPBP
(SRD)
Gaussian (LRD)
Queueing Done
Analysis
Fast/Slow Fast +
Simulat’n slow
SSQ
SSQ
Useless
Approx.
Approx. bounds +
(AZ 92,93,94) (AZN 95) results
here
Fast + slow
Fast
Only
Slow +
results
here
The Markov Modulated Poisson
Process (MMPP) ?
• Several traffic activity modes
• The period of each activity mode
has exponential distribution
• When in mode i – Poisson i
Time
Two State MMPP Results
• Analytical results for queueing
performance are available
•Four parameters
•Fitted to mean, variance, v, +
•Numerical algorithms (Matrix
Geometric) results available for n
state MMPP.
Gaussian Queueing Results
• SRD: results as a function of
three parameters which can be
fitted to mean, variance, v
•LRD: results as a function of
three parameters which can be
fitted to mean, variance, H.
Poisson Pareto Burst Process (PPBP)
• Total work from multiple overlapping bursts
• Burst arrivals according to a Poisson process of
rate 
• Burst durations are Pareto distributed
• During a burst, bit rate is constant
• All bursts have constant bit rate
Exponential
Pareto
Pareto Distribution
 x  
x 
  ,
Pr{ X  x}    
 1,
otherwise


E( X ) 
 1
• For
1   2
the Pareto distribution
– Is a heavy-tailed distribution
– Has infinite variance, but finite mean
Why the PPBP?
• Assume each user transmits at maximum capacity, or
zero capacity
– Each user can be represented as an on-off process
• Assume users are independent of one another
• Assume duration of on times is heavy-tailed
• The PPBP is a limiting case for the sum of multiple
independent heavy-tailed on-off processes – shown in
Likhanov, et al. 95
Heavy Tailed Distribution
x
1
0
2
4
6
8
10
12
14
16
Exp onential
Pr{x > x}
0.1
0.01
0.001
Par eto
18
20
The Poisson Pareto Burst Process
(PPBP)
Exponential ()
Pareto (, )
r
An
An is total work arriving in a fixed size interval of length
t
n
PPBP Parameter Fitting
r
E ( An ) 
 1
3
H
2
2

2r  ( /(2 (  1))  1 / 6
Var ( An )   2
F ( ,  )
2
r



F ( ,  ) 
 
3
6(3   )

 
2
2(2   )

1 
 1


(1   )(2   )(3   )
1   2
Recall: LRD Convergence to Gaussian
To fit  we choose the best curve!
Buffer size, x
1
0
500
0.1
Pr(Q > x)
0.01
0.001
0.0001
0.00001
0.000001
0.0000001




Gaussian
1000
1500
2000
Why does LRD traffic
converge to Gaussian slowly?
I can tell you now.
Long Bursts Short Bursts:
A very good way to consider LRD
traffic
time period
PPBP Initial Conditions
• “Steady state” process has Poisson
number of active bursts at time t
• Mean number of bursts is E(D)
• Remaining duration in each burst
distributed according to its forward
recurrence time
Pareto Forward Recurrence
Times
• Even heavier tail than ordinary Pareto
• Has infinite mean and infinite variance
 1  x 1
  ,

Pr{R  x}      
  1 1  x   1
     
1   2
x 
x 
Forward Recurrence Times – Even
Heavier Tails
Long Bursts and Short Bursts
• Consider a PPBP over the interval (t, t + W)
• At time t, there will be Bt bursts active
• Each of these Bt bursts will last the entire interval with
probability
1
1 W 
Pr{R  W }   
  
• Label the bursts present at the start and the end of the
interval as long bursts
• Rest of the bursts are the short bursts
Long Burst – Short Burst
Division
t
t+W
Long burst process
t
Short burst process
t+W
t
t+W
Properties
• Long bursts and short bursts processes are independent
of one another.
• Number of long bursts, n, is Poisson distributed with
mean E(D)Pr(R > W)
• For a given interval, long bursts process is a CBR
component
• Short bursts process is a correlated Poisson process
with mean rE(D)(1-Pr(R > W))
• Short bursts process is not LRD
Single Server Queue
• In interval n:
–
–
–
–
An is the number of cells arriving
C is the fixed service rate
Yn is the net arrival process
Qn is the amount of work in the buffer
Yn  An  C
Qn1   Qn  Yn 
AAnn
X   max  X ,0

Vnn
Q
Ct
Our Queueing Performance Results
• Overflow probability for short burst process
depends on n, number of long bursts
• Define S(x,n) as overflow probability when
number of long bursts is n
• Probability of n long bursts is Poisson with
mean E(D)Pr(R > W)
• Overall overflow probability for PPBP is:

Pr{Q  x}   Pr{N  n}S ( x, n)
n 0
Instability in a Simulation
• Probability of n long bursts is Poisson with mean
E(d)Pr(R > W)
• n long bursts leaves capacity C – nr for short
bursts
• Mean arrival rate for short bursts process is
 r E(d)(1-Pr(R > W))
• There is non-zero probability that the system will
be unstable for the duration of the simulation
• Can choose simulation length, W, such that this
probability is negligible
• Have demonstrated that overall impact of
instability is limited
Simulation with Random Number of
Long Bursts
• Long bursts may have significant impact on
simulation results
• Initialise simulation with a random number
of bursts and let a random number of these
be long bursts
• Will require a large number of simulations
to be sure that the state space is explored
thoroughly
Weighted Sum to Account for
Long Bursts
• Create a process with no long initial
bursts
• Simulate and find losses in systems with
rate C-nr
• Sum the losses from these systems,
weighted by the probability that N = n
Effect of Improved Simulations
Bu ffer th resh old , x
1
0
50000
100000
150000
2000 00
Pr{Q > x}
0 .1
W eighted Sum Sim ulation
Sim ple Sim ulation
0 .0 1
0 .0 0 1
IP trace fitting
W = 22,000,000
x 60 simulations
0 .0 0 0 1
Bu ffer th resh old , x
1
0
50000
100000
150000
Pr{Q > x}
0 .1
Simple simulation
0 .0 1
0 .0 0 1
0 .0 0 0 1
2000 00
Quasi-Stationary Estimate
• Long burst process is constant for period W
• Use existing techniques to estimate overflow
probabilities for short burst process fed into server
with capacity C - nr
• As with simulation, combine estimates according
to probabilities of n long bursts
• Which W gives best estimate?
– Choose the W which gives highest overflow probability.
QS Estimate for W
W
QS Estimate for W
W
QS Estimate for W
W
QS Estimate for W
Quasi-Stationary (QS) Estimates
W
Large Deviations Results
• Large deviations is a good approach for Gaussian
queues.
• It has failed to provide useful results for LRD non
Gaussian queues.
• There was an attempt to use Large deviation to
obtain analytical results for the continuous time
counterpart of the queue fed by PPBP (called the
M/G/  process) by Tsybakov & Georganas.
• We will discuss it now.
Large Deviations Results (cont.)
• Large deviations results for queues fed by
LRD sources have been derived by a
number of authors.
– Results only hold as
buffers
x  , i.e. for large
• Most useful results for M/G/ input are due
to Tsybakov & Georganas
– They give upper and lower bounds:
Ax (1 ) k  Pr{Q  x}  Bx (1 ) k
C
k  1    E (d )
r

Large Deviations Results (cont.)
Ax (1 ) k  Pr{Q  x}  Bx (1 ) k
C

k  1    E (d )
r

• A and B are constant with respect to the
buffer size x.
• Note that the upper and lower bounds
have the same form.
• We will compare our results against these
bounds.
Prob{Q > }
Comparison of Results
Prob{Q > }
Second Set of Results
Quasi-Stationary Estimate
• Previously have used repeated simulation to
fit final parameter 
• Using the estimate, fitting is faster and more
reliable
• Quasi-stationary value is still only an
estimate
– Most accurate when  is large
–  for PPBP fitted to real data is usually small
 Reliability is questionable
Modelling Measured Traffic
• PPBP has 4 parameters
– Burst arrival rate 
– Rate of work per burst r
– 2 Pareto parameters,  and 
• Parameter Fitting
– Can fit r, ,  to measured mean, variance, H
– Can produce PPBPs with same r, ,  values which
give very different queueing performance results
 Fitting  is vital to give a model which predicts the
performance of real traffic
PPBP Convergence to Gaussian
Buffer size, x
1
0
500
0.1
Pr(Q > x)
0.01
0.001
0.0001
0.00001
0.000001
0.0000001




Gaussian
1000
1500
2000
Good News! - Fitting the PPBP to
Real Traffic
Buffer threshold, x (pac kets)
1
0
0 .1
20000
40000
60000
IP Tra c e
   
G a us s ia n
Pr(Q > x)
0 .0 1
0 .0 0 1
0 .0 0 0 1
0 .0 0 0 0 1
0 .0 0 0 0 0 1
80000
     
   
100000
Autocovariance Fitting
2.50E+07
Autocovariance
2.00E+07
PPBP model (from analysis)
1.50E+07
PPBP model (from simulation)
1.00E+07
Trace
5.00E+06
0.00E+00
0
500
1000
1500
Lag, k
2000
2500
3000
How Are We Doing?
• Our aim was to find a stochastic process with the
following properties:
 Defined by a small number of parameters
• PPBP has only 4 parameters
– If the parameters of the process are fitted using
measurable statistics of an actual traffic stream then
• 3 of 4 parameters fitted to measurable statistics
• Fitting the 4th parameter can now be done systematically
 The first and second order statistics of the model will match
those of the traffic stream
How Are We Doing? (cont.)
If fed through an SSQ the performance results of the
model will accurately predict those of the real traffic stream
in an identical SSQ. This should be true for a wide range of
buffer sizes and service rates.
•PPBP does well
If performance results can be calculated analytically, so
much the better
•Quasi-stationary estimate provides an accurate
analytic estimate
Summary (PPBP)
• Described the Poisson Pareto Burst Process (PPBP)
• Long bursts may have a significant impact on PPBP
simulation results.
• We can factor long bursts into simulations.
• Quasi-stationary analysis gives a reasonable estimate
of the queueing performance of the PPBP.
• Using quasi-stationary estimate, reliable fitting of the
PPBP to real traffic streams is possible.
Speculation: MMPP Resurrection
Anti-thesis??
• The PPBP at this stage is not amenable to state
dependent queueing analysis.
• Such analysis is needed in many
Telecommunications systems.
• MMPP or other Markovian models are
amenable to such analyses.
• I will present now intuitive arguments for the
resurrection of MMPP.
Single Server Queue Realization
G/G/1
Unfinished Work Distribution
P ( V  T )  max P
w 1
w
 ( A
i 1
i
 B )  T 
Ai= work arrives during interval i
B= Service capacity during interval i
Reich’s Formula (1958)
Again, our SSQ Realization:
The relevant correlation duration is from
the beginning of the last busy period.
Indeed, LRD Longer busy periods.
G/G/1
But if we introduce a buffer …
???
BUFFER
The buffer breaks long busy
periods to many short ones!
G/G/1/2
And we may not need to consider LRD in
our traffic modelling.
Queueing Performance Comparison
LOG LOSS PROBABILITY
BUFFER SIZE
LRD
SRD
IID
LOGLOSS PROBABILITY
The resurrection: SRD (MMPP?) as a
model for LRD
BUFFER SIZE
LRD
SRD
IID
LRD vs. SRD
Slope>1: Fractal (LRD)
Slope=1: Non-fractal (SRD)
Log V(A(t))
Log (t)
The resurrection:
SRD (MMPP?) as a model for LRD
Slope>1: Fractal (LRD)
Slope=1: Non-fractal (SRD)
Log V(A(t))
Log (t)
Conclusion
There are arguments for
resurrection of the MMPP as
A traffic model.
The Game goes on
Two approaches:
(1)PPBP (State Dependent (?))
(2)MMPP (Accurate traffic model (?))