2006-AODV-group-presentation

AdhocOn-demandDistanceVector(AODV)RoutingProtocolECE695Spring2006AODVOverviewAODVisapacketroutingprotocoldesignedforuseinmobileadhocnetworks(MANET)IntendedfornetworksthatmaycontainthousandsofnodesOneofaclassofdemand-drivenprotocols•TheroutediscoverymechanismisinvokedonlyifaroutetoadestinationisnotknownUDPisthetransportlayerprotocolSource,destinationandnexthopareaddressedusingIPaddressingEachnodemaintainsaroutingtablethatcontainsinformationaboutreachingdestinationnodes.•Eachentryiskeyedtoadestinationnode.RoutingTableFieldsDestinationIPaddressDestinationSequenceNumberValidDestinationSequenceNumberFlagOtherstateandroutingflagsNetworkInterfaceHopCount(neededtoreachdestination)NextHopPrecursorListLifetime(routeexpirationordeletiontime)Overview(continued)Routingtablesizeisminimizedbyonlyincludingnexthopinformation,nottheentireroutetoadestinationnode.Sequencenumbersforbothdestinationandsourceareused.Managingthesequencenumberisthekeytoefficientroutingandroutemaintenance•Sequencenumbersareusedtoindicatetherelativefreshnessofroutinginformation•Updatedbyanoriginatingnode,e.g.,atinitiationofroutediscoveryoraroutereply.•Observedbyothernodestodeterminefreshness.Overview(continued)Thebasicmessagesetconsistsof:•RREQ–Routerequest•RREP–Routereply•RERR–Routeerror•HELLO–ForlinkstatusmonitoringAODVOperation–MessageTypesRREQMessages•Whilecommunicationroutesbetweennodesarevalid,AODVdoesnotplayanyrole.•ARREQmessageisbroadcastedwhenanodeneedstodiscoveraroutetoadestination.•AsaRREQpropagatesthroughthenetwork,intermediatenodesuseittoupdatetheirroutingtables(inthedirectionofthesourcenode).•TheRREQalsocontainsthemostrecentsequencenumberforthedestination.•AvaliddestinationroutemusthaveasequencenumberatleastasgreatasthatcontainedintheRREQ.RREQMessageB?B?B?B?B?B?B?BAAODVOperation–MessageTypesRREPMessages•WhenaRREQreachesadestinationnode,thedestinationrouteismadeavailablebyunicastingaRREPbacktothesourceroute.•AnodegeneratesaRREPif:Itisitselfthedestination.Ithasanactiveroutetothedestination.Ex:anintermediatenodemayalsorespondwithanRREPifithasa“freshenough”routetothedestination.•AstheRREPpropagatesbacktothesourcenode,intermediatenodesupdatetheirroutingtables(inthedirectionofthedestinationnode).RREPMessageBAAAAAAAAODVOperation–MessageTypesRERRMessages•Thismessageisbroadcastforbrokenlinks•GenerateddirectlybyanodeorpassedonwhenreceivedfromanothernodeAODVOperation–MessageTypesHelloMessages•HelloMessage=RREPwithTTL=1•Thismessageisusedforbroadcastingconnectivityinformation.Ex:Ifaneighbornodedoesnotreceiveanypackets(Hellomessagesorotherwise)formorethanALLOWED_HELLO_LOSS*HELLO_INTERVALmseconds,thenodewillassumethatthelinktothisneighboriscurrentlylost.•AnodeshoulduseHellomessagesonlyifitispartofanactiveroute.MessageroutingABDFCGERREQRREQRREQRREQRREQRREQRREQRREQRREQRREPRREPRREPSourceDestinationCongestionHandlingOnemethodthatAODVhandlecongestionis:•IfthesourcenodereceivesnoRREPfromthedestination,itmaybroadcastanotherRREQ,uptoamaximumofRREQ_RETRIES.•ForeachadditionalattemptthatasourcenodetriedtobroadcastRREQ,thewaitingtimefortheRREPismultipliedby2.DSRisnotcapableofhandlingcongestion.CongestionHandlingOtherpossiblemethodstoimproveAODVcongestionhandling:•Aroutemaypredictwhencongestionisabouttooccurandtrytoavoiditbyreducethetransmissionrate.•Scheduletherequestssothatitwillnotoverloadthenetwork.AODVRoutingTherearetwophases•RouteDiscovery.•RouteMaintenance.Eachnodemaintainsaroutingtablewithknowledgeaboutthenetwork.AODVdealswithroutetablemanagement.Routeinformationmaintainedevenforshortlivedroutes–reversepointers.EntriesinRoutingTableDestinationIPAddressDestinationSequenceNumberValidDestinationSequenceNumberflagOtherstateandroutingflags(e.g.,valid,invalid,repairable,beingrepaired)NetworkInterfaceHopCount(numberofhopsneededtoreachdestination)NextHopListofPrecursorsLifetime(expirationordeletiontimeoftheroute)DSRmaintainsadditionaltableentries,causingalargermemoryoverheadDiscoveryBroadcastRREQmessages.IntermediatenodesupdatetheirroutingtableForwardtheRREQifitisnotthedestination.Maintainback-pointertotheoriginator.DestinationgeneratesRREQmessage.RREQsentbacktosourceusingthereversepointersetupbytheintermediatenodes.RREQreachesdestination,communicationstarts.AlgorithmforDiscovery@OriginatorIfaroutetothedestinationisavailable,startsendingdata.ElsegenerateaRREQpacket.IncrementtheRREQIDby1.Incrementthesequencenumberby1.DestinationIPaddress,currentlyavailablesequencenumberincluded.@IntermediateNodeGenerateroutereply,ifa'freshenough'routeisavalidrouteentryforthedestinationwhoseassociatedsequencenumberisatleastasgreatasthatcontainedintheRREQ.Changethesequencenumberofthedestinationnodeifstale,incrementthehopcountby1andforward.@Destination1.Incrementsequencenumberofthedestination.2.GenerateaRREQmessageandsentbacktoOriginator.DiscoveryMaintenanceHellomessagesbroadcastbyactivenodesperiodicallyHELLO_INTERVAL.NohellomessagefromaneighborinDELETE_PERIOD,linkfailureidentified.Alocalrouterepairtothatnexthopinitiated.After