15-441: Computer NetworkingScenarios and RoadmapWireless Challenges (review)Wireless Bit-ErrorsTCP Problems Over Noisy LinksPerformance DegradationProposed SolutionsApproach Styles (End-to-End)Approach Styles (Link Layer)Next: CSMA/CD Does Not WorkRTS/CTS ApproachAd Hoc NetworksAd Hoc RoutingTraditional Routing vs Ad HocProblems using DV or LSProposed protocolsDSR ComponentsDSR Route DiscoveryC Broadcasts Route Request to FSlide 20H Responds to Route RequestC Transmits a Packet to FForwarding Route RequestsRoute CacheSending DataDiscussionForwarding Packets is expensiveCapacity of multi-hop networkSensor Networks - smart devicesSensor System Types – Smart-Dust/MotesSensors and power and radiosSensor nets goalsPowerExample: AggregationDelay Tolerant Networks (DTNs)ApplicationsCore Ideas for DTN solutions15-441: Computer NetworkingLecture 22: Wireless, Ad-Hoc Networks, Sensor Networks, and Delay Tolerant NetworksLecture 22: 11-13-2007 2Scenarios and Roadmap•Point to point wireless networks•Review of important concepts•Ad hoc networks (wireless++)•Rooftop networks (multi-hop, fixed position)•Mobile ad hoc networks•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.•Delay Tolerant Networks (DTNs)•When All this fails…what do we do?Lecture 22: 11-13-2007 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•Other characteristics of wireless•Noisy lots of losses•Slow•Multipath interferenceLecture 22: 11-13-2007 4Wireless Bit-ErrorsRouterComputer 2Computer 12322Loss Congestion210Loss CongestionWirelessLecture 22: 11-13-2007 5TCP Problems Over Noisy Links•Wireless links are inherently error-prone•Fading, interference, attenuation -> Loss & errors•Errors often happen in bursts•TCP cannot distinguish between corruption and congestion•TCP unnecessarily reduces window, resulting in low throughput and high latency•Burst losses often result in timeouts•What does fast retransmit need?•Sender retransmission is the only option•Inefficient use of bandwidthLecture 22: 11-13-2007 6Performance Degradation•Recall TCP throughput / loss / RTT rel:•BW = MSS / (rtt * sqrt(2p/3))•= proportional to 1 / rtt * sqrt(p)•== ouch!•Normal TCP operating range: < 2% lossInternet loss usually < 1%Lecture 22: 11-13-2007 7Proposed Solutions•Incremental deployment•Solution should not require modifications to fixed hosts•If possible, avoid modifying mobile hosts •Reliable link-layer protocols•Error-correcting codes (or just send data twice)•Local retransmission•End-to-end protocols•Selective ACKs, Explicit loss notification•Split-connection protocols•Separate connections for wired path and wireless hopLecture 22: 11-13-2007 8Approach Styles (End-to-End)•Improve TCP implementations•Not incrementally deployable•Improve loss recovery (SACK, NewReno)•Help it identify congestion•Explicit Loss/Congestion Notification (ELN, ECN), •ACKs include flag indicating wireless loss•Trick TCP into doing right thing E.g. send extra dupacks if you know the network just burped (e.g., if you moved)Wired link Wireless linkLecture 22: 11-13-2007 9Approach Styles (Link Layer)•More aggressive local rexmit than TCP•802.11 protocols all do this. Receiver sends ACK after last bit of data.•Faster; Bandwidth not wasted on wired links. Recover in a few milliseconds.•Possible adverse interactions with transport layer•Interactions with TCP retransmission•Large end-to-end round-trip time variation•Recall TCP RTO estimation. What does this do?•FEC used in some networks (e.g., 802.11a)•But does not work well with burst lossesWired link Wireless linkARQ/FECLecture 22: 11-13-2007 10Next: CSMA/CD Does Not Work•Recall Aloha from many lectures ago•Wireless precursor to Ethernet.•Carrier sense problems•Relevant contention at the receiver, not sender•Hidden terminal•Exposed terminal•Collision detection problems•Hard to build a radio that can transmit and receive at same timeABCABCDHidden ExposedLecture 22: 11-13-2007 11RTS/CTS Approach•Before sending data, send Ready-to-Send (RTS)•Target responds with Clear-to-Send (CTS)•Others who hear CTS defer transmission•Packet length in RTS and CTS messages•Why not defer on RTS alone?•If CTS is not heard, or RTS collides•Retransmit RTS after binary exponential backoff•(There are lots of cool details embedded in this last part that went into the design of 802.11 - if you’re curious, look up the “MACAW” protocol).Lecture 22: 11-13-2007 12Ad 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: RoutingLecture 22: 11-13-2007 13Ad 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 changesLecture 22: 11-13-2007 14Traditional 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 frequentLecture 22: 11-13-2007 15Problems 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 convergenceLecture 22: 11-13-2007 16Proposed protocols•Proactive•Modified/Optimized DV or LS•Each node maintains route to all other nodes•Periodic and/or event triggered routing•Ex1: Destination-Sequenced Distance Vector (DSDV)•Ex2: Optimized Link State Routing (OLSR)•Reactive•Routes are built on-demand•Maintains only active routes•Dynamic Source Routing (DSR)•Ad Hoc On-Demand Distance Vector
View Full Document
Unlocking...