PowerPoint PresentationSlide 2Why Routing?Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Dynamic Source Routing (DSR) [Johnson+ 1996]Route Discovery in DSRSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Route Reply in DSRSlide 20Dynamic Source Routing (DSR)Data Delivery in DSRWhen to Perform a Route DiscoveryDSR Optimization: Route CachingUse of Route CachingSlide 26Use of Route Caching: Can Speed up Route DiscoveryUse of Route Caching: Can Reduce Propagation of Route RequestsRoute Error (RERR)Route Caching: Beware!Dynamic Source Routing: AdvantagesDynamic Source Routing: DisadvantagesSlide 33ReferencesPaper Reviews• Written reviews for each paper to be discussed in class are due by noon on Fridays of the previous week• The soft copy of the reviews should be turned into both the class instructor and TA. • The hard copies need to be turned into the instructor onlyFor each paper, students should write a review answering each of the following questions: 1. What problems (with prior work or the lack thereof) were addressed or surveyed by the authors? 2. What solutions were proposed or surveyed by the authors? 3. What are the technical strengths and main contributions of the paper's proposed solutions? 4. What are the technical weaknesses of the paper's proposed solutions? 5. What suggestions do you have to improve upon the paper's ideas?Routing inMobile Ad hoc NetworksWhy Routing?Common objective:Common objective: Route packets along the optimal pathRoute packets along the optimal path–Routing protocols adapt to changing network conditions and Routing protocols adapt to changing network conditions and by definition offers multi-hop pathsby definition offers multi-hop paths–Routing protocols differ in route tableRouting protocols differ in route tableconstructionconstructionmaintenancemaintenanceupdateupdateNext-hop routing protocols can be categorized as:Next-hop routing protocols can be categorized as:–Link-stateLink-state–Distance-vectorDistance-vector–Traditional link-state protocols may not be suitableTraditional link-state protocols may not be suitable–Closer to centralized version of shortest-path algorithmCloser to centralized version of shortest-path algorithm–Each node maintains a view of network topology with a cost for each linkEach node maintains a view of network topology with a cost for each link–Link costs are broadcast periodically to keep the views consistentLink costs are broadcast periodically to keep the views consistent–Each node updates its view and applies a shortest-path algorithm to find Each node updates its view and applies a shortest-path algorithm to find its next hop for each destinationits next hop for each destination–Routing loops may occur due to propagation delays, partitioned Routing loops may occur due to propagation delays, partitioned networks, and so onnetworks, and so on–Alternative link-state routing approaches may not require all nodes to Alternative link-state routing approaches may not require all nodes to have the identical link-state information and route selection algorithms have the identical link-state information and route selection algorithms and may find routes on demandand may find routes on demandLink-State Approach[Dijkstra 1959 and McQuillan+ 1980]–Based on shortest-path routing algorithms i.e., Distributed Bellman-FordBased on shortest-path routing algorithms i.e., Distributed Bellman-Ford–DBF algorithms are also known as Distance-Vector (DV)DBF algorithms are also known as Distance-Vector (DV)–For each destination, the node stores a single route table entry along with For each destination, the node stores a single route table entry along with next-hop neighbornext-hop neighbor–Route table entry for destination contains Route table entry for destination contains metric metric which is which is distancedistance from from node to the destination and also the next-hop (node to the destination and also the next-hop (vectorvector) towards destination) towards destinationDistance-Vector Approach[Ford+ 1962 and Leiner+ 1987]Ad Hoc Routing Protocols Overview Ad hoc Routing ProtocolsTable Driven (Proactive)CGSRDSDV WRPAODVDSR TORA SSRABRSource-InitiatedOn-demand Driven (Reactive)Hybrid ZRPProactive ProtocolsProactive Protocols–have lower latency due to maintenance of routes at all timeshave lower latency due to maintenance of routes at all times–can result in much higher overhead due to frequent route updatescan result in much higher overhead due to frequent route updatesReactive ProtocolsReactive Protocols may havemay have–higher latency since the routes have to be discovered when the higher latency since the routes have to be discovered when the source node initiates a route requestsource node initiates a route request–lower overhead since routes are maintained only on-demand basislower overhead since routes are maintained only on-demand basisProactive vs. Reactive Routing Protocols–Based on classical distributed Bellman-Ford routing mechanismBased on classical distributed Bellman-Ford routing mechanism–Routing loops in a mobile network have been eliminatedRouting loops in a mobile network have been eliminated–Each node has a routing table (all possible destinations within network, Each node has a routing table (all possible destinations within network, and number of routing hops to each destination)and number of routing hops to each destination)–A sequence numbering system to distinguish stale routes from new ones and assigned by the destination node–Routing table updates are sent periodically (table consistency) Routing table updates are sent periodically (table consistency) –High volumes of control traffic meaning an inefficient utilization of network High volumes of control traffic meaning an inefficient utilization of network resourcesresources–To alleviate this problem, the protocol uses two types of route update To alleviate this problem, the protocol uses two types of route update packets packets Destination-Sequenced Distance-Vector Routing (DSDV)[Perkins+ 1994]Full dumpFull dump Carries all available routing info and can require multiple network protocol Carries all available routing info and can require multiple network protocol data units. Infrequently transmitted while there is not much movement. data units. Infrequently transmitted while there is not much movement. IncrementalIncremental packets