15-441: Computer Networking Lecture 25: Wireless. Ad-Hoc Networks Sensor networks
15-441: Computer Networking Lecture 25: Wireless, Ad-Hoc Networks, Sensor Networks
Scenarios 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) 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 Lecture25:11-302006 2
Lecture 25:11-30-2006 2 Scenarios 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) • 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
Wireless Challenges(review) Need to share airwaves rather than wire Dont know what hosts are involved Host may not be using same link technology No fixed topology of interconnection ·| nterference 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 ·S|ow Multipath interference Lecture25:11-302006 3
Lecture 25:11-30-2006 3 Wireless 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 interference
Wireless bit-Errors Router Computer 1 Computer 2 Loss→ Congestion 0 Loss t Congestion Wireless Lecture25:11-302006
Lecture 25:11-30-2006 4 Wireless Bit-Errors Router Computer 1 Computer 2 23 2 Loss → Congestion 21 0 Loss → Congestion Wireless
TCP 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 bandwidth Lecture25:11-302006
Lecture 25:11-30-2006 5 TCP 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 bandwidth
Performance Degradation 2.0E+06 Best possibl TCP With no errors (1.30Mbps) 1.5E+06 TCP Reno (280 Kbps 8 d50E+05 0.0E+00 10 Time(s) 2 MB wide-area tcP transfer over 2 Mbps lucent WaveLAN Lecture25:11-302006
Lecture 25:11-30-2006 Performance Degradation 0.0E+00 5.0E+05 1.0E+06 1.5E+06 2.0E+06 0 10 20 30 40 50 60 Time (s) Sequence number (bytes) TCP Reno (280 Kbps) Best possible TCP with no errors (1.30 Mbps) 2 MB wide-area TCP transfer over 2 Mbps Lucent WaveLAN
Performance Degredation 2 Recall TCP throughput/loss /rtt rel BW=MSS/(tt *sqrt( p/3)) proportional to 1 /rtt x sqrt(p) = ouch! L/sort(n) Normal TCP operating range: 2%loss Internet loss usually <1% 0.40.50,60.70,80.9 Lecture25:11-302006 7
Lecture 25:11-30-2006 7 Performance Degredation 2 • Recall TCP throughput / loss / RTT rel: • BW = MSS / (rtt * sqrt(2p/3)) • = proportional to 1 / rtt * sqrt(p) • == ouch! • Normal TCP operating range: < 2% loss Internet loss usually < 1%
Proposed 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 pat ath and wireless hop Lecture25:11-302006 8
Lecture 25:11-30-2006 8 Proposed 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 hop
Approach Styles (Link Layer More aggressive local remit 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 losses Wired link Wireless link ARQ/FEC Lecture25:11-302006 9
Lecture 25:11-30-2006 9 Approach 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 losses Wired link Wireless link ARQ/FEC
Approach 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 link Lecture25:11-302006 10
Lecture 25:11-30-2006 10 Approach 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 link