Routing Protocols for Mobile Ad Hoc Network
10/17/05
Outline
Introduction to mobile ad hoc network Ad hoc protocol routing requirements Categorization of ad-hoc routing protocols Representative Ad hoc protocols Destination-sequenced Distance-vector (DSDV) Ad-hoc On-demand Distance Vector (AODV) Dynamic Source Routing (DSR)
Mobile ad hoc network (MANET)
Self-configuring network of mobile stations connected by wireless links Defined as Independent Basic Service Set (IBSS) in IEEE 802.11 standards Peer-to-peer communication without using Access Point (AP) or any wired network Dynamic topology
mobile nodes free to move randomly mobile stations form an arbitrary topology
Mobile ad hoc network (MANET)
d d
Mobile station has router function Peer to peer communication, no central control Multi-hop routes between nodes
Characteristics of MANETs
A s
B d
A s
B d
Dynamic topology
links formed and broken with mobility
Possibly uni-directional links Constrained resources
battery power wireless transmitter range
Network partitions
Routing in MANETs Goal: To find and maintain routes between
nodes in a dynamic topology with possibly uni-directional links, using minimum resources.
Ad Hoc Protocol Routing Requirements
Simple, reliable and efficient Distributed but lightweight in nature Quickly adapts to changes in topology Protocol reaction to topology changes should result in minimal control overhead Bandwidth efficient Mobility management involving user location and hand-off management
Categorization of Ad-Hoc Routing Protocols
Figure from Elizabeth M. Royer, C-K Toh, A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks.
Table Driven Based Routing (Proactive)
Maintain table of all active links in network Calculate the shortest path from table Update table whenever nodes move Immediate tell if node is reachable Data can be sent immediately Very high overheads DSDV
On-demand Routing(Reactive)
Find routes as needed Cache information from other nodes requests No static overhead Slow start before transmitting data AODV, DSR
Representative Ad Hoc Routing Protocols
Destination-Sequenced Distance-Vector Routing (DSDV)- Proactive(table driven), next-hop routing, distance-vector Ad hoc On-demand Distance-Vector Routing (AODV)-reactive,next hop routing,distancevector Dynamic Source Routing (DSR)-reactive (on demand),source routing,link state
DSDV Routing
[Charles Perkins & Pravin Bhagwat]
Current in use on the MIT GRID projects
Route advertisements Route table entry structure Responding to topology changes Route selection criteria Summary
Route Advertisements in DSDV Each mobile node advertise its own route tables to its current neighbors Routing tables update periodically to adapt the dynamic change and maintain table consistency
Route Table Entry Structure in DSDV
When advertisement, each mobile node contain its new sequence number and the following information for each new route
The destinations address The number of costs (hops) required to reach the destination The sequence number of the information received,originally stamped by the destination.
Example of Advertised Table in DSDV
MHi -address for the mobile node, MH4 is the node advertising the route table update
Table from Charles [Link], AD HOC Networking
Responding to Topology Changes in DSDV
Two types of packets defined for route updates full dump packets
Carry all available routing information Size of multiple network protocol data units (NPDUs) Transmitted infrequently during period of occasional movement
Incremental packets
Carry only information changed since last full dump Size of a NPDU Transmitted more frequently Additional table maintained to store the data from the incremental packets
Route Selection Criteria
Routes are preferred if the sequence numbers are newer If the sequence numbers are the same, the one with better metric is preferred Keep track of the settling time of routes-the weighted average time that routes to a destination will fluctuate before the route with best metric is received (Why?)
Route Settling Time and Solution
MN collection 1 B
MN collection 2 C D
Problem
A initiated a route update with a new sequence number Update from B arrives D 10 s before update from C Metric of update from C is better (less hops) Solution delay the broadcast of a routing by the length of the settling time. Exception:When broken link is found, broadcast immediately
Summary of DSDV Routing
Essentially a modification to Bellman-Ford routing algorithm Using sequence number to guarantee loop-free paths Relies on periodic exchange of routing information. Inefficient due to periodic update transmissions even no changes in topology Overhead grows as O(n2) , limiting scalability
Dynamic Source Routing (DSR)
[Dave Johnson] Internet drafts available on MANET webpage Reactive (on demand) Source routing Based on link-state routing algorithm
Route Discovery in DSR (1/6)
Sender floods RREQ through the network Nodes forward RREQs after appending their names Destination node receives RREQ and unicasts a RREP back to sender node
Route Discovery in DSR (2/6)
Z S B A H I C G K D N E F J M L
Represents node that has received RREQ originated from S to D RREQ includes: the source IP address, the destination IP, a unique request ID
Route Discovery in DSR(3/6)
Broadcast transmission [S] S B A H I C G K D N E F J M L Z Y
Represents transmission of RREQ [X,Y] Represents list of identifiers appended to RREQ
Route Discovery in DSR(4/6)
Z S B A H I C [S,C] G K D E [S,E] F J M
Route Discovery in DSR (5/6)
Z S B A H I Node C G [S,C,G] K D E F [S,E,F] J M
C receives RREQ from G and H, but does not forward it again, because node C has already forwarded RREQ once
Route Discovery in DSR(6/6)
Z S B A H I C G K D [S,C,G,K] E F [S,E,F,J] J M
Nodes J and K both broadcast RREQ to node D
Target Node Reaction
Node D examines its route cache, if a route to S found, use it as source route for [Link],
May perform its own route discovery to S, piggyback the RREP on its own RREQ to S Simply reverse the sequence of hops in the route record
Preferred by IEEE 802.11 that require a bidirectional frame exchange Avoids the overhead of a possible second route discovery Tests the discovered route
Advantage : support asymmetric link
Route Reply in DSR
Y Z S B A H I Represents RREP control message C G K D N E RREP [S,E,F,J,D] F J M L
Route reply with its associated route record back to the source node
Summary of DSR Routing
Potentially larger overhead Intended for moderate speed mobile nodes, source
routing, not scalable to large networks No network topology changes, no overhead Support asymmetric link Allow nodes keep multiple routes to one destination in their cache, faster route recovery
References
1. Romit Roy Choudhury and Nitin H. Vaidya, Impact of Directional Antennas on Ad Hoc Routing. 2. Elizabeth M. Royer, C-K Toh, A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks. 3. Charles E. Perkins, AD HOC Networking