Dynamic Source Routing DSR Johnson Maltz 96 Broch et al 98 00 g g g When node S wants to send a packet to node D but does not know a route to D node S initiates a route discovery Source node S floods the network with route request RREQ packets also called query packets Each node appends its own address in the packet header when forwarding RREQ Samir R Das 19 University of Cincinnati Route Discovery in DSR S S RREQ broadcast E F A C G B D represents a node that has received RREQ for D from S X Represents list of addresses appended to RREQ A node receiving a RREQ rebroadcasts it exactly once Samir R Das University of Cincinnati 20 1 Route Discovery in DSR S E S S A RREQ broadcast E F A C G S C D B represents a node that has received RREQ for D from S X Represents list of addresses appended to RREQ A node receiving a RREQ rebroadcasts it exactly once Samir R Das 21 University of Cincinnati Route Discovery in DSR S F A S A B RREQ broadcast E S E F C G B D S C G Destination D receives RREQ via G and F It does not broadcast it further Samir R Das University of Cincinnati 22 2 Route Discovery in DSR g g g Destination D on receiving the first RREQ sends a Route Reply RREP RREP is sent on a route obtained by reversing the route appended to received RREQ RREP includes the reverse route from S to D on which RREQ was received by node D Samir R Das 23 University of Cincinnati Route Reply in DSR S RREP Unicast E F A C G B D F E S D Reverse route in the header of RREP Samir R Das University of Cincinnati 24 3 Route Caching in DSR g g g Node S on receiving RREP caches the route included in the RREP When node S sends a data packet to D the entire route is included in the packet header n Hence the name source routing Intermediate nodes use the source route included in a packet to determine to whom a packet should be forwarded Samir R Das 25 University of Cincinnati Data Delivery in DSR DATA S E F D Cache on S S E F D S E F A DATA packet Unicast C G B D Source route size grows with route length Samir R Das University of Cincinnati 26 4 Route Error DATA S E F D Cache on S S E F D S E F A DATA packet Unicast C G B g D If the next hop link is broken when a data packet is being forwarded a Route Error RERR is generate and propagated backwards Samir R Das University of Cincinnati 27 Route Error Cache on S S E F D S A B g g RERR F E S Failed link FD E F RERR is C Unicast G D If the next hop link is broken when a data packet is being forwarded a Route Error RERR is generate and propagated backwards RERR contains the failed link info Samir R Das University of Cincinnati 28 5 Route Error Cache on S S E F D S A B g RERR F E S Failed link FD E F RERR is C Unicast G D When S receives RERR it erases any cached route with the failed link Samir R Das University of Cincinnati 29 Aggressive Route Caching g g g g g Each node caches a new route it learns by any means When node S finds route S E F D to node D node S also learns route S E F to node F and so on When node G receives RREQ S C destined for node D node G learns route G C S to node S and so on When node F forwards RREP D F E S node F learns route F D to node D and so on Basically when forwarding any packet the node learns a route to all nodes in the source route contained in the packet Samir R Das University of Cincinnati 30 6 Contents of Caches on Selected Nodes After one RREQ RREP Cycle S E F A C G B g g g F E S F D F G C S D D F E S D G C S P Q R represents cached route at a node P More than one routes may be cached for the same destination Compact data structures may be used to implement route caches e g tree Samir R Das University of Cincinnati 31 Use of Route Caching g Salvaging When node S learns that a route to node D is broken it uses another route from its local cache if such a route to D exists in its cache n g g Otherwise node S initiates route discovery by sending a route request Reply from Cache Node X on receiving a RREQ for some node D can send a Route Reply if node X knows a route to node D Aggressive use of route cache n n can speed up route discovery can reduce propagation of route requests Samir R Das University of Cincinnati 32 7 Route Caching Beware g g g Stale caches can adversely affect performance With passage of time and host mobility cached routes may become invalid All cached routes containing a failed link are not erased by route error RERR n g Only that route is erased that is attempted to be used A sender host may try several stale routes obtained from local cache or replied from cache by other nodes before finding a valid route Samir R Das University of Cincinnati 33 Dynamic Source Routing Advantages g g Source routing no special mechanism needed to eliminate loops On demand routing Routes maintained only between nodes who need to communicate n g g Reduces overhead of route maintenance Route caching can further reduce route discovery overhead A single route discovery may yield many routes to the destination due to intermediate nodes replying from local caches n Useful when route breaks Samir R Das University of Cincinnati 34 8 Dynamic Source Routing Disadvantages g g g Not scalable Packet header size grows linearly with route length due to source routing Network wide flood Flood of route requests may potentially reach all nodes in the network Too much overhead Collision Care must be taken to avoid collisions between route requests propagated by neighboring nodes n g insertion of random delays before forwarding RREQ Reply storm problem Increased contention if too many route replies come back due to nodes replying using their local cache n Reply storm may be eased by preventing a node from sending RREP if it hears another RREP with a shorter route Samir R Das University of Cincinnati 35 Dynamic Source Routing Disadvantages g g g Stale cache problem An intermediate node may send Route Reply using a stale cached route thus polluting other caches This problem can be eased …