Optimized Link State Routing (Olsr) Protocol and Comparison of Various Table-Driven Routing Protocols

MANETs can communicate with different networks that are not ad-hoc. Therefore, they can communicate with wired networks creating hybrid networks. In the ad-hoc networks, the mobility of the nodes makes that the topology changes continuously. Hence, a specific dynamic routing protocol for MANETs which discovers and maintains the routes, and deletes the obsolete routes continuously is necessary. The routing protocols for MANETs try to maintain the communication between a pair of nodes (source-destination) in spite of the position and velocity changes of the nodes. To achieve that, when those nodes are not directly connected, the communication is carried out by forwarding the packets, by using the intermediate nodes. Currently there is research on the behaviour of a lot of those routing protocols and the IETF (Internet Engineering Task Force) is working on the standardisation of some of them. The protocols that are in experimental phase RFC (Request For Comments) include DYMO (Dynamic MANET On demand Routing Protocol) [DYMO_06], OLSR [OLSR_03], AODV [AODV_03], DSR (Dynamic Source Routing) [DSR_04] and TBRPF (Topology Dissemination Based on Reverse Path Forwarding) [TBRPF_04]. The origin of MANETs begins in the 70’s for the military necessity of the interconnection of different hosts. This type of networks was implanted to avoid the need of a central base of communications. With these networks it was expected to transmit information in a fast and stable way as well as to cover the major part of the possible range without the necessity of having a previous infrastructure.

Available online at www.ignited.in Page 2

Reactive Routing Protocol (RRP) is a bandwidth-efficient on-demand routing protocol for MANETs. In this protocol the originator node initiates the route search process, whenever it needs to send data packets to a target node. Thus the need for a route triggers the process of route search, hence the name Reactive Routing Protocol. RRP is intended to be implemented in the network layer of mobile nodes i.e. in the layer 3 of ISO OSI reference model. Route Discovery and Route Maintenance functions of the protocol are described next.

The Destination-Sequenced Distance-Vector (DSDV) routing protocol is a table-driven algorithm based on Bellman-Ford routing mechanism. The improvements made by to the Bellman-Ford algorithm include freedom from loops in routing tables. In DSDV every node in the network maintains a routing table in which all of the possible destinations within the network and the number of hops to each destination are recorded. Each entry is marked with a sequence number assigned by the destination node. The sequence numbers enable the mobile nodes to distinguish stale routes from new ones, thereby avoiding the formation of routing loops. Routing table updates are periodically transmitted throughout the network in order to maintain table consistency. To help alleviate the potentially large amount of network traffic that such updates can generate, route updates can employ two possible types of packets: full dump and smaller incremental packets. Each of these broadcasts should fit into a standard-size of network protocol data unit (NPDU), thereby decreasing the amount of traffic generated. The mobile nodes maintain an additional table where they store the data sent in the incremental routing information packets. New route broadcasts contain the address of the destination, the number of hops to reach the destination, the sequence number of the information received regarding the destination, as well as a new sequence number unique to the broadcast. The route labeled with the most recent sequence number is always used. In the event that two updates have the same sequence number, the route with the smaller metric is used in order to optimize (shorten) the path. Mobiles also keep track of the settling time of routes, or the weighted average time that routes to a destination will fluctuate before the route with the best metric is received. By delaying the broadcast of a routing update by the length of the settling time, mobiles can reduce network traffic and optimize routes by eliminating those broadcasts that would occur if a better route was discovered in the very near future.

Optimized link state routing (OLSR) protocol [4] is a proactive routing protocol and based on periodic exchange of topology information. The key concept of OLSR is the use of multipoint relay (MPR) to provide an efficient flooding mechanism by reducing the number of transmissions required. In OLSR, each node selects its oMANET MPR from its neighbors. Each MPR node maintains the list of nodes that were selected as an MPR; this list is called an MPR selector list. Only nodes selected as MPR nodes are responsible for advertising, as well as forwarding an MPR selector list advertised by other MPRs. Generally, two types of routing messages are used in the OLSR protocol, namely, a HELLO message and a topology control (TC) message. A HELLO message is the message that is used for neighbor sensing and MPR selection. In OLSR, each node generates a HELLO message periodically. A node’s HELLO message contains its MANET address and the list of its one-hop neighbors. By exchanging HELLO messages .each node can learn a complete topology up to two hops. HELLO messages are exchanged locally by neighbor nodes and are not forwarded further to other nodes. A TC message is the message that is used for route calculation. In OLSR, each MPR node advertises TC messages periodically. A TC message contains the list of the sender’s MPR selector. In OLSR, only MPR nodes are responsible for forwarding TC messages. Upon receiving TC messages from all of the MPR nodes, each node can learn the partial network topology and can build a route to every node in the network. For MPR selection, each node selects a set of its MPR nodes that can forward its routing messages. In OLSR, a node selects its MPR set that can reach all its two-hop neighbors. In case there are multiple choices, the minimum set is selected as an MPR set.

Mobile routing protocols (MRP) is a path-finding algorithm with the exception of avoiding the count-to-infinity problem by forcing each node to perform consistency checks of predecessor information reported by all its neighbors. MRP is a loop free routing protocol. Each node maintains 4 tables: distance table, routing table, link cost table & message retransmission list table. Link changes are propagated using update messages sent between neighboring nodes. Hello messages are periodically exchanged between neighbors. This protocol avoids count-to infinity problem by forcing each node to check predecessor information.

Available online at www.ignited.in Page 3

Cluster head gateway switch routing (CGSR) protocol is based on a cluster multihop mobile network with several heuristic routing schemes. The authors state that by having a cluster head controlling a group of ad hoc nodes, a framework for code separation (among clusters), channel access, routing, and bandwidth allocation can be achieved. A cluster head selection algorithm is utilized to elect a node as the cluster head using a distributed algorithm within the cluster. However, frequent cluster head changes can adversely affect routing protocol performance since nodes are busy in cluster head selection rather than packet relaying. Hence, instead of invoking cluster head reselection every time the cluster membership changes, a Least Cluster Change (LCC) clustering algorithm is introduced. Using LCC, cluster heads only change when two cluster heads come into contact, or when a node moves out of contact of all other cluster heads. CGSR uses DSDV as the underlying routing scheme, and hence has much of the same overhead as DSDV. However, it modifies DSDV by using a hierarchical cluster-head-to-gate-way routing approach to route traffic from source to destination. Gateway nodes are nodes that are within communication range of two or more cluster heads. A packet sent by a node is first routed to its cluster head, and then the packet is routed from the cluster head to a gateway to another cluster head, and so on until the cluster head of the destination node is reached. The packet is then transmitted to the destination.

Based on important characteristics and parameters of routing protocol, the various table-driven ad hoc routing protocols have been compared in Table 1. It can be observed that the time and communication complexity of these protocols is very high and requires periodic messaging for determining the up-to-date network topology, thus causing network congestion. The next section discusses several routing protocols based on on-demand-driven approach.

On demand protocols create routes only when desired by source nodes. When a node requires a route to destination, it initiates route discovery process within the network. This process is completed once a route is found or all possible route permutations are examined. Once a route is discovered and established, it is maintained by route maintenance procedure until either destination becomes inaccessible along every path from source or route is no longer desired.

[1] Elizabeth M. Royer and Chai-Keong Toh, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks”, IEEE Personal Communications Magazine, April 1999, pages 46-55. See also http://citeseer.nj.nec.com/royer99review.html [2] Borko Furht and Mohammad Ilyas. Wireless Internet Handbook: Technologies, Standards, and Applications. Chapter 16. Auerbach Publications, 2003 [3] Dave B. Johnson and David A. Maltz. The dynamic source routing protocol for mobile ad hoc networks. Internet Draft, Mobile Ad Hoc Network (MANET) Working Group, IETF, October 1999. [4] L. Zhou and Z. J. Haas. Securing ad hoc networks. IEEE Network Magazine, 13(6):24–30, November/December 1999. [5] S. Marti, T. J. Giuli, K. Lai, and M. Baker. Mitigating routing misbehavior in mobile ad hoc networks. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking, pages 255–265, 2000. [6] K. Sanzgiri, B. Dahill, B.N. Levine, C. Shields and E.M. Royer, “A Secure Routing Protocol for Ad hoc Networks”, Proc. 10th IEEE Int’l. Conf. Network Protocols (ICNP’02), IEEE Press, 2002, pp. 78-87. [7] J.-P. HuBaux, L. Buttyan, and S. Capkun. The quest for security in mobile ad hoc networks. In Proc. ACM MOBICOM, Oct. 2001. [8] J. Kong et al. Providing robust and ubiquitous security support for mobile ad-hoc networks. In Proc. IEEE ICNP, pages 251–260, 2001. [9] S. Yi, P. Naldurg, and R. Kravets. Security-aware ad hoc routing for wireless networks. In Proc. ACM Mobihoc, 2001. [10] P. Papadimitratos and Z. J. Haas. Secure routing for mobile ad hoc networks. SCS Communication Networks

Available online at www.ignited.in Page 4

and Distributed Systems Modeling and Simulation Conference (CNDS 2002), Jan 2002. [11] Y. C. Hu, A. Perrig, and D. Johnson. Ariadne: A secure on-demand routing protocol for ad hoc networks. Technical Report TR01-383, Rice University, Dec. 2001. [12] A. Perrig, R. Canetti, D. Song, and D. Tygar. Efficient and secure source authentication for multicast. In Network and Distributed System Security Symposium (NDSS’01), Feb. 2001. [13] S. Buchegger, and J.-Y. Le Boudec, “Performance Analysis of the CONFIDANT Protocol (Cooperation Of Nodes: Fairness In Dynamic Ad hoc NeTworks),” Proc. 3rd Symp. Mobile Ad hoc Networking and Computing (MobiHoc 2002), ACM Press, 2002, pp. 226-236. [14] Mobile Ad-hoc Networks (MANET),http://www.ietf.org/html.charters/manetcharter. html. (1998-11-29). [15] PERKINS, C. E., Ed. Ad Hoc Networking. Addison–Wesley Publishing Company, 2001. ISBN: 0-201-30976-9. [16] SCHILLER, J. Mobile Communications. Addison–Wesley Publishing Company, 2000. ISBN: 0-201-39836-2. [17] E.M. Royer, C-K. Toh, A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks, IEEE Personal Communications Magazine, April 1999, pp. 46-55. http://www.cs.ucsb.edu/~eroyer/publications.html [18] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance Vector Routing (DSDV) for Mobile Computers,” Comp. Commun. Rev., Oct. 1994, pp. 234–44. [19] L. R. Ford Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, 1962 [20] S. Murthy and J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Networks and App. J., Special Issue on Routing in Mobile Communication Networks, Oct. 1996, pp. 183–97.. [21] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc Wireless Networks,” Mobile Computing, T. Imielinski and H. Korth, Eds., Kluwer, 1996, pp. 153 81. [22] C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” Proc. 2nd IEEE Wksp. Mobile Comp. Sys. and Apps., Feb. 1999, pp. 90–100. [23] D. Caˆ mara, A. A. F. Loureiro, and F. Filali. Methodology for formal verification of routing protocols for ad hoc wireless networks, IEEE GLOBECOM 2007, Washington DC, November 2007.