Done, your profile is created.Finish your profile by filling in the following fields
Forgot Password Earn Money,Free Notes
Password sent to your Email Id, Please Check your Mail
Updating Cart........ Please Wait........
Network simulation and simulators
Network simulation and simulators 11
Network simulation and simulators
Lecturer: Dmitri A. Moltchanov
E-mail: moltchancs.tut.Network simulation techniques D.Moltchanov, TUT, 2012
why do we need network simulation?
structure of a simulator
data collection and analysis
simulation with a given accuracy
variance reduction techniques
Practical aspects: ns2
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
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);
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;
collection of data;
statistical analysis of obtained data;
Dierences 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
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.
time consuming, it may take much more time that analytic;
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, buer, etc.);
preprocessing tools (hidden for a user);
data postprocessing tools.
Engine is the most important:
species 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
real time is used: time increments as ne as possible: to capture all state changes.
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
t t t
0 1 3
t t t t t t
0 1 2 3 4 5
t t t t t t t t
0 1 2 3 4 5 6 7
Figure 2: Illustration of dierent 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.
: there are no simulation specic 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 specic 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.
state of the stochastic process.
tells the occurrence time of the next event.
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;
E , i = 1; 2;::: , are corresponding events.
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 identied by event time and event type.
There are two general types of events:
these events modify the state of the system: arrivals/departures of customers.
these are events needed by additional tasks of simulation: run, stoppage, collection of data.
Lecture: Network simulation 14Network simulation techniques D.Moltchanov, TUT, 2012
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:
t t t t t t
0 1 2 3 4 5
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
insertion and deletion are made very easily;
location of the next event depend on the number of event types:
complexity is linear in time.
if the number of event types is large location is time consuming;
in this case dierent organization of the future event list should be considered.
Lecture: Network simulation 20