Discrete Event Simulation - TUM

Chair for Network Architectures and Services – Prof. Carle Department of Computer Science TU München Discrete Event Simulation IN2045 Dipl.-Inform. Alexander Klein Dr. Nils Kammenhuber Prof. Dr.-Ing Georg Carle Chair for Network Architectures and Services Department of Computer Science Technische Universität München http://www.net.in.tum.de

Topics Waiting Queues Random Variable Probability Space Discrete and Continuous RV Frequency Probability(Relative Häufigkeit) Distribution(discrete) Distribution Function(discrete) PDF,CDF Expectation/Mean, Mode, Standard Deviation, Variance, Coefficient of Variation p-percentile(quantile), Skewness, Scalability Issues(Addition) Covariance, Correlation, Autocorrelation Visualization of Correlation PP-Plot QQ-Plot Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 2

Statistics Fundamentals Waiting Queue Theory arrival process rate λ 3.4 0.6 1.7 1.6 0.7 0.7 1.3 buffer, queue random numbers inter-arrival times Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 service process rate μ 1.7 1.0 3.3 4.0 0.7 . service times 3

Statistics Fundamentals What are we talking about and why? Simple queue model: Customers arrive at random times Execution unit serves customers (random duration) Only one customer at a time; others need to queue Standard example Give deeper understanding of important aspects, e.g. Random distributions (input) Measurements, time series (output) Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 4

Statistics Fundamentals Queuing model: Input and output Input: (Inter-)arrival times of customers (usually random) Job durations (usually random) Direct output: Departure times of customers Indirect output: Inter-arrival times for departure times of customers Queue length Waiting time in the queue Load of service unit (how often idle, how often working) Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 5

Statistics Fundamentals Little Theorem X(t) W n 2 1 Bn 1 2 5 3.4 1.7 1.0 t 10 0.6 1.7 3.3 1.6 0.7 0.7 4.0 1.3 n 0.7 arrivals service durations event queue Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 6

Statistics Fundamentals Little Theorem λ : average arrival rate E[X] : average number of packets in the system E[T] : average retention time of packets in the system Arrival Process E[X] Rate λ E[T] to N t 1 o Ti X (t )dt N0 i 1 1 T N t 1 o X X (t )dt to 0 N to t o N X E[T ] to N t o t o lim lim T X Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 1 E[T ] lim T lim t o t o N N T i 1 i t 1 o E[ X ] lim X lim X (t )dt t o t o t o 0 7

Statistics Fundamentals Kendall Notation GI [x] / GI / n - S Number of Places in the Queue S 0 Loss/Blocking System S Waiting System Number of Servers Service Time Distribution Batch Arrival Process Arrival Process Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 8

Statistics Fundamentals Queuing Discipline FIFO / FCFS LIFO / LCFS SIRO PNPN EDF First In First Out / First Come First Served Last In First Out / Last Come First Served Service In Random Priority-based Service Earliest Deadline First Distributions M D Ek GI Hk Markovian Degenerate Distribution Erlang Distribution General distribution Hyper exponential Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 Exponential Service Time A deterministic service time Erlang k distribution General independent Hyper k distribution 9

Statistics Fundamentals System Characteristics Average customer waiting time Average processing time of a customer Average retention time of a customer Average number of customers in the queue Customer blocking probability Utilization of the system / individual processing units Example Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 How to model and evaluate waiting queues in OPNET 10

Statistics Fundamentals Exercise System A: D / D / 1 - Arrival rate λ 1 / s Service rate μ [1;10] / s System B: M / M / 1 - Arrival rate λ 1 / s Service rate μ [1;10] / s System C: M / M / 20 - Arrival rate λ 10 / s Service rate μ 1 / s System D: M / M / 1 - Arrival rate λ 10 / s Service rate μ 20 / s Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 What is the maximum (meaningful) utilization of the system? Which system performs better? What impact does the utilization have on the system? Which system performs better? Would you prefer a single fast processing unit instead of multiple slow processing units? 11

Statistics Fundamentals Exercise System E: M / M / 10 - Arrival rate λ 9 / s Service rate μ 1 / s System F: M / M / 100 - Arrival rate λ 90 / s Service rate μ 1 / s System G: M / D / 1 - Arrival rate λ 1 / s Service rate μ 1 / 0.7 / s System H: D / M / 1 - Arrival rate λ 1 / s Service rate μ 1 / 0.7 / s Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 What is the maximum (meaningful) utilization of the system? Which system performs better? Which system performs better? Which system has a shorter avg waiting time? 12

Statistics Fundamentals System G: M / D / 1 - λ 1 P(T 0.7s) 1 P(T 0.7s) 0.55 Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 System H: D / M / 1 - μ 1 / 0.7 1.43 P(T 1s) 0.75 13

Statistics Fundamentals Customer Arrival Flowchart Arrival Process Yes Schedule the next arrival event Is a service unit idle? Tally a delay of 0 for this customer No Find the shortest queue Mark service unit as busy Place Customer in the shortest queue Schedule a departure event Return Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 14

Statistics Fundamentals Flowchart Departure Process Yes Departure Event Is the queue empty? No Remove the first customer from the queue Set the state of service unit to idle Compute the customers delay Schedule a departure event for this customer Return Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 15

Statistics Fundamentals M/M/n- System of equations x(i 1) i x(i), i 1,2,3,., n, x(i 1) n x(i), i n 1,. x(i) 1 i 0 State Transition Diagram - M / M / n - Picture taken from Tran-Gia, Analytische Leistungsbewertung verteilter Systeme, p. 98 Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 16

Statistics Fundamentals M / M / 10 - State Distribution - M / M / 10 - Picture taken from Tran-Gia, Analytische Leistungsbewertung verteilter Systeme, p. 99 Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 17

Statistics Fundamentals M / M / 10 - The waiting probability decreases with an increasing number of processing units (assuming constant utilization) n number of processing units W - Waiting probability Utilization Picture taken from Tran-Gia, Analytische Leistungsbewertung verteilter Systeme, p. 100 Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 18

Statistics Fundamentals Classic definition of probability The theory of chance consists in reducing all the events of the same kind to a certain number of cases equally possible, that is to say, to such as we may be equally undecided about in regard to their existence, and in determining the number of cases favorable to the event whose probability is sought. The ratio of this number to that of all the cases possible is the measure of this probability, which is thus simply a fraction whose numerator is the number of favorable cases and whose denominator is the number of all the cases possible. - Pierre-Simon Laplace, A Philosophical Essay on Probabilities Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 19

Statistics Fundamentals Random Variable Probability Space (Ereignisraum) Ω {ω1, ω2, ω3, ω4, , ωi} Relation ω1 x1 ω2 ω3 ω4 ωi x2 x3 x4 xi Random Variable X Event Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 20

Statistics Fundamentals Discrete Random Variable: Countable Example: Flipping of a coin ω1 {head-0}, ω2 {tail-1} X {0, 1} Ω {ω1, ω2} Example: Rolling two dice ω1 {2}, ω2 {3}, , ω11 {12} X {2, 3, 4, , 12} Ω {ω1, ω2, , ω11} Continuous Random Variable: Uncountable Example: Round Trip Time T {5ms, 200ms} ω1 {t 10ms}, ω2 {10ms t 20ms}, ω3 {t 20ms} Ω {ω1, ω2} Example: Sensed Interference Level Discrete or not discrete Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 21

Statistics Fundamentals Frequency Probability / Law of large numbers (Relative Häufigkeit) Number of random experiments n total number of trials Xi event or characteristic of the outcome ni number of trials where the event Xi occurred ni h( X i ) n ni n n P( X i ) lim 0 h( X i ) 1 h( X ) 1 i i 0 P( X i ) 1 Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 P( X ) 1 i Vollständigkeitsrelation Xi disjoint i 22

Statistics Fundamentals Vollständiges Ereignissystem X Y N P(Y ) P( X i ) i 1 X Y Verbundereignis X Y P( X Y ) P( X , Y ) P(Y , X ) P( X Y ) P( X ) P(Y ) P( X Y ) Bedingte Wahrscheinlichkeit P( X , Y ) P( X Y ) P(Y ) P( X Y ) P( X , Y ) Statistische Unabhängigkeit P( X Y ) P( X ) Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 v P( X , Y ) P( X ) P(Y ) 23

Statistics Fundamentals Vollständiges Ereignissystem Ω N P(Y ) P( X i , Y ) X1 X2 XN i 1 Y X3 Xi Xi Y Bayes Function P(Y X i ) P( X i ) P(Y X i ) P( X i ) P( X i Y ) N P(Y ) P(Y X k ) P( X k ) k 1 Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 24

Statistics Fundamentals Distribution (Verteilung) X – discrete random variable Function x(i) P(X i) – x(i) e [0,1] , i 0,1,2, ,Xmax (Distribution) X max – x(i ) 1 (Vollständigkeitsrelation) i 0 Example: Rolling two dice ω1 {2}, ω2 {3}, , ω11 {12} X {2, 3, 4, , 12} Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 Ω {ω1, ω2, , ω11} 25

Statistics Fundamentals Example: Throwing two dice Sample Space (Ereignisraum) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 26

Statistics Fundamentals Example: Throwing two dice Sample Space (Ereignisraum) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 27

Statistics Fundamentals Distribution Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 28

Statistics Fundamentals Palour Game: Die Siedler von Catan Rules: Players are only allowed to build along borders of a field Players roll two dice If the sum of the dice corresponds to the number of the field, the player gets the resources from this field Question Where is the best place for a building? Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 29

Statistics Fundamentals Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 30

Statistics Fundamentals 9 8 7 6 5 4 3 2 1 Prison Are all fields reached with the same probability? Network– Security, IN2045 Discrete Event WS 2008/09, Simulation, Chapter SS 92010 31