Performance models of TCPTCP behaviorGeneric TCP behaviorSlide 4Slide 5Slide 6Generic TCP BehaviorSlide 8Slide 9TCP throughput/loss relationshipSlide 11Slide 12Slide 13Recall RED queue managementSlide 15Slide 16Model and solutionSlide 18Bottleneck principle: a qualitative resultSharing bottleneck with TCPReplacing TCP with TCP-newSlide 22Multiple Bottleneck: infinite flowsSlide 24CommentsDynamic (transient) analysis of TCP fluidsLoss ModelA Single Congested RouterAdding RED to the modelSystem of Differential EquationsSystem of Differential Equations (cont.)Slide 32Steady slate behaviorA Queue is not a NetworkHow well does it work?Slide 36Slide 37Scaling PropertiesSummary: TCP flows as fluidsPerformance models of TCPcan simulate (ns-2)+ faithful to operation of TCP- expensive, time consumingdeterministic approximations+ quick- ignore some TCP details, steady statefluid models+ transient behavior- ignore some TCP detailsTCP behaviorcongestion control: decrease sending rate when loss detected, increase when no lossroutersdiscard, mark packets when congestion occursinteraction between end systems (TCP) and routers?want to understand (quantify) this interactionTCP runs at end-hostscongested router drops packetsGeneric TCP behaviorwindow algorithm (window W )up to W packets in networkreturn of ACK allows sender to send another packetcumulative ACKSincrease window by one per RTT W W +1/W per ACK  W W +1 per RTTseeks available network bandwidthsenderreceiverWGeneric TCP behaviorwindow algorithm (window W)increase window by one per RTT W W +1/W per ACKloss indication of congestion decrease window by half on detection of loss, (triple duplicate ACKs), W  W/2senderreceiverTDGeneric TCP Behaviorwindow algorithm (window W)increase window by one per RTT W W +1/W per ACKhalve window on detection of loss, W  W/2timeouts due to lack of ACKs  window reduced to one, W  1senderreceiverTOGeneric TCP Behaviorwindow algorithm (window W)increase window by one per RTT (or one over window per ACK, W W +1/W)halve window on detection of loss, W  W/2timeouts due to lack of ACKs, W  1successive timeout intervals grow exponentially long up to six timesTCP throughput/loss relationshipIdealized model:W is maximum supportable window size (then loss occurs)TCP window starts at W/2 grows to W, then halves, then grows to W, then halves… one window worth of packets each RTTto find: throughput as function of loss, RTTTCPwindow sizetime (rtt)W/2Wloss occursTCP throughput/loss relationshipTCPwindow sizetime (rtt)W/2Wperiod# packets sent per “period” =TCP throughput/loss relationshipTCPwindow sizetime (rtt)W/2Wperiod2/0)2(...122WnnWWWW2/0212WnnWW2)12/(2/212WWWWWW43832# packets sent per “period” = 283WTCP throughput/loss relationshipTCPwindow sizetime (rtt)W/2Wperiod# packets sent per “period” 283W1 packet lost per “period” implies: ploss238Wor: losspW38rttpackets43utavg._thrup WB B throughput formula can be extendedto model timeouts and slow start (PFTK)rttpac kets22.1utavg._t hruplosspB Recall RED queue managementdropping/marking packets depends on average queue length -> p = p(x)More generally: active queue management (AQM)tmintmaxpmax12tmaxMarking probability pAverage queue length x 0Bottleneck behaviori Bi (RTTi ,p) = CC - router bandwidth Bi - throughput of flow ibottleneck router:capacity fully utilizedall interfering sessions see same loss prob.do all sessions see same thruput?Single bottleneck: infinite flowsN infinite TCP sessionstwo way propagation delay Ai, i = 1,…,Nthroughput Bi(p,RTTi) one bottleneck routerRED queue management• avg. queue length x ; dropping probability p(x) to discoverBi: TCP sessions’ throughput,router behavior, e.g., drop prob. avg. queue len.Model and solutionmodelsolve a fixed point problem for xunique solution provided B is monotonic and continuous on xresulting x can be used to obtain RTTi and p p = p(x) (AQM) RTTi = Ai + x /C (round trip time) i B (p , RTT i) = C, for i =1 ,…,N i Bi (x) = C, for i =1 ,…,NModel versus simulation: single bottleneck, infinite flows•fixed router capacity 4 Mbps and RED parameters •10-120 TCP flows •two-way prop. delay 20+2i ms, i = 1,…,N throughputrouter lossBottleneck principle: a qualitative resultnew/improved, Bnew(p)Bnew(p)BTCP(p)pthruputTCP, BTCP(p)Bnew(p) > BTCP(p)Sharing bottleneck with TCPNTCPNnew pNnew Bnew(p) + NTCP Bni(p) = Ca win! C  Bnew(p) > BTCP(p)friendly?Replacing TCP with TCP-newNC N Bnew(pnew) = C vs N BTCP(pTCP) = C  pnew > pTCPa loss!pTCPpnewsimple model for TCP c ≈ 1.2bottleneck principlemultiple bottlenecksfluid models,pTcB Multiple Bottleneck: infinite flowsN TCP flowsthroughputs B = <Bi (Ri,pi)>V congested AQM routerscapacities C = <Cv > avg. queue lengths x = <xv >discard prob. p = <pv (xv )>bottleneck router model i Bi (x ) = Cv , v =1,…,V V equations, V unknownsResults: multiple bottleneck, infinite flows•tandem network core, 5 -10 routers•2-way propagation delay 20-120 ms•bandwidth, 2-6 Mbps•PFTK model error•throughput < 10%•loss rate < 10%•avg. queue length < 15%•similar results for cyclic networksrouter lossthroughputComments what about UDP / non-TCP flows?If there are “non-responsive” flows, just decrease bottleneck capacity by non-responsive flow rate what about short lived flows?Hard (some work in sigcomm 2001 – massoulie) note: throughout, assumption that time to send packets in window is less that RTTDynamic (transient) analysis of TCP fluidsmodel TCP traffic as fluiddescribe behavior of flows and queues using Ordinary Differential Equations solve resulting ODEs numericallyLoss ModelSenderAQM RouterPacket Drop/MarkReceiverLoss Rate as seen by Sender: (t = B(t-p(t-Round Trip Delay ()B(t)p(t)A Single Congested RouterTCP flow iAQM routerC, pfocus on single bottlenecked routercapacity {C (packets/sec) }queue length q(t)discard prob. p(t)N TCP flows thru routerwindow