Presentation On: Ad Hoc Routing
Routing Overview
Network with nodes, edges Goal: Devise scheme for transferring message from one node to another
Which path? Who decides source or intermediate nodes?
msg
Which path?
Generally try to optimize something:
Shortest path (fewest hops(node to node distance)) Shortest time (lowest latency(time delay)) Shortest weighted path (utilize available bandwidth)
Who determines route?
Two general approaches: Source (path) routing
Source specifies entire route: puts complete path to destination in message header: A D FG Intermediate nodes just forward to specified next hop: D would look at path in header, forward to F Like airline travel get complete set of tickets to final destination before departing
Destination (hop-by-hop) routing
Source specifies only destination in message header: G Intermediate nodes look at destination in header, consult internal tables to determine appropriate next hop Like postal service specify only the final destination on an envelope, and intermediate post offices select where to forward next
Comparison
Source routing
Moderate source storage (entire route for each desired dest.) No intermediate node storage Higher routing overhead (entire path in message header)
Destination routing
No source storage High intermediate node storage (table with routing instructions for all possible dests.) Lower routing overhead (just destination in header)
Ad Hoc Routing
Every node participates in routing: no distinction between routers and end nodes No external network setup: selfconfiguring Especially useful when network topology is dynamic (frequent network changes links break, nodes come and go)
The network is called ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points in managed (infrastructure) wireless networks. Instead, each node participates in routing by forwarding data to other nodes, and so the determination of which nodes to forward the data is made dynamically based on the network connectivity.
Common application
Mobile wireless hosts
No External setup (Self Configuring) Communication between wireless nodes
Ad Hoc Routing Protocols
DSR: Dynamic Source Routing
Source routing protocol
AODV: Ad-hoc On-demand Distance Vector Routing
Hop-by-hop protocol
Both are on demand protocols: route information discovered only as needed
Dynamic Source Routing
Source routing: entire path to destination supplied by source in packet header
Utilizes extension header following standard IP header to carry protocol information (route to destination, etc.)
DSR Protocol Activities
Route discovery
Undertaken when source needs a route to a destination
Route maintenance
Used when link breaks, rendering specified path unusable
Routing
Route Discovery
Route Request:
Source broadcasts Route Request message for specified destination.
Route Reply
Destination unicasts Route Reply message to source. Intermediate node may return Route Reply to source if it already has a path stored
Route Maintenance
Used when link breakage occurs
Link breakage may be detected using link-layer ACKs, passive ACKs, DSR ACK request Route Error message sent to source of message when break detected.
Ad-hoc On-demand Distance Vector Routing
Hop-by-hop protocol: intermediate nodes use lookup table to determine next hop based on destination Utilizes only standard IP header
AODV Protocol Activities
Route discovery
Undertaken whenever a node needs a next hop to forward a packet to a destination
Route maintenance
Used when link breaks, rendering next hop unusable
Routing
Route Discovery
Route Request:
Source broadcasts Route Request (RREQ) message for specified destination Intermediate node:
Forwards (broadcasts) message toward destination Creates next-hop entry for reverse path to source, to use when sending reply (assumes bidirectional link)
Route Reply
Destination unicasts Route Reply (RREP) message to source
RREP contains sequence number, hop-count field (initialized to 0) Will be sent along reverse path hops created by intermediate nodes which forwarded RREQ
Intermediate node:
Create next-hop entry for destination as RREP is received, forward along reverse path hop Increment hop-count field in RREP and forward
Route Maintenance
Used when link breakage occurs
Link breakage detected by link-layer ACK, passive ACK, AODV Hello messages
Detecting node may attempt local repair
Send RREQ for destination from intermediate node
Route Error (RERR) message generated
Thank You