18-1©2008 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-08/18-2©2008 Raj JainCSE574sWashington University in St. LouisOverviewOverviewOverview! TCP: Key Features! 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 Wireless18-3©2008 Raj JainCSE574sWashington University in St. LouisTCP: Key FeaturesTCP: Key Features1. Stream-Oriented Transmission: Multiple application packets may be send in one TCP “Segment.”Maximum Segment Size (MSS).All acks are byte numbers. Segment # used in all discussions.2. Reliable Delivery: Segments are buffered at the source until acked. Retransmitted if not acked.3. In-Order Delivery: Destination delivers segments to application only when all previous segments received.4. End-to-End Semantics: Ack ⇒ Data received at destination5. Congestion Control: Increases load slowly from a low initial start. Reduces load if network congested (based on segment timeout, duplicate acks)6. Congestion Avoidance: Explicit Congestion Notification (ECN) bits in TCP/IP headers based on DECbit research18-4©2008 Raj JainCSE574sWashington University in St. LouisTCP Flow ControlTCP Flow Control! Cumulative Acks: Acks all bytes up to the ack! Piggybacked Acks: Acks are sent in the reverse packets if possible.! Delayed Acks: Ack delayed in case another segment is received or segment needs to be sent. Typically 200 ms! Duplicate Acks: If an out of order packet is received, the previous ack is resent. Duplicate acks are not delayed.! Window Flow Control:Throughput = Window/Round Trip Time! Ideal Window Size = Round Trip Time*Link Capacity= Delay-bandwidth product! TCP sets retransmission timer for only one packet. If the ack isnot received and the timer expires, the packet is assumed lost.18-5©2008 Raj JainCSE574sWashington University in St. LouisTCP Congestion MechanismsTCP Congestion Mechanisms! Slow Start! Fast retransmit and recovery! New Reno! Selective Acknowledgement! Explicit Congestion Notification18-6©2008 Raj JainCSE574sWashington University in St. LouisOur Research on TCP CongestionOur Research on TCP Congestion! 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 header18-7©2008 Raj JainCSE574sWashington University in St. LouisSlow StartSlow StartTIMESlowStartWait for TimeoutTimeoutCongestionAvoidanceSlowStartCongestion WindowCongestion AvoidanceSlow StartSegmentlostCWNDCWND/218-8©2008 Raj JainCSE574sWashington University in St. LouisSlow Start (Cont)Slow Start (Cont)! Receiver sends “Receive window” (for flow control)! Sender maintains a Congestion Window (CWND) CWND W < Receiver Window! Set “Slow Start Threshold” SSThresh = 64 kB initially! Start with a CWND W of 1! Increase W by 1 after every ack until SSThresh=> Exponential increase (Slow Start. W doubles every RTT)! Increase W by 1/W after every Acks (W increases by per RTT)=> Linear increase (Congestion Avoidance)! On a timeout, Set SSThresh to half the current window and set window to 1.SSThresh← Max{2, 0.5W}, W ← 118-9©2008 Raj JainCSE574sWashington University in St. LouisFast Retransmit and Recovery (FRR)Fast Retransmit and Recovery (FRR)! Also known as TCP-Reno! Ideas:" Don't have to wait for timeout on a loss" Don't reduce to one on single loss" Duplicate acks ⇒ Loss! On three duplicate acks:" Retransmit the lost segment (Fast Retransmit)" Set SSThresh to Max{2, 0.5 × CWND}" Reduce CWND to 0.5 × CWND + # of dupacks " New ack ⇒ CWND>SSThresh ⇒ Linear increase" Duplicate ack ⇒ inflate CWND by 1. Send a pkt if allowed! Advantage: Recovers from loss without a timeout! Problem: Cannot recover from bursty (3+) losses.Dupacks are also generated if pkts out-of-order (no loss).18-10©2008 Raj JainCSE574sWashington University in St. LouisFRR (Cont)FRR (Cont)CWNDTIME1st FastRetransmitCWNDInflates2nd FastRetransmitWait for TimeoutTimeoutCWND/2CWND/4CWND/818-11©2008 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 windowSenderReceiver18-12©2008 Raj JainCSE574sWashington University in St. LouisTCP Over WirelessTCP Over Wireless! Link Layer Mechanisms! Split TCP Solutions! TCP Aware Link Layer Protocols! Explicit Notification Schemes! TCP Over Satellite! Our Results for Satellite and Wireless Networks18-13©2008 Raj JainCSE574sWashington University in St. LouisLink Layer MechanismsLink 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 218-14©2008 Raj JainCSE574sWashington University in St. LouisSplit TCP SolutionsSplit TCP Solutions! Indirect TCP! Selective Repeat Protocol (SRP)! Mobile TCP! Mobile-End Transport Protocol18-15©2008 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
View Full Document