WIXLIB

Network DesignPerformance Evaluation, andSimulation#6Network Performance.1Network Design Problem Goal Given– QoS metric, e.g., Average delayLoss probability– Characterization of the traffic, e.g., Average interarrival time (arrival rate)Average holding time (message length)Design the systemThree systems will be studied:– Circuit switch, e.g., determine the # lines System 1 M/M/S/S (M/M/S/S / )– Ideal router output port, e.g., determine link capacity System 2 M/M/1 (M/M/1/ / )– Real router output port, e.g., determine link capacity and buffer size System 3 M/M/1/N (M/M/1/N / )Network Performance.2

Network Performance Evaluation Solution methodologies:Mathematical analysis–Model this type of process as a QueueingSystem good for initial design Simulation techniques good for moredetailed analysisNetwork Performance.3Network Simulation Define network simulationDiscuss attributes and application of simulationPresent implementation of simulation systemsDiscuss analysis of simulation resultsDiscuss selection of simulation toolsProvide an overview of ExtendSim8. On the start upExtendsim window there is: A button for tutorials and a video showing how to buildmodels A link to “ExtendSim for DESS Textbook”, a that is a tutorialon the tool. Other useful tools. There is a link to getting the whole user manual on the classweb page. (It is long DO NOT PRINT the whole pdf file.)Network Performance.4

A Definition of Communication NetworkSimulationCommunication network simulation involvesgenerating pseudo-random sequences of message lengthsand interarrival times (or other input processes, e.g. timevarying link quality) then using these sequences toexercise an algorithmic description of the networkoperation.Network Performance.5Attributes of Simulation Simulation Is a Very Flexible Evaluation Tool Simulation Models Can Be Expensive to Construct General Network Characteristics (Sources, Topology,Protocols, Etc.)Minute DetailHuman EffortSimulation Models Can Be Expensive to Run Computer Effort Statistical Analysis of the Results Can Be Difficult Difficult to Gain Insight Into System Behavior Requires Careful InterpretationSimulate Only a Set of Specific ScenariosNetwork Performance.6

When to Use Simulation Whenever Mathematical Analysis Is Difficult or Impossible For Validating Analytic Models and Approximations For Studying Transient Behavior of NetworksFor Systems With Adaptive RoutingFor Systems With Adaptive Flow ControlFor Systems With Blocking (Finite Buffers)For Systems With General Message Interarrival StatisticsHow Accurate Is the Model?Do Approximations Distort the Results?For Experimentation Without Disturbing an OperationalSystem Test Possible Modifications and AdjustmentsNetwork Performance.7Modeling Elements for CommunicationNetworks Traffic and Input Processes Message Arrival Process– Often Interarrival Times Message LengthsOther Message Attributes– Service Class– Error models Algorithmic Descriptions of NetworkProcessing ProtocolsLinks and QueuesRoutingNetwork Performance.8

Sample Realization of an Input ProcessArrivalEvents &LengthsNetwork Performance.9Time Step Approach to NetworkSimulation Approaches to Discrete Event Simulation Time Step Approach (Fixed Increment Time Advance)Event-Scheduling ApproachFixed Increment Time Advance Choice of Increment ImportantToo Large: Multiple Events Happen In Single StepToo Small: Wasted Processing TimeUpdate System States at End of Each Fixed Time IntervalNetwork Performance.10

Event Scheduling Approach to NetworkSimulation Variable Time Advance Update System State Only When Events Occur Advance Time To Next Occurring EventFor Example, Arrivals or DeparturesEvent Calendar Events: Instantaneous Occurrences That Change the State ofthe SystemAn Event is Described by– The Time the Event is to Occur– The Activity to Take Place at the Event Time The Calendar is a Time-Ordered List of EventsNetwork Performance.11Event Scheduling Approach: SimplifiedFlow ControlAn Executive(or Mainline)Controls theSelection of NextEventUse Event Listto determine nextevent to processAdvance simulationclock to event timeUpdate system stateusing event routinesUpdate event listusing event routinesNetwork Performance.12

Event Scheduling for Simple StatisticalMultiplexerNetwork Performance.13Verification and Validation of SimulationModels Model Verification Mathematical (Algorithmic) Description of Behaviour of “RealThing”Determining Whether the Simulation Model Performs As IntendedIn Programming Terminology, “Debugging”Example: Is M/M/1 Model Producing Exponential MessageLengths?Validation Determining Whether the Simulation Model Itself Is an “Accurate”Representation of the Communication Network Under Study (the“Real Thing”)Example: Is the Assumption of Exponential Message LengthsAccurate?Network Performance.14

Verification Methods Modular Development and Verification BreakLarge System Into Smaller Components Verify Component-by-Component Structured Walk-Through Step-by-StepAnalysis of Behavior for Simple CaseNetwork Performance.15Verification Methods Event Trace Detailed Analysis of Model BehaviorCompare to Walk-Through AnalysisModel Simplification and Comparison toAnalytic ResultsGraphical Display of Network Status As theModel Progresses To “See” What Is Happening As It HappensNetwork Performance.16

Some Comments on Validation Simulation Models Are Always ApproximationsA Simulation Model Developed for One ApplicationMay Not Be Valid for OthersModel Development and Validation Should Be DoneSimultaneouslySpecific Modeling Assumptions Should Be TestedSensitivity Analysis Should Be PerformedAttempt to Establish That the Model ResultsResemble the Expected Performance of the ActualSystemGenerally, Validation Is More Difficult ThanVerificationNetwork Performance.17Analysis of Results: StatisticalConsiderations Starting Rules Overcoming Initial TransientsAn Initial Transient Period Is Present Which Can Bias the ResultsAchieving Steady State– Use a Run-in Period: Determine Tb Such That the Long-Run Distribution Adequately Describes theSystem for t Tb– Use a “Typical” Starting Condition (State) to Initialize the Model Quality of Performance Estimates Variance of Estimated Performance MeasuresNetwork Performance.18

Quality of Performance Estimates Simulation results are like laboratorymeasurements, they can be modeled asrandom variablesPerformance estimates should haveacceptable varianceThe more observation reduces the variance.HOWEVER Observations taken fromnetwork simulation will be correlated Cannot directly apply standard statisticalapproaches based on iid (Independent, IdenticallyDistributed) observationsNetwork Performance.19Dealing with Lack of Independence Simple Replication:Multiple SimulationRuns Assume Results for EachReplication AreIndependentCan be InefficientBecause of MultipleStartup PeriodsNetwork Performance.20

Criteria for Selecting a NetworkSimulation Tool Availability CostUsageDocumentationEase of LearningComputation EfficiencyFlexibilityPortabilityUser InterfaceExtendibilityCommon Toolsns-3(http://www.nsnam.org/) Opnet(http://www.opnet.com/) QualNet(http://www.scalable-networks.com ExtendSim Network Performance.21Guidelines to Network Modeling andSimulation Things to Know Know the CustomerKnow the NetworkKnow the Important Performance MetricsThings to Do Establish a Credible ModelExpect the Model to Evolve Plan for successApply Good Software Management TechniquesNetwork Performance.22

ConclusionsSimulation Can Be an Important Tool forCommunication Network Design and Analysis Care and Thought Must Go Into Construction ofCommunication Network Models Care and Thought Must Go Into Interpretation ofModel Output Network Performance.23Extend Overview Allows Graphical Description of Networks Sources,Links, Nodes, Etc.Data Flow Block Diagrams Hierarchical Structure to Control Complexity Be sure and create libraries when creating complexmodels Network Performance.24

Network Performance Evaluation: Elements ofa Queueing verBlockedcustomersNetwork Performance.25Network Performance Evaluation: Elements ofa Queueing er in systemNetwork Performance.26

Network Performance Evaluation: Specific casesfor theoretical analysis Assumptions: Interarrival times are exponentially distributedService times are exponentially distributed– Holding time– Packet length Types of systems– One server (Stat Mux) Infinite memoryFinite memory– S servers and a system size of S (Circuit Switch)Network Performance.27Network Performance Evaluation:Approach Analysis of a pure birth process to characterizearrival processesExtension to general birth/death processes to modelarrivals and departuresSpecialization to the specific cases to find: Probability of system occupancy, Average buffer size, Delay, Blocking probabilityGoal: Design and analyze statisticalmultiplexers and circuit switchingsystemsNetwork Performance.28

Network Performance Evaluation:Analysis of a Pure Birth ProcessArrivals and no departuresλ0λ1λ Arrival rateλλ2 .KOnly Births (Arrivals) AllowedK System State (number in system)-number of arrivals for 0 to t sec-number in system at time tGoal: Find Prob [k arrivals in a t sec interval]Network Performance.29Network Performance.30Network Performance Evaluation:Analysis of a Pure Birth ProcessArrivalsInterarrival Time

Network Performance Evaluation:Analysis of a Pure Birth Process The number represents the State of the system. In networksthis is usually the number in the buffer plus the number inservice. The system includes the server.The time to clock the message bits onto the transmissionfacility is the service time. The server is the model for thetransmission facility.Goal: Find Prob [k arrivals in a t sec interval]Network Performance.31Network Performance Evaluation:Analysis of a Pure Birth Process: Assumptions Prob[ 1 arrivals in t sec ] λ tProb[ 0 arrivals in t sec ] 1- λ tNumber of arrivals in non-overlapping intervals oftimes are statistically independent randomvariables, i.e.,Prob [ N arrivals in t, t T AND M arrivals in t T, t T τ] Prob [ N arrivals in t, t T]*[M arrivals in t T, t T τ]Network Performance.32

Network Performance Evaluation:StateHow to get to state k att t?kk-1tt ttimeNetwork Performance.33Network Performance Evaluation:Analysis Define probability of k in the system at time t Prob[k, t] Probability of k in the system at time t t Prob[k, t t] Prob[(k in the system attime t and 0 arrivals in t) or (k-1 in thesystem at time t and 1 arrival in t)] (1- λ t ) Prob[k,t] λ t Prob[k-1,t]Network Performance.34

Network Performance Evaluation:Analysis Rearranging terms(Prob[k, t t] - Prob[k,t])/ t λProb[k,t] λ Prob[k-1,t] Letting t -- 0 results in the followingdifferential equation:Network Performance.35Network Performance.36Network Performance Evaluation:Analysis For k 0 the solution is: Prob[0,t] For k 1 the solution is: Prob[1,t] For k 2 the solution is: Prob[2,t]

Network Performance Evaluation:Analysis In general the solution is a Poisson probability massfunction of the form:Network Performance.37Network Performance Evaluation: Analysis A Possion pmf of this from has the followingmoments:Poisson Arrival ProcessThe number of arrivals in any T second intervalfollows a Poisson probability mass function.Network Performance.38

Network Performance Evaluation: InterarrivalTime AnalysisArrivalTaArrivalTa interarrival time λ tProb[t Ta t t] Prob[0 arrivals in t sec and1 arrival in t]Prob[t Ta t t] Prob[k 0,t]Prob[k 1, t]tProb[t Ta t t] Network Performance.39Network Performance Evaluation: InterarrivalTime AnalysisLet t -- 0 results in the followingNetwork Performance.40

Network Performance Evaluation:Interarrival Time AnalysisMAIN RESULT:The interarrival timefor a Poisson arrival process followsan exponential probability density function.Network Performance.41Network Performance Evaluation:Birth/Death Process AnalysisNow allow arrivals and departures.The Model for the Birth/Death ProcessNetwork Performance.42