Ad-hoc On-Demand Distance Vector Routing (AODV)OutlineAd-hoc NetworksDestination Sequenced Distance-Vector Routing (DSDV)What is AODV?AODVAODV AlgorithmPath DiscoveryReverse Path SetupSlide 10Details of RREQForward Path SetupSlide 13Slide 14Another ExampleSlide 16Route Table Management (cont.)Path MaintenanceLocal Connectivity ManagementAd-hoc On-Demand Distance Vector Routing(AODV)Charles Perkins, Elizabeth RoyerOutlineIntroductionAd-hoc Network routing constraintsDestination Sequenced Distance Vector (DSDV) RoutingThe Ad-hoc On-Demand Distance Vector (AODV) AlgorithmSimulation and ResultsCurrent Status and Future WorkConclusionAd-hoc NetworksInfrastructure-less networksAll nodes are capable of movementLinks appear and disappear dynamicallySpecial constraints:Limited bandwidthLimited powerHigh error ratesPacket transmission is via broadcast (in physical layer)One challenge:How to build and maintain routes among mobile devices?(Conventional routing protocols –RIP, OSPF, etc- not applicable)Destination Sequenced Distance-Vector Routing (DSDV)A variant of the distance vector routing methodNot efficient for large ad-hoc networksUses periodic advertisementsGlobal dissemination of connectivity informationNodes need to maintain a complete list of routesWhat is AODV?An improvement on DSDVA source initiated (reactive) routing protocolMain goals:Quick adaptation under dynamic link conditionsLow transmission latencyLow control msg overhead (less broadcast)Loop-free property using destination sequence numbers (ds#)Scalable to large networkAODVFeaturesRoutes are created only when required (on-demand)Nodes do not maintain routes to all other nodes (but maintain only active routes they’re involved)Use of sequence numbers at each destination to maintain freshness of routing informationReduces periodic broadcastPaths generated are loop-freeUses symmetric links (if a link is not symmetric it is not used)AODV AlgorithmPath DiscoveryReverse Path SetupForward Path SetupRoute Table ManagementPath MaintenanceLocal Connectivity ManagementPath DiscoveryInitiated when no route exists to reach the destination nodeEach node has 2 counters:Source node sends a route request (RREQ)node sequence number broadcast_idsource_addr (saddr)source_sequence_# (ss#)broadcast_id (b_id)dest_addr (daddr)dest_sequence_# (ds#)hop_cntReverse Path SetupReverse PathBroadcast route request (RREQ): < saddr, ss# , b_id, daddr, ds#, hop_cnt >RREQ uniquely identified by <saddr , b_id>Route reply (RREP) if neighbor is the target, or knows a higher ds# to the targetOtherwise setup a pointer to the neighbor from whom RREQ was receivedMaintain reverse path route entries : daddr, saddr, ssn, b_id, expiration_timeReverse Path SetupSource_sequence_# (ss#): To maintain freshness information about the reverse route to the sourceDest_sequence_# (ds#): how fresh a route to the destination must be in order to be accepted by the sourceEvery node will record the neighbor’s address where first copy of RREQ is fromThese entries will be maintained for long enough for RREQ to traverse and produce a RREP to the senderDetails of RREQ<saddr, b_id> is uniqueB_id is incremented for new RREQIf the neighboring node doesn’t reply with a RREP, it increments hop_cnt RREQ from same node with same b_id will not be broadcasted more than once.SABFA won’t rebroadcast this RREQFor example, node S wants to contact node D, but there is no active path to reach node D.DForward Path Setupsource_addr (saddr)hop_cntdest_addr (daddr)destination_sequence_# (ds#)lifetime (expiration time for reverse path route entry)RREQ arrives at a node that has current route to the destination ( larger/same dest. sequence number as in RREQ)Route ReplyForward Path SetupUnicast route reply (RREP)<saddr, daddr, ds#, hop_cnt, lifetime> to neighborRREP travels back to the source along reverse pathEach upstream node updates ds#, sets up a forward pointer to the neighbor who transmit the RREPForward Path SetupACBDNode A sends B a RREQ with ds#ds# = 100 and B has a route entry to reach D with ds# = 99. B can NOTNOT use its recorded route to respond to the RREQ. B will rebroadcast the RREQ.However, for node C, C can respond with its recorded route.10099100 or > 100C will send node A: RREP <A’s address, D’s address, 100, 1, lifetime> If C can supply a route to destination D, a reverse path has been connected from D to A. If not, RREP traverses from D to A, intermediate nodes will setup a forward pointer to D and updates lifetime and records the latest ds#. Nodes that are not on the path determined by the RREP will timeout after 3 seconds and will delete the reverse pointers (e.g. reverse pointer from E to A)EAnother ExampleACDBFEGHRREP Paths from H to ARREP Paths from H to A100101100101Path Last Dest_Sequence_# Hop_cntHDA 100 2HEBA 101 3HGFCA 101 4Path with largest Path with largest ds#ds# OROR smallest smallest hop_cnthop_cnt with same with same ds#ds# will be will be chosenchosenRoute Table ManagementEach route table entry contains: Destination Next hop Number of hops Sequence number for the destination Active neighbors for this route Expiration time for the route table entryWhen a route entry is used to transmit data from source to destination, timeout for each entry is: current time + current time + active_route_timeoutactive_route_timeoutWhen a new route is available, route table will be updated only if new route has larger ds# or same ds# but with smaller hop_cnt to the destinationRoute Table Management (cont.)Route request expiration time: to purge reverse path routing entries from nodes that are not on the path from source to destinationRoute caching timeout: when the route is considered to be invalidA B C A is an activeactive neighbor of B if A sends/receives >=1 packets from B within active_route_timeout periodThe path A C is activeactive if route entries along node A to node C are activeNote: like DSDV, all routes in routing table are tagged with destination sequence numbers loop-freeWhat is active?Path Maintenance If source node moves during an active session It can redo path discovery If destination or intermediate nodes move A special RREP is sent to affected source nodes
View Full Document
Unlocking...