15-441: Computer NetworkingScenarios and RoadmapWireless Challenges (review)Ad Hoc NetworksAd Hoc RoutingTraditional Routing vs Ad HocProblems Using DV or LSProposed ProtocolsDSRDSR ComponentsDSR Route DiscoveryC Broadcasts Route Request to FSlide 13H Responds to Route RequestC Transmits a Packet to FForwarding Route RequestsRoute CacheSending DataDiscussionForwarding Packets is ExpensiveETX Routing metricCapacity of Multi-Hop NetworkSensor Networks – Smart DevicesSensor Example – Smart-DustSensors, Power and RadiosSensor Nets GoalsPowerExample: AggregationBeyond Sensors – Vehicular Ad-Hoc NetworksVehicular Networks – Challenges?VANET Routing – Simple caseVANET Routing – General caseSlide 33Important Lessons15-441: Computer NetworkingLecture 24: Ad-Hoc Wireless Networks2Scenarios and Roadmap•Point to point wireless networks (last lecture)•Example: your laptop to CMU wireless•Challenges: Poor and variable link quality, hidden and exposed terminals•Ad hoc networks (no infrastructure)•Example: military surveillance network •Extra challenges: Routing and possible mobility•Sensor networks (ad hoc++)•Example: network to monitor temperatures in a volcano•Extra challenge: serious resource constraints•Vehicular networks (ad hoc+++)•Example: vehicle-2-vehicle game network•Extra challenge: extreme mobility3Wireless Challenges (review)•Interference causes losses, which TCP handles poorly•Collisions•Multipath interference•Environmental (e.g. microwaves)•Hidden & exposed terminals•Contention makes it slow•Solutions at the Link Layer •Local retransmissions•RTS/CTS4Ad Hoc Networks•All the challenges of wireless, plus:•No fixed infrastructure•Mobility (on short time scales)•Chaotically decentralized•Multi-hop!•Nodes are both traffic sources/sinks and forwarders, no specialized routers •The biggest challenge: routing5Ad Hoc Routing•Find multi-hop paths through network•Adapt to new routes and movement / environment changes•Deal with interference and power issues•Scale well with # of nodes•Localize effects of link changes6Traditional Routing vs Ad Hoc•Traditional network:•Well-structured•~O(N) nodes & links•All links work ~= well•Ad Hoc network•O(N^2) links - but most are bad!•Topology may be really weird•Reflections & multipath cause strange interference•Change is frequent7Problems Using DV or LS•DV loops are very expensive•Wireless bandwidth << fiber bandwidth…•LS protocols have high overhead•N^2 links cause very high cost•Periodic updates waste power•Need fast, frequent convergence8Proposed Protocols•Destination-Sequenced Distance Vector (DSDV)•Addresses DV loops•Ad Hoc On-Demand Distance Vector (AODV)•Forwarders store route info •Dynamic Source Routing (DSR)•Route stored in the packet header•Let’s look at DSR9DSR•Source routing keeps changes local•Intermediate nodes can be out of date•On-demand route discovery•Don’t need periodic route advertisements•(Design point: on-demand may be better or worse depending on traffic patterns…)10DSR Components•Route discovery•The mechanism by which a sending node obtains a route to destination•Route maintenance•The mechanism by which a sending node detects that the network topology has changed and its route to destination is no longer valid11DSR Route Discovery•Route discovery - basic idea•Source broadcasts route-request to Destination•Each node forwards request by adding own address and re-broadcasting•Requests propagate outward until:•Target is found, or•A node that has a route to Destination is found12C Broadcasts Route Request to FASourceCGHDestinationFEDBRoute Request13C Broadcasts Route Request to FASourceCGHDestinationFEDBRoute Request14H Responds to Route RequestASourceCGHDestinationFEDBG,H,F15C Transmits a Packet to FASourceCGHDestinationFEDBFH,FG,H,F16Forwarding Route Requests•A request is forwarded if:•Node doesn’t know the destination•Node not already listed in recorded source route (loop avoidance)•Node has not seen request with same sequence number (duplicate suppression)•IP TTL field may be used to limit scope•Destination copies route into a Route-reply packet and sends it back to Source17Route Cache•All source routes learned by a node are kept in Route Cache•Reduces cost of route discovery•If intermediate node receives RR for destination and has entry for destination in route cache, it responds to RR and does not propagate RR further•Nodes overhearing RR/RP may insert routes in cache18Sending Data•Check cache for route to destination•If route exists then•If reachable in one hop•Send packet•Else insert routing header to destination and send•If route does not exist, buffer packet and initiate route discovery19Discussion•Source routing is good for on demand routes instead of a priori distribution•Route discovery protocol used to obtain routes on demand•Caching used to minimize use of discovery•Periodic messages avoided•But need to buffer packets•How do you decide between links?20Forwarding Packets is Expensive•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 into account21ETX Routing metric•Measure each link’s delivery probability with broadcast probes (& measure reverse)•P(delivery) = 1 / ( df * dr ) (ACK must be delivered too)•Link ETX = 1 / P(delivery)•Route ETX = sum of link ETX•(Assumes all hops interfere - not true, but seems to work okay so far)22Capacity of Multi-Hop Network•Assume N nodes, each wants to talk to everyone else. What total throughput (ignore previous slide to simplify things)•O(n) concurrent transmissions. Great! But:•Each has length O(sqrt(n)) (network diameter)•So each Tx uses up sqrt(n) of the O(n) capacity.•Per-node capacity scales as 1/sqrt(n)•Yes - it goes down! More time spent Tx’ing other peoples packets…•But: If communication is local, can do much better, and use cool tricks to optimize•Like multicast, or multicast in reverse (data fusion)•Hey, that sounds like … a sensor network!23Sensor Networks – Smart Devices•First introduced in late 90’s by groups at UCB/UCLA/USC•Small, resource limited devices•CPU, disk, power, bandwidth, etc.•Simple scalar sensors –
View Full Document
Unlocking...