All About NS2

NS2 consists of two key languages: C++ and Object-oriented Tool Command Language (OTcl). While the C++ defines the internal mechanism (i.e.,a back end) of the simulation objects, the OTcl sets up simulation by assembling and configuring the objects as well as scheduling discrete events (i.e.,a front end). The C++ and the OTcl are linked together using TclCL. Mapped to a C++ object, variables in the OTcl domains are sometimes referred to as handles. Conceptually, a handle (e.g., n as a Node handle) is just a string (e.g.,o10) in the OTcl domain, and does not contain any functionality. Instead, the functionality(e.g., receiving a packet) is defined in the mapped C++ object (e.g., of class Connector). In the OTcl domain, a handle acts as a front end which interacts with users and other OTcl objects. It may defines its own procedures and variables to facilitate the interaction. Note that the member procedures and variables in the OTcl domain are called instance procedures(instprocs) and instance variables(instvars), respectively. Before proceeding further, the readers are encouraged to learn C++ and OTcl languages and we include it on our previous posts.

NS2 provides a large number of built in C++ objects. It is advisable to use these C++ objects to set up a simulation using a Tcl simulation script. However, advance users may find these objects insufficient. They need to develop their own C++ objects, and use a OTcl configuration interface to put together these objects. After simulation, NS2 outputs either text-based or animation-based simulation results. To interpret these results graphically and interactively, tools such as NAM (Network AniMator) and XGraph are used. To analyze a particular behavior of the network, users can extract a relevant subset of text-based data and transform it to a more conceivable presentation.

INSTALLATION

NS2 is a free simulation tool. It runs on various platforms including UNIX (or Linux), Windows, and Mac systems. Being developed in the Unix environment, with no surprise, NS2 has the smoothest ride there, and so does its installation.

NS2 source codes are distributed in two forms: all-in-one suite and the component-wise. With the all-in-one package, users get all the required components along with some optional components. This is basically a recommended choice for the beginners. This package provides an “install” script which configures the NS2 environment and creates NS2 executable file using the “make” utility. The current all-in-one suite consists of the following main components :

• • NS release 2.30,

  • Tcl/Tk release 8.4.13,

  • OTcl release 1.12, and

  • TclCL release 1.18.

and the following are the optional components:

• • NAM release 1.12: NAM is an animation tool for viewing network simulation traces and packet traces.

  • Zlib version 1.2.3: This is the required library for NAM.

  • Xgraph version 12.1: This is a data plotter with interactive buttons for panning, zooming, printing, and selecting display options.

The idea of the component-wise approach is to obtain the above pieces and install them individually. This option save considerable amount of downloading time and memory space. However, it could be troublesome for the beginners, and is therefore recommended only for experienced users.

Click the following links to know more about installation:

• NS2 INSTALLATION ON LINUX PLATFORM

• NS2 INSTALLATION ON WINDOWS PLATFORM

NS2 DIRECTORY AND LANGUAGES

NS2 DIRECTORY

Normally NS2 is installed in the directory nsallinone-2.35 and we can see that in the following figure.

Figure given below shows the directory structure under directory nsallinone-2.35.

NS2 LANGUAGES

The network simulator is a bank of of different network and protocol objects.

Each of these two languages has its own strengths and weaknesses. NS2 beautifully integrates these two languages to draw out their strengths. For most of the time, you would not need to know the integration mechanism. But you need to know the strength and weaknesses of these two languages in order to apply them properly.

OTCL [Object Oriented Tool Command Language]

OTCL is short for MIT Object TCL and it is an extension to the TCL/TK for object oriented programming.An OTcl program can run on the fly without the need for compilation. Upon execution, the interpreter translates OTcl instructions to machine code understandable to the operating system line by line.Therefore, OTcl codes run more slowly than C++ codes do. The upside of OTcl codes is that every change takes effect immediately.

OTcl helps in the following way:

• 1. With the help of OTcl, we can describe different network topologies.

  2. It helps us to specify the protocols and their applications.

  3. It allows fast development.

  4. Tcl is compatible with many platforms and it is flexible for integration.

  5. Tcl is very easy to use and it is available in free.

C++

Most important parts and kernal of NS2 is created by using C++. A C++ program needs to be compiled (i.e., translated) into the executable machine code. Since the executable is in the form of machine code, C++ program is very fast to run. However, the compilation process can be quite annoying. Every tiny little change like adding “int x = 0;” will take few seconds.

C++ helps in the following way:

• 1. It helps to increase the efficiency of simulation.

  2. Its is used to provide details of the protocols and their operation.

  3. It is used to reduce packet and event processing time.

WHY TWO LANGUAGES???

The main requirement of simulator is;

• • Detailed simulation of Protocol: Run-time speed.

  • Varying parameters or configuration: easy to use.

C++ is fast to run but slower to code and change. Incase of OTCL, it is easy to code but runs slowly.This is the major reason that we are going behind the using of two languages for scripting and for kernal.

====================================================================

after installing gawk, we have to run the awk script using command;

gawk -f <awk file name> <trace file name>

gawk -f file.awk file.tr

The ‘-f’ instructs the awk utility to get the awk program from the source file i.e from .awk file.

After entering command you will get values.

AWK SCRIPTS

1. For calculating Throughput, Click here

2. For calculating End to End Delay,Routing Load and Packet Density Fraction, Click here

3. For calculating Jitter, Click here

4. For calculating energy, Click here

5. For calculating network statistics, Click here

6. For printing congestion window, Click here

7. For calculating all network statistics, Click here

8. For calculating final node position and energy of node, Click here

Note :

1. This awk script is for new trace format files.

2. Copy this awk files to the directory where tcl script is saved.

3. Change initial values as per your need.

PERL Script

Perl is a general-purpose programming language originally developed for text manipulation and now used for a wide range of tasks including system administration, web development, network programming, GUI development, and more.

The language is intended to be practical (easy to use, efficient, complete) rather than beautiful (tiny, elegant, minimal). Its major features are that it's easy to use, supports both procedural and object-oriented (OO) programming, has powerful built-in support for text processing, and has one of the world's most impressive collections of third-party modules.

Like awk script, perl script can also be used to perform post analysis of trace files. Perl script are simple any tiny than awk scripts.

To run a Perl program from the Unix command line:

Alternatively, put this as the first line of your script:

...and run the script as /path/to/script.pl. Of course, it'll need to be executable first, so chmod 755 script.pl (under Unix).

(This start line assumes you have the env program. You can also put directly the path to your perl executable, like in #!/usr/bin/perl ).

__________________________________________________________ Function Returns ----------- ------------------------------------------ abs(x) absolute value of x, |x| acos(x) arc-cosine of x asin(x) arc-sine of x atan(x) arc-tangent of x cos(x) cosine of x, x is in radians. cosh(x) hyperbolic cosine of x, x is in radians erf(x) error function of x exp(x) exponential function of x, base e inverf(x) inverse error function of x invnorm(x) inverse normal distribution of x log(x) log of x, base e log10(x) log of x, base 10 norm(x) normal Gaussian distribution function rand(x) pseudo-random number generator sgn(x) 1 if x > 0, -1 if x < 0, 0 if x=0 sin(x) sine of x, x is in radians sinh(x) hyperbolic sine of x, x is in radians sqrt(x) the square root of x tan(x) tangent of x, x is in radians tanh(x) hyperbolic tangent of x, x is in radians ___________________________________________________________ Bessel, gamma, ibeta, igamma, and lgamma functions are also supported. Many functions can take complex arguments. Binary and unary operators are also supported.

The supported operators in Gnuplot are the same as the corresponding operators in the C programming language, except that most operators accept integer, real, and complex arguments. The ** operator (exponentiation) is supported as in FORTRAN. Parentheses may be used to change the order of evaluation. The variable names x, y, and z are used as the default independent variables.

3. THE plot AND splot COMMANDS

plot and splot are the primary commands in Gnuplot. They plot functions and data in many many ways. plot is used to plot 2-d functions and data, while splot plots 3-d surfaces and data.

Syntax: plot {[ranges]} {[function] | {"[datafile]" {datafile-modifiers}}} {axes [axes] } { [title-spec] } {with [style] } {, {definitions,} [function] ...}

where either a [function] or the name of a data file enclosed in quotes is supplied. For more complete descriptions, type: help plot help plot with help plot using or help plot smooth .

3.1 Plotting Functions

To plot functions simply type: plot [function] at the gnuplot> prompt.

For example, try:

gnuplot> plot sin(x)/x gnuplot> splot sin(x*y/20) gnuplot> plot sin(x) title 'Sine Function', tan(x) title 'Tangent'

3.2 Plotting Data

Discrete data contained in a file can be displayed by specifying the name of the data file (enclosed in quotes) on the plot or splot command line. Data files should have the data arranged in columns of numbers. Columns should be separated by white space (tabs or spaces) only, (no commas). Lines beginning with a # character are treated as comments and are ignored by Gnuplot. A blank line in the data file results in a break in the line connecting data points.

For example your data file, force.dat , might look like:

# This file is called force.dat # Force-Deflection data for a beam and a bar # Deflection Col-Force Beam-Force 0.000 0 0 0.001 104 51 0.002 202 101 0.003 298 148 0.0031 290 149 0.004 289 201 0.0041 291 209 0.005 310 250 0.010 311 260 0.020 280 240

gnuplot> plot "force.dat" using 1:2 title 'Column', \ "force.dat" using 1:3 title 'Beam'

Do not type blank space after the line continuation character, "\" .

Your data may be in multiple data files. In this case you may make your plot by using a command like:

gnuplot> plot "fileA.dat" using 1:2 title 'data A', \ "fileB.dat" using 1:3 title 'data B'

gnuplot> help splot datafile

4. CUSTOMIZING YOUR PLOT

Many items may be customized on the plot, such as the ranges of the axes, the labels of the x and y axes, the style of data point, the style of the lines connecting the data points, and the title of the entire plot.

4.1 plot command customization

Customization of the data columns, line titles, and line/point style are specified when the plot command is issued. Customization of the data columns and line titles were discussed in section 3.

Plots may be displayed in one of eight styles: lines, points, linespoints, impulses, dots, steps, fsteps, histeps, errorbars, xerrorbars, yerrorbars, xyerrorbars, boxes, boxerrorbars, boxxyerrorbars, financebars, candlesticks or vector To specify the line/point style use the plot command as follows:

gnuplot> plot "force.dat" using 1:2 title 'Column' with lines, \ "force.dat" u 1:3 t 'Beam' w linespoints

Note that the words: using , title , and with can be abbreviated as: u , t , and w . Also, each line and point style has an associated number.

4.2 set command customization

Customization of the axis ranges, axis labels, and plot title, as well as many other features, are specified using the set command. Specific examples of the set command follow. (The numerical values used in these examples are arbitrary.) To view your changes type: replot at the gnuplot> prompt at any time.

Create a title: > set title "Force-Deflection Data" Put a label on the x-axis: > set xlabel "Deflection (meters)" Put a label on the y-axis: > set ylabel "Force (kN)" Change the x-axis range: > set xrange [0.001:0.005] Change the y-axis range: > set yrange [20:500] Have Gnuplot determine ranges: > set autoscale Move the key: > set key 0.01,100 Delete the key: > unset key Put a label on the plot: > set label "yield point" at 0.003, 260 Remove all labels: > unset label Plot using log-axes: > set logscale Plot using log-axes on y-axis: > unset logscale; set logscale y Change the tic-marks: > set xtics (0.002,0.004,0.006,0.008) Return to the default tics: > unset xtics; set xtics auto

Other features which may be customized using the set command are: arrow, border, clip, contour, grid, mapping, polar, surface, time, view, and many more. The best way to learn is by reading the on-line help information, trying the command, and reading the Gnuplot manual.

5. PLOTTING DATA FILES WITH OTHER COMMENT CHARACTERS

If your data file has a comment character other than # you can tell Gnuplot about it. For example, if your data file has "%" comment characters (for Matlab compatability), typing

gnuplot> set datafile commentschars "#%"

indicates that either a "#" or a "%" character starts a comment.

6. GNUPLOT SCRIPTS

Sometimes, several commands are typed to create a particular plot, and it is easy to make a typographical error when entering a command. To stream- line your plotting operations, several Gnuplot commands may be combined into a single script file. For example, the following file will create a customized display of the force-deflection data:

# Gnuplot script file for plotting data in file "force.dat" # This file is called force.p set autoscale # scale axes automatically unset log # remove any log-scaling unset label # remove any previous labels set xtic auto # set xtics automatically set ytic auto # set ytics automatically set title "Force Deflection Data for a Beam and a Column" set xlabel "Deflection (meters)" set ylabel "Force (kN)" set key 0.01,100 set label "Yield Point" at 0.003,260 set arrow from 0.0028,250 to 0.003,280 set xr [0.0:0.022] set yr [0:325] plot "force.dat" using 1:2 title 'Column' with linespoints , \ "force.dat" using 1:3 title 'Beam' with points

Then the total plot can be generated with the command: gnuplot> load 'force.p'

7. CURVE-FITTING WITH GNUPLOT

To fit the data in force.dat with a function use the commands:

f1(x) = a1*tanh(x/b1) # define the function to be fit a1 = 300; b1 = 0.005; # initial guess for a1 and b1 fit f1(x) 'force.dat' using 1:2 via a1, b1 Final set of parameters Asymptotic Standard Error ======================= ========================== a1 = 308.687 +/- 10.62 (3.442%) b1 = 0.00226668 +/- 0.0002619 (11.55%)

and the commands:

f2(x) = a2 * tanh(x/b2) # define the function to be fit a2 = 300; b2 = 0.005; # initial guess for a and b fit f2(x) 'force.dat' using 1:3 via a2, b2 Final set of parameters Asymptotic Standard Error ======================= ========================== a2 = 259.891 +/- 12.82 (4.933%) b2 = 0.00415497 +/- 0.0004297 (10.34%)

The curve-fit and data may now be plotted with the commands:

set key 0.018,150 title "F(x) = A tanh (x/B)" # title to key! set title "Force Deflection Data \n and curve fit" # note newline! set pointsize 1.5 # larger point! set xlabel 'Deflection, {/Symbol D}_x (m)' # Greek symbols! set ylabel 'Force, {/Times-Italic F}_A, (kN)' # italics! plot "force.dat" using 1:2 title 'Column data' with points 3, \ "force.dat" using 1:3 title 'Beam data' with points 4, \ a1 * tanh( x / b1 ) title 'Column-fit: A=309, B=0.00227', \ a2 * tanh( x / b2 ) title 'Beam-fit: A=260, B=0.00415'

8. SPREAD-SHEET LIKE CALCULATIONS ON DATA

Gnuplot can mathematically modify your data column by column:

to plot sin( col.3 + col.1 ) vs. 3 * col.2 type:

plot 'force.dat' using (3*$2):(sin($3+$1))

9. MULTI-PLOT

Gnuplot can plot more than one figure in a frame ( like subplot in matlab ) i.e., try:

set multiplot; # get into multiplot mode set size 1,0.5; set origin 0.0,0.5; plot sin(x); set origin 0.0,0.0; plot cos(x) unset multiplot # exit multiplot mode

10. GNUPLOT DEMO FILES AND THE GNUPLOT FAQ

Most of Gnuplot's current features are illustrated in one or more of the Gnuplot demonstration files. To run the demo's yourself, download and unzip demo.zip, start Gnuplot from the resulting demo directory, and type

load "all.dem"

The Gnuplot feature you are looking for will probably be illustrated in one of the demo files. Gnuplot 4.2 also has an extensive FAQ.

11. HARD-COPY (PLOTTING ON PAPER)

You can create a PostScript file of your plot by using the following files and commands. First, download and save the following general-purpose Gnuplot script: save.plt

# File name: save.plt - saves a Gnuplot plot as a PostScript file # to save the current plot as a postscript file issue the commands: # gnuplot> load 'saveplot' # gnuplot> !mv my-plot.ps another-file.ps set size 1.0, 0.6 set terminal postscript portrait enhanced mono dashed lw 1 "Helvetica" 14 set output "my-plot.ps" replot set terminal x11 set size 1,1

Then simply type the following commands to create and print the plot

gnuplot> load 'save.plt' gnuplot> !mv my-plot.ps force.ps gnuplot> !lpr force.ps

The PostScript files produced by Gnuplot may be read and edited with a text editor.

12. ADVANCED COMPUTATION AND VISUALIZATION

Gnuplot is used for plotting in a free and open Matlab-like programming environment called Octave.

13. PRINTING TWO FIGURES ON ONE PAGE

If you would like two figures to be laser-printed on the same page, you may use the following shell script. Create file cat2 , below, and make the file executable by typing: unix% chmod +x cat2

# cat2: Shell script for putting two Gnuplot plots on one page echo %! > g.ps echo gsave >> g.ps echo 0 400 translate >> g.ps # for Gnuplot plots cat $1 | sed -e "s/showpage//" >> g.ps echo grestore >> g.ps echo gsave >> g.ps echo 0 090 translate >> g.ps # for Gnuplot plots cat $2 >> g.ps lpr -Phudsonlp1 g.ps

To combine two PostScript figures (plot1.ps and plot2.ps) on one page:

cat2 plot1.ps plot2.ps

14. USING GNU PLOT WITH NS 2

Use gnuplot to visualize the trace file. For this example,

I use the trace file which is generated from this code click here to down load tcl script.

The first step is using awk to get throughput of cbr and tcp packets from node 2 to node 3. click here to down load the awk script; myflowcalcall.awk.

Run at the terminal :

$ awk -f myflowcalcall.awk -v graphgran=0 -v fidfrom=2 -v fidto=3 -v fid=1 -v flowtype=”tcp” -v outdata_file=”nothing” out_example4.tr > thr1

$ awk -f myflowcalcall.awk -v graphgran=0 -v fidfrom=2 -v fidto=3 -v fid=2 -v flowtype=”cbr” -v outdata_file=”nothing” out_example4.tr > thr2

Result : thr1

0.5 0

1 0.00032

1.5 0.20544

2 0.29968

2.5 0.349568

3 0.413333

3.5 0.430354

4 0.47224

4.5 0.43456

the above data comes from :

r 1.034894 2 3 tcp 40 ——- 1 0.0 3.0 0 113

r 1.104296 2 3 tcp 1040 ——- 1 0.0 3.0 1 123

r 1.502847 2 3 tcp 1040 ——- 1 0.0 3.0 44 238

r 2.006188 2 3 tcp 1040 ——- 1 0.0 3.0 61 375

r 2.500588 2 3 tcp 1040 ——- 1 0.0 3.0 91 511

r 3.008447 2 3 tcp 1040 ——- 1 0.0 3.0 135 658

r 3.5068 2 3 tcp 1040 ——- 1 0.0 3.0 167 793

r 4.005153 2 3 tcp 1040 ——- 1 0.0 3.0 213 939

Result : thr2

0.5 0.736

1 0.864

1.5 0.858667

2 0.892

2.5 0.9216

3 0.928

3.5 0.944

4 0.942

4.5 0.956444

5 0.8672

the above data comes from :

r 0.506706 2 3 cbr 1000 ——- 2 1.0 3.1 46 46

r 1.002706 2 3 cbr 1000 ——- 2 1.0 3.1 108 108

r 1.507553 2 3 cbr 1000 ——- 2 1.0 3.1 166 239

r 2.001294 2 3 cbr 1000 ——- 2 1.0 3.1 228 373

r 2.505294 2 3 cbr 1000 ——- 2 1.0 3.1 294 512

r 3.003553 2 3 cbr 1000 ——- 2 1.0 3.1 354 657

r 3.501906 2 3 cbr 1000 ——- 2 1.0 3.1 420 792

r 4.000259 2 3 cbr 1000 ——- 2 1.0 3.1 478 937

r 4.506706 2 3 cbr 1000 ——- 2 1.0 3.1 546 1028

Visualize thr1 and thr2 with gnuplot :

$ gnuplot

gnuplot> set title “One CBR Competes with One FTP”

gnuplot> set xlabel “Time in second”

gnuplot> set ylabel “Throughput in Mbps”

gnuplot> set key 3,1.8

gnuplot> set label “Yield Point” at 0.003,260

gnuplot> set arrow from 0.002,250 to 0.003,280

gnuplot> set xr[0:5]

gnuplot> set yr[0:2]

gnuplot> plot “thr1″ using 1:2 title ‘CBR Flow’ with lines,\

> “thr2″ using 1:2 title ‘TCP Flow’ with lines

Final Result :

• ROUTING IN WIRED NETWORKS

1. UNICAST ROUTING

In computer networking, Unicast transmission is the sending of messages to a single network destination identified by a unique address.Unicast routing is the process of forwarding unicasted traffic from a source to a destination on an internetwork. Unicasted traffic is destined for a unique address.

If an IP Unicast packet passes through a switch that does not know the location of the associated MAC Address, the packet will be broadcast to all ports on the switch. This failure of Unicast to 'cast to a single device' is called a Unicast flood.

Unicast messaging is used for all network processes in which a private or unique resource is requested.

Certain network applications which are mass-distributed are too costly to be conducted with unicast transmission since each network connection consumes computing resources on the sending host and requires its own separate network bandwidth for transmission. Such applications include streaming media of many forms. Internet radio stations using unicast connections may have high bandwidth costs.

Wireless networks is an emerging new technology that will allow users to access information and services electronically, regardless of their geographic position. Wireless networks can be classified in two types:-

- infra structured network and

- infrastructure less (ad hoc) networks.

Infra structured network consists of a network with fixed and wired gateways. A mobile host communicates with a bridge in the network (called base station) within its communication radius. The mobile unit can move geographically while it is communicating. When it goes out of range of one base station, it connects with new base station and starts communicating through it. This is called hand off. In this approach the base stations are fixed.

In contrast to infrastructure based networks, in ad hoc networks all nodes are mobile and can be connected dynamically in an arbitrary manner. All nodes of these networks behave as routers and take part in discovery and maintenance of routes to other nodes in the network. Ad hoc networks are very useful in emergency search-and-rescue operations, meetings or conventions in which persons wish to quickly share information, and data acquisition operations in inhospitable terrain [Royer99].

Now we discusses proposed routing protocols for these ad hoc networks. These routing protocols can be divided into two categories:

- table-driven and

- on-demand routing

based on when and how the routes are discovered. In table driven routing protocols consistent and up-to-date routing information to all nodes is maintained at each node whereas in on-demand routing the routes are created only when desired by the source host.

TABLE DRIVEN ROUTING PROTOCOLS

In Table-driven routing protocols each node maintains one or more tables containing routing information to every other node in the network. All nodes update these tables so as to maintain a consistent and up-to-date view of the network. When the network topology changes the nodes propagate update messages throughout the network in order to maintain a consistent and up-to-date routing information about the whole network. These routing protocols differ in the method by which the topology change information is distributed across the network and the number of necessary routing-related tables. Now we are going to discuss some existing table-driven ad hoc routing protocols.

Dynamic Destination-Sequenced Distance-Vector Routing Protocol [DSDV]

The Destination-Sequenced Distance-Vector (DSDV) Routing Algorithm is based on the idea of the classical Bellman-Ford Routing Algorithm with certain improvements.

Every mobile station maintains a routing table that lists all available destinations, the number of hops to reach the destination and the sequence number assigned by the destination node. The sequence number is used to distinguish stale routes from new ones and thus avoid the formation of loops. The stations periodically transmit their routing tables to their immediate neighbors. A station also transmits its routing table if a significant change has occurred in its table from the last update sent. So, the update is both time-driven and event-driven. The routing table updates can be sent in two ways:- a "full dump" or an incremental update. A full dump sends the full routing table to the neighbors and could span many packets whereas in an incremental update only those entries from the routing table are sent that has a metric change since the last update and it must fit in a packet. If there is space in the incremental update packet then those entries may be included whose sequence number has changed. When the network is relatively stable, incremental updates are sent to avoid extra traffic and full dump are relatively infrequent. In a fast-changing network, incremental packets can grow big so full dumps will be more frequent. Each route update packet, in addition to the routing table information, also contains a unique sequence number assigned by the transmitter. The route labeled with the highest (i.e. most recent) sequence number is used. If two routes have the same sequence number then the route with the best metric (i.e. shortest route) is used. Based on the past history, the stations estimate the settling time of routes. The stations delay the transmission of a routing update by settling time so as to eliminate those updates that would occur if a better route were found very soon.

MULTICAST ROUTING

- IP MULTICAST

IP multicast is a technique for one-to-many and many-to-many real-time communication over an IP infrastructure in a network. It scales to a larger receiver population by requiring neither prior knowledge of a receiver's identity nor prior knowledge of the number of receivers. Multicast uses network infrastructure efficiently by requiring the source to send a packet only once, even if it needs to be delivered to a large number of receivers. The nodes in the network (typically network switches and routers) take care of replicating the packet to reach multiple receivers such that messages are sent over each link of the network only once. The most common low-level protocol to use multicast addressing is User Datagram Protocol (UDP). By its nature, UDP is not reliable—messages may be lost or delivered out of order. Reliable multicast protocols such as Pragmatic General Multicast (PGM) have been developed to add loss detection and retransmission on top of IP multicast.

Key concepts in IP multicast include an IP multicast group address, a multicast distribution tree and receiver driven tree creation.

An IP multicast group address is used by sources and the receivers to send and receive multicast messages. Sources use the group address as the IP destination address in their data packets. Receivers use this group address to inform the network that they are interested in receiving packets sent to that group. For example, if some content is associated with group 239.1.1.1, the source will send data packets destined to 239.1.1.1. Receivers for that content will inform the network that they are interested in receiving data packets sent to the group 239.1.1.1. The receiver joins 239.1.1.1. The protocol typically used by receivers to join a group is called the Internet Group Management Protocol (IGMP).

With routing protocols based on shared trees, once the receivers join a particular IP multicast group, a multicast distribution tree is constructed for that group. The protocol most widely used for this is Protocol Independent Multicast (PIM). It sets up multicast distribution trees such that data packets from senders to a multicast group reach all receivers which have joined the group. For example, all data packets sent to the group 239.1.1.1 are received by receivers who joined 239.1.1.1. There are variations of PIM implementations: Sparse Mode (SM), Dense Mode (DM), Source Specific Mode (SSM) and Bidirectional Mode (Bidir, or Sparse-Dense Mode, SDM). Of these, PIM-SM is the most widely deployed as of 2006;[citation needed] SSM and Bidir are simpler and scalable variations developed more recently and are gaining in popularity.

IP multicast operation does not require an active source to know about the receivers of the group. The multicast tree construction is receiver driven and is initiated by network nodes which are close to the receivers. IP multicast scales to a large receiver population. The IP multicast model has been described by Internet architect Dave Clark as, "You put packets in at one end, and the network conspires to deliver them to anyone who asks."

IP multicast creates state information per multicast distribution tree in the network. If a router is part of 1000 multicast trees, it has 1000 multicast routing and forwarding entries. On the other hand, a multicast router does not need to know how to reach all other multicast trees in the Internet. It only needs to know about multicast trees for which it has downstream receivers. This is key to scaling multicast-addressed services. It is very unlikely that core Internet routers would need to keep state for all multicast distribution trees,[citation needed] they only need to keep state for trees with downstream membership. In contrast, a unicast router needs to know how to reach all other unicast addresses in the Internet, even if it does this using just a default route. For this reason, aggregation is key to scaling unicast routing. Also, there are core routers that carry routes in the hundreds of thousands because they contain the Internet routing table.

- ROUTING

Each host (and in fact each application on the host) that wants to be a receiving member of a multicast group (i.e. receive data corresponding to a particular multicast address) must use the Internet Group Management Protocol (IGMP) to join. Adjacent routers also use this protocol to communicate.

In unicast routing, each router examines the destination address of an incoming packet and looks up the destination in a table to determine which interface to use in order for that packet to get closer to its destination. The source address is irrelevant to the router. However, in multicast routing, the source address (which is a simple unicast address) is used to determine data stream direction. The source of the multicast traffic is considered upstream. The router determines which downstream interfaces are destinations for this multicast group (the destination address), and sends the packet out through the appropriate interfaces. The term reverse path forwarding is used to describe this concept of routing packets away from the source, rather than towards the destination.

A number of errors can happen if packets intended for unicast are accidentally sent to a multicast address; in particular, sending ICMP packets to a multicast address has been used in the context of DoS attacks as a way of achieving packet amplification.

On the local network, multicast delivery is controlled by IGMP (on IPv4 network) and MLD (on IPv6 network); inside a routing domain, PIM or MOSPF are used; between routing domains, one uses inter-domain multicast routing protocols, such as MBGP.

The following are some common delivery and routing protocols used for multicast distribution:

• 1. Internet Group Management Protocol (IGMP)

  2. Protocol Independent Multicast (PIM)

  3. Distance Vector Multicast Routing Protocol (DVMRP)

  4. Multicast Open Shortest Path First (MOSPF)

  5. Multicast BGP (MBGP)

  6. Multicast Source Discovery Protocol (MSDP)

  7. Multicast Listener Discovery (MLD)

  8. GARP Multicast Registration Protocol (GMRP)

For more click here: >> MULTICAST ROUTING

>> INTRODUCTION TO IP MULTICAST

>> MULTICAST ROUTING PROTOCOLS

3. HIERARCHICAL ROUTING

Hierarchical routing is a method of routing in networks that is based on hierarchical addressing. Hierarchical routing is the procedure of arranging routers in a hierarchical manner. A good example would be to consider a corporate intranet. Most corporate intranets consist of a high speed backbone network. Connected to this backbone are routers which are in turn connected to a particular work group. These work groups occupy a unique LAN. The reason this is a good arrangement is because even though there might be dozens of different work groups, the span (maximum hop count to get from one host to any other host on the network) is 2. Even if the work groups divided their LAN network into smaller partitions, the span could only increase to 4 in this particular example.

Considering alternative solutions with every router connected to every other router, or if every router was connected to 2 routers, shows the convenience of hierarchical routing. It decreases the complexity of network topology, increases routing efficiency, and causes much less congestion because of fewer routing advertisements. With hierarchical routing, only core routers connected to the backbone are aware of all routes. Routers that lie within a LAN only know about routes in the LAN. Unrecognized destinations are passed to the default route.

Most Transmission Control Protocol/Internet Protocol (TCP/IP) routing is based on a two-level hierarchical routing in which an IP address is divided into a network portion and a host portion. Gateways use only the network portion until an IP datagram reaches a gateway that can deliver it directly. Additional levels of hierarchical routing are introduced by the addition of subnetworks.

In hierarchical routing, routers are classified in groups known as regions. Each router has only the information about the routers in its own region and has no information about routers in other regions. So routers just save one record in their table for every other region. In this example, we have classified our network into five regions (see below).

DSDV ROUTING PROTOCOL

For more click here

Wireless Routing Protocol (WRP)

The Wireless Routing Protocol (WRP) is a table-based distance-vector routing protocol. Each node in the network maintains a Distance table, a Routing table, a Link-Cost table and a Message Re transmission list.

The Distance table of a node x contains the distance of each destination node y via each neighbor z of x. It also contains the downstream neighbor of z through which this path is realized. The Routing table of node x contains the distance of each destination node y from node x, the predecessor and the successor of node x on this path. It also contains a tag to identify if the entry is a simple path, a loop or invalid. Storing predecessor and successor in the table is beneficial in detecting loops and avoiding counting-to-infinity problems. The Link-Cost table contains cost of link to each neighbor of the node and the number of timeouts since an error-free message was received from that neighbor. The Message Re transmission list (MRL) contains information to let a node know which of its neighbor has not acknowledged its update message and to re transmit update message to that neighbor.

Node exchange routing tables with their neighbors using update messages periodically as well as on link changes. The nodes present on the response list of update message (formed using MRL) are required to acknowledge the receipt of update message. If there is no change in routing table since last update, the node is required to send an idle Hello message to ensure connectivity. On receiving an update message, the node modifies its distance table and looks for better paths using new information. Any new path so found is relayed back to the original nodes so that they can update their tables. The node also updates its routing table if the new path is better than the existing path. On receiving an ACK, the mode updates its MRL. A unique feature of this algorithm is that it checks the consistency of all its neighbors every time it detects a change in link of any of its neighbors. Consistency check in this manner helps eliminate looping situations in a better way and also has fast convergence.

Global State Routing [GSR]

Global State Routing (GSR) is similar to DSDV. It takes the idea of link state routing but improves it by avoiding flooding of routing messages.

In this algorithm, each node maintains a Neighbor list, a Topology table, a Next Hop table and a Distance table. Neighbor list of a node contains the list of its neighbors (here all nodes that can be heard by a node are assumed to be its neighbors.). For each destination node, the Topology table contains the link state information as reported by the destination and the timestamp of the information. For each destination, the Next Hop table contains the next hop to which the packets for this destination must be forwarded. The Distance table contains the shortest distance to each destination node.

The routing messages are generated on a link change as in link state protocols. On receiving a routing message, the node updates its Topology table if the sequence number of the message is newer than the sequence number stored in the table. After this the node reconstructs its routing table and broadcasts the information to its neighbors.

Fisheye State Routing [FSR]

Fisheye State Routing (FSR) is an improvement of GSR. The large size of update messages in GSR wastes a considerable amount of network bandwidth. In FSR, each update message does not contain information about all nodes. Instead, it exchanges information about closer nodes more frequently than it does about farther nodes thus reducing the update message size. So each node gets accurate information about neighbors and the detail and accuracy of information decreases as the distance from node increases. Figure defines the scope of fisheye for the center (red) node. The scope is defined in terms of the nodes that can be reached in a certain number of hops. The center node has most accurate information about all nodes in the white circle and so on. Even though a node does not have accurate information about distant nodes, the packets are routed correctly because the route information becomes more and more accurate as the packet moves closer to the destination. FSR scales well to large networks as the overhead is controlled in this scheme.

CGSR routing scheme

Each node maintains a cluster member table that has mapping from each node to its respective cluster-head. Each node broadcasts its cluster member table periodically and updates its table after receiving other nodeÆs broadcasts using the DSDV algorithm. In addition, each node also maintains a routing table that determines the next hop to reach the destination cluster.

On receiving a packet, a node finds the nearest cluster-head along the route to the destination according to the cluster member table and the routing table. Then it consults its routing table to find the next hop in order to reach the cluster-head selected in step one and transmits the packet to that node.

ON-DEMAND ROUTING PROTOCOLS

These protocols take a lazy approach to routing. In contrast to table-driven routing protocols all up-to-date routes are not maintained at every node, instead the routes are created as and when required. When a source wants to send to a destination, it invokes the route discovery mechanisms to find the path to the destination. The route remains valid till the destination is reachable or until the route is no longer needed.

Cluster based Routing Protocols [CBRP]

In Cluster Based Routing protocol (CBRP), the nodes are divided into clusters. To form the cluster the following algorithm is used. When a node comes up, it enters the "undecided" state, starts a timer and broadcasts a Hello message. When a cluster-head gets this hello message it responds with a triggered hello message immediately. When the undecided node gets this message it sets its state to "member". If the undecided node times out, then it makes itself the cluster-head if it has bi-directional link to some neighbor otherwise it remains in undecided state and repeats the procedure again. Cluster heads are changed as infrequently as possible.

Each node maintains a neighbor table. For each neighbor, the neighbor table of a node contains the status of the link (uni- or bi-directional) and the state of the neighbor (cluster-head or member). A cluster-head keeps information about the members of its cluster and also maintains a cluster adjacency table that contains information about the neighboring clusters. For each neighbor cluster, the table has entry that contains the gateway through which the cluster can be reached and the cluster-head of the cluster.

When a source has to send data to destination, it floods route request packets (but only to the neighboring cluster-heads). On receiving the request a cluster-head checks to see if the destination is in its cluster. If yes, then it sends the request directly to the destination else it sends it to all its adjacent cluster-heads. The cluster-heads address is recorded in the packet so a cluster-head discards a request packet that it has already seen. When the destination receives the request packet, it replies back with the route that had been recorded in the request packet. If the source does not receive a reply within a time period, it backs off exponentially before trying to send route request again.

In CBRP, routing is done using source routing. It also uses route shortening that is on receiving a source route packet, the node tries to find the farthest node in the route that is its neighbor (this could have happened due to a topology change) and sends the packet to that node thus reducing the route. While forwarding the packet if a node detects a broken link it sends back an error message to the source and then uses local repair mechanism. In local repair mechanism, when a node finds the next hop is unreachable, it checks to see if the next hop can be reached through any of its neighbor or if hop after next hop can be reached through any other neighbor. If any of the two works, the packet can be sent out over the repaired path.

Ad hoc On-demand Distance Vector Routing [AODV]

Ad hoc On-demand Distance Vector Routing (AODV) [Perkins99]is an improvement on the DSDV algorithm discussed in section 2.1. AODV minimizes the number of broadcasts by creating routes on-demand as opposed to DSDV that maintains the list of all the routes.

To find a path to the destination, the source broadcasts a route request packet. The neighbors in turn broadcast the packet to their neighbors till it reaches an intermediate node that has a recent route information about the destination or till it reaches the destination (Figure a). A node discards a route request packet that it has already seen. The route request packet uses sequence numbers to ensure that the routes are loop free and to make sure that if the intermediate nodes reply to route requests, they reply with the latest information only.

When a node forwards a route request packet to its neighbors, it also records in its tables the node from which the first copy of the request came. This information is used to construct the reverse path for the route reply packet. AODV uses only symmetric links because the route reply packet follows the reverse path of route request packet. As the route reply packet traverses back to the source (Figure b), the nodes along the path enter the forward route into their tables.

Route discovery on AODV

If the source moves then it can reinitiate route discovery to the destination. If one of the intermediate nodes move then the moved nodes neighbor realizes the link failure and sends a link failure notification to its upstream neighbors and so on till it reaches the source upon which the source can reinitiate route discovery if needed.

For more click here

Dynamic Source Routing Protocol [DSR]

The Dynamic Source Routing Protocol is a source-routed on-demand routing protocol. A node maintains route caches containing the source routes that it is aware of. The node updates entries in the route cache as and when it learns about new routes.

The two major phases of the protocol are: route discovery and route maintenance. When the source node wants to send a packet to a destination, it looks up its route cache to determine if it already contains a route to the destination. If it finds that an unexpired route to the destination exists, then it uses this route to send the packet. But if the node does not have such a route, then it initiates the route discovery process by broadcasting a route request packet. The route request packet contains the address of the source and the destination, and a unique identification number. Each intermediate node checks whether it knows of a route to the destination. If it does not, it appends its address to the route record of the packet and forwards the packet to its neighbors. To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and it's address is not present in the route record of the packet.

A route reply is generated when either the destination or an intermediate node with current information about the destination receives the route request packet. A route request packet reaching such a node already contains, in its route record, the sequence of hops taken from the source to this node.

As the route request packet propagates through the network, the route record is formed as shown in figure a. If the route reply is generated by the destination then it places the route record from route request packet into the route reply packet. On the other hand, if the node generating the route reply is an intermediate node then it appends its cached route to destination to the route record of route request packet and puts that into the route reply packet. Figure b shows the route reply packet being sent by the destination itself. To send the route reply packet, the responding node must have a route to the source. If it has a route to the source in its route cache, it can use that route. The reverse of route record can be used if symmetric links are supported. In case symmetric links are not supported, the node can initiate route discovery to source and piggyback the route reply on this new route request.

DSRP uses two types of packets for route maintenance:- Route Error packet and Acknowledgements. When a node encounters a fatal transmission problem at its data link layer, it generates a Route Error packet. When a node receives a route error packet, it removes the hop in error from it's route cache. All routes that contain the hop in error are are truncated at that point. Acknowledgment packets are used to verify the correct operation of the route links. This also includes passive acknowledgments in which a node hears the next hop forwarding the packet along the route.

For more click 1 click 2

Temporally Ordered Routing Algorithm [TORA]

The Temporally Ordered Routing Algorithm (TORA) is a highly adaptive, efficient and scalable distributed routing algorithm based on the concept of link reversal. TORA is proposed for highly dynamic mobile, multihop wireless networks. It is a source-initiated on-demand routing protocol. It finds multiple routes from a source node to a destination node. The main feature of TORA is that the control messages are localized to a very small set of nodes near the occurrence of a topological change. To achieve this, the nodes maintain routing information about adjacent nodes. The protocol has three basic functions: Route creation, Route maintenance, and Route erasure.

Each node has a quintuple associated with it -

• • Logical time of a link failure

  • The unique ID of the node that defined the new reference level

  • A reflection indicator bit

  • A propagation ordering parameter

  • The unique ID of the node

The first three elements collectively represent the reference level. A new reference level is defined each time a node loses its last downstream link due to a link failure. The last two values define a delta with respect to the reference level.

Route Creation is done using QRY and UPD packets. The route creation algorithm starts with the height (propagation ordering parameter in the quintuple) of destination set to 0 and all other node's height set to NULL (i.e. undefined). The source broadcasts a QRY packet with the destination node's id in it. A node with a non-NULL height responds with a UPD packet that has its height in it. A node receiving a UPD packet sets its height to one more than that of the node that generated the UPD. A node with higher height is considered upstream and a node with lower height downstream. In this way a directed acyclic graph is constructed from source to the destination. Figure illustrates a route creation process in TORA. As shown in figure 6a, node 5 does not propagate QRY from node 3 as it has already seen and propagated QRY message from node 2. In figure 6b, the source (i.e. node 1) may have received a UPD each from node 2 or node 3 but since node 4 gives it lesser height, it retains that height.

Route creation in TORA

When a node moves the DAG route is broken, and route maintenance is needed to reestablish a DAG for the same destination. When the last downstream link of a node fails, it generates a new reference level. This results in the propagation of that reference level by neighboring nodes as shown in figure below. Links are reversed to reflect the change in adapting to the new reference level. This has the same effect as reversing the direction of one or more links when a node has no downstream links.

In the route erasure phase, TORA floods a broadcast clear packet (CLR) throughout the network to erase invalid routes.

In TORA there is a potential for oscillations to occur, especially when multiple sets of coordinating nodes are concurrently detecting partitions, erasing routes, and building new routes based on each other. Because TORA uses internodal coordination, its instability problem is similar to the "count-to-infinity" problem in distance-vector routing protocols, except that such oscillations are temporary and route convergence will ultimately occur.

Associativity Based Routing [ABR]

The Associativity Based Routing (ABR) protocol is a new approach for routing. ABR defines a new metric for routing known as the degree of association stability. It is free from loops, deadlock, and packet duplicates. In ABR, a route is selected based on associativity states of nodes. The routes thus selected are liked to be long-lived. All node generate periodic beacons to signify its existence. When a neighbor node receives a beacon, it updates its associativity tables. For every beacon received, a node increments its associativity tick with respect to the node from which it received the beacon. Association stability means connection stability of one node with respect to another node over time and space. A high value of associativity tick with respect to a node indicates a low state of node mobility, while a low value of associativity tick may indicate a high state of node mobility. Associativity ticks are reset when the neighbors of a node or the node itself move out of proximity. The fundamental objective of ABR is to find longer-lived routes for ad hoc mobile networks. The three phases of ABR are Route discovery, Route reconstruction (RRC) and Route deletion.

The route discovery phase is a broadcast query and await-reply (BQ-REPLY) cycle. The source node broadcasts a BQ message in search of nodes that have a route to the destination. A node does not forward a BQ request more than once. On receiving a BQ message, an intermediate node appends its address and its associativity ticks to the query packet. The next succeeding node erases its upstream node neighbors' associativity tick entries and retains only the entry concerned with itself and its upstream node. Each packet arriving at the destination will contain the associativity ticks of the nodes along the route from source to the destination. The destination can now select the best route by examining the associativity ticks along each of the paths. If multiple paths have the same overall degree of association stability, the route with the minimum number of hops is selected. Once a path has been chosen, the destination sends a REPLY packet back to the source along this path. The nodes on the path that the REPLY packet follows mark their routes as valid. All other routes remain inactive, thus avoiding the chance of duplicate packets arriving at the destination.

RRC phase consists of partial route discovery, invalid route erasure, valid route updates, and new route discovery, depending on which node(s) along the route move. Source node movement results in a new BQ-REPLY process because the routing protocol is source-initiated. The route notification (RN) message is used to erase the route entries associated with downstream nodes. When the destination moves, the destination's immediate upstream node erases its route. A localized query (LQ [H]) process, where H refers to the hop count from the upstream node to the destination, is initiated to determine if the node is still reachable. If the destination receives the LQ packet, it selects the best partial route and REPLYs; otherwise, the initiating node times out and backtracks to the next upstream node. An RN message is sent to the next upstream node to erase the invalid route and inform this node that it should invoke the LQ [H] process. If this process results in backtracking more than halfway to the source, the LQ process is discontinued and the source initiates a new BQ process.

When a discovered route is no longer needed, the source node initiates a route delete (RD) broadcast. All nodes along the route delete the route entry from their routing tables. The RD message is propagated by a full broadcast, as opposed to a directed broadcast, because the source node may not be aware of any route node changes that occurred during RRCs.

Signal Stability Routing [SSR]

Signal Stability-Based Adaptive Routing protocol (SSR) is an on-demand routing protocol that selects routes based on the signal strength between nodes and a node's location stability. This route selection criterion has the effect of choosing routes that have "stronger" connectivity. SSR comprises of two cooperative protocols: the Dynamic Routing Protocol (DRP) and the Static Routing Protocol (SRP).

The DRP maintains the Signal Stability Table (SST) and Routing Table (RT). The SST stores the signal strength of neighboring nodes obtained by periodic beacons from the link layer of each neighboring node. Signal strength is either recorded as a strong or weak channel. All transmissions are received by DRP and processed. After updating the appropriate table entries, the DRP passes the packet to the SRP.

The SRP passes the packet up the stack if it is the intended receiver. If not, it looks up the destination in the RT and forwards the packet. If there is no entry for the destination in the RT, it initiates a route-search process to find a route. Route-request packets are forwarded to the next hop only if they are received over strong channels and have not been previously processed (to avoid looping). The destination chooses the first arriving route-search packet to send back as it is highly likely that the packet arrived over the shortest and/or least congested path. The DRP reverses the selected route and sends a route-reply message back to the initiator of route-request. The DRP of the nodes along the path update their RTs accordingly.

Route-search packets arriving at the destination have necessarily arrived on the path of strongest signal stability because the packets arriving over a weak channel are dropped at intermediate nodes. If the source times out before receiving a reply then it changes the PREF field in the header to indicate that weak channels are acceptable, since these may be the only links over which the packet can be propagated.

When a link failure is detected within the network, the intermediate nodes send an error message to the source indicating which channel has failed. The source then sends an erase message to notify all nodes of the broken link and initiates a new route-search process to find a new path to the destination.

CONCLUSION

In here, several existing routing protocols for ad hoc Wireless Networks were described. Two categories of routing protocols were discussed. Table-driven and on-demand routing protocols. In table-driven protocols, each node maintain up-to-date routing information to all the nodes in the network where in on-demand protocols a node finds the route to a destination when it desires to send packets to the destination.

Several table-driven protocols were discussed. DSDV and GSR are table-driven protocols that use destination sequence numbers to keep routes loop-free and up-to-date. HSR and ZHLS are hierarchical routing. FSR reduces the size of tables to be exchanged by maintaining less accurate information about nodes farther away. CGSR is a cluster-based routing protocol where nodes are grouped into clusters.

On-demand routing protocols were also discussed. In on-demand protocols, a route creation is initiated by the source when the source wants to communicate to the destination. CBRP is a cluster based routing algorithm like CGSR except that it is an on-demand routing mechanism as opposed to CGSR that is table-driven. AODV on-demand version of DSDV routing protocol. DSRP is a source routing mechanism where the route is in each packet. ABR uses the degree of associativity to select routes. Similarly, SSR selects routes based on signal strength.

For more link 1 link 2