WIXLIB

Route Error (RERR)YRERR [J-D]SZEFBCMJALGHKDINJ sends a route error to S along route J-F-E-S when its attempt toforward the data packet S (with route SEFJD) on J-D failsNodes hearing RERR update their route cache to remove link J-D43Route Caching: Beware!nStale caches can adversely affect performancenWith passage of time and host mobility, cached routesmay become invalidnA sender host may try several stale routes (obtainedfrom local cache, or replied from cache by other nodes),before finding a good route4422

Ad Hoc On-Demand Distance Vector(AODV) Routing [Per99]nDSR includes source routes in packet headersnResulting large headers can sometimes degrade performancenparticularly when data contents of a packet are smallnAODV attempts to improve on DSR by maintaining routing tablesat the nodes, so that data packets do not have to contain routesnAODV retains the desirable feature of DSR that routes aremaintained only between nodes which need to communicate45AODVnRoute Requests (RREQ) are forwarded in a manner similar toDSRnWhen a node re-broadcasts a Route Request, it sets up a reversepath pointing towards the sourcenAODV assumes symmetric (bi-directional) linksnWhen the intended destination receives a Route Request, it repliesby sending a Route ReplynRoute Reply travels along the reverse path set-up when RouteRequest is forwarded4623

Temporally-Ordered Routing Algorithm(TORA) [Par00]nIn TORA, routes to a destination are defined by aDirectional Acyclic Graph (DAG) rooted at the destinationnIt is a merger of the proactive link reversal algorithm fordestination-oriented Directional-Acyclic-Graph creationproposed in [Gaf81] and the on-demand query-replymechanism of Lightweight Mobile Routing (LMR) [Cor95]nTORA also supports a proactive mode47Mobile Ad hoc NetworksIII. Routing Protocols2. Proactive protocols24

Destination-Sequenced Distance-Vector(DSDV) Routing [Per94]nImproves over the conventional Bellman-Ford distance-vectorprotocolnnEach node maintains a routing table which storesnnnnnIt eliminates route looping, increases convergence speed, and reducescontrol message overheadnext hop towards each destinationa cost metric for the path to each destinationa destination sequence number that is created by the destination itselfSequence numbers used to avoid formation of loopsEach node periodically forwards the routing table to its neighborsnnEach node increments and appends its sequence number when sending itslocal routing tableThis sequence number will be attached to route entries created for this49nodeDestination-Sequenced Distance-Vector(DSDV)nAssume that node X receives routing information fromY about a route to node ZXnYZLet S(X) and S(Y) denote the destination sequencenumber for node Z as stored at node X, and as sent bynode Y with its routing table to node X, respectively5025

Destination-Sequenced Distance-Vector(DSDV)nNode X takes the following steps:XYZnIf S(X) S(Y), then X ignores the routing information received from YnIf S(X) S(Y), and cost of going through Y is smaller than the routeknown to X, then X sets Y as the next hop to ZnIf S(X) S(Y), then X sets Y as the next hop to Z, and S(X) is updated toequal S(Y)51Wireless Routing Protocol (WRP)[Mur96]nAgain, improves over the Bellman-Ford distance-vector protocolnnEach node maintains a distance-table matrixnnnnIt reduces amount of route looping, and has a mechanism to ensurereliable exchange of update messagescontains all destination nodes,all neighbors through which the destination node can be reachedFor each neighbor-destination pair, if a route exists, the route length isrecordedEach node neighbor broadcasts its current best route to selecteddestinations on an event driven incremental basisnnacknowledgments are expected from all neighbor nodesIf some acknowledgments are missing, the broadcast will be repeated,with a message retransmission list specifying the subset of neighbors thatneed to respond5226

Optimized Link State Routing (OLSR)[Jac00]nIt’s a link-state protocol where the link information isdisseminated through an efficient flooding techniquenThe overhead of flooding link state information is reduced byrequiring fewer nodes to forward the informationnA broadcast from node X is only forwarded by its multipointrelaysnMultipoint relays of node X are its neighbors such that each twohop neighbor of X is a one-hop neighbor of at least one multipointrelay of XnEach node transmits its neighbor list in periodic beacons, so that all nodescan know their 2-hop neighbors, in order to choose the multipoint relays53Optimized Link State Routing (OLSR)nNodes C and E are multipoint relays of node AFBACGJEHKDNode that has broadcast state information from A5427

Optimized Link State Routing (OLSR)nNodes C and E forward information received from AFBAJEHCGKDNode that has broadcast state information from A55Optimized Link State Routing (OLSR)nnNodes E and K are multipoint relays for node HNode K forwards information received from HnE has already forwarded the same information onceFBACGJEHKDNode that has broadcast state information from A5628

Optimized Link State Routing (OLSR)nOLSR floods information through the multipoint relaysnThe flooded itself is fir links connecting nodes torespective multipoint relaysnRoutes used by OLSR only include multipoint relays asintermediate nodes57Mobile Ad hoc NetworksIII. Routing Protocols3. Hybrid protocols29

Zone Routing Protocol (ZRP) [Pea99]nnnnnZRP combines proactive and reactive approachesAll nodes within hop distance at most d from a node Xare said to be in the routing zone of node XAll nodes at hop distance exactly d are said to beperipheral nodes of node X’s routing zoneIntra-zone routing: Proactively maintain routes to allnodes within the source node’s own zone.Inter-zone routing: Use an on-demand protocol (similarto DSR or AODV) to determine routes to outside zone.59Zone Routing Protocol (ZRP) [Pea99]6030

Core-Extraction Distributed Ad hocRouting (CEDAR) [Siv99]nnnA subset of nodes in the network is identified as the coreEach node in the network must be adjacent to at leastone node in the coreEach core node determines paths to nearby core nodesby means of a localized broadcast61Location-Aided Routing (LAR) [Ko98]nExploits location information to limit scope of route request floodnnExpected Zone is determined as a region that is expected to holdthe current location of the destinationnnLocation information may be obtained using GPSExpected region determined based on potentially old locationinformation, and knowledge of the destination’s speedRoute requests limited to a Request Zone that contains theExpected Zone and location of the sender node6231

Expected Zone in LARX last known location of nodeD, at time t0Y location of node D at currenttime t1, unknown to node Sr (t1 - t0) * estimate of D’s speedrXYExpected Zone63Request Zone in LARNetwork SpaceRequest ZonerBAXYS6432

LARnOnly nodes within the request zone forward routerequestsnNode A does not forward RREQ, but node B does (seeprevious slide)nRequest zone explicitly specified in the route requestnEach node must know its physical location to determinewhether it is within the request zone65LARnOnly nodes within the request zone forward routerequestsnIf route discovery using the smaller request zone fails tofind a route, the sender initiates another route discovery(after a timeout) using a larger request zonennthe larger request zone may be the entire networkRest of route discovery protocol similar to DSR6633

Other Routing ProtocolsnPlenty of other routing protocolsnDiscussion here is far from exhaustive67Mobile Ad hoc NetworksIV. Transport Issues34

User Datagram Protocol (UDP)nUDP provides unreliable deliverynStudies comparing different routing protocols for MANETtypically measure UDP performancenSeveral performance metrics are often usednnnRouting overhead per data packetPacket loss ratePacket delivery delay69UDP PerformancennSeveral relevant ,Das00Infocom,Jacquet00Inria]Results comparing a specific pair of protocols do not alwaysagree, but some general (and intuitive) conclusions can be drawnnnnReactive protocols may yield lower routing overhead than proactiveprotocols when communication density is lowReactive protocols tend to loose more packets (assuming than networklayer drops packets if a route is not known)Proactive protocols perform better with high mobility and densecommunication graph7035

UDP PerformancenMany variables affect performancennnnnTraffic characteristicsn one-to-many, many-to-one, many-to-manyn small bursts, large file transfers, real-time, non-real-timeMobility characteristicsn low/high rate of movementn do nodes tend to move in groupsNode capabilitiesn transmission range (fixed, changeable)n battery constraintsPerformance metricsn delayn throughputn latencyn routing overheadStatic or dynamic system characteristics (listed above)71UDP PerformancenDifficult to identify a single scheme that will performwell in all environmentsnHoly Grail: Routing protocol that dynamically adapts toall environments so as to optimize “performance”nPerformance metrics may differ in different environments7236

Transmission Control Protocol (TCP)nReliable ordered deliverynImplements congestion avoidance and controlnReliability achieved by means of retransmissions ifnecessary73Throughput over Multi-Hop WirelessPaths[Gerla99]nConnections over multiple hops are at a disadvantagecompared to shorter connections, because they have tocontend for wireless access at each hop7437

Impact of Multi-Hop Wireless roughtput(Kbps)12345 6789 10Number of hopsTCP Throughput using 2 Mbps 802.11 MAC75Throughput Degradations withIncreasing Number of HopsnPacket transmission can occur on at most one hop among threeconsecutive hopsnIncreasing the number of hops from 1 to 2, 3 results in increased delay,and decreased throughputnIncreasing number of hops beyond 3 allows simultaneoustransmissions on more than one link, however, degradationcontinues due to contention between TCP Data and Acks travelingin opposite directionsnWhen number of hops is large enough, the throughput stabilizesdue to effective pipelining7638

Ideal Throughputnf(i) fraction of time for which shortest path lengthbetween sender and destination is InT(i) Throughput when path length is InnFrom previous figureIdeal throughput Σ f(i) * T(i)77Actual throughputImpact of MobilityTCP Throughput2 m/s10 m/sIdeal throughput (Kbps)7839

Actual throughputImpact of Mobility20 m/s30 m/sIdeal throughput79Throughput generally degrades withincreasing speed IdealAverageThroughputOver50 runsActualSpeed (m/s)8040

But not always 30 m/s20 m/sActualthroughputMobility pattern #81Why Does Throughput Degrade?mobility causeslink breakage,resulting in routefailureRoute isrepairedTCP sender times out.Starts sending packets againNo throughputNo throughputdespite route repairTCP data and acksen route discarded8241

Why Does Throughput Degrade?mobility causeslink breakage,resulting in routefailureTCP sendertimes out.Backs off timer.TCP sendertimes out.ResumessendingRoute isrepairedNo throughputNo throughputdespite route repairLarger route repair delaysespecially harmfulTCP data and acksen route discarded83Why Does Throughput Improve?Low Speed ScenarioCBDCDBACDBAA1.5 second route failureRoute from A to D is broken for 1.5 second.When TCP sender times after 1 second, route still broken.TCP times out after another 2 seconds, and only then resumes.8442

Why Does Throughput Improve?Higher (double) Speed ScenarioCDBCDBACDBAA0.75 second route failureRoute from A to D is broken for 0.75 second.When TCP sender times after 1 second, route is repaired.85Why Does Throughput Improve?General PrinciplenThe previous two slides show a plausible cause for improvedthroughputnTCP timeout interval somewhat (not entirely) independent of speednNetwork state at higher speed, when timeout occurs, may be morefavorable than at lower speednNetwork statennnLink/route statusRoute cachesCongestion8643

How to Improve Throughput(Bring Closer to Ideal)nNetwork feedbacknInform TCP of route failure by explicit messagenLet TCP know when route is repairednnProbingExplicit notificationReduces repeated TCP timeouts and backoffn87Performance ImprovementWith feedbackActual throughputWithout networkfeedbackIdeal throughput2 m/s speed8844

Performance ImprovementWithout networkfeedbackActual throughputWith feedbackIdeal throughput30 m/s speed89throughput as a fraction ofidealPerformance with Explicit Notification10.8Base TCP0.6With explicitnotification0.40.202102030mean speed (m/s)9045

Impact of CachingnRoute caching has been suggested as a mechanism to reduce routediscovery overhead [Broch98]nEach node may cache one or more routes to a given destinationnWhen a route from S to D is detected as broken, node S may:nnUse another cached route from local cache, orObtain a new route using cached route at another node91Actual throughput (as fraction of expected throughput)To Cache or Not to CacheAverage speed (m/s)9246

Why Performance Degrades WithCachingnWhen a route is broken, route discovery returns a cachedroute from local cache or from a nearby nodenAfter a time-out, TCP sender transmits a packet on the newroute.However, the cached route has also broken after it wascachedtimeout dueto route failurenntimeout, cached timeout, second cachedroute is brokenroute also brokenAnother route discovery, and TCP time-out intervalProcess repeats until a good route is found93IssuesTo Cache or Not to CachenCaching can result in faster route “repair”nFaster does not necessarily mean correctnIf incorrect repairs occur often enough, cachingperforms poorlynNeed mechanisms for determining when cachedroutes are stale9447

Caching and TCP performancenCaching can reduce overhead of route discovery even ifcache accuracy is not very highnBut if cache accuracy is not high enough, gains inrouting overhead may be offset by loss of TCPperformance due to multiple time-outs95TCP PerformanceTwo factors result in degraded throughput in presence of mobility:nLoss of throughput that occurs while waiting for TCP sender totimeout (as seen earlier)nnThis factor can be mitigated by using explicit notifications and betterroute caching mechanismsPoor choice of congestion window and RTO values after a newroute has been foundnHow to choose cwnd and RTO after a route change?9648

IssuesWindow Size After Route RepairnSame as before route break: may be too optimisticnSame as startup: may be too conservativenBetter be conservative than overly optimisticnnnReset window to small value after route repairLet TCP figure out the suitable window sizeImpact low on paths with small delay-bw product97IssuesRTO After Route RepairnSame as before route breaknnSame as TCP start-up (6 second)nnnIf new route long, this RTO may be too small, leading to timeoutsMay be too largeMay result in slow response to next packet lossAnother plausible approach: new RTO function of old RTO, old route length,and new route lengthnnnExample: new RTO old RTO * new route length / old route lengthNot evaluated yetPitfall: RTT is not just a function of route length9849

Mobile Ad hoc NetworksV. Security IssuesSecurity Issues in Mobile Ad HocNetworksnNot much work in this area as yetnMany of the security issues are same as those intraditional wired networks and cellular wirelessnWhat’s new ?10050

What’s New ?nWireless medium is easy to snoop onnDue to ad hoc connectivity and mobility, it is hard toguarantee access to any particular node (for instance, toobtain a secret key)nEasier for trouble-makers to insert themselves into amobile ad hoc network (as compared to a wirednetwork)101Resurrecting DucklingnBattery exhaustion threat: A malicious node may interact with amobile node often with the goal of draining the mobile node’sbatterynAuthenticity: Who can a node talk to safely?nnResurrecting duckling: Analogy based on a duckling and its mother.Apparently, a duckling assumes that the first object it hears is the motherA mobile device will trust first device which sends a secret key10251

Secure RoutingnAttackers may inject erroneous routing informationnBy doing so, an attacker may be able to divert network traffic, ormake routing inefficientnSuggests use of digital signatures to protect routing informationand data bothnSuch schemes need a Certification Authority to manage theprivate-public keys103Secure RoutingnEstablishing a Certification Authority (CA) difficult in amobile ad hoc network, since the authority may not bereachable from all nodes at all timesnSuggests distributing the CA function over multiplenodes10452

MANET Authentication ArchitecturenDigital signatures to authenticate a messagenKey distribution via certificatesnNeed access to a certification authoritynSpecifies message formats to be used to carry signature, etc.105Techniques for Intrusion-Resistant AdHoc Routing Algorithms (TIARA)nFlow disruption attack: Intruder (or compromised) nodeT may delay/drop/corrupt all data passing through, butleave all routing traffic unmodifiedBCADTintruder10653

Techniques for Intrusion-Resistant AdHoc Routing Algorithms (TIARA)nResource Depletion Attack: Intruders may send datawith the objective of congesting a network or depletingbatteriesUBintruderCADTBogus trafficintruder107Intrusion DetectionnDetection of abnormal routing table updatesnnnSimilar abnormal behavior may be detected at other protocol layersnnnUses “training” data to determine characteristics of normal routing tableupdates (such as rate of change of routing info)Efficacy of this approach is not evaluated, and is debatableFor instance, at the MAC layer, normal behavior may be characterized foraccess patterns by various hostsAbnormal behavior may indicate intrusionSolutions proposed in [Zhang00Mobicom] are preliminary, notenough detail provided10854

Mobile Ad hoc Networks

2 Mobile Ad hoc Networks I. Introduction 4 Wireless Networks n Need: Access computing and communication services, on the move n Infrastructure-based Networks n traditional cellular systems (base station infrastructure) n Wireless LANs n typically radio links (802.11, etc), can be Infrared n very flexible within the reception area;