Discrete Event Simulation - Net.in.tum.de
Chair for Network Architectures and Services – Prof. CarleDepartment of Computer ScienceTU MünchenDiscrete Event SimulationIN2045Chapter 1 – Simulation TypesSome of today‘sslides/figures areborrowed from:Richard Fujimoto,James Kurose,Keith W. Ross,Joachim WarschatOliver Rose, AverillLaw, David Kelton,Manfred JobmannDr. Alexander KleinStephan GüntherProf. Dr.-Ing. Georg CarleChair for Network Architectures and ServicesDepartment of Computer ScienceTechnische Universität Münchenhttp://www.net.in.tum.de
Simulation FundamentalsA computer simulation is a computer program that models the behaviourof a physical system over time. Program variables (state variables) represent the current state of thephysical system. Simulation program modifies state variables to model the evolution of the physical system over time and/or to incrementally enhance the level of detail of the physicalsystem‘s stateNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20122
Model taxonomy Static vs. dynamic Static: Simulate state at one point in time / without time Dynamic: State changes over time (focus of lecture!) Deterministic vs. stochastic Deterministic: The same input always effects the same output Stochastic: Under same conditions, same input may yield different outputs Usual reason: Environment modeled as pseudo-random inputContinuous vs. discrete cf. next slides Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20123
Continuous vs. discrete simulationContinuous valuesDiscrete valuesNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20124
Simulation Taxonomy inuousmodelstimesteppedContinuous time simulation State changes occur continuously across time Typically, behavior described by differential equations Example: Flight simulator (time and space are not quantised – atleast not at macroscopic dimensions )Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20125
Simulation Taxonomy inuousmodelstimesteppedDiscrete time simulation [zeitdiskrete Simulation]: State changes only occur at discrete time instants Example: Simulating packets in a computer network Time stepped: time advances by fixed time incrementsEvent stepped: time advances occur with irregular increments,i.e., to the next point ―when something happens‖(cf. next slide)Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20126
Discrete vs. continuousstate variablestate variableGoal: compute state of system over simulation timesimulation timediscreteNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/2012simulation timecontinuous7
Time-stepped vs. event-stepped simulationstate variablestate variableGoal: compute state of system over simulation timesimulation timeTime-stepped executionNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/2012simulation timeEvent-driven execution8
Discrete Event orientedEvent scheduling approach: Event-driven: An event represents an action which might affect the system state.State of the simulation can only change at the time an event is processed.Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20129
Discrete Event Simulation A Discrete Event Simulation (DES) is the reproduction of the behaviourof a system over time by means of a model where the state variables of the models changeimmediately at discrete points in time. These points in time are the ones at which an event occurs.Remark: There are (pseudo-)events that do not lead to changes in thestate variables of the model, e.g.: Data collection for statistics / writing to a log file End of simulation Manual garbage collectionNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201210
Discrete Event Simulation – Waiting SystemsWhat 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,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201211
Discrete Event Simulation Example:Computer networksRouterSimulationNotebookrunning a videoapplication16k DSLData rate [16Mbps]Fiber connection200 MbpsInternetIEEE 802.11nVariable data rate [40-100Mbps]Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/2012Wireless LanRouter withDSL ModemIP/TVBroadcastServer12
Discrete Event Simulation – Queuing ExampleWaiting Queue Theoryarrivalprocess buffer, queueserviceprocessExample:Router Data packets arrive at the router via its wireless interface A packet is forwarded immediately via the DSL interface if the buffer isempty and no packet is currently transmitted Otherwise the packet is stored in the buffer if the buffer is below itsmaximum capacity The service process simulates the time that is required by the router towrite a packet on the DSL interfaceNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201213
Discrete Event Simulation – Queuing ExampleWaiting Queue Theoryarrivalprocess buffer, queueserviceprocessEntity/Packet flow:0PacketarrivesEntity beginsserviceEvent„Event―Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/2012Entity completesserviceEventtime14
Discrete Event Simulation – Queuing Example State variables: Fill state of the queue (discrete) between [0 ; S]with S being the maximum queue capacity State of the service process (discrete) Idle (0) Busy (1) arrivalprocessbuffer, queueserviceprocessRouter / SystemEvents: Packet arrival:A new packet arrives at the routerProcess:- Increase queue by one if service process is busy and queuesize is below maximum capacity Service completion:Service process has transmitted a packetNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201215
Discrete Event Simulation – Queuing Example Events:arrivalprocessbuffer, queueserviceprocess Packet arrival:A new packet arrives at the routerRouter / SystemProcess: Increase queue by one if service process is busy and queue sizeis below maximum capacity . If queue size is at its maximum capacity drop the packet. If service process is idle, set service process to busy state andschedule the next service completion event. Service completion:Service process has transmitted a packetProcess: If queue size is equal to zero, set service process to idle. If queue size is greater than zero, reduce the queue size by oneand schedule the next service completion event.Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201216
Discrete Event Simulation System characteristic: Fill state of the queue at time is given by X(t) The fill state of the queue can only change when an event occursX(t)S21125Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201210time17
Discrete Event Simulation Arrival Events:timeInter-arrivaltime (IAT)X(t)S211 2510timeInter-arrival time: Time between consecutive arrival eventsNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201218
Discrete Event Simulation Service completion events:X(t)S2115timeService completiontime (SCT) Service completion time:Time between consecutive service completion events.Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/2012time19
Discrete Event Simulation Event queue:X(t)S2115timetimeEvent queue is a dynamic list of events which is executed in sequential order.Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201220
Discrete Event Simulation Event queue:X(t)Wn21Bn1253.4t100.61.71.60.7 0.71.3narrivalsservice time1.71.03.34.00.7eventqueueNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201221
What’s inside a DES? (1/2: data) Simulated time: internal (to simulation program) variable that keepstrack of simulated time May progress in huge jumps (e.g., 1ms, then 20s, then 2ms, ) Not related to real time or CPU time in any way! System state: variables maintained by simulation program definesystem state, e.g.: number of packets in queue, current routing table ofa router, TCP timeout timers, Events: points in time when system may changes state Each event has an associate event time e.g., arrival of packet at a router, departure from the router precisely at these points in time, the simulation must take action (i.e.,change state and maybe come up with new future events) Model for time between events (probabilistic) caused by externalenvironment Event queue: dynamic list of events ( later slides)Statistical counters: used for observing the systemNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201223
What’s inside a DES? (2/2: program code) Timing routine: determines the next event and moves the simulation clock to the next event time Event routine: ―process the event‖, i.e., change the system state when anevent happens One subroutine per event type [P]RNG library routines: generate random numbersReport generators: compute performance parameters from statisticalcounters and generate a report. Runs at simulation end, at interestingevents, and/or or at specific pseudo-eventsMain program:while(simulation time end time){next event getNextEvent();next event.process();}Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201224
Pure event-oriented simulation is challenging One event can be a composed of acomplicated sequence of many actions: Web client sends HTTP requestHTTP request encapsulated into TCP frameTCP frame encapsulated into IP frameIP frame encapsulated into Ethernet framePut frame into queue of outgoing interfaceEven more complicated: Many complicated events(receiving request, sending back answer etc.)that are correlatedNetwork– Security,IN2045Discrete EventWS nt!(if we neglectsimulatingCPU time)32
Pure event oriented simulation is challenging One event can be a composed of acomplicated sequence of many actions: Web client sends HTTP requestHTTP request encapsulated into TCP frameTCP frame encapsulated into IP frameIP frame encapsulated into Ethernet framePut frame into queue of outgoing interfaceonesingleevent!(if we neglectsimulatingCPU time)Even more complicated: Many complicated events(receiving request, sending back answer etc.)that are correlatedProblem #1: Event-based programming doesn‘t look like normalprogramming at all!Problem #2: Prone to create spaghetti code!?Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201233
Solution: Process-oriented simulation What is a process? ( in the context of simulation) A body of code Variables allocated to that code Current point of execution in the code Not much different from a process in an OS How is it used? A process groups sets of related events together A process can execute and then be suspended.Important use cases: Simulation time elapses (e.g., simulate propagation delays) Interactions with other processes that temporarily block(e.g., blocking system calls) Internally, all this is translated into series of events without the programmernoticing itNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201234
Applying processesTwo alternative approaches:One resource one process Examples: One process foreach simulated : CPU Hard disk Network interface User Jobs using these services (e.g.,simulated WWW clientprogram) are data structures are passed from process toprocessOne job one process Examples: One process foreach simulated : WWW client program WWW server program Peer-to-peer client program Resources used by these jobs(e.g., simulated networkinterface) are global variables / datastructuresWhich approach is better? — It depends!Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201235
Simulation neventorientedtimesteppedprocessorientedNetwork– Security,IN2045Discrete EventWS delsProcess orientation: Focus: on simulated objects For more complex systems Programming closer to realworld programming Example: Write into socket;operation blocks Usually own simulationlanguage/software (e.g. OPNET) Internally translated intosequence of events36
Overview: Event orientation process orientation Event-oriented simulation: Modeler considers one event after the otherSimulation clock is stopped during event executionRather straightforward to implementOften used in non-commercial simulatorsProcess-oriented simulation: A process is a ordered series of events related to a certain model object(e.g., customer, job, product) Simulation clock moves on during process execution Commercial simulators use this approach because of simplified modeldescriptions A process may have several entry points In the simulator kernel, the processes are split into events (may be tricky toimplement)Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201237
Event list for processes: Usually simplerEvent-oriented simulationProcess-oriented simulation(still event-driven!)TimeEventTimeEvent10.0Take packet P1 out ofsender queue and put onlink10.0Run queuingprocess20.0Take packet P2 out ofsender queue and put onlink20.0Run queuingprocess27.3Deliver packet P1 from linkto receiver27.3Run receiverprocess30.0Take packet P3 out ofsender queue and put onlink30.0Run queuingprocess37.3Deliver packet P2 from linkto receiver37.3Run receiverprocessNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201238
Problem: Simulating blocking behaviour Normal programming:result read(tcp socket);// Blocked until tcp socket has received some data.use(result); But how should we simulate the blocking character of read() in aprocess-oriented simulator!? Blocking call: consume simulation time Other events will take place during the time that read() is blocked In particular: The event that a new packet has arrived, which in turntriggers the return of the read() call! Obviously, these events must not be blockedResuming from returning read() is a new eventNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201239
Other Solutions Solution #1: Use threads (?) One thread for process that calls read()One thread for process that moves packet in networkOne thread for Problem: Integration with event concept is difficultProblem: Synchronisation of threads All threads need to access the event list Events must be ordered by time Once some thread has processed an event at time t, then no otherthread must generate any event at a time t‘ t [N.B.: Parallel simulation on multiple CPUs is a complex task.]Solution #2a: Using continuationsSolution #2b: Using coroutinesNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201240
Continuations Normal programming:result f(parameters);use(result);Continuation-passing style:f(parameters, &callback);// &callback means in C-like syntax:// pointer or reference to function callbackdo other stuff( );callback(result) {// This is just a normal function.use(result);}Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201241
What is it good for? Normal programming:result f(parameters);// We‘re blocked until f( ) returnsuse(result);Continuation-passing style:f(parameters, &callback); //& : pointer// Will return quickly without blocking.// Note that f() does not return any results.maybe do other stuff( );f(p, cb) {/* Do some calculations; set internal state flags so thatcallback(.) is invoked as soon as the state of thecurrent process has been changed by one or moreevents such that we simulate that “f() returns” */}callback(result) {// A normal function; called to simulate that “f() returns”use(result);}Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201242
Simulating blocking calls with continuations Normal programming:result read(tcp socket);// Blocked until tcp socket has received some data.answer parse(result);write(tcp socket, answer); Simulator:simulate read(tcp socket, &cont);cont(result) {answer parse(result);simulate write(tcp socket, answer, &cont2);}Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201243
What happens inside of simulate read()? simulate read(tcp socket, &cont); Does simulate read() schedule a new event for wakeupwith a pointer to cont()? No, not quite! When does the data arrive?—We don‘t know yet! Solution: During the processing of this event, simulate read() passes control to other entities (processes); e.g.,reader IP stack network card physical link Each of these entities sets state variables which indicate that new dataarriving should wake them up. At some point, the event ‗packet received‘ is processed. The packet getshandled by the various entities (physical link network card IP stack ), and at some point, cont gets called, and ―read() returns‖Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201244
Problem: Source code difficult to readNormal source code:result read(socket);answer parse(result);success write(socket, answer);if (success WRITE OK) {blah;} else if (success WRITE FAIL) {blubb;}Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201245
Coroutines: Generalisation of subroutines Subroutine Stateless: local variables alwaysExecution always starts at beginningExecution always ends at last line or return statementReturning from subroutine jump back to calling program contextCo-routine Can keep state Execution resumes from the place where you left(or at the beginning when called for the 1st time) Execution is suspended at yield statement ( depends onprogramming language, of course!) and will resume thereafter Depending on definition/language, yield can specify a target tojump to (i.e., not necessarily the caller of the coroutine!) Multiple co-routines calling and yielding to each other cooperative multitaskingNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201246
Simula—A forgotten curiosity Developed in the 1960s (standards: Simula-I, S.-67, S.-87)by Ole-Johan Dahl and Kristen Nygaard (both †2002) Superset of Algol-60Purpose: Process-oriented discrete-event simulationAn underrated pioneering language: The 1st language that introduced coroutines The 1st language that introduced object-oriented programming! Classes Objects Virtual method calls (dynamic binding) Inheritance Some Simula keywords still used today: class, new, this Garbage collection (idea taken from Lisp, 1950s)Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201247
Summary of Introduction (Chapters 0 and 1) System, model, observer, simulationWhy and why not to simulateTypical workflow / important aspects in a simulation study Verify that your model makes sense Verify the output of your simulation is not just random noise Remember: trash in trash out! Simulation taxonomy Continuous discrete Time-based event-based Event-driven process-driven What is inside a discrete event simulator Event list, sorted by timeSimulation time counterState variablesEvent processing: changes state, but consumes no timeNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201248
Chair for Network Architectures and Services – Prof. CarleDepartment of Computer ScienceTU MünchenDiscrete Event SimulationIN2045Chapter 1.5 – How to build a DESDr. Alexander KleinStephan GüntherProf. Dr.-Ing. Georg CarleSome of today‘sslides/figures areadopted fromLaw&KeltonChair for Network Architectures and ServicesDepartment of Computer ScienceTechnische Universität Münchenhttp://www.net.in.tum.de
Discrete Event Simulation – Queuing Systems System Characteristics:arrivalprocessbuffer, queueserviceprocessPopulation Finite / Infinite Entity size Deadline Single queue / Multiple queues Finite / Infinite capacity Queuing strategy (FIFO, LIFO ) Single processor /multiple processor State-(in)dependent VacationPerformance Characteristics: Average/maximum customer waiting timeAverage/maximum processing time of a customerAverage/maximum retention time of a customerAverage/maximum number of customers in the queueCustomer blocking probabilityUtilization of the system / individual processing unitsNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201250
Discrete Event Simulation – Waiting Queue ExampleQueuing 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 customersQueue lengthWaiting time in the queueLoad of service unit (how often idle, how often working)Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201251
Discrete Event Simulation – Waiting Queue azy) cashierManufacturingCustomer mputerJobCPUComputer networkData packetRadio channelCacheContentStorageNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201252
Discrete Event SimulationWaiting Queue Theoryarrivalprocessrate λ3.40.61.71.60.70.71.3buffer, queuerandom numbersinter-arrival timesNetwork– Security,IN2045Discrete EventWS ssrate μ1.71.03.34.00.7.service times53
Discrete Event Simulation – Waiting Queue ExampleCustomer ArrivalFlowchartArrival ProcessSchedule thenext arrival eventYesIs a serviceunit idle?Tally a delay of 0for this customerNoFind the shortestqueueMark service unitas busyPlace Customer inthe shortest queueSchedule adeparture eventReturnNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201254
Discrete Event Simulation – Waiting Queue ExampleFlowchartDeparture ProcessDeparture EventYesIs thequeueempty?NoRemove the firstcustomer from thequeueSet the state ofservice unit to idleCompute thecustomers delaySchedule a departureevent for thiscustomerReturnNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201255
Discussion How to build a Discrete Event Simulator? What are the necessary modules? What are the interesting performance parameters?Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201256
Waiting Queue Simulation – Step by StepStep by StepNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201257
Waiting Queue Simulation – Step by Step Events: Customer Arrival Events Service Completion Events Simulation Termination Event System variables: Q(t) – number of waiting customers at time t B(t) – number of busy servers at time t Performance parameters: Average customer waiting time Utilization of the system Customer blocking probabilityNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/2012We will need to collectsome data to providethese statistics58
Waiting Queue Simulation – Step by Step Waiting Queue Simulation: System with 2 serving units/processorsSingle queue with a capacity of 3 customersSimulation duration of 30 simulation ticksThe first customer is inserted at time 0System Characteristics:arrivalprocess General independentinter-arrival timesbuffer, queue Finite capacity – 3 Customers Queuing strategy - FIFONetwork– Security,IN2045Discrete EventWS ss Multi-processor – 2 processors General independentservice completion times59
Waiting Queue Simulation – Step by StepSimulation timeCurrent EventProcess RoutineNumber of busy serversInitializationnoneInsert first customer arrival;Insert simulation termination;B(t) 0Event queueTime of arrival of customers in queue[0;CA], [30;ST]Q(t) 0Number of arrived customers 0Number of served customers 0Q(t)B(t)Number of waiting customersNumber of blocked customers 0 Q(t ) 0 B(t ) 0tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival timeService completion timeNetwork– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201260
Waiting Queue Simulation – Step by StepSimulation timeCurrent Event0Customer Arrival[0;CA]Event queueProcess RoutineSchedule next arrival- IAT 2.0;Increase B(t); Schedule servicecompletion- SCT 5.0Time of arrival of customers in queue[2;CA], [5;SC], [30;ST]B(t)B(t) 1Number of waiting customersQ(t) 0Number of arrived customers 1Number of served customers 0Q(t)Number of busy serversNumber of blocked customers 0 Q(t ) 0 B(t ) 0tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival time2.0Service completion time5.0Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201261
Waiting Queue Simulation – Step by StepSimulation timeCurrent Event2Customer Arrival[2;CA]Event queueProcess RoutineSchedule next arrival- IAT 1.0;Increase B(t); Schedule servicecompletion- SCT 5.0Time of arrival of customers in queue[3;CA], [5;SC], [7;SC], [30;ST]Number of arrived customers 2Number of served customers 0Q(t)B(t)Number of busy serversB(t) 2Number of waiting customersQ(t) 0Number of blocked customers 0 Q(t ) 0 B(t ) 2tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival time2.01.0Service completion time5.05.0Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201262
Waiting Queue Simulation – Step by StepSimulation timeCurrent Event3Customer Arrival[3;CA]Process RoutineSchedule next arrival- IAT 1.0;All servers busy- Insertcustomer in queueNumber of busy serversB(t) 2Event queueTime of arrival of customers in queueNumber of waiting customers[4;CA], [5;SC], [7;SC], [30;ST][3;CA]Q(t) 1Number of arrived customers 3Number of served customers 0Number of blocked customers 0Q(t)B(t) Q(t ) 0 B(t ) 4tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival time2.01.0Service completion time5.05.01.0Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/201263
Waiting Queue Simulation – Step by StepSimulation timeCurrent Event4Customer Arrival[4;CA]Process RoutineSchedule next arrival- IAT 2.0;All servers busy- Insertcustomer in queueNumber of busy serversB(t) 2Event queueTime of arrival of customers in queueNumber of waiting customers[5;SC], [6;CA], [7;SC], [30;ST][3;CA], [4;CA]Q(t) 2Number of arrived customers 4Number of served customers 0Number of blocked customers 0Q(t)B(t) Q(t ) 1 B(t ) 6tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival time2.01.0Service completion time5.05.01.0Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20122.064
Waiting Queue Simulation – Step by StepSimulation timeCurrent Event5Service Completion[5;SC]Process RoutineRemove customer from queue;Schedule service completion- SCT 6.0;Number of busy serversB(t) 2Event queueTime of arrival of customers in queueNumber of waiting customers[6;CA], [7;SC], [11;SC], [30;ST][4;CA]Q(t) 1Number of arrived customers 4Number of served customers 1Number of blocked customers 0Q(t)B(t) Q(t ) 3 B(t ) 8tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival time2.01.01.0Service completion time5.05.06.0Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20122.065
Waiting Queue Simulation – Step by StepSimulation timeCurrent Event6Customer Arrival[6;CA]Process RoutineSchedule next arrival- IAT 1.0;All servers busy- Insertcustomer in queueNumber of busy serversB(t) 2Event queueTime of arrival of customers in queueNumber of waiting customers[7;SC], [7;CA], [11;SC], [30;ST][4;CA], [6;CA]Q(t) 2Number of arrived customers 5Number of served customers 1Number of blocked customers 0Q(t)B(t) Q(t ) 4 B(t ) 10tt3210 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t0 12 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30t21Inter-arrival time2.01.01.0Service completion time5.05.06.0Network– Security,IN2045Discrete EventWS 2008/09,Simulation,ChapterWS92011/20122.01.066
Waiting Queue Simulation – Step by StepSimulation timeCurrent EventProcess Routine7Customer Arrival /Service CompletionNumber of busy serversB(t) 2Event queueTime of arrival of customers in queueNumber of waiting customers[7;SC], [7;CA], [11;SC], [30;ST][4;CA], [6;CA]Q(t) 2Number of arrived customers XNumber of served customers XNumber of blocked custom
Network Security, WS 2008/09, Chapter 9IN2045 – Discrete Event Simulation, WS 2011/2012 10 Discrete Event Simulation A Discrete Event Simulation (DES) is the reproduction of the behaviour of a system over time by means of a model where the state variables of the models change
Event 406 - Windows Server 2019 58 Event 410 58 Event 411 59 Event 412 60 Event 413 60 Event 418 60 Event 420 61 Event 424 61 Event 431 61 Event 512 62 Event 513 62 Event 515 63 Event 516 63 Event 1102 64 Event 1200 64 Event 1201 64 Event 1202 64 Event 1203 64 Event 1204 64
2. Benefits of Discrete Event Simulation Discrete Event Simulation has evolved as a powerful decision making tool after the appearance of fast and inexpensive computing capacity. (Upadhyay et al., 2015) Discrete event simulation enables the study of systems which are discrete, dynamic and stoc
Discrete Event Simulation (DES) 9 Tecniche di programmazione A.A. 2019/2020 Discrete event simulation is dynamic and discrete It can be either deterministic or stochastic Changes in state of the model occur at discrete points in time The model maintains a list of events ("event list") At each step, the scheduled event with the lowest time gets
7 www.teknikindustri.org 2009 Discrete-change state variable. 2. Discrete Event Simulation 8 www.teknikindustri.org 2009. Kejadian (Event) . pada langkah i, untuk i 0 sampai jumlah discrete event Asumsikan simulasi mulai pada saat nol, t 0 16 www.teknikindustri.org 2009 0 t1: nilai simulation clock saat discrete eventpertama dalam
2.1 Discrete-Event Simulation To discuss the area of DES, we rst need to introduce the concept of a discrete-event system. According to Cassandras et al. [4], two characteristic properties describing a given system as a discrete-event system are; 1.The state space is a discrete set. 2.The state transition mechanisms are event-driven.
A discrete-event simulation is the modeling over time of a system all of whose state changes occur at discrete points in time those points when an event occurs. A discrete-event simulation (hereafter called a simulation) proceeds by producing a sequence of system snapshots (or system images) which represent t
simulation system state via direct computing, yet without loss of simulation accuracy. As the traditional discrete event network simulator (such as NS[4]) obtains all the changes of simulation system state via discrete events, this method can cut down the number of discrete events and reduce the simulation running time compared with the
Have a brain storming session where they generate 10-15 themes. (Be patient, they'll get there eventually.) After they generate the list, allow people to talk in behalf of specific ideas Sometimes they may combine items Give everyone 3 votes and go through the list voting. If there is a clear winner then proceed. Otherwise repeat the process, but with one vote. Post the chosen theme .
