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 DataDiscussionAODVRREQ/RREPRoute MaintanienceSlide 23Forwarding Packets is expensiveRouting MetricsSlide 26Route StabilitySlide 28PerformanceSlide 30Detour about energy/capacitySlide 32Slide 33Slide 34Slide 35Example MetricsHop CountETXETX 1/throughputETTCapacity of multi-hop networkSensor Networks - smart devicesSensor System Types – Smart-Dust/MotesSensors and power and radiosSensor nets goalsPowerExample: AggregationProgrammable Matter (or, Seth’s interest in ad-hoc networks)15-441: Computer NetworkingLecture 27: Ad-Hoc Networks15-441 F08 2Scenarios and Roadmap•Point to point wireless networks•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.•Adds challenge: Serious resource constraints•Current, popular, research.15-441 F08 3Wireless Challenges (review)•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.•Other characteristics of wireless•Noisy lots of losses•Slow•Multipath interference15-441 F08 4Ad Hoc Networks•All the challenges of wireless, plus some of:•No fixed infrastructure•Mobility (on short time scales)•Chaotically decentralized (:-)•Multi-hop!•Nodes are both traffic sources/sinks and forwarders•The big challenge: Routing15-441 F08 5Ad 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 changes15-441 F08 6Traditional Routing vs Ad Hoc•Traditional network:•Well-structured•~O(N) nodes & links•All links work ~= well•Ad Hoc network•N^2 links - but many stink!•Topology may be really weird•Reflections & multipath cause strange interference•Change is frequent15-441 F08 7Problems 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 convergence15-441 F08 8Proposed protocols•Basic Taxonomy:•Reactive (on-demand)•Proactive (table driven)•Source routing•Hop-by-hop routing•Destination-Sequenced Distance Vector (DSDV)•Dynamic Source Routing (DSR)•Ad Hoc On-Demand Distance Vector (AODV)•Let’s look at DSR first15-441 F08 9DSR•Source routing•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…)15-441 F08 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 valid15-441 F08 11DSR 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 found15-441 F08 12C Broadcasts Route Request to FASourceCGHDestinationFEDBRoute Request15-441 F08 13C Broadcasts Route Request to FASourceCGHDestinationFEDBRoute Request15-441 F08 14H Responds to Route RequestASourceCGHDestinationFEDBG,H,F15-441 F08 15C Transmits a Packet to FASourceCGHDestinationFEDBFH,FG,H,F15-441 F08 16Forwarding Route Requests•A request is forwarded if:•Node is not the destination•Node not already listed in recorded source route•Node has not seen request with same sequence number•IP TTL field may be used to limit scope•Destination copies route into a Route-reply packet and sends it back to Source15-441 F08 17Route 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 cacheRoute cache: Issues?15-441 F08 18Sending 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 discovery15-441 F08 19Discussion•Source routing is good for on demand routes instead of a priori distribution•But, high packet overhead•Route discovery protocol used to obtain routes on demand•Caching used to minimize use of discovery•No Periodic messages•But, need to buffer packetsWhy esp important?AODV•On-demand protocol•Table-driven, distance-vector routing•Similar to DSR in finding routes, but•Uses sequence numbers on route updates•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 RREQ•REPLY If my dest-seq >= received dest-seq ORI am destintation•DISCARDIf src-adr & broadcast-seq were seen•Re-broadcastotherwise15-441 F08 21Route Maintanience•Can update routing table when they get information that improves on the routing metric:•A smaller hop-count with a larger dest-seq number•Broken links cause unsolicited RREP to be sent (may cause new RREQ with higher dest-seq number)•Eavesdrop and periodic hellos15-441 F08 2215-441 F08 23Discussion•Can use on-demand discovery and do hop-by-hop routing•Only 1 route per destination•Route discovery
View Full Document
Unlocking...