Question? Leave a message!




Network simulation and simulators

Network simulation and simulators 11
EdenKelly Profile Pic
EdenKelly,United States,Professional
Published Date:12-07-2017
Website URL
Comment
Network simulation and simulators Lecturer: Dmitri A. Moltchanov E-mail: moltchancs.tut. Network simulation techniques D.Moltchanov, TUT, 2012 OUTLINE  Theoretical aspects why do we need network simulation? structure of a simulator discrete-event simulation data collection and analysis simulation with a given accuracy variance reduction techniques  Practical aspects: ns2 ns2 overview; ns2 architecture; simulation procedure; support tools: nam and xgraph; examples: bottleneck, routing and 802.11 WLANs. Lecture: Network simulation 2Network simulation techniques D.Moltchanov, TUT, 2012 1. Why do we need network simulations? Analyze communication networks: two ways  analytical analysis;  simulation studies. Example: analysis of queuing system:  modeling of arrival process as a stochastic process;  modeling of service time are a stochastic process;  representation of interactions of these processes as an another process. What is important for analytical analysis:  often analytical analysis is too complicated or even not possible;  even if possible, it requires restrictive assumptions. Lecture: Network simulation 3Network simulation techniques D.Moltchanov, TUT, 2012 1.1. Simple example GI/G/1 queuing system. ... ... arrivals unlimited of waiting positions server Figure 1: Graphical representation of GI/G/1 queuing system. System is characterized by:  arbitrary i.i.d. distributed interarrival times (GI);  arbitrary i.i.d. distributed service times (G);  single server;  FCFS queuing discipline. Lecture: Network simulation 4Network simulation techniques D.Moltchanov, TUT, 2012 What should be noted:  there are no analytical solution for GI/G/1 queue;  what should we do? Approximate solution can be derived for:  overloaded GI/G/1 system ();  unloaded GI/G/1 system ();  results in terms of bounds. Notes on GI/G/1 queue:  GI/G/1 does not capture correlation between arrivals;  arrival processes in real networks are often correlated;  simulation is the only suitable way in this case. Lecture: Network simulation 5Network simulation techniques D.Moltchanov, TUT, 2012 1.2. Simulations vs. analytic: queue example Simulation of a queue consists of:  representation of the arrival process as a stochastic one;  representation of service time as a stochastic process;  representation of interoperation as a stochastic process;  simulation run;  collection of data;  statistical analysis of obtained data;  drawing conclusions. Di erences between analytical analysis and simulations:  incorporation of simulation execution;  incorporation of data collection and analysis. Lecture: Network simulation 6Network simulation techniques D.Moltchanov, TUT, 2012 1.3. Advantages/shortcoming of simulations Advantages:  does not require restrictive assumption or require less of them;  model structure, algorithms and variable may be changed quickly;  models of trac and service times can be used as is just from measurements;  may provide results which are not obtainable using analytical techniques. Shortcomings:  time consuming, it may take much more time that analytic;  computationally expensive;  validation of results take additional time;  results may be inaccurate when time of analysis is not sucient;  simulations may be of higher complexity than required;  relationship between variables is hard to visualize and explain;  sensitivity analysis is dicult. Lecture: Network simulation 7Network simulation techniques D.Moltchanov, TUT, 2012 2. Structure of a simulator We have the following components:  simulation engine (core);  a collection of models (link, bu er, etc.);  frontend (interface);  preprocessing tools (hidden for a user);  data postprocessing tools. Engine is the most important:  speci es how to handle simulations;  everything is handled in uniform way;  does not matter what you simulate. Lecture: Network simulation 8Network simulation techniques D.Moltchanov, TUT, 2012 2.1. Types of simulations Continuous simulations:  real time is used: time increments as ne as possible: to capture all state changes. Discrete simulations:  system is observed at discrete times t ;t + t;t + 2t;::: . 0 0 0 Discrete event simulations:  we focus on system changes only at event times;  after processing the current event, the system clock is forwarded to another event  simulation moves from the current system state to the event occurring next;  processing of the event may create additional events;  event list which is updated for the system. Lecture: Network simulation 9Network simulation techniques D.Moltchanov, TUT, 2012 Discrete-event t t t 0 1 3 Discrete t t t t t t 0 1 2 3 4 5 Continuous ... t t t t t t t t 0 1 2 3 4 5 6 7 Figure 2: Illustration of di erent types of simulations. Lecture: Network simulation 10Network simulation techniques D.Moltchanov, TUT, 2012 2.2. The simulation procedure Define the problem Debug Analyze data Validate model Formulate submodels Design experiments Combine submodels Run the simulator Collect data Analyze the results Write the program Implement results Lecture: Network simulation 11Network simulation techniques D.Moltchanov, TUT, 2012 2.3. The simulation program Simulation program can be implemented using:  general purpose programming languages: C: suitable for one purpose simulations; C++: suitable for writing multiple purposes simulations. +: very exible languages; : there are no simulation speci c functions and error detection.  simulation oriented programming languages: OPNET: all networks; OMNET++: all networks; Qualnet: very good for cellular networks; ns2: all networks: +: reliable approach; : sometimes not fast (incorporate a lot of functionality;) : sometimes limited to speci c functionality; : one more language to learn. Lecture: Network simulation 12Network simulation techniques D.Moltchanov, TUT, 2012 3. Discrete event simulation The basic idea:  only events change the state of the system;  no need to track state of the system between events. The whole system consists of the following components:  system under consideration: process under considerations: product of other processes and RVs.  system state: state of the stochastic process.  simulation clock: tells the occurrence time of the next event.  event list: holder for events: consider it as a two dimensional vector: time and event. Lecture: Network simulation 13Network simulation techniques D.Moltchanov, TUT, 2012 The idea of the event list is illustrated in the following gure:  T , i = 1; 2;::: , are event times; i  E , i = 1; 2;::: , are corresponding events. i E E E E 1 2 3 i ... ... T T T T 1 2 3 i Figure 3: The idea of the event list. Events are identi ed by event time and event type. There are two general types of events:  basic events: these events modify the state of the system: arrivals/departures of customers.  additional events: these are events needed by additional tasks of simulation: run, stoppage, collection of data. Lecture: Network simulation 14Network simulation techniques D.Moltchanov, TUT, 2012 General algorithm:  initialization procedure: system clock should be set to zero; system state is assigned an initial value; generate list of the event and place the next event to this list.  handling of events during a simulation: system clock should be set to the occurrence time of the rst (next) event in event list; handle the event making all appropriate actions associated with the event; update the system state.  stop of simulation. Note that the following is not included:  storing of statistical data;  statistical analysis of obtained data. Lecture: Network simulation 15Network simulation techniques D.Moltchanov, TUT, 2012 3.1. Time advance methods Time advance methods in discrete-event simulations:  event-advance method;  unit-advance method. unit-time advance: t t t t t t 0 1 2 3 4 5 event advance: t t t 0 1 3 Figure 4: Time advance techniques in discrete-event simulations. Lecture: Network simulation 16Network simulation techniques D.Moltchanov, TUT, 2012 3.2. Event list Future event list: collection of events that occur in the future. What type of operation are performed in a list:  locating the next event and its type: required when advancing the time.  deleting the event: required when the events has already been treated.  inserting the event in a list: required when generating new event; required when basic event generates conditional events. Basically, there are two ways of organizing a list:  using sequential array;  using linked list. Lecture: Network simulation 17Network simulation techniques D.Moltchanov, TUT, 2012 3.3. Sequential arrays The approach: all future event times are stored sequentially in array. How to implement:  associate each event type with a certain integer i;  clock associated with this event is stored in the ith position in array. Example: we need N positions in array:  clock value of the type 1 event is stored in 1st position;  clock value of the type 2 event is stored in 2nd position;  :::  clock value of the type N event is store in Nth position; Figure 5: Using sequential array as a future event list. Lecture: Network simulation 18Network simulation techniques D.Moltchanov, TUT, 2012 How to nd the next event:  locate the smallest value in array of N elements. Example: nd the smallest element and its index in array Ei, i = 0; 1;:::;N 1:  variable smallest returns the smallest element;  variable index returns the index of the smallest element. smallest = E0; index = 0; for (i=1; iN; i++) if (Ei smallest) smallest = Ei; index = i; Lecture: Network simulation 19Network simulation techniques D.Moltchanov, TUT, 2012 How to deal with other functions:  deletion: set the value of the clock associated with event of type i to very big one; not deleted physically  insertion: update the value of the clock associated with event of type i. not inserted physically Advantages:  insertion and deletion are made very easily;  location of the next event depend on the number of event types: complexity is linear in time. Shortcoming:  if the number of event types is large location is time consuming;  in this case di erent organization of the future event list should be considered. Lecture: Network simulation 20