Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Fast TCPMatt WeaverCS622 Fall 200715/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceFAST TCP: Motivation, Architecture, Algorithms, PerformanceDavid X. Wei, Student Member, IEEE, Cheng Jin, Steven H. Low, Senior Member, IEEE, and Sanjay Hegde15/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceAbstractFAST TCP is a congestion control algorithm that attempts to solve the problems of congestion control.This paper covers: The algorithm itself.Performance metrics315/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceBackground“Congestion control is a distributed algorithm to share network resources among competing users.”A difficult problem to solve...Resource needs vary, depending on time of day.Available resources is usually static.415/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceFAST TCPFAST is a recursive acronym: FAST AQM Scalable TCP○AQM: Active Queue Management○TCP: Transmission Control Protocol (duh)515/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceCurrent IssuesAs congestion is monitored, current algorithms slow down monitoring as packets are dropped, the average sending rate depends on low loss probability.High data transmission rates are required for low loss.Usually lower than WiFi can support.615/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceSolutionFAST TCP uses queues to store a constant number of packets.If too few packets are queued, the sending rate increases.If too few, the rate decreases.715/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceCongestion ControlCurrent TCP congestion control algorithm (aka Reno).At the packet level, linear increase by one packet per roundtrip time (RTT) is too slow, and multiplicative decrease per loss event is too drastic. At the flow level, maintaining large average congestion windows requires an extremely small equilibrium loss probability.At the packet level, oscillation in congestion window is unavoidable because TCP uses a binary congestion signal (packet loss).At the flow level, the dynamics is unstable, leading to severe oscillations that can only be reduced by the accurate estimation of packet loss probability and a stable design of the flow dynamics.815/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceMotivationsTwo levels of design: The flow level (macroscopic) covers:○QoS○Stability○etcPacket level (microscopic) covers:○The same goals, but focused on end to end.Reno suffered because higher level control was considered after the micro level.915/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceCalculationsCongestion and utility: U calculates utility for each stakeholder (user) at a given flow.1015/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceCalculationsEquilibrium (FAST): 11Equilibrium (Reno):15/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceCalculations“A key departure of our model from those in the literature is that we assume that a source’s send rate, defined as xi(t) :=wi(t)=Ti(t), cannot exceed the throughput it receives. “1215/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceDynamic StructureThe weakness of current schemes versus FAST is shown for large window sizes.1315/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceEquilibriumEquilibrium measures congestion consistency.1415/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceDifferencesThough all of the aforementioned algorithms look different at the packet level, they actually have similar structures at the flow and equilibrium levels.1515/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformancePerformance Test 1To test performance, packet data is pushed through a semi-articial network.Identical sender and receiver boxes, running dummynet on FreeBSD.Emulated router.Dummynet running:○Paths with RTTs of 50, 100, 150, and 200ms.○Second path with a bottleneck capacity of 8M/s and a buffer size of 2,000 packets shared by all the delay pipes.1615/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceResultsDynamic state I:Small flows, large windowsDynamic state II:Larger flows1715/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceDynamic State I1815/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance19FAST vs Reno IThroughputkbpsQueue(avg)# of pktsSec15/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceDynamic State II2015/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceDynamic State II2115/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance22FAST vs Reno II15/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance23BIC15/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformancePerformance Test 2Dummynet tests are limited to a single bottleneck and the same protocols.NS-2 Simulation run in lab:Same algorithm.Noise added to eliminate phase artifacts.2415/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance2515/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance2615/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance2715/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance2815/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance2915/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance3015/01/19 FAST TCP: Motivation, Architecture, Algorithms, PerformanceConclusionBecause of the use of queues, FAST TCP can handle lower transmission rates.The paper also covers some simulated scenarios (too lengthy to cover properly here).3115/01/19 FAST TCP: Motivation, Architecture, Algorithms, Performance32Caveat EmptorPossibly biased research:Jin Cheng, Steve Low, and David Wei (the authors) patented and market the FAST TCP algorithm.FAST TCP implementation sold as FastSoft Aria (a 1 U rack mountable hardware solution). http://www.fastsoft.com/Ao Tang proposed that these measurements were somewhat misleading in another paper.15/01/19