DOC PREVIEW
SBU CSE 590 - Dynamic Source Routing (DSR)

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

119Samir R. Das University of CincinnatiDynamic Source Routing (DSR) [Johnson-Maltz-96,Broch et. al. 98-00]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.g Source node S floods the network with route request (RREQ) packets (also called query packets).g Each node appends its own address in the packet header when forwarding RREQ.20Samir R. Das University of CincinnatiRoute Discovery in DSRASEFBCGDRREQ broadcast[S]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.221Samir R. Das University of CincinnatiRoute Discovery in DSRrepresents a node that has received RREQ for D from S.ASEFBCGDRREQ broadcast[S,E][X,..,..] Represents list of addresses appended to RREQ.[S,C][S,A]A node receiving a RREQ rebroadcasts it exactly once.22Samir R. Das University of CincinnatiRoute Discovery in DSRASEFBCGDRREQ broadcast[S,E,F][S,C,G][S,A,B]Destination D receives RREQ via G and F.It does not broadcast it further.323Samir R. Das University of CincinnatiRoute Discovery in DSRg Destination D on receiving the first RREQ, sends a Route Reply (RREP).g RREP is sent on a route obtained by reversing the route appended to received RREQ.g RREP includes the reverse route from S to D on which RREQ was received by node D.24Samir R. Das University of CincinnatiRoute Reply in DSRASEFBCGDRREP Unicast[D,F,E,S]Reverse routein the header of RREP425Samir R. Das University of CincinnatiRoute Caching in DSRg Node S on receiving RREP, “caches” the route included in the RREP.g When node S sends a data packet to D, the entire route is included in the packet headern Hence the name source routing.g Intermediate nodes use the source routeincluded in a packet to determine to whom a packet should be forwarded.26Samir R. Das University of CincinnatiData Delivery in DSRASEFBCGDCache on S:[S,E,F,D]DATA [S,E,F,D]DATA packetUnicastSource route size grows with route length.527Samir R. Das University of CincinnatiRoute Errorg If the next hop link is broken when a data packet is being forwarded, a Route Error (RERR) is generate and propagated backwards.ASEFBCGDCache on S:[S,E,F,D]DATA [S,E,F,D]DATA packetUnicast28Samir R. Das University of CincinnatiRoute Errorg If the next hop link is broken when a data packet is being forwarded, a Route Error (RERR) is generate and propagated backwards.g RERR contains the failed link info.ASEFBCGDCache on S:[S,E,F,D]RERR [F,E,S] [Failed link = FD]RERR isUnicast629Samir R. Das University of CincinnatiRoute Errorg When S receives RERR, it erases any cached route with the failed link.ASEFBCGDCache on S:[S,E,F,D]RERR [F,E,S] [Failed link = FD]RERR isUnicast30Samir R. Das University of CincinnatiAggressive Route Cachingg Each node caches a new route it learns by any meansg 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.g When node G receives RREQ [S,C] destined for node D, node G learns route [G,C,S] to node S and so on.g When node F forwards RREP [D,F,E,S], node F learns route [F,D] to node D and so on.g Basically, when forwarding any packet, the node learns a route to all nodes in the source route contained in the packet.731Samir R. Das University of CincinnatiContents of Caches on Selected Nodes After one RREQ-RREP Cycleg [P,Q,R] represents cached route at a node P.g More than one routes may be cached for the same destination.g Compact data structures may be used to implement route caches (e.g., tree).ASEFBCGD[D,F,E,S][D,G,C,S][F,E,S][F,D][F,G,C,S]32Samir R. Das University of CincinnatiUse of Route Cachingg 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 Otherwise, node S initiates route discovery by sending a route requestg 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.g Aggressive use of route cache n can speed up route discovery.n can reduce propagation of route requests.833Samir R. Das University of CincinnatiRoute Caching: Beware!g Stale caches can adversely affect performance.g With passage of time and host mobility, cached routes may become invalid.g All cached routes containing a failed link are not erased by route error (RERR).n Only that route is erased that is attempted to be usedg A sender host may try several stale routes (obtained from local cache, or replied from cache by other nodes), before finding a valid route.34Samir R. Das University of CincinnatiDynamic Source Routing: Advantagesg Source routing: no special mechanism needed to eliminate loops.g On demand routing: Routes maintained only between nodes who need to communicaten Reduces overhead of route maintenance.g Route caching can further reduce route discovery overhead.g A single route discovery may yield many routes to the destination, due to intermediate nodes replying from local caches.n Useful when route breaks.935Samir R. Das University of CincinnatiDynamic Source Routing: Disadvantagesg Not scalable: Packet header size grows linearly with route length due to source routing.g Network-wide flood: Flood of route requests may potentially reach all nodes in the network. Too much overhead.g Collision: Care must be taken to avoid collisions between route requests propagated by neighboring nodesn insertion of random delays before forwarding RREQg Reply storm problem: Increased contention if too many route replies come back due to nodes replying using their local cachen Reply storm may be eased by preventing a node from sending RREP if it hears another RREP with a shorter route.36Samir R. Das University of CincinnatiDynamic Source Routing: Disadvantagesg Stale cache problem: An intermediate node may send Route Reply using a stale cached route, thus polluting other caches.g This problem can be eased if some mechanism to purge (potentially) invalid cached routes is incorporated. g Current research: how to invalidate caches effectively.n Example: Timer-based. Or propagate the route error widely.1037Samir R. Das University of CincinnatiAd Hoc On-Demand Distance Vector Routing (AODV)[Perkins-Royer-Das 99,00]g AODV retains the desirable feature of DSR that routes are maintained only between nodes which need to communicate.g AODV attempts to improve on DSR by maintaining routing tables at the nodes, so that data packets do


View Full Document

SBU CSE 590 - Dynamic Source Routing (DSR)

Download Dynamic Source Routing (DSR)
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Dynamic Source Routing (DSR) and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dynamic Source Routing (DSR) 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?