Introduction

• What are Mobile Adhoc Networks (MANETs)?
• Routing in MANETs
• Traditional algorithms not feasible
• Two main types of Protocol:
• Proactive / Table Driven (examples: DSDV,CGSR etc.)
• Reactive / On-demand (example AODV, DSR etc.)

Destination Sequenced Distance Vector Routing

• Each node maintains a routing table determining next hop for every other node

​

Destination Next Hop Metric Seq #

2 1 4 2

3. 5 5 9

7 7 1 50

Routing Table For Node 4

Destination Sequenced Distance Vector Routing

• Routing Table Management
• Periodic broadcasts / immediate broadcasts when topology changes
• Full Dump / Incremental dumps
• Broadcast starts with neighbors with metric equals to 1
• Neighbors increment the metric and rebroadcast to its neighbors. This Process continues until destination is reached. Destination updates its entries if its sequence number is less than new sequence number
• Sequence number determines the freshness of information

Cluster Head Gateway Switch Routing (CSGR)

• Nodes are organized as clusters with one node acting as cluster head (CH)
• Uses DSDV as underlying protocol
• A gateway node is a node that is within communication range of two/more CH
• Packet sent by a node is first routed to its CH and then to gateway to another CH until destination CH is reached. The destination CH will send the packet to the destination

Cluster Head Gateway Switch Routing (CSGR)

• Every node maintains cluster member table which stores cluster heads of every destination that is updated just like broadcasting in DSDV
• In addition a routing table is also maintained by every node.

​

Ad-hoc On-Demand Distance Vector Routing

• Built on DSDV
• Route Discovery
• RREQ packet is sent to neighbors to determine route to destination
• On receiving a packet, a node checks if it is the destination / if it knows the complete path to destination. Failing to meet these two conditions, node will forward the packets to its neighbors
• Intermediate nodes creates a reverse path while forwarding

​

​

​

Ad-hoc On-Demand Distance Vector Routing

• If packet reached destination or a node with fresh route, a reply is uni-casted
• As packet is going back, a forward entry is made into every intermediate node
• Used for symmetric links only
• Route Maintenance
• If a node moves, its neighbor notices and propagates notification (RREP with infinite metric) to upstream routers, upstream will notify to its upstream routers and so on until source is reached
• Source will then re-initiate the discovery process

Ad-hoc On-Demand Distance Vector Routing

• RFC 3561 – http://www.ietf.org
• Ad-hoc Support Library http://aslib.sourceforge.net/
• Ad-hoc Support Library (ASL) is a user-space library which provides an API to facilitate implementation of routing protocols for wireless ad-hoc networks in Linux.
• In development phase. Beta version is available

​

​

​

​

Dynamic Source Routing

• Based on Source Routing
• Route cache maintains the path it is aware of
• Route Discovery
• RREQ is sent to neighbors
• If intermediate nodes doesn’t know of the destination, it appends its own address to the packet and forwards the packet to its destination.
• If a packet reached the destination, RREP is generated

Dynamic Source Routing

• If an intermediate node knows about the destination it appends its cached route to the packet route and generates a RREP
• To return RREP, node checks if it has a path to source, it will use that route
• If symmetric routes are supported, node can reply by just reversing packet route
• Else node will initiate its own route discovery and piggyback the route reply on new request

​

​

Dynamic Source Routing

• IETF Draft http://www.monarch.cs.rice.edu/internet-drafts/draft-ietf-manet-dsr-01.txt
• picoNet http://piconet.sourceforge.net/
• API for Linux
• In development phase
• Monarch Project http://www.monarch.cs.rice.edu/dsr-impl.html
• DSR Implementation by Rice University
• In Development Phase
• Implementation contains most of the features of IETF Draft

​

Preemptive Ad-hoc On Demand Distance Vector Routing

• Two preemptive mechanisms
• Reschedule discovery in advance
• Reply packets contains information about life time of the newly discovered path
• Based on life time, a path discovery can be rescheduled
• Warning Messages
• When transfer time of packet to its neighbor is too high, that node is monitored
• If monitoring indicates this link is going to break, warning message is sent to the source
• Source then invokes the rediscovery process

Associativity-Based Routing

• A new routing metric known as degree of association stability
• Each node sends periodically beacon messages to neighbors
• Associativity ticks is incremented for ever beacon messages

​

Associativity-Based Routing

• Route Discovery
• Node broadcasts a BQ message
• Nodes receiving this message appends append their address and associativity ticks with respect to neighbors along with QoS information to message and forwards to destination
• Destination is then able to select the best route based on associativity ticks
• Destination will then generate a REPLY back to the source along this path

Signal Stability Routing

• Selects routes based on signal strength
• Two Cooperative Protocols:
• Dynamic Routing Protocols (DRP)
• Maintains Signal Stability Table (SST) and Routing Table (RT)
• SST records signal strength of neighboring nodes obtained by periodic beacons from link layer of each neighboring nodes. Strength are recorded as weak/strong
• After updating all table entries, DRP passes a received packet to the SRP

​

​

Signal Stability Routing

• Static Routing Protocol (SRP)
• SRP passes the packets up to the stack, if it is the intended destination
• Otherwise, it will forward the packet to next hop based on RT
• If no entry is found, route search process in initiated
• A node forwards a route requests only if they are received over a strong channel and have not processed previously
• Destination chooses the first arriving route-search packet to send back
• DRP then reverses the selected route and sends a route-reply message back to the initiator
• If no reply packet reaches the source within specified time, source changes a field in header to make weak channels acceptable

Summary and Conclusion

• Different types of Routing Protocols for Ad hoc networks are described
• Proactive protocols have good throughput than Reactive protocols, however proactive protocols have more routing load
• Presently different routing protocols are under study by IETF MANET working group for evaluation and standardization. These include:
• Ad hoc On-Demand Distance Vector Routing Protocol
• Dynamic Source Routing Protocol
• Zone based Routing Protocol
• Temporally Ordered Routing Protocol

References

• ‘A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks’, Elizabeth M. Royer, Santa Barbara, Chai-Keong Toh
• ‘Performance Evaluation of Routing Protocols for Ad hoc Wireless Networks’, Azzedine Boukerche
• ‘Routing protocols For Mobile ad-hoc networks’ , Amit Jain, Indian Institute of Technology, Kanpur
• ‘Request for Comments: 3561’, IETF MANET Working Group

​