Dynamic Virtual Subnet
Routing (DVSR) In Ad-Hoc Networks
ARUN SUBRAMANIAM
Department Of Computer Science, University Of Central England, Birmingham, U.K
E-mail: aruncse@hotmail.com
1. Introduction:
Ad-Hoc network is a network where the nodes are mobile and there is no central administrator for monitoring the network and providing services to the clients like in the client-server architecture. So, due to these reasons the task of designing a routing protocol for a network like Ad-hoc becomes more challenging because in a normal network the protocol knows where each node is located since the nodes are stable. Whereas in Ad-Hoc network the task of routing protocol is humungous because the protocol should know where each node is located every second so that the router can identify the path and send the packet at any time to the destination node.
The main thing now is to tackle the issues like power consumption, bandwidth utilization & efficient route establishment between the nodes using a routing protocol. How can we do that? It’s by using a concept called Virtual Subnet. The subnet is created with respect to the power level of the packet. The power level is set to a minimum level at the beginning (e.g. 1500mW), so that the power consumption for transferring packets between the nodes will be less and will be in shorter hops since its using less power.
Why did I choose this topic in specific? Well if you see the task of designing a protocol for a network like Ad-Hoc network, it’s more complex & challenging, since there is more issues like node mobility, no central administrator, less power availability and efficient bandwidth utilization. When I saw these issues as a network engineer, I felt that I have more things to solve in an Ad-Hoc network. So, due to these reasons I chose this topic as my research topic.
2. Major Factors
in Ad-Hoc:
While designing this routing protocol many questions were considered like how to find the route to the destination without having routing table of other subnets, should the protocol send ACK when packet is passed from one node to another node, how to avoid routing loops when passing packets between nodes, should the protocol send regular keepalive messages between nodes so that the subnet knows who is in it’s subnet region and also many criteria’s to be fulfilled like should not waste more power while transferring packets, should not overuse the bandwidth by using unnecessary updates or messages and should have efficient route discovery & maintenance. These are the main hypothetical questions & criteria’s considered while designing this protocol, so that there will be power & bandwidth efficient routing of packets between the nodes.
3. DVSR Approach:
3.1 Neighbour
Node Discovery:
When a node enters a radio range the corresponding node forms a virtual subnet with respect to the threshold power level, which is minimum at the beginning (e.g. 1500 mW). After setting the threshold power level for the packet, it sends the broadcast message with that power level. So that whoever gets that message within that power level from the source node (i.e) whoever is inside the virtual subnet will send an ACK for the packet received from the source node saying that “ I am in your range and this is my IP address & MAC address”. Then the source node gets that ACK and data packet and updates its routing table and in reply sends a message saying, “I got your message and this is my IP address & MAC address” and when the destination node receives this packet it updates its routing table. Like this each node inside the subnet exchanges packets and finally everyone inside the subnet will know who is in & out of the subnet. Now the question is why is this node sending both IP address and MAC address? The answer for this question will be explained in next section.
3.2 Address Assignment To Nodes:
Generally, Address is assigned dynamically to each node at the beginning and when this node enters a subnet it checks with the other nodes, whether it’s IP address and other nodes IP addresses clashes, if it does then the node starts to differentiate from the other node by using the IP address and MAC address combination. So that in the mere future even though they exchange packets with each other they will be distinguished by this address combination. The reason for using this technique is, since each node will have distinct MAC address there will be no possibility of having the same IP and MAC address combination.
Hope you got the answer for the question I asked in the introduction section that, why is this protocol using both IP & MAC address combination when it’s advertising to other node while entering the subnet. The reason is, if a node advertises at the beginning itself both the addresses, then when this node comes to see a node with the same IP address then at that time the nodes will start communicating using the MAC & IP address combination which will be there in their routing table rather than asking their MAC address at the time when this problem arises, which will cause some latency in routing packets due to the MAC address request.
3.3 Route
Discovery:
At the beginning when a node enters a subnet it will advertise to everyone its IP & MAC addresses and it also gets all the nodes addresses that is located within its subnet only. After getting them the nodes will start marking Border Nodes (BN) in the routing table for those nodes that are present at the border of its subnet. The process of finding whether a node is located in it’s subnet border or not is done by calculating the time it takes to send and receive the packet from a node and also by seeing the power consumption by the packet after its received by the node. The power consumed by the packet is compared with the threshold power level (for marking whether its BN or not) set by the protocol so that the protocol will identify which packet is weaker and stronger in power.
Figure-1: Ad-Hoc Network With Routing Table.
As we can see in the above diagram, the Node 3 routing table has an entry for node 4 which is not in the boundary so its marked as “N”, which says that its not the boundary node.
In the above diagram, if node 3 wants to send a packet to node 2, which is present in node 1’s subnet, then node 3 will send a broadcast to all the border nodes (i.e) nodes 5 & 1. After sending the broadcast, the corresponding nodes will broadcast to its corresponding BN’s and keeps going till it reaches its maximum hop count or till it finds the destination node. Coming back to the example, when node 3 sends a broadcast to the nodes 1 & 5 these nodes again will keep sending the broadcast till the maximum hop count is reached but node 1 will find the route to node 2 since this node has an entry in the node 1’s routing table. So by following this approach, unnecessary broadcast of data between the intermediate nodes is reduced and the communication will be between the BN’s only which will be less in number compared to intermediate nodes. After the destination node receives the packet from source node it sends back through the same route saying, “hey, this is the route you should follow to talk with me”. Then the source node will see that packet and follow that route and talk with the destination.
Till now everything is fine, but what if a BN node or an intermediate node goes out off range when sending from source to destination or vice versa. Then the actual route will be disturbed, so to avoid this the node, which found that disturbed route would send a broadcast to all its BN again and find the new route and append it to the existing route and send to the destination. Now the question is how to avoid route loops? In this protocol sequence numbers are used. The sequence numbers are build in such a way that each sequence number will be unique compared to other sequence number, so that if any 2 nodes send broadcasts at the same time asking to send to a destination node a packet then the node which received this packet should be able to differentiate these 2 broadcast messages, so for this reason, this protocol will use a unique sequence numbers and its created by using the machine part’s MAC address of the corresponding node, since it will be unique for each node . By following this approach the routing loop problem can be avoided.
3.4 Routing
Table Maintenance:
After creating routing tables, the nodes won’t broadcast those tables to anyone, instead it uses for its own use. If the node is idle for long time and if it doesn’t get any packets to transfer or the node itself doesn’t send any packets for a long time then the node should do something to know whether he is in the same subnet or not. So for that, the protocol sends keepalive messages every 90 seconds saying that “ I am in this subnet, are you with me?” and if the sending node receives a reply then it doesn’t change its routing table but if it doesn’t get a reply then it deletes the corresponding node’s entry from the table. These keepalive messages will be send if the node is idle for a long time but if its not idle, then after sending a packet or delivering a packet for another node it replies to the source node saying that “I am in your range and at the same time I delivered your packet to the next hop”. The routing table will be updated whenever the node gets a packet from a new node that has entered the subnet recently or if it couldn’t find an intermediate node, which was there before in its subnet.
4.0 Future Development &
Scope:
Well even though this protocol is designed by considering many issues, as an engineer I feel many changes can be made to this protocol using expert’s guidance. The development that can be made is that, the virtual subnet considered in this protocol can be made as a real subnet itself, so that each subnet will have a particular fixed IP address range (e.g. 192.168.0.0) to it. So that if a particular node gets into this subnet then the node will be assigned an IP address from this range and if in case the number of nodes available becomes greater than the number of IP addresses available then the nodes can be differentiated using IP & MAC address combination.
Now you can say that each node will have many number of IP addresses assigned because the node keeps moving from subnet to subnet. The reason for suggesting this approach is that the node doesn’t need to maintain or transfer the routing table because the fixed subnet regions will be arranged in such a way that by seeing the destination node’s subnet range the source node can track a map to the destination subnet easily and after reaching that subnet the BN node in that subnet will have entries of all the nodes inside its subnet. The main advantage is that we can reuse a set of IP addresses used in one region in another region by using a combination of this IP address and a unique subnet number. By doing this even though the IP address range clashes with each other the subnet number will be different compared to other subnet. Finally if you see it’s like having a fixed subnet range in each region and the nodes go through these subnets and the nodes use these fixed subnets as a road sign to reach the destination. The reason for not designing using this approach is that, for using these approaches the designer should need a good planning and guidance from a group of expert’s.
I feel DVSR protocol will have a scope, since it has an efficient routing mechanism & a good power management approach while routing packets.
I would be pleased to work with a group of expert’s in developing a routing protocol for Ad Hoc network and try to implement it practically.
References:
