20-1©2010 Raj JainCSE574sWashington University in St. LouisTCP over TCP over Wireless NetworksWireless NetworksRaj JainProfessor of Computer Science and Engineering Washington University in Saint LouisSaint Louis, MO 63130Audio/Video recordings of this lecture are available at:http://www.cse.wustl.edu/~jain/cse574-10/20-2©2010 Raj JainCSE574sWashington University in St. LouisOverviewOverviewOverview TCP Congestion Mechanisms Our Initial Research on TCP Congestion TCP Over Wireless: Issues and Solutions TCP over Satellite Our research on TCP over Satellite and Wireless20-3©2010 Raj JainCSE574sWashington University in St. LouisResearch on Congestion ControlResearch on Congestion Control Early 1980s Digital Equipment Corporation (DEC) introduced Ethernet products Noticed that throughput goes down with a higher-speed link in middle (because no congestion mechanisms in TCP) Results:1. Timeout ⇒ Congestion ⇒ Reduce the TCP window to one on a timeout [Jain 1986]2. Routers should set a bit when congested (DECbit). [Jain, Ramakrishnan, Chiu 1988]3. Introduced the term “Congestion Avoidance”4. Additive increase and multiplicative decrease (AIMD principle) [Chiu and Jain 1989] There were presented to IETF in 1986.⇒ Slow-start based on Timeout and AIMD [Van Jacobson 1988]1Mbps 1Mbps 1MbpsTime=6 minutes1Mbps 10Mbps 1MbpsTime=6 hoursBit in header20-4©2010 Raj JainCSE574sWashington University in St. LouisAIMD PrincipleAIMD Principle Additive Increase, Multiplicative Decrease W1+W2 = Capacity ⇒ Efficiency, W1=W2 ⇒ Fairness (W1,W2) to (W1+DW,W2+DW) ⇒ Linear increase (45° line) (W1,W2) to (kW1,kW2)⇒ Multiplicative decrease (line through origin)CapacityW1W2CFairEfficientRef: D. Chiu and Raj Jain, "Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks," Journal of Computer Networks and ISDN, Vol. 17, No. 1, June 1989, pp. 1-14, http://www.cse.wustl.edu/~jain/papers/cong_av.htm20-5©2010 Raj JainCSE574sWashington University in St. LouisSlow Start Congestion ControlSlow Start Congestion Control Window = Flow Control Avoids receiver overrun Need congestion control to avoid network overrun The sender maintains two windows: Credits from the receiverCongestion window from the networkCongestion window is always less than the receiver window Starts with a congestion window (CWND) of 1 segment (one max segment size) ⇒ Do not disturb existing connections too much. Increase CWND by 1 MSS every time an ack is received20-6©2010 Raj JainCSE574sWashington University in St. LouisSlow Start (Cont)Slow Start (Cont) If segments lost, remember slow start threshold (SSThresh) to CWND/2Set CWND to 1 MSSIncrement by 1 per ack until SSthreshIncrement by 1 MSS/CWND per ack afterwardsTimeCongestionWindowCWNDReceiver WindowIdleIntervalTimeout1SSThresh20-7©2010 Raj JainCSE574sWashington University in St. LouisSlow Start (Cont)Slow Start (Cont) At the beginning, SSThresh = Receiver window After a long idle period (exceeding one round-trip time), reset the congestion window to one. Exponential growth phase is also known as “Slow start” phase The linear growth phase is known as “congestion avoidance phase”20-8©2010 Raj JainCSE574sWashington University in St. LouisFast RecoveryFast Recovery Optional – implemented in TCP Reno(Earlier version was TCP Tahoe) Duplicate Ack indicates a lost/out-of-order segment On receiving 3 duplicate acks: ¾ Enter Fast Recovery mode Retransmit missing segment Set SSTHRESH=CWND/2 Set CWND=SSTHRESH+3 MSS Every subsequent duplicate ack: CWND=CWND+1MSS20-9©2010 Raj JainCSE574sWashington University in St. LouisProblems of Current TCPProblems of Current TCP TCP cannot distinguish wireless errors from congestion. Frequent errors ⇒ Frequent window reductions ⇒ Low throughput On CDMA, Overload ⇒ Errors. Otherwise no relationship. Error or CongestionDuplicate acksReduced windowSenderReceiver20-10©2010 Raj JainCSE574sWashington University in St. LouisTCP Over WirelessTCP Over Wireless1. Link Layer Mechanisms2. Split TCP Solutions3. TCP Aware Link Layer Protocols4. Explicit Notification Schemes5. TCP Over Satellite6. Our Results for Satellite and Wireless Networks20-11©2010 Raj JainCSE574sWashington University in St. Louis1. Link Layer Mechanisms1. Link Layer Mechanisms Forward Error Correction (FEC): ¾ Reduces loss due to errors. ¾ Reduced link throughput even if no errors. Automatic Repeat Request (ARQ): ¾ Link layer retransmission and acknowledgement¾ No reduction in throughput if no errors¾ Reduced throughput and increased delay at link layer¾ May cause congestion¾ May increase variance of RTT ⇒ Increased RTO¾ May cause head-of-line blocking Adaptive Link layer strategies:¾ Dynamically vary FEC code, retransmission limit, frame sizeReceiver 1Receiver 220-12©2010 Raj JainCSE574sWashington University in St. Louis2. Split TCP Solutions2. Split TCP Solutions Indirect TCP Selective Repeat Protocol (SRP) Mobile TCP Mobile-End Transport Protocol20-13©2010 Raj JainCSE574sWashington University in St. LouisIndirect TCPIndirect TCP Two TCP connections: ¾ Fixed host to Base¾ Base to Mobile Independent flow control on two connections Packets buffered in the base Ack at sender ≠ MH has received ¾ Violates TCP’s end-to-end semantics¾ BS retains hard state. BS failure ⇒ loss of data¾ On handoff, stored packets must be sent to new BS¾ Does not work if connection not bi-directional. E.g., satellites Reference: Bakre95, Bakre 97FixedHostBaseStationMobileHost20-14©2010 Raj JainCSE574sWashington University in St. Louis3. TCP Aware Link Layer Protocols3. TCP Aware Link Layer Protocols Snoop Protocol WTCP Delayed DupAcks Protocol SCPS-TP20-15©2010 Raj JainCSE574sWashington University in St. LouisSnoop ProtocolSnoop Protocol Split connection and link level retransmission Base monitors returning acks. Retransmits on duplicate acks and drops the duplicate ack Advantages: Only soft state at BS. Only BS modified. No changes to FH or MH. If wireless link delay is less than 4 packets, 3 duplicate ackswill not happen and a simple link-level retransmission without dropping duplicate ack will also work. Disadvantages: Does not work with encrypted packets Does not work on asymmetric paths Ref: Balakrishnan9520-16©2010 Raj JainCSE574sWashington University in
View Full Document