DSR The Dynamic Source Routing Protocol for Multi Hop Wireless Ad Hoc Networks David B Johnson David A Maltz Josh Broch slides Patrick DSR Goals Assumptions Multihop wireless networks as opposed to 802 11 infrastructure mode Dynamic topology Find shortest path number of hops Question is this the right metric Uni directional or bi directional links Promiscuous mode for optimisations Why a new routing protocol Conventional wired routing protocols E g link state distance vector Pro active Hop by hop DSR On demand Source routed Why Pro active vs On demand Pro active Continuously maintains routes to all destinations Creates a lot of overhead But capacity is precious On demand Routing packets exchanged only when route is needed Overhead scales to routes currently in use Aside inspired by ARP Disadvantages What about latency Source routing vs Hop by hop Hop by hop Intermediate nodes know nexthop for a destination Potential for routing loops during convergence especially if nodes move around Source routing Sender includes list of hops in each data packet Enables aggressive snooping of routes But overhead in each data packet Other reasons why wired protocols don t cut it DSR Route discovery Give me a route Snooping Route maintenance Your route is broken Here is a shorter route Route Discovery Three cases Case 1 answered by destination Case 2 overhear and cache Case 3 answered from other node s cache Route Discovery Case 1 Route Reply A B C D Route Request A B C D Sender uses exponential back off for same target Route Discovery Case 2 Aggressive caching of overheard routes Anything goes Source routes in data packets Routes in route requests Routes in route replies Route Discovery Case 2 What if caches get stale Route error discussed later clears caches Route Discovery Case 3 Route Reply A B C D From cache Route Request A B C D Route Discovery Case 2 Corner cases e g Route Discovery What if MAC requires bi directionality Note route request is broadcast 802 11 broadcasts are not acked Solution Route Reply uses reverse route Route Discovery Multiple routes may result Good allows fail over How destination may return multiple routes Intermediate nodes cannot return multiple routes Req id prevents this What about unidirectional links Route Discovery Other features Prevent route reply storms Non propagating route requests Route Maintenance Each node ensures next hop receives e g 802 11 ACK Passive acknowledgement Software acknowledgement Trigger route error if not acked Route Maintenance Route Error Retransmission by higher layer TCP Route Maintenance Route error responsible for clearing caches Piggyback route error on route requests Forward router error along error path Route Maintenance Other features Packet salvaging Automatic route shortening Gratuitous route reply Caching negative information Protocol stack Layer 3 Support multiple link layer types Seamless interoperation with Internet Mobile IP Support multicast functionality But implemented as broadcast Simulation Ns 2 Implemented detailed physical link layer model 802 11 DCF ARP Simulation 50 mobile nodes in 1500m x 300m area Of which 10 20 30 traffic sources Constant bit rate UDP 4 packets second Movement random waypoint model Simulation Evaluation Loss rate Routing overhead What about latency Testbed Testbed 5 mobile nodes 10 meters second 2 stationary nodes 700 meters distance WaveLAN PCMCIA PC Cards 900 MHz Variety of data traffic tyepes and loads No evaluation presented Summary Novel approach on demand source routing Metric shortest path may not be optimal Not evaluated Latency may be a weak point Cache miss rate Behaviour under congestion lossy links etc
View Full Document
Unlocking...