Network SimulationThe evaluation spectrumWhat is simulation?Why Simulation?Simulation: advantages/drawbacksProgramming a simulationDiscrete Event SimulationSimulation: exampleSlide 9Slide 10Gathering Performance StatisticsAnalyzing Output ResultsSlide 13Slide 14Transient BehaviorEffect of initial conditionsSlide 17Steady state behaviorSlide 19Slide 20Example: Random Waypoint ModelIssue with RWP Model: DecayConfidence IntervalsSlide 24Confidence Intervals: Central Limit ThmConfidence Intervals .. moreConfidence Intervals .. the recipeInterpretation of Confidence IntervalGenerating confidence intervals for steady state measuresIndependent replications0ther methodsSlide 32Comparing two different systemsns-2, the network simulator“ns” componentsNetwork SimulationMotivation: learn fundamentals of evaluating network performance via simulationOverview:fundamentals of discrete event simulationanalyzing simulation outputsns-2 simulationThe evaluation spectrumnumericalmodelssimulationemulationprototypeoperational systemWhat is simulation?system under study(has deterministic rules governing its behavior)exogenous inputsto system(the environment)system boundaryobserver“real” lifecomputer programsimulates deterministic rules governing behaviorpseudo random inputsto system(models environment)program boundaryobserver“simulated” lifeWhy Simulation?goal: study system performance, operationreal-system not available, is complex/costly or dangerous (eg: space simulations, flight simulations)quickly evaluate design alternatives (eg: different system configurations)evaluate complex functions for which closed form formulas or numerical techniques not availableSimulation: advantages/drawbacksadvantages:drawbacks/dangers:Programming a simulationWhat ‘s in a simulation program?simulated time: internal (to simulation program) variable that keeps track of simulated timesystem “state”: variables maintained by simulation program define system “state”e.g., may track number (possibly order) of packets in queue, current value of retransmission timerevents: points in time when system changes stateeach event has associated event time•e.g., arrival of packet to queue, departure from queue•precisely at these points in time that simulation must take action (change state and may cause new future events)model for time between events (probabilistic) caused by external environmentDiscrete Event Simulationsimulation program maintains and updates list of future events: event listsimulator structure:initialize event listget next (nearest future)event from event listtime = event timeprocess event(change state values, add/delete future events from event listupdate statisticsdone?nNeed:well defined set of eventsfor each event: simulated system action, updating of event listySimulation: examplepackets arrive (avg. interrarrival time: 1/ ) to router (avg. execution time 1/) with two outgoing linksarriving packet joins link i with probability i12state of system: size of each queuesystem events: job arrivals service time completionsdefine performance measure to be gatheredSimulation: example12Simulator actions on arrival eventchoose a link if link idle {place pkt in service, determine service time (random number drawn from service time distribution) add future event onto event list for pkt transfer completion, set number of pkts in queue to 1} if buffer full {increment # dropped packets, ignore arrival} else increment number in queue where queuedcreate event for next arrival (generate interarrival time) stick event on event listSimulation: exampleSimulator actions on departure eventremove event, update simulation time, update performance statistics decrement counter of number of pkts in queueIf (number of jobs in queue > 0) put next pkt into service – schedule completion event (generate service time for put)Gathering Performance Statisticsavg delay at queue i: record Dij : delay of customer j at queue i. Let Ni be # customers passing through queue iiiiTNaverage queue length at i:iNtotal simulated timethroughput at queue i, i = iNjijiNDTi1Little’s LawAnalyzing Output ResultsEach time we run a simulation, (using different random number streams), we will get different output results!distribution of random numbersto be used during simulation(interarrival, service times)random number sequence 1simulationoutput results 1inputoutputrandom number sequence 2simulationoutput results 2inputoutputrandom number sequence Msimulationoutput results Minputoutput… …… …… …Analyzing Output ResultsW2,n: delay of nth departing customer from queue 212Analyzing Output Resultseach run shows variation in customer delayone run different from nextstatistical characterization of delay must be madeexpected delay of n-th customerbehavior as n approaches infinityaverage of n customersTransient Behaviorsimulation outputs that depend on initial condition (i.e., output value changes when initial conditions change) are called transient characteristics“early” part of simulationlater part of simulation less dependent on initial conditionsEffect of initial conditionshistogram of delay of 20th customer, given initially empty (1000 runs)histogram of delay of 20th customer, given non-empty conditions (1000 runs)Simulation: examplepackets arrive (avg. interrarrival time: 1/ ) to router (avg. execution time 1/) with two outgoing linksarriving packet joins link i with probability i12Steady state behavioroutput results may converge to limiting “steady state” value if simulation run “long enough”discard statistics gathered during transient phase, e.g., ignore first n0 measurements of delay at queue 2avg delayof packets [n, n+10]00nNDTiNnjijiipick n0 so statistic is “approximately the same” for different random number streams and remains same as n increasesavg of 5 simulationsExample: Random Waypoint ModelSimplest random waypoint model:mobile picks next waypoint Mn uniformly in area, independent of past and presentmobile picks next speed Vn uniformly in [vmin; vmax] independent of past and presentmobile moves towards Mn at constant speed VnMnMn+1Issue with RWP Model: DecayDistributions of node speed, position,