15-744: Computer NetworkingTCP & RoutersOverviewTCP Vegas Slow StartPacket PairSlide 6Packet Pair in PracticeTCP Vegas Congestion AvoidanceSlide 10Slide 11Slide 12Changing WorkloadsTCP Friendly Rate Control (TFRC)RTO/RTT EstimationLoss EstimationSlide 17Congestion AvoidanceSlide 20TCP PerformanceSingle TCP Flow Router without buffersSummary Unbuffered LinkSlide 25Slide 26Single TCP Flow Router with large enough buffers for full link utilizationExampleIf flows are synchronizedIf flows are not synchronizedCentral Limit TheoremSlide 34Queuing DisciplinesTypical Internet QueuingFIFO + Drop-tail ProblemsActive Queue ManagementActive Queue DesignsSlide 41Internet ProblemsDesign ObjectivesLock-out ProblemFull Queues ProblemRandom Early Detection (RED)RED AlgorithmRED OperationSlide 49Queue EstimationThresholdsSlide 53Extending RED for Flow IsolationSlide 55FREDFRED – Fragile FlowsSlide 58CHOKeSlide 60Stochastic Fair BlueSlide 62Slide 63Fairness GoalsWhat is Fairness?Max-min FairnessImplementing Max-min FairnessBit-by-bit RRBit-by-bit RR IllustrationFair QueuingFQ IllustrationBit-by-bit RR ExampleFair Queuing TradeoffsSlide 76Core-Stateless Fair QueuingSlide 78Edge Router BehaviorCore Router BehaviorF vs. AlphaEstimating Fair ShareOther IssuesHow does XCP Work?Slide 85Slide 86How Does an XCP Router Compute the Feedback?Getting the devil out of the details …LessonsNext Lecture15-744: Computer NetworkingL-5 TCP & RoutersL -5; 10-15-04© Srinivasan Seshan, 2004 2TCP & Routers•TCP Vegas/alternative congestion control schemes•RED•Fair queuing•Core-stateless fair queuing/XCP•Assigned reading•[BP95] TCP Vegas: End to End Congestion Avoidance on a Global Internet•[FJ93] Random Early Detection Gateways for Congestion Avoidance•[DKS90] Analysis and Simulation of a Fair Queueing Algorithm, Internetworking: Research and Experience•[SSZ98] Core-Stateless Fair Queueing: Achieving Approximately Fair Allocations in High Speed Networks•[KHR02] Congestion Control for High Bandwidth-Delay Product NetworksL -5; 10-15-04© Srinivasan Seshan, 2004 3Overview•TCP Vegas•TFRC and Alternatives•TCP & Buffers•Queuing Disciplines•RED•RED Alternatives•Fair-queuing•Core-stateless FQ & XCPL -5; 10-15-04© Srinivasan Seshan, 2004 4TCP Vegas Slow Start•ssthresh estimation via packet pair•Only increase every other RTT •Tests new window size before increasingL -5; 10-15-04© Srinivasan Seshan, 2004 5Packet Pair•What would happen if a source transmitted a pair of packets back-to-back?•Spacing of these packets would be determined by bottleneck link•Basis for ack clocking in TCP•What type of bottleneck router behavior would affect this spacing•Queuing schedulingL -5; 10-15-04© Srinivasan Seshan, 2004 6Packet Pair•FIFO scheduling•Unlikely that another flows packet will get inserted in-between•Packets sent back-to-back are likely to be queued/forwarded back-to-back•Spacing will reflect link bandwidth•Fair queuing•Router alternates between different flows•Bottleneck router will separate packet pair at exactly fair share rateL -5; 10-15-04© Srinivasan Seshan, 2004 7Packet Pair in Practice•Most Internet routers are FIFO/Drop-Tail•Easy to measure link bandwidths•Bprobe, pathchar, pchar, nettimer, etc.•How can this be used?•NewReno and Vegas use it to initialize ssthresh•Prevents large overshoot of available bandwidth•Want a high estimate – otherwise will take a long time in linear growth to reach desired bandwidthL -5; 10-15-04© Srinivasan Seshan, 2004 8TCP Vegas Congestion Avoidance•Only reduce cwnd if packet sent after last such action•Reaction per congestion episode not per loss•Congestion avoidance vs. control•Use change in observed end-to-end delay to detect onset of congestion•Compare expected to actual throughput•Expected = window size / round trip time•Actual = acks / round trip timeL -5; 10-15-04© Srinivasan Seshan, 2004 10TCP Vegas•Fine grain timers•Check RTO every time a dupack is received or for “partial ack”•If RTO expired, then re-xmit packet•Standard Reno only checks at 500ms•Allows packets to be retransmitted earlier•Not the real source of performance gain•Allows retransmission of packet that would have timed-out•Small windows/loss of most of window•Real source of performance gain•Shouldn’t comparison be against NewReno/SACKL -5; 10-15-04© Srinivasan Seshan, 2004 11TCP Vegas•Flaws•Sensitivity to delay variation•Paper did not do great job of explaining where performance gains came from•Some ideas have been incorporated into more recent implementations•Overall•Some very intriguing ideas•Controversies killed itL -5; 10-15-04© Srinivasan Seshan, 2004 12Overview•TCP Vegas•TFRC and Alternatives•TCP & Buffers •Queuing Disciplines•RED•RED Alternatives•Fair-queuing•Core-stateless FQ & XCPL -5; 10-15-04© Srinivasan Seshan, 2004 13Changing Workloads•New applications are changing the way TCP is used•1980’s Internet•Telnet & FTP long lived flows•Well behaved end hosts•Homogenous end host capabilities•Simple symmetric routing•2000’s Internet•Web & more Web large number of short xfers•Wild west – everyone is playing games to get bandwidth•Cell phones and toasters on the Internet•Policy routing•How to accommodate new applications?L -5; 10-15-04© Srinivasan Seshan, 2004 14TCP Friendly Rate Control (TFRC)•Equation 1 – real TCP response•1st term corresponds to simple derivation•2nd term corresponds to more complicated timeout behavior•Is critical in situations with > 5% loss rates where timeouts occur frequently•Key parameters•RTO•RTT•Loss rateL -5; 10-15-04© Srinivasan Seshan, 2004 15RTO/RTT Estimation•Not used to actually determine retransmissions•Used to model TCP’s extremely slow transmission rate in this mode•Only important when loss rate is high•Accuracy is not as critical•Different TCP’s have different RTO calculation•Clock granularity critical 500ms typical, 100ms, 200ms, 1s also common•RTO = 4 * RTT is close enough for reasonable operation•EWMA RTT•RTTn+1 = (1- )RTTn + RTTSAMPL -5; 10-15-04© Srinivasan Seshan, 2004 16Loss Estimation•Loss event rate vs. loss rate•Characteristics•Should work well in steady loss rate•Should weight recent samples more•Should increase only with a new loss•Should decrease only with long period without loss•Possible
View Full Document
Unlocking...