115-744: Computer NetworkingL-8 WirelessL -8; 11-12-04© Srinivasan Seshan, 2004 2Mobile Routing• Mobile IP• Ad-hoc network routing• TCP on wireless links• Wireless MAC• Assigned reading• [BMJ+98] Performance Comparison of Multi-Hop Wireless Ad Hoc Routing Protocols• [BPSK97] A Comparison of Mechanism for Improving TCP Performance over Wireless Links• [LBC+01] Capacity of Ad Hoc Wireless Networks• [BDS+94] MACAW: A Media Access Protocol for Wireless LAN’s• [She98] A Channel Access Scheme for Large Dense Packet Radio NetworksL -8; 11-12-04© Srinivasan Seshan, 2004 3Wireless Challenges• Force us to rethink many assumptions• Need to share airwaves rather than wire• Don’t know what hosts are involved• Host may not be using same link technology• Mobility• Other characteristics of wireless• Noisy Æ lots of losses•Slow• Interaction of multiple transmitters at receiver• Collisions, capture, interference• Multipath interferenceL -8; 11-12-04© Srinivasan Seshan, 2004 4Cellular Reuse• Transmissions decay over distance• Spectrum can be reused in different areas• Different “LANs”• Decay is 1/R2in free space, 1/R4in some situations2L -8; 11-12-04© Srinivasan Seshan, 2004 5Overview• Wireless TCP• Internet routing• Ad hoc routing• Geographic ad hoc routing, MAC, Capacity (Brad Karp)L -8; 11-12-04© Srinivasan Seshan, 2004 6Wireless Challenges• Force us to rethink many assumptions• Need to share airwaves rather than wire• Don’t know what hosts are involved• Host may not be using same link technology• Mobility• Other characteristics of wireless• Noisy Æ lots of losses• Slow• Interaction of multiple transmitters at receiver• Collisions, capture, interference• Multipath interferenceL -8; 11-12-04© Srinivasan Seshan, 2004 7TCP Problems Over Noisy Links• Wireless links are inherently error-prone• Fades, interference, attenuation• 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• Sender retransmission is the only option• Inefficient use of bandwidthL -8; 11-12-04© Srinivasan Seshan, 2004 8Constraints & Requirements• Incremental deployment• Solution should not require modifications to fixed hosts• If possible, avoid modifying mobile hosts• Probably more data to mobile than from mobile• Attempt to solve this first3L -8; 11-12-04© Srinivasan Seshan, 2004 9Challenge #1: Wireless Bit-ErrorsRouterComputer 2Computer 12322Loss Æ Congestion210Burst losses lead to coarse-grained timeoutsResult: Low throughputLoss Æ CongestionWirelessL -8; 11-12-04© Srinivasan Seshan, 2004Performance Degradation0.0E+005.0E+051.0E+061.5E+062.0E+060 102030405060Time (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 WaveLANL -8; 11-12-04© Srinivasan Seshan, 2004 11Proposed Solutions• End-to-end protocols• Selective ACKs, Explicit loss notification• Split-connection protocols• Separate connections for wired path and wireless hop• Reliable link-layer protocols• Error-correcting codes• Local retransmissionL -8; 11-12-04© Srinivasan Seshan, 2004 12Approach Styles (End-to-End)• Improve TCP implementations• Not incrementally deployable• Improve loss recovery (SACK, NewReno)• Help it identify congestion (ELN, ECN)• ACKs include flag indicating wireless loss• Trick TCP into doing right thing Æ E.g. send extra dupacks• What is SMART?• DUPACK includes sequence of data packet that triggered itWired link Wireless link4L -8; 11-12-04© Srinivasan Seshan, 2004 13Approach Styles (Split Connection)• Split connections• Wireless connection need not be TCP• Hard state at base station• Complicates mobility• Vulnerable to failures• Violates end-to-end semanticsWired link Wireless linkL -8; 11-12-04© Srinivasan Seshan, 2004Split-Connection Congestion Window• Wired connection does not shrink congestion window • But wireless connection times out often, causing sender to stall01000020000300004000050000600000 20 40 60 80 100 120Time (sec)Congestion Window (bytes) Wired connectionWireless connectionL -8; 11-12-04© Srinivasan Seshan, 2004 15Approach Styles (Link Layer)• More aggressive local rexmit than TCP• Bandwidth not wasted on wired links• Adverse interactions with transport layer• Timer interactions• Interactions with fast retransmissions• Large end-to-end round-trip time variation• FEC does not work well with burst lossesWired link Wireless linkARQ/FECL -8; 11-12-04© Srinivasan Seshan, 2004 16Hybrid Approach: Snoop Protocol• Shield TCP sender from wireless vagaries• Eliminate adverse interactions between protocol layers• Congestion control only when congestion occurs• The End-to-End Argument [SRC84]• Preserve TCP/IP service model: end-to-end semantics• Is connection splitting fundamentally important?• Eliminate non-TCP protocol messages• Is link-layer messaging fundamentally important?Fixed to mobile: transport-aware link protocolMobile to fixed: link-aware transport protocol5L -8; 11-12-04© Srinivasan Seshan, 2004 17Snoop Overview• Modify base station• to cache un-acked TCP packets• … and perform local retransmissions• Key ideas• No transport level code in base station• When node moves to different base station, state eventually recreated thereL -8; 11-12-04© Srinivasan Seshan, 2004Snoop Protocol: CH to MHCorrespondent HostMobile HostBase Station5112346• Snoop agent: active interposition agent• Snoops on TCP segments and ACKs• Detects losses by duplicate ACKs and timers• Suppresses duplicate ACKs from FH senderSnoop AgentL -8; 11-12-04© Srinivasan Seshan, 2004Snoop Protocol: CH to MHCorrespondent HostMobile HostBase Station• Transfer of file from CH to MH• Current window = 6 packetsSnoop Agent654321L -8; 11-12-04© Srinivasan Seshan, 2004Snoop Protocol: CH to MHCorrespondent HostMobile HostBase Station• Transfer beginsSnoop Agent654 3 216L -8; 11-12-04© Srinivasan Seshan, 2004Snoop Protocol: CH to MHCorrespondent HostMobile HostBase Station5112346• Snoop agent caches segments that pass bySnoop AgentL -8; 11-12-04© Srinivasan Seshan, 2004Snoop Protocol: CH to MHCorrespondent HostMobile HostBase Station512346• Packet 1 is LostSnoop Agent231Lost Packets1L -8; 11-12-04©
View Full Document
Unlocking...