Reactive Routing Protocols

Reactive Routing Protocols: These protocols are called on demand protocols. As opposed to storing a complete routing table having route information to all destinations in the network, reactive protocols finds route between source node and the destination node only when need arises.

This has advantage of reducing the traffic load in the network at the cost of latency occurred during finding out a path only on demand basis.

Some of the well known protocols are:

Dynamic Source Routing Protocols: The nodes get routing information from the source routes which are stored in data packets. A node maintains route caches containing the routes it knows. Protocols span two phases:

Root Discovery

Root Maintenance

Route discovery: When a source node wants to send data, first it checks its own routing cache to see if it already has a route to destination. Routing cache is fast and convenient table used to store recently used routing information. If there is no route to destination in the cache then source node initiates the process of route discovery.

It broadcast packet containing:

• source address,               

• destination address,

• Unique identification number

• path

If a node saw the packet before, it discards it; otherwise, the route looks up its route caches to look for a route to destination, If not find, appends its address into the packet, rebroadcast. If it finds a route in its route cache, sends a route reply packet, which is sent to the source by route cache or the route discovery.

Route reply: Route reply is initiated in two cases. Firstly, if the route request packet has reached its destination; secondly if an intermediate node to the destination has route to the destination. After this the question arises for the path back to the source. The reverse path from destination to source depends on two conditions.

If the destination has the route to the source then follow it.

In case of symmetric links, reverse the route in route record and follow it.

In case of asymmetric links, the destination node is supposed to initiate its own route discovery.

Route Maintenance:  Once the route between source and destination has been established, it must be maintained for the duration of transmission. Route maintenance is done by:

• Route error message

• Acknowledgement

Route Error message: Whenever a node transmits a data packet, a route reply, or a route error, it must verify that the next hop correctly receives the packet. If not, the node must send a route error to the node responsible for generating this route header. The source restarts the route discovery.

Acknowledgement:  Nodes are supposed to notify the correct operation of route links. 

Dynamic Source Routing- Example:

When MH S wants to send a packet to MH D, but does not know a route to D, MH S initiates a route discovery. For this purpose, the source node S floods Route Request (RREQ) to all the neighboring nodes in the network.

Each MH appends own identifier when forwarding RREQ

Proactive Routing Protocols

Routing implies to the best path selection among all the available possible paths from transmitter to receiver. Protocols are the rules or regulations. In this way, routing protocols are set of rules to select a best path among all the available paths from source to destination. Before going into details of routing in Ad hoc network, let’s discuss basics of link state and distance vector routing protocols.

• Distance Vector Routing

• Link State Routing

Distance Vector Routing Protocol: 

In this routing protocol, each node maintains a metric called distance and the destination address. Let us take an example of three nodes, A,  B and C.

In above figure, let's us focus on the first table maintained by node A. The first column of this table shows the destination addresses/ identifications.

Likewise, the next column shows the next node (hop) to reach that destination and the third column indicates the metric to reach that destination. (Metric in our case is the distance in terms of number of hops). In the same way, the initial routing tables are shown  in the figure above for node B and C.

Let’s say that there is some change at node B, that is the metric between node B to node C has been changed from 2 to 1.  To let others nodes know about this change, node B sends new information to node A and node C.

After some time, a new MH, D enters the Ad hoc network and its routing table is shared with rest of the nodes i.e., A, B and C. The following figure shows the exchange of updated routing table entries among the nodes.

After some successful exchanges of messages, say, due to some problems, node D becomes inactive and as can be seen that only node C can detect this. The rule is that if a node goes down the neighboring node mentions it in their routing table as an unreachable node by setting its value to infinity. Following this rule node C sets the distance to D as infinity as depicted as in following figure. 

However, node B does not have this information and it broadcast its routing table to C telling him that D is still reachable.

In this way, at later stage node C sends the same information back to node B and this situation prevails. After some time, the routing table at A will be as given below.

As can be seen it will go to infinity, in simple words, C will keep sending the information to B that D is reachable through it that is node C. In the same way, B will also do the same; it will be sending information to C that D is reachable by it that is by node B. Ultimately, the distance to node D will reach infinity. 

Due to this loop, count to infinity problem occurs in the network. Count to infinity implies to the distance to a node which actually does not exist in the network. To solve this problem in Ad hoc network, various variations are suggested which are discussed below. Some of the well known protocols are listed below.

• Destination-Sequenced Distance-Vector Protocol

• The Wireless Routing Protocol

• The Topology Broadcast based on Reverse Path Forwarding Protocol

• The Optimized Link State Routing Protocol

• The Source Tree Adaptive Routing Protocol

Destination-Sequenced Distance-Vector Protocol: 

This protocol is based on Distributed Bellman-Ford algorithm. This is also referred as RIP (Routing Information Protocol). In this protocol, every node of Ad hoc network maintains following information in its routing table.

• All available destinations

• The next node to reach to destination

• The number of hops to reach the destination

In DSDV routing protocols, each node in the network maintains a routing table.

Every node periodically sends routing information to its neighboring nodes even when there is no change. Change means there is no failure of any node or  there is no movement of any node.

The routing information exchanged between nodes is shown in the following table.

First column shows the destination address, next column is the next MH to reach the destination, the third column shows the distance to the destination. Fourth column shows the sequence number which indicates the newness of the routing information received from the surrounding nodes. Final column is the install time of routing information into its own table.

Destination	Next	Metric	Seq. Nr	Install Time
A	A	0	A-550	001000
B	B	1	B-102	001200
C	B	3	C-588	001200
D	B	4	D-312	001200

In this protocol, count to infinity problem is solved by using destination sequence number. Every time a node wants to advertise it routing table, it adds 1 to its sequence number and broadcasts its routing table. If a node fails, the adjacent node increase its sequence number and set hop count to that node as infinity and advertises this. 

The Wireless Routing Protocol:

The Wireless Routing Protocol is proactive and table driven protocol. Every node in the network sends an update message and receive acknowledgment message from all other nodes in the network. Nodes maintain shortest path spanning tree depending upon the update message from its neighbor nodes.

An update message has:

• The destination address
• The distance to destination
• Information about node at second-to-last hop (Predecessor)

A null update message is sent every now and then to assure connectivity. In case when a node does not respond for some specific interval of time then a special HELLO message is sent to get the updated information from that node.

These are the four tables stored in every node of Ad hoc network.

• Distance
• Routing
• Link-cost
• Message Retransmission List (MRL) tables

                                     (Each entry in MRL contains the sequence number of the update message)

Each node sends distance and second-to-last hop information to every node in the network. The routing table at each node stores address to destination, distance to destination, predecessor to destination and successor to destination. Successor is the next hop neighbor to the destination.

Let’s take an example for understanding:

In the above example, node A has been taken as a source node where the above routing table is saved. It shows, for instance, destination node E which is reachable with cost 3 and its predecessor node C and successor node is B, depicted as follows.

There are two options to go from A from E.

A→C→D (but the cost will be 11)

A→B→C→D (but the cost will be 3) 

Therefore, option 2 is selected and is shown in the table.

In case a link fails:

The scenario of any link in the network fails can be best understood by following example where link 1 which connects node A to node B fails.

The following sequence of events occurs after link-1 fails.

Node A will be notified about this failure.

Let us take a single destination – for instance Node X fails.

• Node A will change the distance to X as infinity.  Predecessor and Successor will change to “null”.
• This information will be sent to Node C.
• C will update its routing table with new path to A by means of link 2.
• This update is then broadcast to A.
• Node A then computes new routing information via C

The updated routing Table at node A is shown in the following table.

The main difference between DSDV and WRP is that the first uses full dump or incremental packets for route updates and the later uses HELLO messages. In addition, they both use different number of routing tables.

Topology Broadcast based on Reverse Path Forwarding Protocol (TBRPFP)

TBRPFP uses broadcasting topology information to all nodes in the network. Topology information includes link costs and up/down status. Each link-state update is sent on every link of the network though flooding

Flooding refers to forwarding to every node except the one from which received as depicted below.

Spanning Tree:

Spanning tree is a graph of mobile nodes in an Ad hoc network where all nodes are connected with minimum number of paths between them and without any cycle.

Communication cost of broadcasting topology can be reduced if updates are sent along spanning trees. In TBRPFP, messages generated by a given source are broadcast in the reverse direction along the directed spanning tree formed by the shortest paths from all MHs (nodes) to the source.

Each node i selects a next node Pi(v) along the shortest path between i  and destination v.

As in above example, TBRPFP uses spanning tree for forwarding packets, instead of simple flooding because in flooding packet is broadcast to all connected nodes and hence increases the packet traffic. In this way, control traffic is also reduced required for flooding.

The Optimized Link State Routing Protocol:

This is proactive and link state routing protocol which as opposed to flooding uses only selected nodes called multipoint relays to send its message to all nodes in the network.

It also saves bandwidth by reducing the bandwidth of control messages. Every control message has a sequence number; therefore, in order delivery of packets at destination is not needed. Routing of messages is performed in hop by hope mode.

Multi Point Relays (MPR): In flooding every node broadcasts therefore traffic in the network become very heavy. To solve it, only selected nodes are used to forward those packets. These nodes are called multipoint relays. Every node in the network selects its MPR from its neighboring nodes which are one hop away such that they can cover all the nodes which are two hops away. 

Challenges in Wireless/ Mobile Ad hoc NETworks (MANET)

As we can see that there are many application areas where Ad hoc networks can be used to benefit the human being, there has been a tremendous research work in this direction. However, still there are many challenging issues which need particular attention from research community.

Here we discuss some of the problems faced by this infrastructure-less wireless communication technology. Some of the main issues are:

• Scalability

• Quality of service

• Client server model shift

• Security

• Energy conservation

• Node cooperation

• Interoperation

Scalability: Most of the Ad hoc network applications imply no bound on the network size. In other words, any number of wireless nodes and enter or leave the network. However, if the number of nodes keeps increasing the resultant bandwidth available to a node within the network will decrease by the following formula:

Because the jobs like node discovery, route acquisition, service location and many of the handshakes required during establishment of a connection between nodes occupies bandwidth. Therefore, scalability is one of the great challenges being faced by Ad hoc networks

Quality of service: Most system works on the principle of best effort delivery service. Best-effort delivery describes a network service in which the network does not provide any guarantees that data is delivered or that a user is given a guaranteed quality of service level or a certain priority. In a best-effort network all users obtain best-effort service, meaning that they obtain unspecified variable bit rate and delivery time, depending on the current traffic load.

Quality of Service parameters:

•      Delay

•      Jitter

•      Bandwidth

•      Packet Loss Probability

Client server model shift: Internet depends on client server model, where the information request from client is served by the Servers available in the network. In contrary to this in Ad hoc network, there is no infrastructure to support this kind of model, therefore, a suitable model which may fit in the infrastructure less type of network is needed.

Security: Like all the wireless technologies, signals being exchanged between the nodes use electromagnetic waves which are prone to various detrimental effects like eavesdropping, spoofing, fading etc.

Energy conservation: In some specific applications like in sensor network, the size of the node being used in Ad hoc network is so small that cannot carry large batteries to support communication for a long time. In some situation, Ad hoc nodes are designed to be used only once and than they are thrown away. In both of the case, the battery life plays an important role. To enhance the battery time of nodes in Ad hoc network, various maximization techniques keeping node or complete network into mind are being studies and they require further investigation to bring even better battery performance of the node and network.

Node cooperation: The survival of Ad hoc network depends on mutual receiving and forwarding the messages on behalf of each other. This mutual cooperation is sometimes broken if there are some of the nodes selfish or malicious nodes in the network. To handle such type of nodes in the network, some policies of reward and penalty on the nodes is required to be studied.

Applications of Wireless/ Mobile Ad hoc NETworks (MANET)

Collaborative Work: Collaborative computing might be important outside office environments which not only support users at far distances but it connects user on one application in real time.

Crisis-management Applications: Ad hoc network can be very productive in natural disasters like Tsunamis, Hurricanes when entire communications infrastructure is destroyed and nobody can communicate if they are farther from each other that there voice is lost due to distance. In such situations, ad hoc network could be established in hours which otherwise needs days/weeks.

Personal Area Networking: Personal area network is the network established between the personal electronic gadgets owned by a single person. Personal gadgets can also be connected in Ad hoc fashion. These gadgets many include cell phone, PDAs, laptop computers, pulse watch, belt, headsets etc. One of the best examples could be Bluetooth.

Medical and Healthcare Applications: A patient at remote end can be treated by earlier transmission health related data of the patient like his current diagnosis. Remote consultation can be initiated in case of no network with the help of ad hoc network.

Military application: In situation like war, ad hoc network can be established and maintained among soldiers and their headquarters.

Vehicles: Ad hoc network can be established between the close by vehicles to avoid accidence or share other useful data of mutual interest among the cars nearby. This ad hoc network can also transmit news, road condition or even the cars running nearby can share the music or movie between them. In addition, in case of any accident the information about initial condition of persons and vehicles can be transmitted to hospitals for preparation for the emergency.

In addition to that mobile ad hoc network can be used as a mobile office, to establish local area network in Moen Jo Daro like area where installing a permanent infrastructure is not allowed. It can also support multi-user games. It can help a tourist in guiding him through tourist places and can be sent to him location dependent news.

Pakistan Planning to Launch 5G Services in 2019

Looking at the importance of early launch of future generation technology of mobile called “5G”, Government of Pakistan has announced that it is preparing to launch 5G in the country by 2019. The legacy mobile standards are focused to provide people to people contact whereas 5G is supposed to support connection from people to everything.

This is great news, as the introduction of this technology on one hand will bring foreign investment in the country and on the other hand it will provide state of the art mobile services to the peoples of Pakistan.

We already have four cellular operators in Pakistan. First is Zong from China Mobile, second comes Ufone by Pak Telecom Mobile Ltd., the third is Telenor from Norway and the last fourth one is Jazz by Russian Vimpelcom.

Pakistan, which has already secured 4th position as freelancing capitals in the world in a survey conducted by Oxford Internet Institute, will be taking more advantage by the huge bandwidth and quality of service promises made by 5G.

Applications of 5G:

eHealth: Some of the major application areas of 5G are eHealth where patient’s data like heart beats, glucose level etc can be sent to distant hospital to face emergency condition of a patient.

Self Driving Cars: In self driving cars, the nearby cars can communicate with each to avoid accidents or to help each other find traffic free roads.

Smart Cities: Smart cities will be based on 5G services to provide smart streetlights, information about available parking places, intelligent cameras to monitor streets of the city for security purpose etc.

Autonomous Driving Car Martti with 5G

Two giants from Finland join hands for experimenting Fifth Generation (5G) of mobile technology for real time communications between driverless car, Martti and 5G. This experiment tries to validate the transmission of road conditions, real time traffic condition, traffic camera as well as traffic lights data to and from Martti car over cloud based services to (Mobile Edge Computing) MEC as well as to other vehicles in that vicinity.  

VTT Research

The core of the studies to see the data like traffic lights, traffic cameras, sensors in the cars to be transmitted to MEC server located at some distance as shown in figure below. 

This data is then analyzed at MEC server and on the basis of the results from this data instruction may be transmitted back through low latency and high bandwidth network of 5G to change the course of the car if needed.

Martti Car communicating with with Mobile Edge Computing shown as Tower in this image

However, this is still in experimental phase until the final promises of 5G on low latency as well as huge bandwidth are fulfilled. The full details of the working of the trial can be seen on the following YouTube video.

5G targets:

Some of the target in terms of different performance parameters for wireless link of 5G are as follows.

1. Download Speed 10-100Gbps
2. Round Trip Time = 1millisecond
3. Latency 1 to 10 milliseconds