《TCP擁塞控制【優(yōu)質(zhì)內(nèi)容】》由會員分享，可在線閱讀，更多相關(guān)《TCP擁塞控制【優(yōu)質(zhì)內(nèi)容】（87頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、1第二章TCP擁塞控制江勇2Outline Window Flow Control Analysis of TCP Congestion Control Tahoe,Reno,NewReno,Sack,Vegas Beyond TCP Congestion Control3OutlineWindow Flow Control Analysis of TCP Congestion Control Tahoe,Reno,NewReno,Sack,Vegas Beyond TCP Congestion Control4Problem Flow control-make sure that the r
2、eceiver can receive as fast as you send Congestion control-make sure that the network delivers the packets to the receiver5Window flow control Lost packet detected by ACK Approximately W packets transmitted per RTT Higher window higher throughput Self-clocking112W221RTTWWtimetimeSourceDestination6Ea
3、rly TCP Pre-1988 Go-back-N ARQ-Detects loss from timeout-Retransmits from lost packet onward Flow control:self-clocking7Source rate Limit the number of packets in the network to window W Source rate=bps If W too small then rate capacityIf W too big then rate capacity=congestionRTTMSSW 8Why do You Ca
4、re About Congestion Control?Otherwise you get to congestion collapse How might this happen?-Assume network is congested(a router drops packets)-You learn the receiver didnt get the packet either by ACK,NACK,or Timeout-What do you do?retransmit packet-Still receiver didnt get the packet-Retransmit ag
5、ain-.and so on-And now assume that everyone is doing the same!9Why do You Care About Congestion Control?Network will become more and more congested-And this with duplicate packets rather than new packets!October 1986,Internet had its first congestion collapse-Link LBL to UC Berkeley 400 yards,3 hops
6、,32 Kbps throughput dropped to 40 bps factor of 1000 drop!1988,Van Jacobson proposed TCP flow control10Solutions?Increase buffer size.Why not?Slow down-If you know that your packets are not delivered because network congestion,slow down Questions:-How do you detect network congestion?-By how much do
7、 you slow down?11Outline Window Flow ControlAnalysis of TCP Congestion Control Tahoe,Reno,NewReno,Sack,Vegas Beyond TCP Congestion Control12Whats Really Happening?Knee point after which-Throughput increases very slow-Delay increases fastCliff point after which-Throughput starts to decrease very fast
8、 to zero(congestion collapse)-Delay approaches infinityNote(in an M/M/1 queue)-Delay=1/(1 utilization)LoadLoadThroughputDelaykneecliffcongestioncollapsepacketloss13Congestion Control vs.Congestion Avoidance Congestion control goal-Stay left of cliff Congestion avoidance goal-Stay left of kneeLoadThr
9、oughputkneecliffcongestioncollapse14Goals Operate near the knee point Remain in equilibrium How to maintain equilibrium?-Dont put a packet into network until another packet leaves.How do you do it?-Use ACK:send a new packet only after you receive an ACK.Why?-Maintain number of packets in network“con
10、stant”15How Do You Do It?Detect when network approaches/reaches knee point Stay there Questions-How do you get there?-What if you overshoot(i.e.,go over knee point)?Possible solution:-Increase window size until you notice congestion -Decrease window size if network congested16Detecting Congestion Ex
11、plicit network signal-Send packet back to source(e.g.ICMP Source Quench)Control traffic congestion collapse-Set bit in header(e.g.DEC DNA/OSI Layer 4CJ89,ECN)Can be subverted by selfish receiver SEW01-Unless on every router,still need end-to-end signal-Could be robust,if deployed 17Detecting Congest
12、ion Implicit network signal-Loss(e.g.TCP Tahoe,Reno,New Reno,SACK)+relatively robust,-no avoidance-Delay(e.g.TCP Vegas)+avoidance,-difficult to make robust-Easily deployable-Robust enough?Wireless?18Efficient AllocationToo slow-Fail to take advantage of available bandwidth underloadToo fast-Overshoo
13、t knee overload,high delay,lossEveryones doing it-May all under/over shoot large oscillationsOptimal:-xi=XgoalEfficiency=1-distance from efficiency lineUser 1:x1User 2:x2Efficiencyline2 user exampleoverloadunderload19Fair AllocationMaxmin fairness-Flows which share the same bottleneck get the same a
14、mount of bandwidthAssumes no knowledge of prioritiesFairness=1-distance from fairness lineUser 1:x1User 2:x22 user example2 gettingtoo much1 getting too muchfairnessline 22iixnxxF20Control System Model CJ89 Simple,yet powerful modelUser 1User 2User nx1x2xnxiXgoaly21Possible ChoicesMultiplicative inc
15、rease,additive decrease-aI=0,bI1,aD0,bI=1,aD1,aD=0,0bD0,bI=1,aD=0,0bD=ssthresh ACK 1segment 1cwnd=1cwnd=2segment 2segment 3ACK 2cwnd=4segment 4segment 5segment 6segment 7ACK3-4cwnd=834Congestion Avoidance Slow down“Slow Start”If cwnd ssthresh then each time a segment is acknowledged increment cwnd b
16、y 1/cwnd (cwnd+=1/cwnd).So cwnd is increased by one only if all segments have been acknowlegded.Congestion avoidance and slow start are independent algorithms with different objectives.In practice they are implemented together.35Slow Start/Congestion Avoidance Example Assume that ssthresh=8cwnd=1cwn
17、d=2cwnd=4cwnd=8cwnd=9cwnd=10Roundtrip timesCwnd(in segments)ssthresh36Putting Everything Together:TCP PseudocodeInitially:cwnd=1;ssthresh=infinite;New ack received:if(cwnd ssthresh)/*Slow Start*/cwnd=cwnd+1;else /*Congestion Avoidance*/cwnd=cwnd+1/cwnd;Timeout:/*Multiplicative decrease*/ssthresh=cwn
18、d/2;cwnd=1;while(next unack+win)transmit next packet;where win=min(cwnd,flow_win);unacknextwinseq#37Packet Loss Packet loss detected by-Retransmission timeouts(RTO timer)-Duplicate ACKs(at least 3)123456123PacketsAcknowledgements337338Fast Retransmit Immediately retransmits after 3 dupACKs without w
19、aiting for timeout(fast retransmit)Adjusts ssthresh-ssthresh max(flightsize/2,2)-flightsize:The amount of data that has been sent but not yet acknowledged.Enter Slow Start(cwnd=1)Assumption:loss indicates congestion(buffer overflow)The fast retransmit algorithm first appeared in the 4.3BSD Tahoe rel
20、ease,and it was followed by slow start.39Summary:Tahoe Basic ideas-Gently probe network for spare capacity-Drastically reduce rate on congestion-Windowing:self-clocking-Other functions:round trip time estimation,error recoveryfor every ack if W ssthresh then W+(ss)else W+=1/W(ca)for every lossssthre
21、sh:=W/2 W :=1 40TCP Reno (Jacobson 1990)Slow start,congestion avoidance,fast retransmit Addition:fast recovery Most widely used version of TCP today sstimewindowcass:slow startca:congestion avoidance41Fast recoveryMotivation:prevent pipe from emptying after fast retransmitIdea:each dupACK represents
22、 a packet having left the pipe,that is,there is still data flowing between the two ends.Enter FR/FR after 3 dupACKs-Set ssthresh max(flightsize/2,2)-Retransmit lost packet-Set cwnd ssthresh+3*MSS(window inflation)-Each time another duplicate ACK arrives,cwnd+=MSS.Transmit a packet,if allowed by the
23、new value of cwnd.-On non-dup ACK(1 RTT later),set cwnd ssthresh(window deflation)Enter CA42Example:FR/FR Fast retransmit-Retransmit on 3 dupACKs Fast recovery-Inflate window while repairing loss to fill pipe The fast recovery algorithm appeared in the 4.3BSD Reno release.12timeStimeD345687100070099
24、000111Exit FR/FRRTT843Summary:Reno Basic ideas-Fast recovery avoids slow start-dupACKs:fast retransmit+fast recovery-Timeout:fast retransmit+slow start At steady state,cwnd oscillates around the optimal window size.slow startretransmitcongestion avoidance FR/FR dupACKstimeout44Variant:NewReno(Fall&F
25、loyd1996)Motivation:multiple losses within a window-Partial ACK acknowledges some but not all packets outstanding at start of FR-Partial ACK takes Reno out of FR,deflates window-Sender may have to wait for timeout before proceeding Idea:partial ACK indicates lost packets-Stays in FR/FR and retransmi
26、ts immediately-Retransmits 1 lost packet per RTT until all lost packets from that window are retransmitted-Eliminates timeout45Example:NewRenoOn 3 dupACKs,receiver has packets 2,4,6,8,cwnd=8,retransmits pkt 1,enter FR/FRNext dupACK increment cwnd to 9After a RTT,ACK arrives for pkts 1&2,exit FR/FR,c
27、wnd=5,8 unacked pktsNo more ACK,sender must wait for timeout12timeStimeD34568718FR/FR090000098 unackd pkts253timeout46Variant:SACK (Mathis,Mahdavi,Floyd,Romanow 96)Motivation:Reno&NewReno retransmit at most 1 lost packet per RTT-Pipe can be emptied during FR/FR with multiple lossesIdea:SACK provides
28、 better estimate of packets in pipe-SACK TCP option describes received packets-On 3 dupACKs:retransmits,halves window,enters FR-Updates pipe=packets in pipe Increment when lost or new packets sent Decrement when dupACK received-Transmits a(lost or new)packet when pipe cwnd-Exit FR when all packets o
29、utstanding when FR was entered are acknowledged47TCP Vegas(Brakmo&Peterson 1994)Reno with a new congestion avoidance algorithm Converges(provided buffer is large)!sstimewindowca48Congestion avoidance Each source estimates number of its own packets in pipe from RTT Adjusts window to maintain estimate
30、 between ad and bdfor every RTT if W/RTTmin W/RTT b RTTmin then W-for every lossW:=W/249Implications Congestion measure=end-to-end queueing delay At equilibrium-Zero loss-Stable window at full utilization-Approximately weighted proportional fairness-Nonzero queue,larger for more sources Convergence
31、to equilibrium-Converges if sufficient network buffer-Oscillates like Reno otherwise50Reflections on TCP Assumes that all sources cooperate Assumes that congestion occurs on time scales greater than 1 RTT Only useful for reliable,in order delivery,non-real time applications Vulnerable to non-congest
32、ion related loss(e.g.wireless)Can be unfair to long RTT flows51Outline Window Flow Control Analysis of TCP Congestion Control Tahoe,Reno,VegasBeyond TCP Congestion Control52TCP Problems When TCP congestion control was originally designed in 1988:-Maximum link bandwidth:10Mb/s-Users were mostly from
33、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)53High Bandwidth-Delay Product Paths Motivation-10Gb/s links now common in
34、 Internet core as a result of Wave Division Multiplexing(WDM),link bandwidth 2x/9 months-Some users have access to and need for 10Gb/s end-to-end e.g.,very large scientific,financial databases-Satellite/Interplanetary links have a high delay Problems-slow start-Additive increase,multiplicative decre
35、ase(AIMD)54Slow 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 ti
36、me:382MB/3.6s=850Mb/s-8.5%utilization not very good Lose only one packet drop out of slow start into AIMD(even worse)55AIMD 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 durin
37、g 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,000s56Simulation ResultsRound Trip Delay(sec)Avg.TCP UtilizationBottleneck Bandwidth(Mb/s)Avg.TCP UtilizationShown analyti
38、cally in Low01 and via simulations50 flows in both directionsBuffer=BW x DelayRTT=80 ms50 flows in both directionsBuffer=BW x DelayBW=155 Mb/s57Proposed Solution:Decouple Congestion Control from FairnessExample:In TCP,Additive-Increase Multiplicative-Decrease(AIMD)controls bothCoupled because a sing
39、le 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 fairness58Characteristics of Solution1.Improved Congestion Control(in high bandwidth-delay&conventional environments):Small queu
40、esAlmost no drops2.Improved Fairness3.Scalable(no per-flow state)4.Flexible bandwidth allocation:min-max fairness,proportional fairness,differential bandwidth allocation,59XCP:An eXplicit Control Protocol1.Congestion Controller2.Fairness Controller60Feedback Round Trip TimeCongestion WindowCongestio
41、n HeaderFeedback Round Trip TimeCongestion Window How does XCP Work?Feedback =+0.1 packet61Feedback=+0.1 packet Round Trip TimeCongestion WindowFeedback =-0.3 packet How does XCP Work?62 Congestion Window=Congestion Window+FeedbackRouters compute feedback without any per-flow state How does XCP Work
42、?XCP extends ECN and CSFQ63How Does an XCP Router Compute the Feedback?Congestion ControllerFairness ControllerGoal:Divides between flows to converge to fairnessLooks at a flows state in Congestion Header Algorithm:If 0 Divide equally between flowsIf 0 Divide equally between flowsIf k coded blocks-c
43、an recover original k blocks from any k of the n blocks-n-k blocks of overhead-trade bandwidth for loss-can recover from loss in time independent of link RTT useful for links that have long RTT(e.g.satellite)-pay n-k overhead whether loss or not need to adapt n,k depending on current channel conditi
44、ons83Hybrid Indirect TCP BB95-Split TCP connection into two parts-regular TCP from fixed host(FH)to base station-modified TCP from base station to mobile host(MH)-base station fails?-wired path faster than wireless path?84Hybrid TCP Snoop BSK95-Base station snoops TCP packets,infers flow-cache data
45、packets going to wireless side-If dup acks from wireless side,suppress ack and retransmit from cache-soft state-what about non-TCP protocols?-what if wireless not last hop?85ConclusionTransport protocol modifications not deployed-SACK was deployed because of general utilityCellular,802.11b-link leve
46、l retransmissions-802.11b:acks necessary anyway in MAC for collision avoidance-additional delay is only a few link RTTs(5ms)Satellite-FEC because of long RTT issuesLink layer solutions give adequate,predictable performance,easily deployable86References W.Stevens.TCP Slow Start,Congestion Avoidance,F
47、ast Retransmit,and Fast Recovery Algorithms.RFC 2001,Jan.1997.S.Floyd and T.Henderson.The NewReno Modification to TCPs Fast Recovery Algorithm.RFC2582,April 1999.M.Mathis,J.Mahdavi,S.Floyd,and A.Romanow.TCP Selective Acknowledgment Options.RFC 2018,October 1996.87Reading Papers Dina Katabi,Mark Handley,and Charlie Rohrs.Congestion Control for High Bandwidth-Delay Product Networks,In:Proceedings on ACM Sigcomm 2002.-http:/ana.lcs.mit.edu/dina/XCP/L.Brakmo,S.OMalley,and L.Peterson.TCP Vegas:New techniques for congestion detection and avoidance.In Proceedings of ACM SIGCOMM 1994.
TCP擁塞控制【優(yōu)質(zhì)內(nèi)容】
