Multihop Network Routing Using NS3 simulation and python #GROUP-7

by G Madhan, P Hemasai, K Manohar, A Rohith

INTRODUCTION:

             

                           Communication is a major part in modern day life. If we consider the network nodes, they are mobile in nature. It is not necessary that they have to stay at a particular position. And all these nodes are combined to make a multi hop network i.e. our present day networking system. The important task is to make sure that each communicating pair of nodes should be provided with the best available connection for data transferring. But here comes the problem as they are movable, their path will change time to time and should be updated regularly and this will definitely increase the complexity of the routing. We are going to simulate the routing process with contrast to parameters such as shortest path, less delay and with least possible collisions. There are many protocols such as proactive, reactive and hybrid routing protocols. We are going with a proactive routing protocol which has DVR( distance vector routing ) and LSR (link state routing) protocols. Our default conditions are we are considering queuing delay and processing delay as zero. For the shortest path we are using Dijkstra’s algorithm and we will discuss CS-MA/CD for collision detection.

                 

MOTIVATION:

                          In real life scenario, As the routing is a bit complex in reality as we discussed earlier, we have to establish some protocols to solve these issues. So our main motto is to explain how this problems are being solved in real life with various routing algorithms.There are several protocol available for this but we are going to work with link state routing which is a proactive routing protocol. Providing a good routing will make the data transferring efficient and friendly. After all it is not guaranteed that the routing is best, as there are many other algorithms which gives ideal result.

CONCEPT:

Routing protocol:

                            The distance vector routing and link state routing are the two of routing algorithms. Depending on the way the routing tables are updated they are classified. Distance vector is that in distance vector routing the router shares the knowledge of the entire network. In link state routing the router shares the knowledge of only their neighbor routers in the network. Here each router attempts to construct its own data table of the network. At the stage, when a router becomes active, it sends the messages to all the other nodes in the network and collects the information from the routers to which it is directly connected. It also provides information about whether the link to reach the router is active or not. This information is used by other routers to construct its data table. Then the router uses this table to choose the best path.

The routing protocols function by these three things:

1.  Discovering remote networks 
2.  Maintaining current routing information 
3.  path determination

Link state routing protocols usually have a complete view of the topology. They usually know of the best paths as well as backup paths to networks. Link state protocols use the shortest-path first algorithm to find the best path to a network.

But for using LSR there should be some favorable conditions:

1. The network should be hierarchical
2. There should be fast convergence of the network
3. The administrators should have a good knowledge of the implemented LSR protocol.

Dijkstra's algorithm:

                                 We are using Dijkstra's algorithm for our routing, where we estimate the distance of each node from the source node. Then we visit each node and its neighbors to find the shortest sub path to those neighbors. This uses a greedy approach in the sense that we find the next best solution hoping that the end result is the best solution for the whole problem. In every subsequent step the algorithm tries to minimize the cost for reaching each node. The cost can be distance, money or time.

Delay:

          Another parameter is delay. The delay of a network specifies how long it takes for a bit of data to travel across the network from one endpoint to another. As we made queuing and processing delays as zero, we will be working with propagation delay and transmission. We predefined the propagation delay in our code and we can show the delay created after every first shortest path is lost in the network.

Collisions:

                 It is a common issue that all data packets face when they travel in the network when bits from different hosts start traveling at the same time. To prevent this, we are using the CS-MA/CD concept,

where it checks for the presence of any signal in the routes. If no hosts are transmitting packets then the sender starts sending frames. The sender also checks whether any other hosts are transmitting or not, in case if they transmit at same time and collision is detected then the sender sends a jam signals which tells other hosts to stop transmitting until some random time.

THE COMPLETE FLOW CHART OF HOW DATA PACKET TRAVEL

WORKING WITH NS-3 (Network Simulator -3):

                                                                              We used network simulator version 3 software for simulating the routing process. We assumed some cases for this, like a multi hop system with individual nodes, a system with both CS-MA and individual nodes and a system with Ethernet connected nodes (only CS-MA). We represented the shortest path from source to destination and meanwhile deactivated those connections to show that the network utilizes the next best path using the Dijkstra algorithm or not. Here we considered the number of nodes as weight and we are choosing the path which has the least number of nodes. From each compilation of the network file, we are creating trace and pcap files which have the data packets transfer details and their timings such that we can observe the delay that it avoids in its best Path. We are making a network such that multiple sources and destinations will be there and routing should be ideal and beneficial. Here you can observe at first the data is passing directly from 1 to 2 node as there is direct connection and it is shortest path, after it is traveling through 0 node as the first path is deactivated and after some time it is using the 1342 path as it is the path left after the remaining two paths were disabled. For delay part we created trace files and packet capture files where each and every movement of the data packet is stored with the type of transport protocol it is using, the IP addresses where it traveled and the time taken. So we are directly taking the difference between each time taken by the different paths so that we will get the extra time taken by them.

This is when all nodes are individual

Here it directly uses the shortest path as it is determined by the routing algorithm. which is 1-2 nodes. when that link is down it chooses next shortest path.

So now it choose two hop way where it passes two paths to reach destination




here it chooses 1-0-2 path as previous shortest path is disabled.

here it chooses 1-3-4-2 path as it is the remained shortest path.

This is when there is a CSMA network with individual nodes

Now let us see when there is a CSMA network in place of individual nodes. 

Once the data packet is released as usual due to the algorithm the it chooses shortest path that is from 0-5 
 








when that path is off then it chooses the second but here it is a CSMA network, here the node 1 will send the data packets to each and every other node (1 - 2,3,4) and again the node near to the destination ( node 4 ) will be identified and that node will send the data which is ( 4 - 5 )

NOTE: In these pictures the red particles are nodes and arrows represent data particle movement.

WORKING WITH Python:

                                          We used python to do the collision part as NS3 doesn't support collisions. So in this we created the same thing what we did with NS3, along with the collisions. So when ever a collision occurs those data packets will be lost and collision signal will be sent to both the sources, then they will wait for some random time and they again release the data packets, so whatever the packet comes first they will reach the destination and then handover that path to the next source.

So this is just a sample of how collision occurs, you can see that data packets are traveling from red node (source) to green node(destination1) and again red node to yellow node (destination2).

 

 

The case is like data packets has to travel from red node to green to yellow and other has to travel from red to yellow to green

 This is due to somehow the protocol choose second shortest path for red source and green destination and similarly from red source to yellow destination due to the previous routing path. ( maybe the first path is busy before sending the packets).

Here the data packets should reach green node and also other packets should turn and reach yellow node. In this case the data packets will get collide and sends a signal back to source to wait for some time.

Here you can see that the square particles which are like collision identifiers, which move from the collision to the source, since there is only one source it will identify that its packets are colliding so that it sends at different timings.

NOTE: In these pictures red node is source, green and yellow are destinations and the moving red particles are data packets.

SUMMARY: 

So in short our project explains how to design a routing protocol of a multi hop network system. The parameters we took for comparing is distance, delay and number of collisions per second. We shown that the path took by the network for data transferring is shortest available path for that source and takes less delay. Also collisions takes place in worst condition where because our network is too small, so the available paths are less, hence there are chances of collisions. The real life example of this kind of network is MANET (Mobile ad-hoc networks).
 

CHALLENGES:

1) Actually Network simulator is not supporting the collision as it takes ideal condition where zero collisions occurs such that data packets travel without collisions.

2) delay is taken whole at a time in the simulation i.e we cant give queuing delay, propagation delay, transmission delay and processing delay separately.