JOURNAL OF INFORMATION, KNOWLEDGE AND RESEARCH IN COMPUTER SCIENCE AND APPLICATIONS
A Study of Routing Protocols in Wireless Mesh Networks
ISSN: 0975 –6728| NOV 09 TO OCT 10 | Volume 1, Issue 1 Page 6
JOURNAL OF INFORMATION, KNOWLEDGE AND RESEARCH IN COMPUTER SCIENCE AND APPLICATIONS
1M. Arif Siddiqui, 2Qazi SHoeb Ahmad, 3M.H. Khan
1Faculty of Applied Sciences, Integral University, Lucknow, India
2Faculty of Applied Sciences, Integral University, Lucknow, India
3Department of Computer Science & Engineering
Institute of Engineering & Technology,
UP Technical University, Lucknow, India
ISSN 0975 –6728| NOV 09 TO OCT 10 | Volume 1, Issue 1 Page 8
JOURNAL OF INFORMATION, KNOWLEDGE AND RESEARCH IN COMPUTER SCIENCE AND APPLICATIONS
ABSTRACT: A wireless mesh networks (WMNs) is a collection of mesh routers and mesh clients. Mesh routers form the backbone of WMNs and mesh clients form the mesh network with mesh routers. Mesh routers are stationary or less mobile and forwards information to other nodes. Routing protocol plays a significant role in performance of a network. The AODV, DSR and DSDV are among the most discussed and used multi-hop wireless ad hoc routing protocols. This paper presents an overview of the aforementioned protocols.
Keywords : Routing Protocol, Routing Metric, Dynamic Source Routing, Ad Hoc On-Demand Distance Vector, Optimized Link State Routing, Destination-Sequenced Distance Vector
ISSN 0975 –6728| NOV 09 TO OCT 10 | Volume 1, Issue 1 Page 8
JOURNAL OF INFORMATION, KNOWLEDGE AND RESEARCH IN COMPUTER SCIENCE AND APPLICATIONS
1. INTRODUCTION
Routing is the process of choosing paths through which network traffic flows. Routing is implemented in different sort of networks, for instance telephone network, electronic data networks and internet network. In electronic data networks routing uses packet switching technology. In packet switching networks, routing makes the path for packet forwarding, and also supports for the transportation of addressed packets from source to destination through intermediate nodes by using hardware devices like routers, bridges, gateways, firewalls or switches. Ordinary computers with multiple network cards may forward packets and activate routing, regardless of limited performance. The routing process usually adopts forwarding in terms of routing tables. Therefore for the manufacturing of routing tables memory is necessary for precise routing.
Routing schemes have different attributes in their delivery.
· Unicast à Sends message to a single special node.
· Broadcast à Sends message to all the nodes in the network.
· Anycast à Sends message to anyone which is not included in node’s groups, probably the closest to source.
Unicast is the prominent kind of message delivery in internet [1]. Routing plays the vital role in the internet, to support messages to pass from one to another computer and consequently reach the destination. Each middle computer performs routing. This procedure includes analyzing a routing table to find the best path. Routing is mostly being mixed with bridging, as the functions of both the techniques are identical. The basic difference between them is that bridging takes place at low level in which hardware component performs main role, whereas the routing occurs at high level in which software component has vital role. Routing creates complex analysis to determine the suitable path for the packet [2].
2. TYPES OF ROUTING
There are mainly two types of routing which are as follows.
· Proactive Routing
· Reactive Routing
Proactive Routing
Proactive routing protocols are also known as table-driven routing protocols. Proactive protocols try to maintain consistent up-to-date routing information from each node to every other node in the network [3]. Each node maintains a routing table which contains routing information for all nodes in the network. When the network topology changes, update messages will propagate as a broadcast message throughout the network. In response, every node in the network updates its routing table with the changes in the network. As a result, up-to-date routing tables are maintained at every node in the network.
Route selection: In hop-by-hop routing, every node maintains its routing table that indicates next hops for the routes for all other nodes in the network [3]. In this routing, message overhead is very small because packet contains only destination address. The intermediate nodes relay the packet according to destination address. However, the proactive routing protocols are very inefficient overall due to the number of control messages propagated in the network for updating routing table information.
Reactive Routing
It is also know as on-demand routing. In on-demand routing, a source node will find a route for the destination node only when there is a need for a route (when source node needs to send packets to destination node). A flooding technique is used to discover routes when it is needed. Once routes are discovered, they are stored and maintained in route cache. Afterwards these stored routes are used for packet transfer instead of flooding. As a result, performance of an on-demand routing protocol is better than a table driven protocol because of less overhead in maintaining routing tables.
3. ROUTING IN WMNS
Wireless mesh networking and mobile ad hoc networking use the same key concept—communication between nodes over multiple wireless hops on a meshed network graph. Since WMNs share common features with wireless ad hoc networks, the routing protocols developed for MANETs can be applied to WMNs. For example, Microsoft Mesh Networks [4] are built based on Dynamic Source Routing (DSR) [5], and many other companies, e.g., [6] are using Ad hoc On-demand Distance Vector (AODV) routing [7], Optimized Link State Routing (OLSR) [8].
Currently, the design of routing protocols for WMN is still an active research area no matter the many available routing protocols for MANETs.
4. PRE-REQUISITE OR GENERAL PROSPECTIVE FOR WMNS ROUTING
To resolve the main issues like dynamic connectivity and guaranteed delivery for routing protocols in WMNs or MANETs following factors play vital role. There should be the clear path from source to destination, so that routing protocols can easily deliver data through that path. If there is variation due to change in connectivity between nodes, routing protocols should have the capability to recover by using alternate path. There are also some other issues and problems regarding routing wireless Ad-hoc networks, for instance overhead is very important in wireless networks with small bandwidth. One of the other issues is power consuming issue in MANETs. Moreover other vital issue is to maintain quality of service. Routing protocols should have the ability to handle traffic balance on links. Protocols scalability should be updated regarding large networks. The implementation of security through routing protocols is also necessary to protect against different sort of attacks like sniffer, interruption, fabrication and denial of service etc. Routing protocols can also depend on other layers, for instance the implementation of Global position System in Wireless Ad-hoc networks. The determination or analysis of mobility can also play important role to give worth to routing in WMNs. Cross layer designing is another field of research in the field of MANET protocols [9].
5. WIRELESS MESH NETWORK ROUTING PROTOCOLS
Wireless Mesh Networks are generally considered as the type of mobile ad-hoc networks. However there are some differences between them. Firstly in wireless mesh networks all most all the traffic starts from gateways and ends ups also on gateway. Secondly in wireless mesh networks, nodes are clearly separated from each other either they are in the form of stagnant nodes or mobile nodes. MANETs are linked with mobile ad-hoc networks, general MANETs routing protocols can be used in WMNs. Additionally WMNs are new technological networks which are similar to MANETs. One of the applications of WMNs is that, it provides connection to an infrastructure node. It plays vital role for providing broadband internet access. The other successful production of WMNs is Wireless local area network. Routing is basic attribute of WMNs. The protocols have the clear effect on the behavior of WMNs. Therefore selection of suitable routing protocol increases the efficiency of network. Some of the effects of routing protocols in WMNs are listed below.
1. They are responsible to strength the network.
2. They are helpful to make connection between nodes.
3. Creates synchronization between nodes.
4. Provides quality of service in terms of bandwidth utilization, delay, throughput, network load, and jitter.
As mentioned earlier general MANETs protocols can be implemented in WMNs, however the more efficient protocol which synchronizes with wireless mesh networks is mesh routing protocol (MRP). The protocol creates the continuity between routing paths and gateway destinations. It has also the ability to select the route, which is basic requirement to make better communication in WMNs. There are lots of relevant protocols in this context. Many of them have been authorized by Internet Engineering Task Force (IETF), some of them are reactive and some of them are proactive for example AODV and DSR are implemented for ad-hoc networks. Wireless mesh technology is the latest well developed technology which has vital role in the field of telecommunication as well as internet services; however there are still some challenges and problems which have been faced by trouble shooters. To fix up the problems in WMNs many projects have been launched such as MAC layer, internet mobility and transport layer efficiencies. Consequently for designing of routing protocols in WMNs, it must be considered that almost all the traffic is supposed to flow to and from gateway to internet systems. Thus routing protocol should be designed to avoid flooding for the discovery of route [10].
5.1 Ad-hoc on-Demand Distance Vector
The Ad-hoc on-demand is basically reactive protocol which supports multi routing between nodes which are playing their roles to form an Ad-hoc network. AODV is the improved version of DSDV protocol, but the main difference is that AODV is reactive whereas DSDV is proactive. It has great advantages, for instance, for disseminating information through routes on demand basis requirement for maintenance is not necessary. One of the main qualities of AODV is that it is free from hops. The environment where AODV is activated, target sequence numbers confirm the route, to be refreshed properly. The algorithm use d in AODV considers two messages, one is route request, to establish the route request message is being activated by AODV, and the other is hello message. These messages support nodes to strengthen neighbor nodes. Without the presence of hello messages, the identification of nodes is difficult. AODV has the ability to provide lot of information about the following technical aspects [6].
· Target IP addresses, where the packets should be sending.
· Sequence numbers.
· Counting of hops, that packet has passed.
· Next hop, stability of routes
· Neighbor nodes activity
· Request, the request should be on at a time.
Process to Find out Route
The node starts to find out the path, the path is necessary for determining and travelling of data. The source finds out the path and sends the message towards the destination. The request message is also activated to find out the appropriate route for sending the message [6].
Route Management Policy
To manage the route, it is necessary to point out the route that lacks its validity, then the removal of route entry exists and link failure message is conveyed. This message is also transferred to nodes which are using the same route which has been suffering from breakage. The neighbor’s nodes are properly updated. This process is repeated again and again. The main benefit of AODV is the limitation of routing messages as compared to ordinary protocols. This is all due to the reactive behavior of AODV [6].
5.2 Dynamic Source Routing (DSR)
The DSR [5] [11] is a simple and efficient protocol for routing in mobile ad hoc and wireless networks. DSR is suitable for routing in multi-hop networks. A mobile ad hoc network is completely self-organizing by using the DSR protocol. All nodes cooperate to forward packets of its neighbors which are not in direct communication range of the destination node(s). DSR is an on-demand or reactive protocol. For example, when any node wants a route, DSR initiates a route discovery process. In other words, due to the reactive nature of the protocol, when there is a need for a route, it starts discovering them.
DSR is based on source routing. A source node has complete hop-by-hop route information for destination in their route cache. Every generated packet carries this information (source route or path) in its packet header. When a node needs a path to a destination, it generates a route request (RREQ) packet. Each node first checks its route cache to determine the route for destination. If route is found in its cache then it will initiate a route reply for the source node of the route, otherwise each node keeps forwarding until the RREQ packet reaches the destination indicated in the path.
There are three types of messages in DSR for its routing. Firstly, Route Request Message (RREQ) is used for discovery a route. Secondly, Route Reply Message (RREP) is generated in response of RREQ message which contains route information. These two messages are used in route discovery process. Finally, Route Error Message (RERR) is generated when a broken link is discovered in the network. This message is used for route maintenance process. DSR has two mechanisms; Route Discovery and Route Maintenance. These mechanisms will allow DSR to discover and maintain routes for particular destination nodes in the network.
Route Discovery
Route discovery is the mechanism by which source node discovers route for destination. In route discovery, the source node floods the route request packet throughout the network, and the reply is returned either through the destination node or through any intermediate nodes which contains the route to destination in its route cache. For example, if source Node A wishes to send packet to Destination Node B, it obtains a source route for Node B. This route discovery is initiated only when Node A tries to send packet for Node B and does not find any route in its own route cache. Finding a route for destination will be purely on demand using the route discovery mechanism.
Route discovery mechanism
In route discovery mechanism, for example in figure (2.1), Node A broadcasts a Route Request Packet (RREQ) in the network to discover route for Node B. This RREQ contains the address of initiator (source node A in this scenario), the address of target node (Destination Node B), maximum hop-count (how many nodes this packet will traverse), and Route Request number, which is set by the initiator of the route discovery message. This route request number identifies different route requests from different nodes. Each node maintains a routing table in which it adds request number before propagating these requests to the next node. An Up-to-date table also avoids duplication of route request process by each node. The request which is initiated by source Node A reaches an intermediate Node C. The Node C checks its route cache to determine the route for the destination. If successful, it makes a RREP Packet and appends its own address to RREQ packet and combines the route which is found from its route cache (route from C to B). If unsuccessful, Node C also initiates a route discovery like Node A with the same route request number set by Node A. Same route discovery procedure will be applied by every intermediate node until the packet reaches its destination or some intermediate node will reply from its route cache. Finally, when the packet reaches the destination node, destination Node B will add its own address at the end of the packet’s route (containing whole path information through which this packet has travelled). Now the destination reverses this route and makes a RREP packet. The RREP packet traverses in the opposite direction from where it came from, until it reaches the initiator of this route discovery.