Department Of Electronics, Information And Bioengineering .
Politecnico di MilanoDepartment of Electronics, Information andBioengineering (DEIB)Introduction to Simulation ofCommunication Networks5hr-Seminar in the course«Network Design and Planning»ECS289iMassimo Tornatore(Courtesy of Prof. Fabio Martignon)1
Summary What is simulation? Discrete-event simulation Systems, models and variablesGeneration of pseudo-random numbers– Synthesis of random variablesStatistical Analysis– Statistical confidence of simulative resultsNext Lecture: example of C/C simulator2Introduction to Simulation
Introduction to simulation Why, as we are going to study queuing theory, do we also have to usethe simulation?Isn’t queuing theory sufficient to determine the performance oftelecommunications networks?No In fact: Queuing theory can describe and give results for a small ensembleof very simplified models and systems How can we study a complex system?––––Queues with not Poisson arrivals: bursty arrivals, arrive in groups,back-off rejected requests, etc.Queues with complex mechanisms for managing queues (PQ, WFQ,RED, ecc.)Queue networks that do not meet Jackson’s assumptions (steady state)Analysis of the transient behavior of queuing systems3Introduction to Simulation
Introduction to simulation In addition there are network systems that can not beeasily described by queuing models, e.g.:––––– Access Interface of wireless systems (LTE, WLAN, ecc.) witherrors due to channel characteristics and interferenceDynamic routing mechanisms for IP or optical networksCongestion control mechanisms (e.g., TCP)Admission control mechanisms (e.g., CSMA-CA)Retransmission complex protocols such as, for example,protocols with piggybacking, selective reject, ecc.When you start from real systems is quite difficult tofind a model solvable only with the queueing theory4Introduction to Simulation
Introduction to simulation What is SIMULATION: Simulation seeks to build an experimental device,that behaves like the real system under study forsome important aspectsExamples:–––scale models of airplanes, cars or trains, used inwind tunnelsSimCity, Railroad Tycoon, and other videogamesbased on reproducing how a system worksflight simulators for pilot training5Introduction to Simulation
Introduction to simulation Other:–––––predicting the development of ecosystems afterartificial alterationverification of stock-exchange tacticsweather forecastsverification of battle tacticsetc.6Introduction to Simulation
Models and Systems System– is a very general concept that can be definedinformally as a collection of parts, called components,that interact with each other Model– is a system representation. This representation cantake many forms (e.g., that of physical replication ),but here we focus on the representation by means ofmathematical or software/simulative models7F. Martignon: Introduction to Simulation
State of a system and level of abstraction State– the system state describes the current state of all itscomponents– to the system state it corresponds a state of the system modeland the model represents the evolution of the systemthrough the history of changes in state The level of abstraction of a model indicates thatsome features of the system state are omitted– The level of abstraction is tightly related to the measuresthat model is aimed at– The best model is simply the easiest model by which youget the measures (performance) you want8M. Tornatore: Introduction to Simulation
Models and Systems Variables–the activities of the model are described asrelationships or functions between variables– a mathematical model is described using variables.Same for a simulative model!–State variables– state variables define the state of the model– their evolution defines the evolution of the system–Input variables– input variables describe external stimula on the systemunder consideration9Introduction to Simulation
Models and Systems–Output variables– are a function of state and input variables– they represent, therefore, the probes inserted in themodel for the measure– the solution of the model is to obtain the values ofoutput variables Solution– the analytical solution of a model involves, e.g.,mathematical methods for solving equations thatdescribe relationships between variables– the simulated solution of a model reproduces theevolution of the system by evolving the state variablesand directly measuring the output variables10Introduction to Simulation
Simulation vs. Theoretical Models Simulation Properties:––––simulation is “descriptive” and not “prescriptive”simulation provides information on the behavior ofthe system, given the parametersthe simulation DOES NOT tell you how to set theparameters for best system behavior, or to test thelimits of the systemExample: M/M/11D – I see immediately the capacity limit– If I simulate the system, I have to run lot of simulations,increasing the load, till I find out which is the limit11Introduction to Simulation
Deterministic vs. Stochastic Simulations There are many ways to classify simulations, e.g.:–– Deterministic vs. StochasticContinuous time vs. Discrete timeDeterministic vs. Stochastic simulations:– deterministic simulations are completely defined bythe model, and their evolution is deterministicallyassociated to the input parameters;– stochastic simulations are based on models thatinclude random variables or processes and so theyrequire the generation of random variables; theevolution of the model depends on the inputparameters and the generation of random variables12Introduction to Simulation
Deterministic vs. Stochastic Simulations (2) Examples– Deterministic simulation:– Consider the motion of the billiard balls on the pooltable. Given the position of the balls, direction andstrength of impact of the cue, we can simulate theoutcome of the shot (without explicitly solving ananalytical model)–Stochastic simulation:– Consider a GSM cell with N-channel (or a phoneconcentrator) to which connection requests arriveaccording to a Poisson process with rate – We want to determine the probability of rejection,knowing that with probability p rejected calls retry tolog on after a time equal to T13Introduction to Simulation
Static and Dynamic Simulations (1) Stochastic simulations can be classified asstatic or dynamicStatic Simulations––––also called Monte Carlo simulationsthe time variable plays no rolethe basic objective is to determine some statisticalcharacteristics of one or more of randomvariablesin fact, the Monte Carlo simulations tipicallyevaluates statistical measures throughindependently repeated experiments14Introduction to Simulation
Static and Dynamic Simulations (2) Dynamic simulations–––also called temporal simulationstime becomes the main variable to be tied to theevolution of the modelthe purpose is to collect statistics for randomprocesses observed at different time16Introduction to Simulation
Static and Dynamic Simulations (3) Simple Monte Carlo example (it can besolved analytically):––––Consider a slotted random multiple access systemwith 10 users of type A, 10 users of type B and 13users of type CUsers A, B and C have a packet ready fortransmission in each slot with probability 3p, 2pand p, respectivelyFind the throughput of the system given p.Determine the value of p that maximizes thethroughput17Introduction to Simulation
Static and Dynamic Simulations (4) Another (more complex) Monte Carlosimulation example–––Consider a cellular packet system in which apacket is transmitted by a mobile user placed inrandom position in each time interval withprobability G.The attenuation of the channel is a function ofdistance and a random factor (fading) andtransmitted power is fixed. The packet isreceived correctly only if the signal/interferenceis greater than 6 dB.Determine the probability of a successfultransmission. Determine the value of G thatmaximizes the throughput.Introduction to Simulation18
Static and Dynamic Simulations (5) Example of dynamic simulation (1):–Consider a queue system with a server and aqueue of up to K packets. Interarrival times havea uniform random distribution between time aand b and each arrival is composed of a numberof users x, where x is a random variable Binomialwith reason p. Determine the probability ofrejection and the average delay to the crossing.19Introduction to Simulation
Static and Dynamic Simulations (6) Example of dynamic simulation (2):–Consider a slotted polling system with N queues.Packet length x is randomly distributedaccording to a cartain known pdf. Interarrivaltime are distributed according to a Poissonprocess with rate . Assuming that:– The server adopts a policy of priority queuing (i.e., itcontinues to serve a queue until it is empty)– The server chooses the next queue according to a«longest-queue» policy–Determine the average transfer time through thesystem20Introduction to Simulation
Classification of Dynamic Simulation Discrete-event dynamic simulation The system state changes in response to«events»– Continuous-time dynamic simulation The system state evolves in response to thechange of continuous-time variable– Network simulation (OPNET, NS-2)Weather ForecastNB: simulated time vs simulation time!21Introduction to Simulation
Simulation of discrete events Simulation of discrete events is fundamental importance fortelecommunications networksIn discrete event simulation the state variables change valueonly at discrete instants of timeThe change of the system state is called event and ischaracterized by an instant of occurrence– An event has no durationAfter the event occurs, in the system an activity starts thatpersists for some time––An activity is usually characterized by a start event and an end eventFor example, the beginning and the end of the transmission of apacket are events, while the transmission itself is an activity22Introduction to Simulation
Simulation of discrete events In discrete event simulation we should:––––––define the types of events that can occurdefine the changes in the system state associated to eacheventdefine a time variability and an ordering of events in acalendar based on the instant of event occurrencedefine an initial statescroll through the calendar and, each time an eventoccurs, make changes to state variables according to thateventmeasure on the output variables23Introduction to Simulation
Example: Simulation of a queue system Model:––Queue system with a server and an infinite queueInput variables:– interarrival times of requests (packets)– service times of requests–State variables:– number of requests in the system–Initial state– e.g., no user in the system–Output variables:– average time spent by a packet in the system24Introduction to Simulation
Example: Simulation of a queue system Events–1. first arrival– Set service start– Set service end–-I can not read the calendar .Initialization (“init”)2. from the second arrival on– In this case we should act differently on the basis of the state:– Arrival» in an empty system immediate service start and scheduleservice end» in a not-empty system add a packet in the queue (serviceend? We can’t add service end!)– End (? See next slides)» with empty queue (hold till next event)» with non-empty queue (set new service start and service end)25Introduction to Simulation
Example: simulation of a queue system Filling the calendar of events– PROBLEM: it is not possible to place the endservice events of each queued requests as we donot know the service duration of requests queuedin front of them– SOLUTION: the calendar can be filled with newevents while other events are pending– Example: a new packet will be queued even if theservice end events of the packets before it in the queueare not known.26Introduction to Simulation
Example: a queue system simulation In summary: whenwe have an «arrival» event, we increase thenumber of users, then if the system is empty, a new end event is inserted in thecalendar at a time equal to «CLOCK service time» if the system is busy, add a packet in the queue when an service-end event is reached, wedecrease the number of users, then If the queue is empty, no action if the queue is not empty, a new end event is inserted inthe calendar at a time equal to the value of «CLOCK service time»27Introduction to Simulation
Example: a queue system simulation Measurement of output variables1. Transfer time– User arrival: storage time of arrival– End of service: calculation of the service time(CLOCK - t arrival)2. Average users in the queue– Weigthed average of the users in the systems duringeach activity interval («time slices»)28Introduction to Simulation
Simulation of discrete events Note: the correct inclusion of a new event inthe calendar is a critical operation if thecalendar has many events–Efficient techniques must be used for inclusion ofan element in an ordered list29Introduction to Simulation
The variable Clock Sliding of the «CLOCK» variable–«clock driven» simulations– the CLOCK variable is always increased of a fixed step» E.g., Slotted systems–«event driven» simulations– the CLOCK variable is increased according to the time intervalbetween the occurrence of an event and the occurence of thefollowing event–Notes:– from a computational-time point of view it may be convenient toadopt a method rather than the other depending on the model30Introduction to Simulation
Some final considerations Considering the power/efficiency of modern codinglanguages and computing systems, simulation is today apowerful tool of analysis to address complex problems But simulation is also a tool that should be used with carefor the following reasons:–––is not easy to validate the obtained resultsthe computational time can easily get very highis not easy to understand how different parameters affect theresult31Introduction to Simulation
Simulation of discrete eventsThe simulation of a stochastic model involves theutilization of random input variables We need statistical distribution of input variables So, for computer simulation, pseudo-randomnumber generation and synthesis of statisticalvariables is needed (the next topic .)–Example: traffic entering a queue system described bythe process of arrivals and the process of service times32Introduction to Simulation
Summary What is simulation? Systems, models and variablesDiscrete-event simulation Generation of pseudo-random numbers– Synthesis of random variablesStatistical Analysis– Statistical confidence of simulative results33Introduction to Simulation
The Role of Random numbers When the model to be analyzed via simulation isstochastic, two important problems arise: the generation of pseudo-random numbers tobe use for the generation of input variables the statistical analysis of the results obtainedthrough the output variables34Introduction to Simulation
What I assume you know Basic of statistics Average (mean), variance Concept of random variable Probability density function (pdf) f(x) Cumulative distribution function (CDF) F(x) Theorem of central limit Gaussian (normal), t-student distributions35M. Tornatore: Introduction to Simulation
Generation of pseudo-random numbers Rigorously speaking, numbers generated by acomputer cannot be random due todeterministic nature of a computerWe can however generate pseudo-randomsequences that meet a series of statistical testsof randomness36Introduction to Simulation
Generation of pseudo-random numbers The problem of generating pseudo-randomnumbers can be logically divided in two parts: generation of sequences of random numbersuniformly distributed between 0 and 1 generation of sequences of random numbersdistributed in an arbitrary mode–Poisson, Bernoulli, Weibull, Exponential, etc .37Introduction to Simulation
Generation of pseudo-random numbers The pseudo-random sequences are obtainedthrough the implementation of recursive formulas Some history The first method to generate random sequenceswas Von Neumann's «square center» method The next number is obtained by squaring theprevious number and taking the central number38Introduction to Simulation
Von Neumann’s examplex0 3456that squared provides(x0) 2 11943936sox1 9439Sequence of random number obtainedThis method was abandoned: difficult to analyze,relatively slow and statistically unsatisfactory39Introduction to Simulation
Generation of pseudo-random numbers Factors determining the quality of a method:1)numbers must be statistically independent2)we must be able to re-produce the sequence3)numbers must be uniformly distributed (i.e., theymust have the same probability to occur)4)sequence must be of an arbitrary length5)the method should be quickly executable by thecomputer and must consume small amount ofmemory40Introduction to Simulation
Generation of pseudo-random numbers Let’s recall some basic math operators Module:x mod y x y x / y – Property of module:Congruency:x mod y0 1yx y (mod z )x mod z y mod z41Introduction to Simulation
Generation of pseudo-random numbers Linear Congruency Method (Lehmer 1948){X n }n N X 0, X1, X 2,., X i ,. That:X n 1 aX n c (mod m) X0initial value or seeda multiplierc increasem moduleNB: The method is called:- multiplicative if c 0- mixed if c 042Introduction to Simulation
Generation of pseudo-random numbers Example: X0 a c 7 m 10 {Xn}n N 7, 6, 9, 0,7, 6, 9,.Note: 0 Xi m, for all i43Introduction to Simulation
Generation of pseudo-random numbers Drawbacks of linear congruency As soon as Xp X0, the sequence is repeatedperiodically; p is the period of the sequence Being p m, the period will be less than or equalto mNote(1): if p m then all numbers between 0 andm-1 are repeated once in the sequenceNote(2): to obtain a sequence in [0,1):{Rn }n NX 0 X1 X 2Xi , , ,., ,.m m mm44Introduction to Simulation
Generation of pseudo-random numbers We can relate directly Xn to X0 This emphasizes even more the deterministic nature of the sequence!X 1 (aX 0 c) mod mX 2 (aX 1 c) mod m (a 2 X 0 (1 a )c) mod m3a 13X 3 (a X 0 c) mod ma 1.na 1nX n (a X 0 c) mod ma 145Introduction to Simulation
Generation of pseudo-random numbers How to choose the multiplier a and increase c: 1.2.a and c strongly influence the period and thestatistical properties of the sequencethere are rules for choosing a and c that will returnperiods p m (full period)Criteria to ensure optimality:The parameters c and m must be co-prime, i.e.:MCD(c,m) 1Every prime divisor of m must divide (a-1)Ex: if m 10, its prime factors are 2 and 5. (a-1) must be a multiple of 2 and 53.If m is a multiple of 4, also (a-1) must be46Introduction to Simulation
Generation of pseudo-random numbers It is not easy to find values that satisfy (1), (2), (3) Ex: m 10, a 21, c 3 (Xn 3,6,9,2,5,8,1,4,7,0,.) Some researchers have therefore identified thefollowing values in accordance with these criteria: KNUTHm 231; a int (p * 108) ; c 453806245GOODMAN/MILLERm 231 -1; a 75 ; c 0GORDONm 231; a 513 ; c 0LEORMONT/LEWISm 231; a 216 3 ; c 047Introduction to Simulation
Generation of pseudo-random numbers A simpler condition:– if the method is multiplicative (c 0) you can showthat if m 2b then the maximum period is p 2b-2 ifb 4Note: the equivalence of multiplicative andmixed approaches has been proven48Introduction to Simulation
Generation of pseudo-random numbers Notes on the choice of module m m influences the period because p m m also affects the computational speed:––––to calculate a module, we should generally perform aproduct, a sum and a divisionit is possible to do everything together if you chooseas module the maximum integer representable bythe computer plus onein this module the operation correspond to atruncationif b is the number of bits used by the computer, youwil
Introduction to Simulation 9 Models and Systems Variables – the activities of the model are described as relationships or functions between variables –a mathematical model is described using variables. Same for a simulative model! – State variables –state variables define the state of the model –their evolution defines the evolution of the system
LG Electronics V10 10 LG Electronics V20 10 LG Electronics V30 30 LG Electronics V40 ThinQ Dual SIM 80 LG Electronics V50 ThinQ 160 LG Electronics VELVET 4G 100 LG Electronics VELVET 5G 120 LG Electronics X Powe
Electronics Code A.2 Conceptualize, Analyze & Design A.2.1 Signal Processing System A.2.2 Analog and Digital Electronics System. A.2.3 Communication Systems A2.4 Electro-Acoustics System A.2.5 Broadcast System A 2.6 Instrument ation A.2.7 Control System. A 2.8 Industrial Electronics A.2.9 Power Electronics A.2.10 Electronics Devices and Systems .
1 Opto Electronics PG (Opto Electronics & Communication Systems) 2 Fibre Optics PG (Opto Electronics & Communication Systems) 3 Optical Communication Technology PG (Opto Electronics & Communication Systems) 4 Power Electronics B Tech Electrical & Electronics Engg. (CUSAT) 5 DC Machines and Transformers B Tech
Analogue Electronics: 24 hours of lectures and tutorials (12 weeks 2 hours/week) Assessment for analogue electronics: Mid-semester test in November, analogue electronics only, 1 hour, 8% of the final mark. Final examination in January, analogue & digital electronics, 2 hours, 50% of the final mark.
Accelerators and Electronics Many accelerators have aging infrastructures, including their electronics While this might be a problem on many other fronts, the older electronics are better suited to high radiation environments than modern electronics As many accelerators are modernizing their electronics or are significantly changing their infrastructures, facilities are finding .
Medical Electronics Lab This Lab facilitates two major skills development: 1. Basic Analog & Digital Electronics 2. Medical Electronics ( Application of electronics in biomedical ) For Basic Electronics skills development the Lab is equipped with Com3 Kits which have electronics trainer boards interfaced with software on PC. This
malle.krunks@ttu.ee, 372 620 3363 www.ttu.ee 2 Tallinn University of Technology, Thomas Johann Seebeck Department of Electronics, Faculty of Information technology Semiconductor electronics. Internet of electronics. Department of Electronics' area of expertise is high-level scientific and engineering activities
4. Basic Electronics(7 th Edition)-Malvino and Bates 5. Electronics Fundamentals and Applications-D. Chattopadhyay and P.G.Rakshit, 6. Electronics: Fundamentals of Analog circuits-Thomas L. Floyd, David Buchla, 7. Electronic Devices and Circuit Theory-Robert Boylestad, Louis Nashelsky 8. Basic Electronics-Debashis De 9. Basic Electronics .
