In lab Assignment 3 - Probability, Poisson Process, M/M/1 queues and NS2 Installation


This week you will learn about basic probability theory, poisson processes and M/M/1 queues in addition to installing NS2.

What's new in this week:

Why do you need to learn all this?

Part I (adapted from Wikipedia)

*Probability Theory:

The word probability derives from the Latin probare (to prove, or to test). Informally, probable is one of several words applied to uncertain events or knowledge, being closely related in meaning to likely, risky, hazardous, and doubtful. Chance, odds, and bet are other words expressing similar notions. Just as the theory of mechanics assigns precise definitions to such everyday terms as work and force, the theory of probability attempts to quantify the notion of probable.

Basic Concepts
Random Experiment: An experiment is said to be a random experiment, if it's out-come can't be predicted with certainty.
Example; If a coin is tossed, we can't say, whether head or tail will appear. So it is a random experiment.
 

Sample Space: The sent of all possible out-comes of an experiment is called the sample space. It is denoted by 'S' and its number of elements are n(s).
Example; In throwing a dice, the number that appears at top is any one of 1,2,3,4,5,6. So here:
S ={1,2,3,4,5,6} and n(s) = 6
Similarly in the case of a coin, S={Head,Tail} or {H,T} and n(s)=2.
The elements of the sample space are called sample point or event point.
 

Event: Every subset of a sample space is an event. It is denoted by 'E'.
Example: In throwing a dice S={1,2,3,4,5,6}, the appearance of an event number will be the event E={2,4,6}.
Clearly E is a sub set of S.
 

Simple event; An event, consisting of a single sample point is called a simple event.
Example: In throwing a dice, S={1,2,3,4,5,6}, so each of {1},{2},{3},{4},{5} and {6} are simple events.
Compound event: A subset of the sample space, which has more than on element is called a mixed event.
Example: In throwing a dice, the event of appearing of odd numbers is a compound event, because E={1,3,5} which has '3' elements.
 

Equally likely events: Events are said to be equally likely, if we have no reason to believe that one is more likely to occur than the other.
Example: When a dice is thrown, all the six faces {1,2,3,4,5,6} are equally likely to come up.
 

Exhaustive events: When every possible out come of an experiment is considered.
Example: A dice is thrown, cases 1,2,3,4,5,6 form an exhaustive set of events.
Classical definition of probability:
If 'S' be the sample space, then the probability of occurrence of an event 'E' is defined as:
P(E) = n(E)/N(S) = number of elements in 'E' / number of elements in sample space 'S'
Example: Find the probability of getting a tail in tossing of a coin.
Solution:
Sample space S = {H,T}  and n(s) = 2
Event 'E' = {T}  and n(E) = 1
therefore P(E) = n(E)/n(S) = ½


Note: This definition is not true, if
(a) The events are not equally likely.
(b) The possible outcomes are infinite.
an interesting link with a fun tutorial and interactive problems is located at http://www.mathgoodies.com/lessons/vol6/intro_probability.html try it!

Conditional Probability: When you need to find the probability of an event given information about the occurrence of another event. Say I want to find the probability of "Anirban wears a red shirt" given that you know "Anirban wore a colored shirt today". This is formulated in the following manner,

P(Anirban wears a red shirt/Anirban wore a colored shirt) and we calculate it in the following manner.

Say Event R defines - Anirban wears a red shirt and event C defines - Anirban wore a colored shirt, we need to calculate P(R/C)

P(R/C) =  P(R)P(C/R)/ P(Ri)P(C/Ri) + P(Ri+1)P(C/Ri+1)  + P(Ri+2)P(C/Ri+2)....

This is known as the Bayes' Theorem.

*Poisson Process:

A Poisson process, named after the French mathematician Siméon-Denis Poisson (1781 - 1840), is a stochastic process which is defined in terms of the occurrences of events. A stochastic process N(t) is a (time-homogeneous, one-dimensional) Poisson process if,

where the positive number λ is a fixed parameter, known as the rate parameter. In words, this means that the random variable N(t + τ) − N(t), giving the number of occurrences in the time interval [t,t + τ], has a Poisson distribution with parameter λτ.

An important difference to understand is the difference between the poisson process and the poisson random variable (rv). A poisson rv is defined just like the the equation above except that the RHS does not have the τ . If you are given a column of numbers in a file, and you are told that this "distribution follows a poisson distribution", what that means is that each of the values in the column is actually a poisson rv, and on the whole if you plot the values, you will observe that all the values seem to follow a poisson behavior. A process can be considered to be the entity which generated all these rv's.

More interesting material can be found at

Example:

                    
 
*M/M/1 queue:

Computer networks are often modeled as M/M/1 queues. The reason for this is that packets leaving your computer do not magically end up at the destination. They have to pass through network elements such as routers, switches, bridges and more. Each of these elements has a fixed amount of memory available for storing incoming packets. Once packets arrive into this memory and form a queue they are serviced by the network element, in the form of doing a look-up operation wherein the router/switch etc. decides where next to forward the current packet.

One important concept of M/M/1, is that it represents a queue being serviced by a server. The input process or the arrival process of the packets into the queue is assumed to be poisson and the service rate is assumed to be exponential. And this process is memoryless. What this implies is that no matter when you start to take measurements, or look at the system, you will always observe the same distributions of packets arriving to the router and the router servicing them. In more elaborate terms, if you start measuring how packets are arriving and how they are being serviced at time 10:00 AM and then again at 11:00 AM you will find that even though the raw numbers may be different the distribution of how packets arrive and how they are serviced is still the same.

M/M/1 can be applied to systems that meet certain criteria. But if the system you are designing can be modeled as an M/M/1 queueing system, you are in luck. The equations describing a M/M/1 queueing system are fairly straight forward and easy to use.

First we define p(row), the traffic intensity (sometimes called occupancy). It is defined as the average arrival rate (lambda) divided by the average service rate (mu). For a stable system the average service rate should always be higher than the average arrival rate. (Otherwise the queues would rapidly race towards infinity). Thus p should always be less than one. Also note that we are talking about average rates here, instantaneous arrival rate may exceed the service rate. Over a longer time period, the service rate should always exceed arrival rate.

  Traffic intensity equation

Mean number of customers in the system (N) can be found using the following equation:

Number of users in an M/M/1 queueing system

You can see from the above equation that as p approaches 1 number of customers would become very large. This can be easily justified intuitively. p will approach 1 when the average arrival rate starts approaching the average service rate. In this situation, the server would always be busy hence leading to a queue build up (large N). 

Lastly we obtain the total waiting time (including the service time):

Wait time in an M/M/1 queueing system

Again we see that as mean arrival rate (lambda) approaches mean service rate (mu), the waiting time becomes very large.

A useful tutorial can be found at http://www.dcs.ed.ac.uk/home/jeh/Simjava/queueing/mm1_q/mm1_q.html  .

Part II: Installing NS2

 
What is NS2? NS2 is an event driven network simulator developed at UC Berkeley that simulates variety of IP networks.t implements network protocols such as TCP and UPD, traffic source behavior such as FTP, Telnet, Web, CBR and VBR, router queue management mechanism such as Drop Tail, RED and CBQ, routing algorithms such as Dijkstra, and more. NS also implements multicasting and some of the MAC layer protocols for LAN simulations. Additional information for Ns2 you can find in the NS by example Site
An introduction for Ns2, by Lap Kong Law, can be find here

Now we will see the installation procedure of Ns2. Download the Network Simulator Ns2 to your local drive and copy it to the location: /home/projects/cs164/cs164_06spr/your_user_name/. Untar it and then go inside the ns-allinone-2.29 folder and type install, in order to begin installation of ns2.

After the installation of Ns2 has finished you will see in your terminal that you have to make some corrections, in order the simulator to work. The message that you will see will be like the following:

Please put:

/home/projects/cs164/cs164_06spr/aggelos/ns-allinone-2.29/bin:/home/projects/cs164/cs164_06spr/aggelos/ns-allinone-2.29/tcl8.4.5/unix:/home/projects/
cs164/cs164_06spr/aggelos/ns-allinone-2.29/tk8.4.5/unix
into your PATH environment; so that you'll be able to run itm/tclsh/wish/xgraph.


IMPORTANT NOTICES:

(1) You MUST put

/home/projects/cs164/cs164_06spr/aggelos/ns-allinone-2.29/otcl- 1.11, /home/projects/cs164/cs164_06spr/aggelos/ns-allinone-2.29/lib,
into your LD_LIBRARY_PATH environment variable.
If it complains about X libraries, add path to your X libraries
into LD_LIBRARY_PATH.
If you are using csh, you can set it like:
setenv LD_LIBRARY_PATH <paths>
If you are using sh, you can set it like:
export LD_LIBRARY_PATH=<paths>

(2) You MUST put

/home/projects/cs164/cs164_06spr/aggelos/ns-allinone-2.29/tcl8.
4.11/library into your TCL_LIBRARY environmental
variable. Otherwise ns/nam will complain during startup.

(3) [OPTIONAL] To save disk space, you can now delete directories tcl8.4.11
and tk8.4.11. They are now installed under /home/projects/cs164/cs164_06spr/a
ggelos/ns-allinone-2.29/{bin,include,lib}

After these steps, you can now run the ns validation suite with
cd ns-2.29; ./validate

For trouble shooting, please first read ns problems page
http://www.isi.edu/nsnam/ns/ns-problems.html. Also search the ns mailing list ar
chive
for related posts.

/home/projects/cs164/cs164_06spr/aggelos/ns-allinone-2.29
 
In order to do these modifications you will have to add some lines of code into the .bashrc file, which is located in your home directory. WARNING:Before you make any modifications to the .bashrc file have a backup, in case something goes wrong

In detail you will have to add the following lines:

In the above lines, replace aggelos with your username. That's all that you have to change in the .bashrc file

In the terminal do not run the command .validate because it takes a long time to run .... Additional resources and information you can find in the Official Site of Ns2
That's about it :-). Now we can experiment with an simple simulation in ns2

Part 2 - A Simple Simulation

This section shows a simple NS simulation script and explains what each line does. Example 1 is an OTcl script that creates the simple network configuration and runs the simulation scenario in Figure 1. To run this simulation, download "ns-simple.tcl" and type "ns ns-simple.tcl" at your shell prompt.

Figure 1. A Simple Network Topology and Simulation Scenario

This network consists of 4 nodes (n0, n1, n2, n3) as shown in above figure. The duplex links between n0 and n2, and n1 and n2 have 2 Mbps of bandwidth and 10 ms of delay. The duplex link between n2 and n3 has 1.7 Mbps of bandwidth and 20 ms of delay. Each node uses a DropTail queue, of which the maximum size is 10. A "tcp" agent is attached to n0, and a connection is established to a tcp "sink" agent attached to n3. As default, the maximum size of a packet that a "tcp" agent can generate is 1KByte. A tcp "sink" agent generates and sends ACK packets to the sender (tcp agent) and frees the received packets. A "udp" agent that is attached to n1 is connected to a "null" agent attached to n3. A "null" agent just frees the packets received. A "ftp" and a "cbr" traffic generator are attached to "tcp" and "udp" agents respectively, and the "cbr" is configured to generate 1 KByte packets at the rate of 1 Mbps. The "cbr" is set to start at 0.1 sec and stop at 4.5 sec, and "ftp" is set to start at 1.0 sec and stop at 4.0 sec.

#Create a simulator object
set ns [new Simulator]

#Define different colors for data flows (for NAM)
$ns color 1 Blue
$ns color 2 Red

#Open the NAM trace file
set nf [open out.nam w]
$ns namtrace-all $nf

#Define a 'finish' procedure
proc finish {} {
global ns nf
$ns flush-trace
#Close the NAM trace file
close $nf
#Execute NAM on the trace file
exec nam out.nam &
exit 0
}

#Create four nodes
set n0 [$ns node]
set n1 [$ns node]
set n2 [$ns node]
set n3 [$ns node]

#Create links between the nodes
$ns duplex-link $n0 $n2 2Mb 10ms DropTail
$ns duplex-link $n1 $n2 2Mb 10ms DropTail
$ns duplex-link $n2 $n3 1.7Mb 20ms DropTail

#Set Queue Size of link (n2-n3) to 10
$ns queue-limit $n2 $n3 10

#Give node position (for NAM)
$ns duplex-link-op $n0 $n2 orient right-down
$ns duplex-link-op $n1 $n2 orient right-up
$ns duplex-link-op $n2 $n3 orient right

#Monitor the queue for link (n2-n3). (for NAM)
$ns duplex-link-op $n2 $n3 queuePos 0.5


#Setup a TCP connection
set tcp [new Agent/TCP]
$tcp set class_ 2
$ns attach-agent $n0 $tcp
set sink [new Agent/TCPSink]
$ns attach-agent $n3 $sink
$ns connect $tcp $sink
$tcp set fid_ 1

#Setup a FTP over TCP connection
set ftp [new Application/FTP]
$ftp attach-agent $tcp
$ftp set type_ FTP


#Setup a UDP connection
set udp [new Agent/UDP]
$ns attach-agent $n1 $udp
set null [new Agent/Null]
$ns attach-agent $n3 $null
$ns connect $udp $null
$udp set fid_ 2

#Setup a CBR over UDP connection
set cbr [new Application/Traffic/CBR]
$cbr attach-agent $udp
$cbr set type_ CBR
$cbr set packet_size_ 1000
$cbr set rate_ 1mb
$cbr set random_ false


#Schedule events for the CBR and FTP agents
$ns at 0.1 "$cbr start"
$ns at 1.0 "$ftp start"
$ns at 4.0 "$ftp stop"
$ns at 4.5 "$cbr stop"

#Detach tcp and sink agents (not really necessary)
$ns at 4.5 "$ns detach-agent $n0 $tcp ; $ns detach-agent $n3 $sink"

#Call the finish procedure after 5 seconds of simulation time
$ns at 5.0 "finish"

#Print CBR packet size and interval
puts "CBR packet size = [$cbr set packet_size_]"
puts "CBR interval = [$cbr set interval_]"

#Run the simulation
$ns run
 
 

Example 1. A Simple NS Simulation Script

The following is the explanation of the script above. In general, an NS script starts with making a Simulator object instance.

  • set ns [new Simulator]: generates an NS simulator object instance, and assigns it to variable ns (italics is used for variables and values in this section). What this line does is the following:
     
    • Initialize the packet format (ignore this for now)
    • Create a scheduler (default is calendar scheduler)
    • Select the default address format (ignore this for now)
       

    The "Simulator" object has member functions that do the following:
     

    • Create compound objects such as nodes and links (described later)
    • Connect network component objects created (ex. attach-agent)
    • Set network component parameters (mostly for compound objects)
    • Create connections between agents (ex. make connection between a "tcp" and "sink")
    • Specify NAM display options
    • Etc.
       

    Most of member functions are for simulation setup (referred to as plumbing functions) and scheduling, however some of them are for the NAM display. The "Simulator" object member function implementations are located in the "ns-2/tcl/lib/ns-lib.tcl" file.
     

  • $ns color fid color: is to set color of the packets for a flow specified by the flow id (fid). This member function of "Simulator" object is for the NAM display, and has no effect on the actual simulation.
     
  • $ns namtrace-all file-descriptor: This member function tells the simulator to record simulation traces in NAM input format. It also gives the file name that the trace will be written to later by the command $ns flush-trace. Similarly, the member function trace-all is for recording the simulation trace in a general format.
     
  • proc finish {}: is called after this simulation is over by the command $ns at 5.0 "finish". In this function, post-simulation processes are specified.
     
  • set n0 [$ns node]: The member function node creates a node. A node in NS is compound object made of address and port classifiers (described in a later section). Users can create a node by separately creating an address and a port classifier objects and connecting them together. However, this member function of Simulator object makes the job easier. To see how a node is created, look at the files: "ns-2/tcl/libs/ns-lib.tcl" and "ns-2/tcl/libs/ns-node.tcl".
     
  • $ns duplex-link node1 node2 bandwidth delay queue-type: creates two simplex links of specified bandwidth and delay, and connects the two specified nodes. In NS, the output queue of a node is implemented as a part of a link, therefore users should specify the queue-type when creating links. In the above simulation script, DropTail queue is used. If the reader wants to use a RED queue, simply replace the word DropTail with RED. The NS implementation of a link is shown in a later section. Like a node, a link is a compound object, and users can create its sub-objects and connect them and the nodes. Link source codes can be found in "ns-2/tcl/libs/ns-lib.tcl" and "ns-2/tcl/libs/ns-link.tcl" files. One thing to note is that you can insert error modules in a link component to simulate a lossy link (actually users can make and insert any network objects). Refer to the NS documentation to find out how to do this.
     
  • $ns queue-limit node1 node2 number: This line sets the queue limit of the two simplex links that connect node1 and node2 to the number specified. At this point, the authors do not know how many of these kinds of member functions of Simulator objects are available and what they are. Please take a look at "ns-2/tcl/libs/ns-lib.tcl" and "ns-2/tcl/libs/ns-link.tcl", or NS documentation for more information.
     
  • $ns duplex-link-op node1 node2 ...: The next couple of lines are used for the NAM display. To see the effects of these lines, users can comment these lines out and try the simulation.

Now that the basic network setup is done, the next thing to do is to setup traffic agents such as TCP and UDP, traffic sources such as FTP and CBR, and attach them to nodes and agents respectively.

  • set tcp [new Agent/TCP]: This line shows how to create a TCP agent. But in general, users can create any agent or traffic sources in this way. Agents and traffic sources are in fact basic objects (not compound objects), mostly implemented in C++ and linked to OTcl. Therefore, there are no specific Simulator object member functions that create these object instances. To create agents or traffic sources, a user should know the class names these objects (Agent/TCP, Agnet/TCPSink, Application/FTP and so on). This information can be found in the NS documentation or partly in this documentation. But one shortcut is to look at the "ns-2/tcl/libs/ns-default.tcl" file. This file contains the default configurable parameter value settings for available network objects. Therefore, it works as a good indicator of what kind of network objects are available in NS and what are the configurable parameters.
     
  • $ns attach-agent node agent: The attach-agent member function attaches an agent object created to a node object. Actually, what this function does is call the attach member function of specified node, which attaches the given agent to itself. Therefore, a user can do the same thing by, for example, $n0 attach $tcp. Similarly, each agent object has a member function attach-agent that attaches a traffic source object to itself.
     
  • $ns connect agent1 agent2: After two agents that will communicate with each other are created, the next thing is to establish a logical network connection between them. This line establishes a network connection by setting the destination address to each others' network and port address pair.

Assuming that all the network configuration is done, the next thing to do is write a simulation scenario (i.e. simulation scheduling). The Simulator object has many scheduling member functions. However, the one that is mostly used is the following:

  • $ns at time "string": This member function of a Simulator object makes the scheduler (scheduler_ is the variable that points the scheduler object created by [new Scheduler] command at the beginning of the script) to schedule the execution of the specified string at given simulation time. For example, $ns at 0.1 "$cbr start" will make the scheduler call a start member function of the CBR traffic source object, which starts the CBR to transmit data. In NS, usually a traffic source does not transmit actual data, but it notifies the underlying agent that it has some amount of data to transmit, and the agent, just knowing how much of the data to transfer, creates packets and sends them.

After all network configuration, scheduling and post-simulation procedure specifications are done, the only thing left is to run the simulation. This is done by $ns run.

 

The above example and information come from the Worcester Polytechnic Institute and from the site Ns by Example. There you can find many examples for Ns Simulator and additional resources.
 

Now that we saw a simple example of how Ns work, try to change the bandwidth of the links between the nodes and watch the drops of the packets in comparison with the bandwidth of the links.

Appendix : None

When you are writing your programs keep in mind the 2 holy rules of programming: