4-1Ad hoc On Demand Distance Vector (AODV) Routing ProtocolCS: 647 Advanced Topics in Wireless NetworksDr. Baruch Awerbuch & Dr. Amitabh MishraDepartment of Computer ScienceJohns Hopkins4-2Reading❒ Chapter 6, Sections 6.1-6.3, 6.5 – Ad Hoc Networking, Perkins, Addison Wesley, 20014-3Outline❒ Introduction❒ AODV properties❒ Route discovery❍ Flooding❒ Route maintenance❒ Local connectivity management – Hello Messages❒ Summary4-4Introduction: DSDV vs. AODV❒ In AODV such broadcasts are not necessary❒ If a link breakage does not affect on going transmission -> no global broadcast occurs❒ Only affected nodes are informed ❒ Local movements of nodes have local effects❒ AODV reduces the network wide broadcasts to the extent possible❒ Significant reduction in control overhead as compared to DSDV❒ DSDV broadcasts every change in the network to every node❒ When two neighbors enter communication range of each other ❍ This results in a network wide broadcast❒ Similarly when two nodes drift apart from each other’s range –> link breakage❍ Also results in a network wide broadcast❒ Local movements have global effects4-5Ad Hoc On Demand Distance-Vector (AODV) Routing (1)❒ Reactive or on Demand❒ Descendant of DSDV❒ Uses bi-directional links❒ Route discovery cycle used for route finding ❒ Maintenance of active routes❒ Sequence numbers used for loop prevention and as route freshness criteria❒ Provides unicast and multicast communication4-6Ad Hoc On Demand Distance-Vector (AODV) Routing (2)❒ Whenever routes are not used -> get expired -> Discarded ❍ Reduces stale routes❍ Reduces need for route maintenance❒Minimizes number of active routes between an active source and destination❒ Can determine multiple routes between a source and a destination, but implements only a single route, because❍ Difficult to manage multiple routes between same source/destination pair❍ If one route breaks, its difficult to know whether other route is available❍ Lot of book-keeping involved4-7AODV Properties (1)1. AODV discovers routes as and when necessary❒ Does not maintain routes from every node to every other 2. Routes are maintained just as long as necessary3. Every node maintains its monotonically increasing sequence number -> increases every time the node notices change in the neighborhood topology4-8AODV Properties (2)❒ AODV utilizes routing tables to store routing information1. A Routing table for unicast routes2. A Routing table for multicast routes❒The route table stores: <destination addr, next-hop addr, destination sequence number, life_time>❒ For each destination, a node maintains a list ofprecursor nodes, to route through them❍ Precusor nodes help in route maintenance (more later)❒Life-time updated every time the route is used ❍ If route not used within its life time -> it expires4-9AODV – Route Discovery (1) ❒ When a node wishes to send a packet to some destination –❍ It checks its routing table to determine if it has a current route to the destination• If Yes, forwards the packet to next hop node• If No, it initiates a route discovery process❒ Route discovery process begins with the creation of a Route Request (RREQ) packet -> source node creates it❒ The packet contains – source node’s IP address, source node’s current sequence number, destination IP address, destination sequence number4-10AODV – Route Discovery (2)❒ Packet also contains broadcast ID number ❍ Broadcast ID gets incremented each time a source node uses RREQ❍ Broadcast ID and source IP address form a unique identifier for the RREQ❒ Broadcasting is done via Flooding4-11Outline❒ Introduction❒ AODV properties❒ Route discovery❍ Flooding❒ Route maintenance❒ Local connectivity management – Hello Messages❒ Summary4-12Flooding for Control Packet Delivery❒ Sender S broadcasts a control packet P to all its neighbors❒ Each node receiving P forwards P to its neighbors❒ Sequence numbers help to avoid the possibility of forwarding the same packet more than once❒ Packet P reaches destination D provided that D is reachable from sender S❒ Node D does not forward the packet4-13Flooding for Control Packet Delivery - ExampleBASEFHJDCGIKRepresents that connected nodes are within each other’s transmission rangeZYRepresents a node that has received packet PMNL4-14Flooding for Control Packet DeliveryBASEFHJDCGIKRepresents transmission of packet PRepresents a node that receives packet P forthe first timeZYBroadcast transmissionMNL4-15Flooding for Control Packet DeliveryBASEFHJDCGIK Node H receives packet P from two neighbors:potential for collisionZYMNL4-16Flooding for Control Packet DeliveryBASEFHJDCGIK Node C receives packet P from G and H, but does not forwardit again, because node C has already forwarded packet P onceZYMNL4-17Flooding for Control packet DeliveryBASEFHJDCGIKZYM Nodes J and K both broadcast packet P to node D Since nodes J and K are hidden from each other, theirtransmissions may collide=> Packet P may not be delivered to node D at all, despite the use of floodingNL4-18Flooding for Control Packet DeliveryBASEFHJDCGIKZY Node D does not forward packet P, because node Dis the intended destination of packet PMNL4-19Flooding for Control Packet DeliveryBASEFHJDCGIK Flooding completed Nodes unreachable from S do not receive packet P (e.g., node Z) Nodes for which paths go through the destination Dalso do not receive packet P (example: node N)ZYMNL4-20Flooding for Control Packet DeliveryBASEFHJDCGIK Flooding may deliver packets to too many nodes(in the worst case, all nodes reachable from sender may receive the packet)ZYMNL4-21Flooding of Control Packets - Summary❒ Many protocols perform flooding of controlpackets e.g. AODV & DSR, instead of data packets❒ The control packets are used to discover routes ❒ Discovered routes are subsequently used to send data packet(s)❒ Overhead of control packet flooding is amortizedover data packets transmitted between consecutive control packet floods4-22Flooding for Data Delivery -Advantages❒ Simplicity❒ May be more efficient than other protocols when rate of information transmission is low enough that the overhead of explicit route discovery and maintenance incurred by other protocols is relatively higher❍ this scenario may occur, for instance, when nodes transmit small data packets relatively infrequently, and many topology changes