Question? Leave a message!




Network simulation and simulators

Network simulation and simulators 11
Network simulation and simulators Lecturer: Dmitri A. Moltchanov Email: moltchancs.tut. Network simulation techniques D.Moltchanov, TUT, 2012 OUTLINE  Theoretical aspects why do we need network simulation structure of a simulator discreteevent 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 Discreteevent 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 discreteevent simulations:  eventadvance method;  unitadvance method. unittime 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 discreteevent 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 20Network simulation techniques D.Moltchanov, TUT, 2012 3.4. Linked list The idea: to access data elements in correct order  we store data element;  we store pointer to the next element. De nitions:  pointer is referred to as link;  data element and the link(s) are referred to as node. Example:  node consists of two elements: one is data elements, the next one is link;  link F points to the rst element; link of the last node is set to zero. Figure 6: Using linked list as a future event list. Lecture: Network simulation 21Network simulation techniques D.Moltchanov, TUT, 2012 Implementation example: arrange integer numbers in T in ascending order:  create new array P of the same dimension;  the content of P (i) is the link to location in T containing element larger than T (i);  example: P (1) = 7, next larger after T (1) is T (7)... Notes:  F (= 5) is the rst element;  node: location in T and corresponding location in P . Figure 7: Locating values in a singly linked list. Lecture: Network simulation 22Network simulation techniques D.Moltchanov, TUT, 2012 Locating element: we want to locate number 10 in T :  using pointer F we check the value stored in the rst node: (T (5);P(5));  using pointer P (5) we locate the second node: (T (3);P(3));  using pointer P (3) we locate the third node: (T (1);P(1));  pointer P (1) contains the address we are looking for;  general: if we know address of the rst node we can locate any element. Note: we can only move forward using singly linked link Figure 8: Deletion of elements in a singly linked list. Lecture: Network simulation 23Network simulation techniques D.Moltchanov, TUT, 2012 Deletion: we want to delete number 10:  change the value of the pointer of the previous node;  previous node: (T (1);P(1)) = (5; 4);  node containing 10 has the pointer P (7) = 4;  to delete: set P (1) =P (7) = 4. Note: information is not physically deleted, just not accessible Figure 9: Deletion of elements in a singly linked list. Lecture: Network simulation 24Network simulation techniques D.Moltchanov, TUT, 2012 Insertion: we want to insert number 6:  locate two nodes between which we should put 6;  starting from the rst node we nd them as: (5; 7) and (10; 4) (see previous slide);  get unused location in T : T (2);  set P (1) = 2 to go from T (1) = 5 to T (2) = 6;  set T (2) = 6, P (2) = 7 to go from T (2) = 6 to T (7) = 10. Figure 10: Insertion of elements in a singly linked list. Lecture: Network simulation 25Network simulation techniques D.Moltchanov, TUT, 2012 3.5. Implementation of linked lists We have to be able:  organize data elements and pointers into nodes;  access node using pointer;  create and delete nodes. There are two ways:  use builtin commands to carry these operations (if any);  setup your own storage scheme. Notes:  must be long enough to accommodate all events that might be generated;  all unused nodes must be linked together to form a pool of free nodes. Lecture: Network simulation 26Network simulation techniques D.Moltchanov, TUT, 2012 3.6. Event list using linked list General notes:  nodes are organized such that CL CL CL ; i j n  the next event is given by pointer F ( rst node);  when the event occurred and processed it should be deleted;  if conditional events are generated they are place in linked list. Advantages:  location and deletion is made easily: using linked lists in simulation we have to delete only the rst node Shortcomings  we have to use location procedure to insert an event in a linked list;  search of the linked lists might be time consuming if the number of event types is large;  solution: use better location procedure (e.g. use pointer pointing to the middle of the list) Lecture: Network simulation 27Network simulation techniques D.Moltchanov, TUT, 2012 3.7. Doubly linked lists The main problem of the singly linked lists:  we can go only forward Doubly linked lists:  link two successive node with two pointers;  we can go forward and backward Note: there are some advantages for speci c applications. Figure 11: Example of the doubly linked list. Lecture: Network simulation 28Network simulation techniques D.Moltchanov, TUT, 2012 4. Data collection How to carry out a simulation:  set the initial state;  start the simulation;  obtain simulation results for some time... We distinguish between:  transient simulations (results for warmup period);  steadystate simulation (results for steadystate period). N(t) warmup steadystate T T t W Lecture: Network simulation 29Network simulation techniques D.Moltchanov, TUT, 2012 4.1. Transient simulations What is the reason:  analyze problems associated with a speci c initial state; T is a function of the initial conditions; W this might give some hints how to start a certain system... example: which initial state faster leads to steadystate.  analyze transient state itself: a certain system may not have a steadystate at all; example: M/M/1 queuing system with = = 1. M/M/1 0 1 lambda/mu Lecture: Network simulation 30 N(t), number of jobsNetwork simulation techniques D.Moltchanov, TUT, 2012 4.2. Steadystate simulations: initial condition What is the reason:  typical application of simulations;  simulation has to run long enough to get away from the transient state (T ). W Note: T is a function of the initial conditions. W How to choose initial condition:  assume no activities in the system prior to time 0; no particular reasons for that; as good as any other choice of the initial state.  set to some typical state of the system: should be as representative as possible; apriori knowledge of the system is required; advantage: may signi cantly shorten the length of the transient period, T . W Lecture: Network simulation 31Network simulation techniques D.Moltchanov, TUT, 2012 4.3. Steadystate simulation: e ect of the transient period Transient period: may deteriorate statistics:  how to remove transient period;  how to determine the length of the transient period. What are approaches to deal with:  use very long simulation runs such that (meanwhile, how long is 'long enough'): the amount of data in transient period is small relative to those of steadystate; timeconsuming approach.  no data collection during transient period: simulate till the steadystate is reached; clear all data accumulated up to this point; continue to get enough statistical data. Hint for both approaches: set the initial state to what is expected in the long run. Lecture: Network simulation 32Network simulation techniques D.Moltchanov, TUT, 2012 4.4. Steadystate simulation: detecting transient period There are three methods to detect T : W  method of trials;  movingaverage method;  blind guess using timeseries... Method of trials:  try out di erent transient periods: T ;T ;:::;T , T T :::;T ; 1 2 k 1 2 k  compile steadystate statistics for each run;  choose T such that for all j i statistics do not change signi cantly. i Movingaverage method: P i  compute moving average as time progresses: R = N ; i j j=ir where N is some metric of interest, r is the range of moving averages. j  steadystate when R no longer changes signi cantly over time. i Lecture: Network simulation 33Network simulation techniques D.Moltchanov, TUT, 2012 4.5. Estimating metrics How to estimate the mean:  use point estimator;  estimate con dence intervals. Con dence interval for the mean:   s s p p Pr EXz EX +z  1 ; (1) =2 =2 N N s s p p Note: interval EXz ;EX +z is 100(1 ) con dence interval for . =2 =2 N N a a 2 2 Lecture: Network simulation 34Network simulation techniques D.Moltchanov, TUT, 2012 What is the problem with the following expression   s s Pr EXz p EX +z p  1 ; (2) =2 =2 N N  we have to estimate sample mean and sample variance;  point estimator of the variance is given by: N X 1 2 2 s = (X EX) ; i N 1 i=0 N X 1 EX = X; (3) i N i=0 2  X , i = 1; 2;:::;N must be independent for s to be unbiased i  quite often observations are dependent (correlated, in particular): example: waiting time of the packet i depends on the waiting time of packet (i 1) The main problem how to remove dependence between observations Lecture: Network simulation 35Network simulation techniques D.Moltchanov, TUT, 2012 The following approaches have been proposed:  use of autocorrelation function: tries to explicitly take correlation into account.  batch means method; tries to remove correlation from observations.  replication method; tries to remove correlation from observations.  regenerative method. tries to remove correlation from observations. Note the following:  when sample size is really large the e ect of dependence can be negligible;  use any of above methods when sample size is not really huge. Lecture: Network simulation 36Network simulation techniques D.Moltchanov, TUT, 2012 4.6. Use of ACF How to estimate the variance: 2 2 2  idea: take into account the e ect of correlation explicitly ( = + + 2Cov ); XY X+Y X Y  get the sample X ;X ;:::;X ; 1 2 N  compute autocorrelation coecients R(i), i = 0; 1;:::;k;  the variance can now be estimated as: 2 3   N=4 X k 2 2 4 5 s =s 1 + 2 1 R(k) : (4) X N k=1 2  s is the point estimator of the variance assuming no serial correlation: X N X 1 2 2 s = (X EX) : (5) i X N 1 i=1 Lecture: Network simulation 37Network simulation techniques D.Moltchanov, TUT, 2012 4.7. Batch means method correlation N(t) ... T time W Figure 12: Correlation between successive batches. Do the following:  let EX be the sample mean of the batch i, i = 1; 2;:::;k; i  ifb is large: EX ;EX ;:::;EX are approximately uncorrelated and normally distributed. 1 2 k Lecture: Network simulation 38 batch 1 batch 2 batch 3 batchkNetwork simulation techniques D.Moltchanov, TUT, 2012 Given that EX ;EX ;:::;EX are uncorrelated and normally distributed: 1 2 k k X 1 EX = EX ; i k i=1 k X 1 2 2 s = (EX EX) : (6) i k 1 i=1 Thus, for large k, k 30 we get the following con dential intervals:   s s EX 1:96p ;EX + 1:96p : (7) k k  construct con dential intervals using t distribution. Important notes:  if b is not large enough, this computation gives biased estimates;  estimate of b: plot ACF of X ;X ;:::;X : 1 2 N b should be approximately 5 times greater than the last signi cant correlation. Lecture: Network simulation 39Network simulation techniques D.Moltchanov, TUT, 2012 4.8. Method of replications The idea: replicate simulation run several times:  make n runs each resulting in m observations: (X ;X ;:::;X ); (X ;X ;:::;X );:::; (X ;X ;:::;X ): (8) 11 12 1m 21 22 2m n1 n2 nm  for each sample compute the sample mean using point estimator of the mean: n X 1 EX = x (9) i m j=1  treat sample means as a sample of independent observations: n n X X 1 1 2 2 EX = EX ; s = (EX EX) : (10) i i n n 1 i=1 i=1 Classic problems:  determine the length of each simulation run;  determine the length of the transient period. Lecture: Network simulation 40Network simulation techniques D.Moltchanov, TUT, 2012 4.9. Regenerative method Comparison of methods:  batch means: obtain approximately independent samples from a single run.  method of replications: obtain strictly independent samples from multiples runs;  regenerative method: obtain strictly independent samples from a single run; application is limited to systems with speci c behavior. Where it is used:  simulation of queuerelated problems. Lecture: Network simulation 41Network simulation techniques D.Moltchanov, TUT, 2012 4.10. Estimation for transient simulations Two cases are possible:  trajectories are all random: estimation may have no sense;  trajectories are somewhat similar. How to estimate:  the transient state depends on initial conditions;  the only way to get independent realizations of X is to use method of replications; Repeating experiments:  must start with the same initial condition;  must use di erent random numbers (di erent seeds);  we have to know the length of transient period. Lecture: Network simulation 42Network simulation techniques D.Moltchanov, TUT, 2012 5. Simulation with a given accuracy Two inverse tasks:  we considered: what are the con dence intervals given N observation: is it OK to say that mean is 50 30  what we are asked: provide a kind of assurance: say what would be the values with con dence3...  question: how many experiments are needed to achieve that General notes: p  recall, width of con dence intervals is proportional to 1= N;   s s p p EXz ;EX +z : (11) =2 =2 N N N: number of iid observations; the larger N the smaller is the interval.  to halve the con dence interval: increase N four times. Lecture: Network simulation 43Network simulation techniques D.Moltchanov, TUT, 2012 Observe that:  we do not know how many observations are needed: what accuracy may N experiments give e.g. how many observations are needed to get 50 3 Two techniques:  Solution 1: use of pilot experiments: aim 1: to get overall idea how things go; aim 2: obtain rough estimate of N providing required accuracy.  Solution 2: sequential 'insimulation' checking: test is carried out periodically to check whether required accuracy is achieved. Can be applied to:  batch mean method;  method of replications. Lecture: Network simulation 44Network simulation techniques D.Moltchanov, TUT, 2012 5.1. Example: replications + pilot experiments Use of pilot experiments:  we want to estimate statistics a with the intervals0:1a :  pilot experiments is carried out to collect N replications; 1  let a be a point estimator of a; 1  let  be the width of con dence intervals; 1  check the following: if   0:1a we stop; 1 1 2 if  0:1a we carry out main simulation with N = ( =0:1a ) N replications; 1 1 2 1 1 1  we obtain new a and  : 2 2 they may not be exactly what we wanted (0:1a ) due to randomness. 2  if  0:1a carry out new attempt. 1 1 Lecture: Network simulation 45Network simulation techniques D.Moltchanov, TUT, 2012 5.2. Example: batch means + insimulation checking Sequential 'insimulations' checking:  we want to estimate statistics a with the intervals0:1a :  gather k batches;  estimate a and  ; 1 1  check the following: if   0:1a we stop; 1 1 if  0:1a gather k additional batches. 1 1  calculate new a and  based on total 2k batches; 2 2  check the following: if   0:1a we stop; 2 2 if  0:1a gather k additional batches. 2 2  repeat... Lecture: Network simulation 46Network simulation techniques D.Moltchanov, TUT, 2012 6. Variance reduction techniques Suppose we have to estimate mean given N iid observations:  point estimate of the mean is: N X 1 EX = X; (12) i N i=1  con dence intervals for the mean are given by:   s s EXz p ;EX +z p : (13) =2 =2 N N 2 where s is the estimate of the variance. How to shorten the con dence intervals:  accuracy of an estimate can be increased by increasing the number of observations; shortcoming: may require very long simulations.  accuracy can also be achieved by reducing variance. Lecture: Network simulation 47Network simulation techniques D.Moltchanov, TUT, 2012 Lecture: Network simulation 48Network simulation techniques D.Moltchanov, TUT, 2012 7. Network simulators Free simulators  ns2/ns3: www.isi.edu/nsnam/ns;  OMNET++: www.omnetpp.org  QualNet: www.scalablenetworks.com  ITGuru: www.opnet.com Commercial:  OPNET: www.opnet.com  a plenty of others.... Note: ITGuru is an academic edition of OPNET. Lecture: Network simulation 49Network simulation techniques D.Moltchanov, TUT, 2012 8. ns2 Overview Characteristics:  discreteevent engine;  network simulator;  basically TCP/IP networks;  wired and wireless components included. Intended usage:  research;  development;  education. Developing:  research institutes and universities;  freely distributed and open source. Lecture: Network simulation 50Network simulation techniques D.Moltchanov, TUT, 2012 8.1. History of developing Brie y:  1989: REAL simulator by UCB;  1990: ns1: LBL;  1995: ns2 DARPA VINT project (Virtual InterNet Testbed)  2011: ns3. Current status:  ns2 runs on: almost all UNIX and Linux and Win 95/98/2000/XP.  last stable version: 2.35 released in Nov. 4, 2011 roughly 1 release in 6 months + daily snapshots.  http://www.isi.edu/nsnam/ns/ or http://nsnam.isi.edu/nsnam/index.php/Main Page  200000 line of codes; 1000 institutions; 10000 users; 400 pages of short manual;  ns3 project started in July 2006, http://www.nsnam.org/ Lecture: Network simulation 51Network simulation techniques D.Moltchanov, TUT, 2012 8.2. Components ns2 distribution consists of:  ns2 itself;  nam: Network AniMator visualizing ns2 output; GUI for simple scenarios.  Mandatory support tools: tcl/tk: script language otcl: objectoriented tcl; TclCL: tcl library.  Preprocessing tools: trac, topology generators, converters.  Postprocessing tools: trace analysis: awk, sed, perl, tcl. very simple and not recommended. Lecture: Network simulation 52Network simulation techniques D.Moltchanov, TUT, 2012 8.3. Installation Di ers for:  Unix/Linux;  Windows. Two types are available:  Via compilation; get 'allinone package'; get pieces and then compile.  Obtaining binaries. easiest way to run on Win platform. Hints and notes:  to compile on Windows you need Cygwin (Unix emulation);  Size of 'allinone' is around 320Mb (v2.29). Lecture: Network simulation 53Network simulation techniques D.Moltchanov, TUT, 2012 Building from pieces (Unix/Linux):  get Otcl, TclCL and ns2;  unpack in some temp folder at the same level;  cd into the OTcl directory;  run ./con gure;  run make;  cd into the TclCL directory;  run ./con gure;  run make;  cd into the ns directory;  run ./con gure;  run make;  Verify that it built correctly and runs by running ./validate. Note: ns2 'allinone' contains 'install' script (just run it). Lecture: Network simulation 54Network simulation techniques D.Moltchanov, TUT, 2012 8.4. Support Documentation:  mailing list: nsusersisi.edu to get in send message to the address with "subscribe nsusers" in the body; to browse archive go to http://www.isi.edu/nsnam/ns/.  ns manual: available at http://www.isi.edu/nsnam/ns/; is only a short reference guide.  tutorials: a number is available on http://www.isi.edu/nsnam/ns/; FAQ: http://www.isi.edu/nsnam/ns/nsfaq.html; defacto tutorial: http://www.isi.edu/nsnam/ns/tutorial/index.html; installation and bug xes: http://www.isi.edu/nsnam/ns/nsproblems.html; E. Altman, T. Jimenez: http://wwwsop.inria.fr/maestro/personnel/Eitan.Altman/ns.htm. Lecture: Network simulation 55Network simulation techniques D.Moltchanov, TUT, 2012 9. Ns 2 architecture Objectoriented structure:  advantage: code reuse;  shortcomings: performance. Software structure:  uses two languages to separate control and processing: C++: packet processing; Otcl: control.  Packet processing: C++ makes it fast and detailed; C++ makes it scalable.  Control: Otcl makes it easy to create scenarios; Otcl makes it easy to understand third party scripts. Lecture: Network simulation 56Network simulation techniques D.Moltchanov, TUT, 2012 9.1. Scalability and extensibility Scalability:  perpacket processing must be fast;  separating control and packet handling. Extensibility:  must be easy to add new objects;  object trees to understand hierarchy: in C++; in Otcl.  C++ and Otcl trees are split: if not needed nothing have to be changed at a certain level; helps a lot  Otcl class hierarchy: http://wwwsop.inria.fr/planete/software/nsdoc/nscurrent/;  C++ class hierarchy: http://www.isi.edu/nsnam/nsdocclasses/index.html. Lecture: Network simulation 57Network simulation techniques D.Moltchanov, TUT, 2012 9.2. Simple script Lecture: Network simulation 58Network simulation techniques D.Moltchanov, TUT, 2012 9.3. Tcl basics Tcl language:  semantics is similar to perl;  one can check tutorial at: http://www.msen.com/7Eclif/TclTutor.html;  real programming language to create network topology;  tcl is used by Otcl to construct advanced objects. Tcl contains:  lists, arrays, associative arrays etc.;  procedures and functions;  ow controls: if, while, for, etc. Lecture: Network simulation 59Network simulation techniques D.Moltchanov, TUT, 2012 Lecture: Network simulation 60Network simulation techniques D.Moltchanov, TUT, 2012 9.4. Otcl basics  codes can be reused (for example, di erent version of TCP). Lecture: Network simulation 61Network simulation techniques D.Moltchanov, TUT, 2012 9.5. Viewing source code Where to nd:  C++: /whereYouInstalled/ns(ver)/ where (ver) is your version of ns2 (e.g. 2.1b9a).  Otcl: /whereYouInstalled/ns(ver)/tcl/lib/  nsdefault.tcl: default values for ns2 objects;  other Otcl de nitions. /whereYouInstalled/ns(ver)/tcl/  specialized objects in subdirs. Lecture: Network simulation 62Network simulation techniques D.Moltchanov, TUT, 2012 10. Simulation procedure Basic steps:  Create the simulation environment; event list, scheduler, etc.;  Create the network: nodes and links between them.  Create connections: TCP, UDP (in some sense).  Create applications: CBR ow, FTP, WWW trac.  Trace network elements: trace queue, trace ow. Lecture: Network simulation 63Network simulation techniques D.Moltchanov, TUT, 2012 10.1. Creating environment The following are the common commands:  Create event scheduler: set ns new Simulator;  Schedule events: ns at time event;  Start scheduler: ns run.  Stop and close everything: ns at x "exit". where x is some instant of time. Note: before closing you must take additional actions:  ush all traces to les;  close all les. Lecture: Network simulation 64Network simulation techniques D.Moltchanov, TUT, 2012 10.2. Generating RVs Create new generator:  set rng new RNG;  rng seed 0. RNs from other distributions:  using class RNG: uniform: rng uniform a b.  using class RandomVariable: distributions: uniform, exponential, hyperexponential, Pareto; Lecture: Network simulation 65Network simulation techniques D.Moltchanov, TUT, 2012 10.3. Creating the network Nodes:  set n0 ns node. Links and queuing:  ns duplexlink n0 n1 bandwidth delay queue type;  queue type: DropTail, RED, CBQ, FQ, SFQ, DRR;  example: link with 10 Mbps, 10 ms delay, bu er size 100, RED bu er control Lecture: Network simulation 66Network simulation techniques D.Moltchanov, TUT, 2012 10.4. Creating connections Creating UDP ow In one command:  ns createconnection src type src node dst type dst node packet class;  example: ns createconnection UDP n0 Null n1 1. Other sources:  TCP (we will consider);  RTP source, RTCP source.  TCP for wireless links. Lecture: Network simulation 67Network simulation techniques D.Moltchanov, TUT, 2012 Creating TCP ow In one command:  ns createconnection src type src node dst type dst node packet class;  example: ns createconnection TCP n0 TCPSink n1 1. Some included TCP versions:  TCP: Tahoe TCP (slow start and AIMD);  TCP/Reno: Reno TCP (... + fast retransmit/fast recovery);  TCP/NewReno: TCP Reno with improved fast retransmit;  TCP/Sack: TCP SACK (Selective ACK). Lecture: Network simulation 68Network simulation techniques D.Moltchanov, TUT, 2012 10.5. Creating trac on top of UDP CBR:  Constant bit rate;  set src new Application/Trac/CBR. Exponential or Pareto ON/OFF:  on/o times are exponentially distributed;  set src new Application/Trac/Exponential;  set src new Application/Trac/Pareto. Connecting to transport:  udp de ned earlier;  src attachagent udp. Lecture: Network simulation 69Network simulation techniques D.Moltchanov, TUT, 2012 ns2 includes support for trac traces: What le should look like:  each record consist of two 32 bit eld;  interpacket time (msec) and packet size (in bytes). For example: there is converter for MPEG frame size le to ns2. Lecture: Network simulation 70Network simulation techniques D.Moltchanov, TUT, 2012 10.6. Creating trac on top of TCP FTP:  set ftp new Application/FTP;  attaching to TCP: ftp attachagent tcp. Telnet:  set telnet new Application/Telnet;  attaching to TCP: telnet attachagent tcp. Lecture: Network simulation 71Network simulation techniques D.Moltchanov, TUT, 2012 10.7. Starting/stopping trac sources Starting and stopping times scheduled as events to the scheduler:  ns at time event. Starting:  ns at 1.0 "ftp start";  sends in nitely long;  the same for CBR, telnet and on/o sources. Stopping:  ns at 5.0 "ftp stop";  the same for CBR, telnet and on/o sources. Sending for example 1000 packets:  ns at 7.0 "ftp produce 1000";  works for FTP only. Lecture: Network simulation 72Network simulation techniques D.Moltchanov, TUT, 2012 10.8. Tracing Trace packets on all links of the network:  ns traceall open test.out w. Tracing on speci c links:  ns tracequeue n0 n1. Lecture: Network simulation 73Network simulation techniques D.Moltchanov, TUT, 2012 10.9. Monitoring Queue monitor:  set qmon ns monitorqueue n0 n1;  for packet arrivals and drops: set parr qmon set parrivals ; set drops qmon set pdrops . Flow monitor:  enable ow monitoring: set fmon nssim make owmon Fid; nssim attachfmon nssim link n0 n1 fmon.  count arrivals and drops for ow with id xx: set fclassi er fmon classi er; set ow1 fclassi er lookup auto 0 0 xx; set parr ow1 set parrivals ; set pdrops ow1 set pdrops . Lecture: Network simulation 74Network simulation techniques D.Moltchanov, TUT, 2012 10.10. Generic methodology Lecture: Network simulation 75Network simulation techniques D.Moltchanov, TUT, 2012 10.11. Other functionalities ns2 also provides:  errors on the datalink layer;  LAN and WLAN;  Routing;  Multicasting;  Mobile IP;  Di Serv;  MPLS;  ::: Lecture: Network simulation 76Network simulation techniques D.Moltchanov, TUT, 2012 11. Support tools: nam and xgraph Nam (Network AniMator):  packetlevel animation;  almost integrated with ns2. controls node link packet time Lecture: Network simulation 77Network simulation techniques D.Moltchanov, TUT, 2012 Lecture: Network simulation 78Network simulation techniques D.Moltchanov, TUT, 2012 Xgraph allows to make graphs:  frequently used with ns2;  simple visualizer. Lecture: Network simulation 79Network simulation techniques D.Moltchanov, TUT, 2012 12. Example: analyzing a bottleneck Environment is the same Create a simulator object set ns new Simulator Open the nam trace file set nf open out.nam w ns namtraceall nf Define a 'finish' procedure proc finish global ns nf ns flushtrace close nf exec nam out.nam exit 0 BODY Call the finish procedure after5 seconds simulation time ns at 5.0 "finish" Run the simulation ns run Lecture: Network simulation 80Network simulation techniques D.Moltchanov, TUT, 2012 Let's create four nodes: set n0 ns node set n1 ns node set n2 ns node set n3 ns node Duplex links between them with droptail queuing: ns duplexlink n0 n2 1Mb 10ms DropTail ns duplexlink n1 n2 1Mb 10ms DropTail ns duplexlink n3 n2 1Mb 10ms DropTail Relayout topology for goodlooking in nam: ns duplexlinkop n0 n2 orient rightdown ns duplexlinkop n1 n2 orient rightup ns duplexlinkop n2 n3 orient right Lecture: Network simulation 81Network simulation techniques D.Moltchanov, TUT, 2012 What we get in nam: What is next:  two UDP agents with CBR sources at n0 and n1;  null agent at node n3. Lecture: Network simulation 82Network simulation techniques D.Moltchanov, TUT, 2012 We use these commands: CreateaUDPagentandattachittonoden0 set udp0 new Agent/UDP ns attachagent n0 udp0 CreateaCBRtrafficsourceandattachittoudp0 set cbr0 new Application/Traffic/CBR cbr0 set packetSize 500 cbr0 set interval 0.005 cbr0 attachagent udp0 CreateaUDPagentandattachittonoden1 set udp1 new Agent/UDP ns attachagent n1 udp1 CreateaCBRtrafficsourceandattachittoudp1 set cbr1 new Application/Traffic/CBR cbr1 set packetSize 500 cbr1 set interval 0.005 cbr1 attachagent udp1 CreateaNullagentandattachittonoden3 set null0 new Agent/Null ns attachagent n3 nul Lecture: Network simulation 83Network simulation techniques D.Moltchanov, TUT, 2012 Connect two CBR agents to the Null agent: ns connect udp0 null0 ns connect udp1 null0 ... Schedule their sending times: ns at 0.5 "cbr0 start" ns at 1.0 "cbr1 start" ns at 4.0 "cbr1 stop" ns at 4.5 "cbr0 stop" Classic bottleneck scenario:  both sources send 200 pps with size 500 bytes;  n0 to n2: 0:8 Mbps, n1 to n2: 0:8 Mbps;  link between n2 and n3 is 1 Mbps. Questions: which packets get lost how many what is the e ect of queuing Lecture: Network simulation 84Network simulation techniques D.Moltchanov, TUT, 2012 12.1. Marking ows Set class to UDP sources rst: udp0 set class 1 udp1 set class 2 Set colors to ows: ns color 1 Blue ns color 2 Red Lecture: Network simulation 85Network simulation techniques D.Moltchanov, TUT, 2012 12.2. Monitoring a queue Add queue monitor: ns duplexlinkop n2 n3 queuePos 0.5 Everything is droptail on that queue Lecture: Network simulation 86Network simulation techniques D.Moltchanov, TUT, 2012 Why not to add some fairness with stochastic fair queuing (SFQ): ns duplexlink n3 n2 1Mb 10ms SFQ Everything is SFQ on that queue Example: http://www.isi.edu/nsnam/ns/tutorial/examples/example2.tcl Lecture: Network simulation 87Network simulation techniques D.Moltchanov, TUT, 2012 13. Routing Create 8 nodes: for set i 0 i 7 incr i set n(i) ns node Create circular topology: for set i 0 i 7 incr i ns duplexlink n(i) n(expr (i+1)7) 1Mb 10ms DropTail Lecture: Network simulation 88Network simulation techniques D.Moltchanov, TUT, 2012 Lecture: Network simulation 89Network simulation techniques D.Moltchanov, TUT, 2012 Send some data from n0 to n3: Create a UDP agentandattachittonode n(0) set udp0 new Agent/UDP ns attachagent n(0) udp0 Create a CBR traffic source andattachittoudp0 set cbr0 new Application/Traffic/CBR cbr0 set packetSize 500 cbr0 set interval 0.005 cbr0 attachagent udp0 set null0 new Agent/Null ns attachagent n(3) null0 ns connect udp0 null0 ns at 0.5 "cbr0 start" ns at 4.5 "cbr0 stop" By default trac goes over shortest path n0n1n2n3 Lecture: Network simulation 90Network simulation techniques D.Moltchanov, TUT, 2012 Introducing link failure: ns rtmodelat 1.0 down n(1) n(2) ns rtmodelat 2.0 up n(1) n(2) Lecture: Network simulation 91Network simulation techniques D.Moltchanov, TUT, 2012 Introduce destination vector (DV) routing to tackle the problem: ns rtproto DV . Example: http://www.isi.edu/nsnam/ns/tutorial/examples/example3.tcl Lecture: Network simulation 92Network simulation techniques D.Moltchanov, TUT, 2012 14. Wireless simulations in ns2 What we consider:  simple 2nodes wireless scenario;  nodes move within the area 500m 500m;  nodes start out initially at two opposite ends of the boundary;  nodes move towards each other and then move away;  TCP connection is setup between the two nodes;  packets are exchanged as nodes come within hearing range of each other;  as nodes move away, packets start getting dropped. We start with simple template:  just as usual some 'must do' things;  http://www.isi.edu/nsnam/ns/tutorial/examples/simplewireless.tcl Lecture: Network simulation 93Network simulation techniques D.Moltchanov, TUT, 2012 Array 'val()' is used to set basic parameters:  link layer (LL);  interface queue (IfQ);  MAC layer;  wireless channel nodes transmit and receive signals from... ====================================================================== Define options ====================================================================== set val(chan) Channel/WirelessChannel ; channel type set val(prop) Propagation/TwoRayGround ; radiopropagation model set val(ant) Antenna/OmniAntenna ; Antenna type set val(ll) LL ; Link layer type set val(ifq) Queue/DropTail/PriQueue ; Interface queue type set val(ifqlen) 50 ; max packet in ifq set val(netif) Phy/WirelessPhy ; network interface type set val(mac) Mac/80211 ; MAC type set val(rp) DSDV ; adhoc routing protocol set val(nn) 2 ; number of mobile nodes Lecture: Network simulation 94Network simulation techniques D.Moltchanov, TUT, 2012 Create an instance of the simulator: set ns new Simulator Setup trace supportand call the procedure 'traceall': set tracefd open simple.tr w ns traceall tracefd Create a topology object that keeps track of movements: set topo new Topography Provide the topography object with x and y coordinates: topo loadflatgrid 500 500 Next we create the object God (general operations director), as follows: creategod val(n  keeps track of wireless environment. Lecture: Network simulation 95Network simulation techniques D.Moltchanov, TUT, 2012 We have to con gure nodes before creating them providing e.g.:  type of adressing ( at or hierarchial or...);  routing protocol, LL, IfQ, MAC, etc. nsnodeconfig addressingType flat orhierarchicalorexpanded adhocRouting DSDV orDSR orTORA llType LL macType Mac/80211 propType "Propagation/TwoRayGround" ifqType "Queue/DropTail/PriQueue" ifqLen 50 phyType "Phy/WirelessPhy" antType "Antenna/OmniAntenna" channelType "Channel/WirelessChannel" topoInstance topo energyModel "EnergyModel" initialEnergy (in Joules) rxPower (in W) txPower (in W) agentTrace ON orOFF routerTrace ON orOFF macTrace ON orOFF movementTrace ON orOFF Lecture: Network simulation 96Network simulation techniques D.Moltchanov, TUT, 2012 We use the following con guration: Configure nodes ns nodeconfig adhocRouting val(rp) \ llType val(ll) \ macType val(mac) \ ifqType val(ifq) \ ifqLen val(ifqlen) \ antType val(ant) \ propType val(prop) \ phyType val(netif) \ topoInstance topo \ channelType val(chan) \ agentTrace ON \ routerTrace ON \ macTrace OFF \ movementTrace OFF Then we create two nodes disabling random movement: for set i 0 i val(nn) incr i set node(i) ns node node(i) randommotion 0 ; disable random motion Lecture: Network simulation 97Network simulation techniques D.Moltchanov, TUT, 2012 Give initial positions of nodes: Provide initial (X,Y, for now Z=0) coordinates for node(0) and node(1) node(0) set X 5.0 node(0) set Y 2.0 node(0) set Z 0.0 node(1) set X 390.0 node(1) set Y 385.0 node(1) set Z 0.0 Setting movement of nodes: Node(1) starts to move towards node(0) ns at 50.0 "node(1) setdest 25.0 20.0 15.0" ns at 10.0 "node(0) setdest 20.0 18.0 1.0" Node(1) then starts to move away from node(0) ns at 100.0 "node(1) setdest 490.0 480.0 15.0" ns at 50.0 "node (1) setdest 25.0 20.0 15.0": at 50.0s, it moves to (x=25,y=20) at 15m/s. Lecture: Network simulation 98Network simulation techniques D.Moltchanov, TUT, 2012 Setup trac ow between nodes: set tcp new Agent/TCP tcp set class 2 set sink new Agent/TCPSink ns attachagent node(0) tcp ns attachagent node(1) sink ns connect tcp sink set ftp new Application/FTP ftp attachagent tcp ns at 10.0 "ftp start" Setting up time when simulation ends and reset to initial states: for set i 0 i val(nn) incr i ns at 150.0 "node(i) reset"; ns at 150.0001 "stop" ns at 150.0002 "puts \"NS EXITING...\" ; ns halt" proc stop global ns tracefd close tracefd Lecture: Network simulation 99Network simulation techniques D.Moltchanov, TUT, 2012 Example: http://www.isi.edu/nsnam/ns/tutorial/examples/simplewireless.tcl What actually happens:  TCP ow starting at 10.0s from node0;  no packets are exchanged as nodes too far apart;  around 81.0s the routing info begins to be exchanged between both the nodes;  around 100.0s we see the rst TCP packet being received by node1;  the connection breaks down again around time 116.0s. Note the following:  all wireless traces starts with WL in their rst eld;  we enabled DSDV so we have routing messages. Lecture: Network simulation 100
Website URL
Comment