1Ad Hoc RoutingCMU 15-744David AndersenAd Hoc Routing• Goal: Communication betweenwireless nodes– No external setup (self-configuring)– Often need multiple hops to reach dst2Challenges and Variants• Poorly-defined “links”– Probabilistic delivery, etc. Kind of n^2 links• Time-varying link characteristics• No oracle for configuration (no groundtruth configuration file of connectivity)• Low bandwidth (relative to wired)• Possibly mobile• Possibly power-constrainedGoals• #0: Provide connectivity!• Low consumption of memory, bandwidth,{possibly power}• Scalable with numbers of nodes• Localized effects of link failure– (For scalability and stability)3Standard Routing: DV and LS• DV protocols may form loops– Very wasteful in wireless: bandwidth, power– Loop avoidance sometimes complex• LS protocols: high storage andcommunication overhead – particularlywhen potentially n^2 links!• More links in wireless (e.g., clusters) - maybe redundant higher protocol overheadProblems Using DV or LS• Periodic updates waste power– Tx sends portion of battery power into air– Reception requires less power, but periodicupdates prevent mobile from “sleeping”• Convergence may be slower inconventional networks but must be fast inad-hoc networks and be done withoutfrequent updates4Design Space• 1) How to disseminate information about links and tosend packets along a path• 2) How to decide which path to use from manypossibilities– (How good is a particular path?)– Really early models: binary– Early models: If deliver > x%, good– New models: ETX/ETT (wait for it)• Base knowledge: Every node knows about neighborsbecause they can hear them directly. (Periodic beacons,transmissions, etc.)Evaluating Ad Hoc Protocols• Parameter question: How much mobility?– And what mobility model?– Consider reality: Random waypoint? Clustered?• Businesspeople wandering to/from work vs. soldiers, etc.• Link model– Early research all used spherical propagation, etc.• Tended to binary “working” or “not working”– More modern uses traces from real deployments ormore realistic models5Proposed Protocols• Destination-Sequenced Distance Vector(DSDV)– DV protocol, destinations advertise sequencenumber to avoid loops, not on demand• Temporally-Ordered Routing Algorithm (TORA)– On demand creation of hbh routes based on link-reversal• Dynamic Source Routing (DSR)– On demand source route discovery• Ad Hoc On-Demand Distance Vector (AODV)– Combination of DSR and DSDV: on demand routediscovery with hbh routingDSR Concepts• Source routing– No need to maintain up-to-date info atintermediate nodes• On-demand route discovery– No need for periodic route advertisements6DSR Components• Route discovery– The mechanism by which a sending nodeobtains a route to destination• Route maintenance– The mechanism by which a sending nodedetects that the network topology haschanged and its route to destination is nolonger validDSR Route Discovery• Route discovery - basic idea– Source broadcasts route-request toDestination– Each node forwards request by adding ownaddress and re-broadcasting– Requests propagate outward until:• Target is found, or• A node that has a route to Destination is found7C Broadcasts Route Request toFASourceCGHDestinationFEDBRoute RequestC Broadcasts Route Request toFASourceCGHDestinationFEDBRoute Request8H Responds to Route RequestASourceCGHDestinationFEDBG,H,FC Transmits a Packet to FASourceCGHDestinationFEDBFH,FG,H,F9Forwarding Route Requests• A request is forwarded if:– Node is not the destination– Node not already listed in recorded sourceroute– Node has not seen request with samesequence number– IP TTL field may be used to limit scope• Destination copies route into a Route-replypacket and sends it back to SourceRoute Cache• All source routes learned by a node arekept in Route Cache– Reduces cost of route discovery• If intermediate node receives RR fordestination and has entry for destination inroute cache, it responds to RR and doesnot propagate RR further• Nodes overhearing RR/RP may insertroutes in cache10Sending Data• Check cache for route to destination• If route exists then– If reachable in one hop• Send packet– Else insert routing header to destination andsend• If route does not exist, buffer packet andinitiate route discoveryDiscussion• Source routing is good for on demandroutes instead of a priori distribution• Route discovery protocol used to obtainroutes on demand– Caching used to minimize use of discovery• Periodic messages avoided• But need to buffer packets• How do you decide between links?11Deciding Between Links• Most early protocols: Hop Count– Link-layer retransmission can mask some loss– But: a 50% loss rate means your link is only50% as fast!• Threshold?– Can sacrifice connectivity. – Isn’t a 90% path better than an 80% path?• Real life goal: Find highest throughputpathsForwarding Packets isexpensive• Throughput of 802.11b =~ 11Mbits/s– In reality, you can get about 5.• What is throughput of a chain?– A -> B -> C ?– A -> B -> C -> D ?– Assume minimum power for radios.• Routing metric should take this intoaccount! Affects throughput12ETX• Measure each link’s delivery probabilitywith broadcast probes (& measurereverse)• P(delivery) = ( df * dr ) (ACK must bedelivered too…)• Link ETX = 1 / P(delivery)• Route ETX = Σ link ETX• (Assumes all hops interfere - not true, butseems to work okay so far)ETX: Sanity Checks• ETX of perfect 1-hop path: 1• ETX of 50% delivery 1-hop path: 2• ETX of perfect 3-hop path: 3• (So, e.g., a 50% loss path is better than aperfect 3-hop path! A threshold wouldprobably fail here…)13ETT• What if links @ different rates?• ETT – expected transmission time– ETX / Link rate= 1 / ( P(delivery) * Rate)SampleRate• What is best rate for link?– The one that maximizes ETT for the link!– SampleRate is a technique to adaptivelyfigure this out. (See new Roofnet paper)14ETX measurement results• Delivery is probabilistic– A 1/r^2 model wouldn’t really predict this!– Sharp cutoff (by spec) of “good” vs “no” reception.Intermediate loss range band is just a few dB wide!• Why?– Biggest factor: Multi-path interference• 802.11 receivers can suppress reflections < 250ns• Outdoor
View Full Document
Unlocking...