DOC PREVIEW
Berkeley COMPSCI 268 - Lecture Notes

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 ProblemsWhen 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 SiteWeb servers implement TCP RenoPath asymmetricCluster: IBM/RS 6000(Connect by Token Ring)NAPLoad balancerClient4TCP RenoFast retransmit: retransmit a segment after 3 DUP AcksFast recovery: reduce cwnd to half instead of to oneTimecwndSlow StartCongestionAvoidanceTimeoutFast RecoveryFast recovery5Findings: Single TCPFinding 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 casesFinding 3: Ack compression is real, and there is a pos. correlation between Ack compression factor and packet loss6Solutions: Single TCPTCP SACK (Selective Acknowledgement)-Would help only with 4.4% of retransmission timeoutsRight-edge recovery-When receiving a DUP Ack send a new packet (why?)-Take care of 25% of retransmission timeouts7Findings: Parallel TCPsThe 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 TCPsTCP-Int: -One congestion window for all TCPs to the same destination-TCPs are served in a round-robin fashionAdvantages-New TCPs start faster-Less likely for a loss to cause RTO Disadvantages (?)9High Delay High Bandwidth Challenges: Slow StartTCP throughput controlled by congestion window (cwnd) sizeIn slow start, window increases exponentially, but may not be enoughexample: 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 goodLoose only one packet  drop out of slow start into AIMD (even worse)10High Delay High Bandwidth Challenges: AIMDIn AIMD, cwnd increases by 1 packet/ RTTAvailable 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/sTime 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 NTinpktspktpktRTTCwndTN)/(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

Berkeley COMPSCI 268 - Lecture Notes

Documents in this Course
Lecture 8

Lecture 8

33 pages

L-17 P2P

L-17 P2P

50 pages

Multicast

Multicast

54 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?