15-441: Computer NetworkingLecture 27: Ad-Hoc NetworksScenarios and Roadmapp• Point to point wireless networksElYlttCMUil•Example: Your laptop to CMU wireless• Challenges:• Poor and variable link quality (makes TCP unhappy)• Many people can hear when you talk• Pretty well defined.• Ad hoc networks (wireless++)• Rooftop networks (multi-hop, fixed position) (MESH)• Mobile ad hoc networks (MANET)• Adds challenges: routing, mobility• Some deployment + some research• Sensor networks (ad hoc++)• Scatter 100s of nodes in a field / bridge / etc.15-441 F08 2• Adds challenge: Serious resource constraints• Current, popular, research.Wireless Challenges (review)g( )• Need to share airwaves rather than wire• Don’t know what hosts are involved• Host may not be using same link technology• No fixed topology of interconnection• Interference• Other hosts: collisions, capture, interference• The environment (e.g., microwaves + 802.11)• Mobility -> Things change often• Environmental changes do too• How do microwaves work? Relate to 802.11 absorption.p• Other characteristics of wireless• Noisy Æ lots of losses•Slow15-441 F08 3Slow• Multipath interferenceAd Hoc Networks•All the challenges of wireless, plus some of:All the challenges of wireless, plus some of:• No fixed infrastructure•Mobility (on short time scales)Mobility (on short time scales)• Chaotically decentralized (:-)• Multi-hop!• Nodes are both traffic sources/sinks and forwarders• The big challenge: Routing15-441 F08 4Ad Hoc Routingg•Find multi-hop paths through networkFind multihop paths through network• Adapt to new routes and movement / environment changesg• Deal with interference and power issues•Scale well with # of nodesScale well with # of nodes• Localize effects of link changes15-441 F08 5Traditional Routing vs Ad Hocg•Traditional network:Traditional network:• Well-structured• ~O(N) nodes & linksO(N) nodes & links• All links work ~= well•Ad Hoc network•Ad Hoc network• N^2 links - but many stink!Tl b ll id•Topology may be really weird• Reflections & multipath cause strange interferenceCh i f t15-441 F08 6•Change is frequentProblems using DV or LSg•DV loops are very expensiveDV loops are very expensive• Wireless bandwidth << fiber bandwidth…•LS protocols have high overhead•LS protocols have high overhead• N^2 links cause very high cost• Periodic updates waste power• Need fast, frequent convergenceqg15-441 F08 7Proposed protocolspp• Basic Taxonomy:y• Reactive (on-demand)• Proactive (table driven)• Source routing• Hop-by-hop routing•DestinationSequenced Distance Vector (DSDV)•Destination-Sequenced Distance Vector (DSDV)• Dynamic Source Routing (DSR)•Ad Hoc OnDemand Distance Vector (AODV)•Ad Hoc On-Demand Distance Vector (AODV)Lt’ l k tDSRfi t15-441 F08 8•Let’s look at DSR firstDSR•Source routingSource routing• Intermediate nodes can be out of date•Ondemand route discovery•On-demand route discovery• Don’t need periodic route advertisements• (Design point: on-demand may be better or worse depending on traffic patterns…)15-441 F08 9DSR Componentsp• Route discoveryy• The mechanism by which a sending node obtains a route to destination• Route maintenance• The mechanism by which a sending node dhh klhhddetects that the network topology has changed and its route to destination is no longer valid15-441 F08 10DSR Route Discoveryy• Route discovery - basic ideay• Source broadcasts route-request to Destination• Each node forwards request by adding own address and re-broadcastingReq ests propagate o t ard ntil•Requests propagate outward until:• Target is found, or•A node that has a route to Destination is foundA node that has a route to Destination is found15-441 F08 11C Broadcasts Route Request to FqADSourceCEBRoute RequestCDestinationFGH15-441 F08 12C Broadcasts Route Request to FqADSourceCEBRoute RequestCDestinationFGH15-441 F08 13H Responds to Route RequestpqADSourceCEBCDestinationFGHG,H,F15-441 F08 14C Transmits a Packet to FADSourceCEBCDestinationFG,H,FGHFH,F15-441 F08 15Forwarding Route Requestsgq•A request is forwarded if:A request is forwarded if:• Node is not the destination•Node not already listed in recorded sourceNode not already listed in recorded source route•Node has not seen request with sameNode has not seen request with same sequence number• IP TTL field may be used to limit scopeyp• Destination copies route into a Route-reply packet and sends it back toSource15-441 F08 16packet and sends it back to SourceRoute Cache•All source routes learned by a node areAll source routes learned by a node are kept in Route Cache•Reduces cost of route discoveryReduces cost of route discovery• If intermediate node receives RR for destination and has entry for destination indestination and has entry for destination in route cache, it responds to RR and does not propagate RR furtherpropagate RR further• Nodes overhearing RR/RP may insert ro tes in cache15-441 F08 17routes in cacheRoute cache: Issues?Sending Datag•Check cache for route to destinationCheck cache for route to destination• If route exists then•If reachable in one hop•If reachable in one hop• Send packet•Else insert routing header to destination and•Else insert routing header to destination and send•If route does not exist buffer packet and•If route does not exist, buffer packet and initiate route discovery15-441 F08 18Discussion•Source routing is good for on demand routes instead ggof a priori distribution•But, high packet overheadWhy esp important?•Route discovery protocol used to obtain routes on demand• Caching used to minimize use of discovery•No Periodic messages•But, need to buffer packets15-441 F08 19AODV•On-demand protocolOndemand protocol• Table-driven, distance-vector routingSimilar to DSR in finding routes but•Similar to DSR in finding routes, but• Uses sequence numbers on route updatesHidffh f•Has an idea of freshness of a route• RREQ includes normal stuff plus• src-seq, Broadcast-seq, dest-seq, hop-count15-441 F08 20RREQ/RREP•On RREQOn RREQ• REPLY If my dest-seq >= received dest-seq ORyqqI am destintation• DISCARDIf src-adr & broadcast-seq were seen• Re-broadcastotherwise15-441 F08 21Route Maintanience•Can update routing table when they getCan update routing table when they get information that improves on the
View Full Document
Unlocking...