CS268: Beyond TCP Congestion ControlTCP ProblemsTCP Behavior For Web Traffic (B+98)TCP RenoFindings: Single TCPSolutions: Single TCPFindings: Parallel TCPsSolutions: Parallel TCPsHigh Delay High Bandwidth Challenges: Slow StartHigh Delay High Bandwidth Challenges: AIMDSimulation ResultsSlide 12Characteristics of SolutionXCP: An eXplicit Control ProtocolHow does XCP Work?Slide 16Slide 17How Does an XCP Router Compute the Feedback?DetailsSlide 20XCP Remains Efficient as Bandwidth or Delay IncreasesXCP Shows Faster Response than TCPXCP is Fairer than TCPXCP SummarySelfish UsersAck DivisionOptimistic AckingSolution: Cumulative NonceECNSlide 30Selfish Users SummaryConclusionCS268: Beyond TCP Congestion ControlIon StoicaFebruary 9, 20042TCP ProblemsWhen TCP congestion control was originally designed in 1988:-Key applications: FTP, E-mail-Maximum link bandwidth: 10Mb/s-Users were mostly from academic and government organizations (i.e., well-behaved)-Almost all links were wired (i.e., negligible error rate)Thus, current problems with TCP:-High bandwidth-delay product paths-Selfish users-Wireless (or any high error links)3TCP Behavior For Web Traffic (B+98)Workload: 1996 Olympic Game SiteWeb servers implement TCP RenoPath asymmetricCluster: IBM/RS 6000(Connect by Token Ring)NAPLoad balancerClient4TCP RenoFast retransmit: retransmit a segment after 3 DUP AcksFast recovery: reduce cwnd to half instead of to oneTimecwndSlow StartCongestionAvoidanceTimeoutFast RecoveryFast recovery5Findings: Single TCPFinding 1: retransmission due to-43.8% due to fast retransmission-56.2% due to RTOs (6.9% due to RTOs in slow start)Finding 2: Receiver window size is limiting factor in 14% of casesFinding 3: Ack compression is real, and there is a pos. correlation between Ack compression factor and packet loss6Solutions: Single TCPTCP SACK (Selective Acknowledgement)-Would help only with 4.4% of retransmission timeoutsRight-edge recovery-When receiving a DUP Ack send a new packet (why?)-Take care of 25% of retransmission timeouts7Findings: Parallel TCPsThe throughput of a client is proportional to the number of connection it opens to a server (relevant for HTTP 1.0)-Additive increase factor for n connections: n-Multiplicative decrease factor for n connections: 0.758Solutions: Parallel TCPsTCP-Int: -One congestion window for all TCPs to the same destination-TCPs are served in a round-robin fashionAdvantages-New TCPs start faster-Less likely for a loss to cause RTO Disadvantages (?)9High Delay High Bandwidth Challenges: Slow StartTCP throughput controlled by congestion window (cwnd) sizeIn slow start, window increases exponentially, but may not be enoughexample: 10Gb/s, 200ms RTT, 1460B payload, assume no loss-Time to fill pipe: 18 round trips = 3.6 seconds-Data transferred until then: 382MB-Throughput at that time: 382MB / 3.6s = 850Mb/s-8.5% utilization not very goodLoose only one packet drop out of slow start into AIMD (even worse)10High Delay High Bandwidth Challenges: AIMDIn AIMD, cwnd increases by 1 packet/ RTTAvailable bandwidth could be large-e.g., 2 flows share a 10Gb/s link, one flow finishes available bandwidth is 5Gb/s-e.g., suffer loss during slow start drop into AIMD at probably much less than 10Gb/sTime to reach 100% utilization is proportional to available bandwidth-e.g., 5Gb/s available, 200ms RTT, 1460B payload 17,000s11Simulation ResultsRound Trip Delay (sec)Avg. TCP UtilizationBottleneck Bandwidth (Mb/s)Avg. TCP UtilizationShown analytically in [Low01] and via simulations50 flows in both directionsBuffer = BW x DelayRTT = 80 ms50 flows in both directionsBuffer = BW x DelayBW = 155 Mb/s12Proposed Solution: Decouple Congestion Control from FairnessExample: In TCP, Additive-Increase Multiplicative-Decrease (AIMD) controls bothCoupled because a single mechanism controls bothHow does decoupling solve the problem? 1. To control congestion: use MIMD which shows fast response2. To control fairness: use AIMD which converges to fairness13Characteristics of Solution1. Improved Congestion Control (in high bandwidth-delay & conventional environments):•Small queues•Almost no drops2. Improved Fairness3. Scalable (no per-flow state)4. Flexible bandwidth allocation: min-max fairness, proportional fairness, differential bandwidth allocation,…14XCP: An eXplicit Control Protocol1. Congestion Controller2. Fairness Controller15Feedback Round Trip TimeCongestion WindowCongestion HeaderFeedback Round Trip TimeCongestion Window How does XCP Work?Feedback = + 0.1 packet16Feedback = + 0.1 packet Round Trip TimeCongestion WindowFeedback = - 0.3 packet How does XCP Work?17 Congestion Window = Congestion Window + FeedbackRouters compute feedback without any per-flow state Routers compute feedback without any per-flow state How does XCP Work?18How Does an XCP Router Compute the Feedback?Congestion ControllerFairness ControllerGoal: Divides between flows to converge to fairnessLooks at a flow’s state in Congestion Header Algorithm:If > 0 Divide equally between flowsIf < 0 Divide between flows proportionally to their current rates MIMD AIMDGoal: Matches input traffic to link capacity & drains the queueLooks at aggregate traffic & queueAlgorithm:Aggregate traffic changes by ~ Spare Bandwidth ~ - Queue SizeSo, = davg Spare - Queue19 = davg Spare - Queue22402 andTheorem: System converges to optimal utilization (i.e., stable) for any link bandwidth, delay, number of sources if:(Proof based on Nyquist Criterion)DetailsCongestion ControllerFairness ControllerNo Parameter Tuning No Parameter Tuning Algorithm:If > 0 Divide equally between flowsIf < 0 Divide between flows proportionally to their current ratesNeed to estimate number of flows NTinpktspktpktRTTCwndTN)/(1RTTpkt : Round Trip Time in header Cwndpkt : Congestion Window in headerT: Counting IntervalNo Per-Flow State No Per-Flow State20BottleneckS1S2R1, R2, …, RnSnSubset of ResultsSimilar behavior over:21Avg. UtilizationAvg. UtilizationXCP Remains Efficient as Bandwidth or Delay IncreasesBottleneck Bandwidth (Mb/s) Round Trip Delay (sec)Utilization as a function of Delay XCP increases proportionally to spare bandwidth and chosen to make XCP robust to delayUtilization as a function of
View Full Document