TCP over Wireless NetworksOverviewTCP: Key FeaturesTCP Flow ControlTimeout CalculationsTCP Congestion MechanismsOur Research on TCP CongestionSlow StartSlow Start (Cont)Fast Retransmit and Recovery (FRR)FRR (Cont)TCP New RenoNew Reno (Cont)Selective AckProblems of Current TCPTCP Over WirelessLink Layer MechanismsSplit TCP SolutionsIndirect TCPSelective Repeat Protocol (SRP)Mobile TCPMobile-End Transport ProtocolTCP Aware Link Layer ProtocolsSnoop ProtocolWTCPDelayed DupAcks ProtocolSCPS-TPExplicit Notification SchemesExplicit Loss NotificationExplicit Loss Notification 2Explicit Bad State NotificationPartial Ack ProtocolsReceiver-Based SchemeSender-Based Discrimination SchemeTCP Over SatelliteIETF TCPSATSatellite Transport Protocol (STP)Early Acks: ACKprimeOur Results for Satellite NetworksWireless Networks: Our SolutionSurvey of Prior ProposalsCongestion CoherenceCongestion Coherence AlgorithmGoodputSummaryReading AssignmentHomeworkReferences10-1©2006 Raj JainCSE574sWashington University in St. LouisTCP over TCP over Wireless NetworksWireless NetworksRaj Jain Washington UniversitySaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse574-06/10-2©2006 Raj JainCSE574sWashington University in St. LouisOverviewOverviewOverviewOverviewTCP: Key FeaturesTCP Congestion MechanismsOur Initial Research on TCP CongestionTCP Over Wireless: Issues and SolutionsTCP over SatelliteOur research on TCP over Satellite and Wireless10-3©2006 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 research10-4©2006 Raj JainCSE574sWashington University in St. LouisTCP Flow ControlTCP Flow ControlCumulative Acks: Acks all bytes up to the ackPiggybacked 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 msDuplicate 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 TimeIdeal Window Size = Round Trip Time*Link Capacity= Delay-bandwidth productTCP sets retransmission timer for only one packet. If the ack is not received and the timer expires, the packet is assumed lost.10-5©2006 Raj JainCSE574sWashington University in St. LouisTimeout CalculationsTimeout CalculationsOld Method: Using only the mean of measured round triperror = sampleRTT - mean mean += a * error /* 0 < a < 1 */ timeout = d * mean /* d > 1 */ RFC 793 suggested 0.1 to 0.2 for a, and 1.3 to 2.0 for d. New Method: Using mean and standard deviationerror = sampleRTT - mean mean += a * error /* 0 <= a <= 1 */ sample_dev = |error| dev_error = sample_dev - mean_dev mean_dev += b * (sample_dev - mean_dev) /* 0 <= b <= 1 */ timeout = mean + c * mean_dev /* c >= 0 */ The usual values for the constants are a = 1/8, b = 1/4, c = 4. RTT is measured in multiples of a “tick.” 1 tick = 500 ms usually. RTO is at least 2 ticks. Double RTO on repeated timeouts.10-6©2006 Raj JainCSE574sWashington University in St. LouisTCP Congestion MechanismsTCP Congestion MechanismsSlow StartFast retransmit and recoveryNew RenoSelective AcknowledgementExplicit Congestion Notification10-7©2006 Raj JainCSE574sWashington University in St. LouisOur Research on TCP CongestionOur Research on TCP CongestionEarly 1980s Digital Equipment Corporation (DEC) introduced Ethernet productsNoticed 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 header10-8©2006 Raj JainCSE574sWashington University in St. LouisSlow StartSlow StartTIMESlowStartWait for TimeoutTimeoutCongestionAvoidanceSlowStartCongestion WindowCongestion AvoidanceSlow StartSegmentlostCWNDCWND/210-9©2006 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 WindowSet “Slow Start Threshold” SSThresh = 64 kB initiallyStart with a CWND W of 1Increase 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 110-10©2006 Raj JainCSE574sWashington University in St. LouisFast Retransmit and Recovery (FRR)Fast Retransmit and Recovery (FRR)Also known as TCP-RenoIdeas:Don't have to wait for timeout on a lossDon't reduce to one on single lossDuplicate acks LossOn 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 increaseDuplicate ack inflate CWND by 1. Send a pkt if allowedAdvantage: Recovers from loss without a timeoutProblem: Cannot recover from bursty (3+) losses.Dupacks are also generated if pkts out-of-order (no loss).10-11©2006 Raj JainCSE574sWashington University in St. LouisFRR (Cont)FRR (Cont)CWNDTIME1st FastRetransmitCWNDInflates2nd FastRetransmitWait for
View Full Document