Archive for the ‘Project Background’ Category
This presentation provides all the basics of WMN along with its implementation. It covers all the challenges associated with all the layers and also the topics which should be taken into account for research purpose. the presentation also states Current State of the Art in much detailand will be helpful for us.
Routing is the task of finding a path from a sender to a desired destination.In the IP “Internet model” this reduces primarily to a matter of finding a series of routers between the source and destination networks.As long as a message or datagram remains on a single network or subnet, any forwarding problems are the responsibility of technology that is specific to the network. For example, Ethernet and the ARPANET
Distance vector algorithms are based on the exchange of only a small amount of information. Each entity (router or host) that participates in the routing protocol is assumed to keep information about all of the destinations within the system. Generally, information about all entities connected to one network is summarized by a single entry, which describes the route to all destinations on that network.
Each entity keeps a routing database with one entry for every possible destination in the system. An actual implementation is likely to need to keep the following information about each destination:
– address: in IP implementations of these algorithms, this will be
the IP address of the host or network.
– router: the first router along the route to the destination.
– interface: the physical network which must be used to reach the
– metric: a number, indicating the distance to the destination.
– timer: the amount of time since the entry was last updated.
In addition, various flags and other internal information will probably be included. This database is initialized with a description of the entities that are directly connected to the system. It is updated according to information received in messages from neighboring routers.
let d(i,j) represent the cost of going directly from entity i to entity j. It is infinite if i and j are not immediate neighbors. (Note that d(i,i)
is infinite. That is, we don’t consider there to be a direct
connection from a node to itself.) Since costs are additive, it is
easy to show that the best metric must be described by
D(i,i) = 0, all i
D(i,j) = min [d(i,k) + D(k,j)], otherwise
and that the best routes start by going from i to those neighbors k
for which d(i,k) + D(k,j) has the minimum value. (These things can
be shown by induction on the number of steps in the routes.) Note
that we can limit the second equation to k’s that are immediate
neighbors of i. For the others, d(i,k) is infinite, so the term
involving them can never be the minimum.
(Only router will participate in routing and none of the host will participate in it .Consider there are 2 router A and F and A have host B,C,D,and E as we know that internal structure of IP is not visible so IP’s of A,B,C,D,E is summarized as single IP having same distance that will save the space in routing table and reduce unnecessary updates)
Limitations of the Protocol
This protocol does not solve every possible routing problem. As
mentioned above, it is primary intended for use as an IGP in networks
of moderate size. In addition, the following specific limitations
are be mentioned:
– The protocol is limited to networks whose longest path is 15 hops. The designers believe that the basic protocol design is inappropriate for larger networks.
– The protocol depends upon “counting to infinity” to resolve certain
unusual situations.If the system of networks has several hundred networks, and a
routing loop was formed involving all of them, the resolution of
the loop would require either much time or bandwidth . Such a loop would consume a large amount of network bandwidth before the loop was corrected. We believe that in realistic cases, this will not be a problem except on slow lines. Even then, the problem will be fairly unusual, since various precautions are taken that should prevent these
problems in most cases.
– This protocol uses fixed “metrics” to compare alternative routes.
It is not appropriate for situations where routes need to be chosen
based on real-time parameters such a measured delay, reliability,
or load. The obvious extensions to allow metrics of this type are
likely to introduce instabilities of a sort that the protocol is
not designed to handle.
Change in Topology
In RIP every router that participates in routing sends an update message to all its neighbors once every 30 seconds. Suppose the current route for network N uses router G. If we don’t hear from G for 180 seconds, we can assume that either the router has crashed or the network connecting us to it has become unusable. Thus, we mark the route as invalid.
The nightmare days are over!
Now you dont have to spend hours on your linux distro(ubuntu) installing and validating ns2.x
Ubuntu 10.10 has greatly simplified things. You can now install ns,nam and xgraph by just a single command in the Terminal:
$ sudo apt-get install ns nam xgraph
You will be prompted for the user password. Enter it and watch Ubuntu 10.10 do the things for You!
On heeding to my blog visitors requests, I would like to update this post with the steps to install ns2.34, the traditional way.
Step1: Download ns-allinone-2.34 package from this <site>. I will be using ns version 2.34.
Step2: Place the ns-allinone-2.34.tar.gz file in your home folder(/home/micman in my case). Right click on the package and extract the contents in the same home folder.
Step3: Next, open the Terminal(Applications–>Accessories–>Terminal in ubuntu)
Step4: Change to ns-allinone-2.34 directory
$ cd /home/micman/ns-allinone-2.34
Step5: First, Install the dependencies
$ sudo apt-get install build-essential autoconf automake libxmu-dev gcc-4.3
Note that we are downgrading the gcc version, as ns2.34 works well with gcc4.3
Edit Makefile.in found at this location ns-allinone-2.34/otcl-1.13/Makefile.in as follows:
Find the line that says:
and change it to:
Step6: Begin ns2.34 installation
$ sudo su
Step7: Once the installation is successful i.e. without any errors, we need to add the path information to the file ~/.bashrc
$ gedit ~/.bashrc
Step8: Append the following lines to the file ~/.bashrc
# Note: the above two lines starting from XGRAPH should come in the same line
Here replace /home/micman with the path to your home folder.
Step9: For the changes to take effect immediately, do the following:
$ source ~/.bashrc
type ns to see % and type nam to show the nam startup window. This shows your installation has been successful.
- If the tk compilation failed, especially for tk3d.c, make sure you have installed libx11-dev package.
- If the otcl configuration failed, make sure you have installed x-dev and xorg-dev packages.
nsbash: ns: command not found
This could be because you have not set the $PATH variable. Therefore, the OS does not know where to look for the command “ns“. more detailed solution
Undefined reference to vtable
Based on AODV, an improved routing protocol is presented named Mesh On-Demand Distance Vector based on Weighted Link State (MODVWLS), in which link state including available bandwidth, error ratio and transmission delay rather than the number of hops is used as evaluation criteria, the cost (weight) of each hop is taken into account and the path with minimal accumulative weight is finally used as the preferred route.
The simulation performed in ns-2 shows that the packet delivery fraction goes up and the average end-to-end delay declines as the pause time increases. This is because as the pause time increases, the packet loss and the delay resulted from by routing discovery and maintenance decrease,the performance of MODVWLS varies smoothly and is obviously better than the one of AODV. The reason is that the packet loss and transmission delay caused by overload, retransmission, buffer overflow, routing discovery and routing maintenance, to some extent , are efficiently overcame by MODVWLS.Normalized routing load of MODVWLS is less than AODV.There is a slight increase in processing load at mesh routers due to calculating and storing weight of each loop and also routing overhead is increased a bit because link weight is included in the routing messages.