Transcript ppt

PhD Course: Performance & Reliability Analysis
of IP-based Communication Networks
Henrik Schiøler, Hans-Peter Schwefel, Mark Crovella, Søren Asmussen
•
Day 1
Basics & Simple Queueing Models(HPS)
•
Day 2
Traffic Measurements and Traffic Models (MC)
•
Day 3
Advanced Queueing Models & Stochastic Control (HPS)
•
Day 4
Network Models and Application (HS)
•
Day 5
Simulation Techniques (HPS, SA)
•
Day 6
Reliability Aspects (HPS)
Organized by HP Schwefel & H Schiøler
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 1
Hans Peter Schwefel
Content
1. Basic concepts
•
•
Principles of discrete event simulation
Simulation tools
2. Random Number Generation
3. Output Analysis
•
•
Terminating simulations
Non-terminating/steady state case
Exercises I
4. Rare Event Simulation I: Importance Sampling
Exercises II
5. Rare Event Simulation II: Adaptive Importance Sampling
Exercises III
Note: this slide-set contains only the outline of the lecture; many formulas and the mathematical
derivations will be presented on the black-board!
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 2
Hans Peter Schwefel
Simulation Models (I)
• Basic principles of discrete event simulation
– Virtual simulation time t
– System state S(t)
– Events occur at certain times ti
• Instantaneous changes of system state S(ti-1)S(ti)
• Possibly scheduling of follow-up events
– Events stored in ordered event list
– System description:
• Entities, attributes, and activities
• Frequently object oriented implementation
• Important aspects
– Initial state S(0)
– Termination Criterion
• Fixed simulation time T
• Fixed number of packets/connections
• Occurrence of certain events (e.g. Loss of connectivity)
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 3
Hans Peter Schwefel
Simulation Models (II)
• Application to wireless networks:Main components
–
–
–
–
–
Topology definition: nodes and connectivity
Link properties: e.g., Propagation models
Node functionalities: e.g., schedulers, buffer management, L2/L3 protocol implementation
Traffic models (and transport protocol implementation)
Mobility Models
•
probabilistic elements in several of these components  stochastic simulation
– ’alternative’: trace-driven simulations
•
Output parameters, statistics collection, e.g.
Packet based
• End-to-end packet delay
• packet loss rate
• energy per packet
Connection based
• File Transfer times
• Fraction of blocked calls
• throughput
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 4
Node/Link Properties
• Buffer occupancy
• Link utilizations
• throughput
Hans Peter Schwefel
Overview of Simulation Tools (examples)
• ’Libraries’ and programming languages with basic functionalities and data types:
– Sim_lib [Watkins, Kevin: Discrete Event Simulation in C, 1993]
– Simula [e.g. R. Pooley: An Introduction to Programming in SIMULA, 1987]
• General Purpose Simulation Environments
– DEMOS/MAOS [Birtwistle, A system for discrete event modelling on SIMULA (DEMOS), 1979]
– GPSS [http://www.minutemansoftware.com]
• Network Simulation Tools
–
–
–
–
NS2 [http://www.isi.edu/nsnam/ns/]
OPNET
WIPSIM [http://www.wipsim.net/]
Glomosim [http://pcl.cs.ucla.edu/projects/glomosim]
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 5
Hans Peter Schwefel
Content
1. Basic concepts
•
•
Principles of discrete event simulation
Simulation tools
2. Random Number Generation
3. Output Analysis
•
•
Terminating simulations
Non-terminating/steady state case
Exercises I
4. Rare Event Simulation I: Importance Sampling
Exercises II
5. Rare Event Simulation II: Adaptive Importance Sampling
Exercises III
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 6
Hans Peter Schwefel
Random Number Generation (I)
• Uniform Random Number Generator (RNG)
–
–
–
–
Sequence U1,U2,... of i.i.d. ’random’ numbers
Uniform distributed in ]0,1[
Pseudo-random: same seed X0  same sequence
example: linear congruential generator
• Xi+1=(a Xi + b) mod c, Ui+1=Xi+1/c
• E.g. a=75=16807, b=0, c=231-1 (prime)
– Properties of ‘good’ uniform RNGs
• Long cycle length  ‘uniform’ histogram of Uis
• Uniformity of tuples (Ui, Ui+1,…, Ui+k)
• Successfully passing independence tests
• Issues with pseudo-RNGs
– Seed selection
– Multiple number streams
[see also http://random.mat.sbg.ac.at]
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 7
Hans Peter Schwefel
Random Number Generation (II)
• Non-uniform RNGs
– Y1,Y2,… with cumulative distribution function F(x)
derived from uniform stream U1,U2,… by
• Inversion: Yi=F-1(Ui), e.g.
• Exponentially distributed RVs
• Discrete distributions
• Rejection
• Convolution/Composition, e.g.
• Erlang distributed RVs
• Normally distributed RVs
•
Example: Generation of Power-Tailed RVs
– Inversion
– Using infinite Matrix-Exponential Representation (see Day 3)
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 8
Hans Peter Schwefel
Content
1. Basic concepts
•
•
Principles of discrete event simulation
Simulation tools
2. Random Number Generation
3. Output Analysis
•
•
Terminating simulations
Non-terminating/steady state case
Exercises I
4. Rare Event Simulation I: Importance Sampling
Exercises II
5. Rare Event Simulation II: Adaptive Importance Sampling
Exercises III
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 9
Hans Peter Schwefel
Output Analysis (I): General
• Goal: Obtain Estimator Ž of desired performance parameter 
– Note: Ž often multi-dimensional
– Ž is a random variable with some distribution fŽ(x)
– Main cases
• Moments: Ž is estimator of =E(Z)
• Quantiles: Ž is estimator of quantile [not considered here]
• Probabilities: Ž is estimator of probability p(A);
p(A)=E( I(A) )  equivalent to estimating moments [event A, I Indicator function]
•
Properties of estimator: Žt is called (t=simulation time)
• Unbiased when E(Žt)=
• Consistent when lim Žt= for t (stochastic convergence)
• Types of Simulations
– Terminating simulations ~ ’transient parameters’
– Non-terminating simulations ~ Steady-state parameters
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 10
Hans Peter Schwefel
Output Analysis II: Terminating Simulations
• Terminating Simulations
– Explicite stopping criterion, e.g.
• Fixed simulation time
• Fixed number of arrivals/connections
• Specific event (e.g. Buffer overflow, component failure)
– Approach: Independent Replications
• Repeat Experiment R times, each time with different seeds
 independent outcomes Z1,Z2,...ZR
• Estimator Ž=1/R  Zi
• Unbiased
• Asymptotically normal distributed
•
Relevant examples:
•
•
•
•
Determine mean first passage time (starting with empty buffer)
Determine average buffer-occupancy during busy hours 9-17hrs (starting empty at 9hrs)
Determine probability that call will be dropped before its desired end (given initial conditions)
Determine probability of buffer-overflow within n packet arrivals (given empty buffer in
beginning)
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 11
Hans Peter Schwefel
Output Analysis III: Confidence Intervals
•
Example: Estimate Probability =Pr(Overflow before simulation time t)
– R replications with indep. outcomes Zi={1 when overflow occurred, 0 otherwise}
– Estimator Ž=1/R  Zi
• R* Ž Binomially distributed: expected value R, variance R (1- )
• E(Ž)=  (unbiased!), Var(Ž)=(1- )/R
• Estimates Š2 of Var(Zi)=2
• Š2 = Ž(1-Ž) [for probabilities]
•
General case: Š2 = 1/(R-1)  (Zi-Ž)2
Approaches for Confidence Intervals:
•
Convergence to normal distribution
• R (Ž- )/  in the limit standard normal distributed
•
General variance estimate  use of Student t distribution
• R (Ž- )/Š approx. Student-t distribured with (R-1) degrees of freedom
•
Variance stabilization for probability estimates
•
R (2 arcsin Ž – 2 arcsin ) approx. standard normal distributed
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 12
Hans Peter Schwefel
Output Analysis IV: non-terminating case
• Steady state parameters  in theory infinite simulation needed
• Finite simulation length causes biased estimator
• Approaches:
– Independent replications, impact of transient phase
 ’avoid’ transient phase
– Single, long simulation run
• Problem: correlated samples require adjustment of variance estimate
• Alternatives
• Batching
• Regenerative Simulation
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 13
Hans Peter Schwefel
Content
1. Basic concepts
•
•
Principles of discrete event simulation
Simulation tools
2. Random Number Generation
3. Output Analysis
•
•
Terminating simulations
Non-terminating/steady state case
Exercises I
4. Rare Event Simulation I: Importance Sampling
Exercises II
5. Rare Event Simulation II: Adaptive Importance Sampling
Exercises III
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 14
Hans Peter Schwefel
Exercises I:
1.
RNGs: Use the method of inversion to generate samples from an exponential distribution with rate . Use
MATLAB’s rand function to generate the underlying uniform samples. Check your exponential random
numbers by computing the mean, coefficient of variation, and by comparing the histogram with the
exponential density function.
2.
(take-home) Time varying Poisson processes: an analysis of a daily utilization profile of a network indicates a time-
3.
Output Analysis for terminating simulations: Use the given MATLAB code to simulate an M/M/1/10
queue with =0.9, =1. Use independent replications to determine an estimate of the probability
=Pr(packet loss occurs within first 100 arrivals | buffer is empty at time t=0),
including 95% confidence intervals.
4.
(take home) Transient Phase: Use the given M/M/1 simulator to obtain an estimate for the mean queue-length.
varying packet generation rate of approximately (t)=144-(t-12)2, 0<t<24). Generate packet inter-arrival times for a timevarying Poisson process with that rate.
Compare the estimates (and confidence intervals) obtained from simulation runs (indep. Replications) with simulation times of
t=10,100,1e4. Compare the estimates with the true value and with simulations in which the first [5,20,100,500] samples are
not taken into account for the estimator.
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 15
Hans Peter Schwefel
References
•
•
•
Cassandras, Lafortune, ’Introduction to Discrete Event Systems’,
Chapt. 10, Kluwer, 1999.
Heyman, Sobel (ed.), ‘Stochastic Models’,
Chapt. 6 and 7, North-Holland,1990
S. Asmussen, P. Glynn, ‘Stochastic Simulation. With a view towards stochastic
processes’,
Springer, 2004.
PHD Course: Performance & Reliability Analysis, Day 5, Spring04
Page 16
Hans Peter Schwefel