《TCP拥塞控制【优质内容】》由会员分享，可在线阅读，更多相关《TCP拥塞控制【优质内容】（87页珍藏版）》请在金锄头文库上搜索。
1、1第二章TCP拥塞控制江勇2OutlineWindow Flow ControlAnalysis of TCP Congestion ControlTahoe, Reno, NewReno,Sack, VegasBeyond TCP Congestion Control3OutlineWindow Flow ControlAnalysis of TCP Congestion ControlTahoe, Reno, NewReno, Sack, VegasBeyond TCP Congestion Control4ProblemFlow control-make sure that the re
2、ceiver can receive as fast as you send Congestion control-make sure that the network delivers the packets to the receiver5Window flow controlLost packet detected by ACKApproximately W packets transmitted per RTTHigher window higher throughputSelf-clocking112W221RTTWWtimetimeSourceDestination6Early T
3、CPPre-1988Go-back-N ARQ-Detects loss from timeout-Retransmits from lost packet onwardFlow control: self-clocking7Source rateLimit the number of packets in the network to window WSource rate = bpsIf W too small then rate capacityIf W too big then rate capacity= congestion8Why do You Care About Conges
4、tion Control?Otherwise you get to congestion collapseHow might this happen?-Assume network is congested (a router drops packets) -You learn the receiver didnt get the packeteither by ACK, NACK, or Timeout-What do you do? retransmit packet-Still receiver didnt get the packet-Retransmit again-. and so
5、 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, 32 Kbp
6、sthroughput dropped to 40 bpsfactor 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 downQuestions:-How do you detect network congestion?-By how much do you sl
7、ow down?11OutlineWindow Flow ControlAnalysis of TCP Congestion ControlTahoe, Reno, NewReno, Sack, VegasBeyond 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 to
8、zero (congestion collapse)-Delay approaches infinityNote (in an M/M/1 queue)-Delay = 1/(1 utilization)LoadLoadThroughputDelaykneecliffcongestioncollapsepacketloss13Congestion Control vs. Congestion AvoidanceCongestion control goal-Stay left of cliff Congestion avoidance goal-Stay left of kneeLoadThr
9、oughputkneecliffcongestioncollapse14GoalsOperate near the knee pointRemain in equilibriumHow 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 “co
10、nstant”15How Do You Do It?Detect when network approaches/reaches knee pointStay thereQuestions-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 CongestionE
11、xplicit 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
12、 CongestionImplicit 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 underload
13、Too fast-Overshoot 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
14、bottleneck get the same amount of bandwidthAssumes no knowledge of prioritiesFairness = 1 - distance from fairness lineUser 1: x1User 2: x22 user example2 gettingtoo much1 getting too muchfairnessline20Control System Model CJ89Simple, yet powerful modelUser 1User 2User nx1x2xnxiXgoaly21Possible Choi
15、cesMultiplicative increase, 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 AvoidanceSlow down “Slow Start”If cwnd ssthresh then each time a
16、segment is acknowledged increment cwnd by 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 Avoid
17、ance ExampleAssume that ssthresh = 8Roundtrip 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:/* Multipli
18、cative decrease */ssthresh = cwnd/2;cwnd = 1;while (next unack + win)transmit next packet;where win = min(cwnd, flow_win);unacknextwinseq #37Packet LossPacket loss detected by-Retransmission timeouts (RTO timer)-Duplicate ACKs (at least 3)123456123PacketsAcknowledgements337338Fast RetransmitImmediat
19、ely retransmits after 3 dupACKs without waiting 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
20、 algorithm first appeared in the 4.3BSD Tahoe release, and it was followed by slow start. 39Summary: TahoeBasic 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 s
21、sthresh then W + (ss) else W += 1/W (ca)for every lossssthresh := W/2 W := 1 40TCP Reno (Jacobson 1990)Slow start, congestion avoidance, fast retransmitAddition: fast recoveryMost widely used version of TCP today sstimewindowcass: slow startca: congestion avoidance41Fast recoveryMotivation: prevent
22、pipe from emptying after fast retransmitIdea: each dupACK represents 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 an
23、other duplicate ACK arrives, cwnd += MSS. Transmit a packet, if allowed by the new value of cwnd. -On non-dup ACK (1 RTT later), set cwnd ssthresh (window deflation)Enter CA42Example: FR/FRFast retransmit-Retransmit on 3 dupACKsFast recovery-Inflate window while repairing loss to fill pipeThe fast r
24、ecovery algorithm appeared in the 4.3BSD Reno release. 12timeStimeD345687100070099000111Exit FR/FRRTT843Summary: RenoBasic ideas-Fast recovery avoids slow start-dupACKs: fast retransmit + fast recovery-Timeout: fast retransmit + slow startAt steady state, cwnd oscillates around the optimal window si
25、ze.slow startretransmitcongestion avoidance FR/FR dupACKstimeout44Variant : NewReno (Fall & Floyd1996)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
26、 timeout before proceedingIdea: partial ACK indicates lost packets-Stays in FR/FR and retransmits 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, retrans
27、mits pkt 1, enter FR/FRNext dupACK increment cwnd to 9After a RTT, ACK arrives for pkts 1 & 2, exit FR/FR, cwnd=5, 8 unacked pktsNo more ACK, sender must wait for timeout12timeStimeD34568718FR/FR090000098 unackd pkts253timeout46Variant: SACK (Mathis, Mahdavi, Floyd, Romanow 96)Motivation: Reno & New
28、Reno retransmit at most 1 lost packet per RTT-Pipe can be emptied during FR/FR with multiple lossesIdea: SACK provides better estimate of packets in pipe-SACK TCP option describes received packets-On 3 dupACKs: retransmits, halves window, enters FR-Updates pipe = packets in pipeIncrement when lost o
29、r new packets sentDecrement when dupACK received-Transmits a (lost or new) packet when pipe cwnd-Exit FR when all packets outstanding when FR was entered are acknowledged47TCP Vegas (Brakmo & Peterson 1994)Reno with a new congestion avoidance algorithmConverges (provided buffer is large) !sstimewind
30、owca48Congestion avoidanceEach source estimates number of its own packets in pipe from RTTAdjusts window to maintain estimate between ad and bdfor every RTT if W/RTTmin W/RTT b RTTmin then W - for every lossW := W/249ImplicationsCongestion measure = end-to-end queueing delayAt equilibrium-Zero loss-
31、Stable window at full utilization-Approximately weighted proportional fairness-Nonzero queue, larger for more sourcesConvergence to equilibrium-Converges if sufficient network buffer-Oscillates like Reno otherwise50Reflections on TCPAssumes that all sources cooperateAssumes that congestion occurs on
32、 time scales greater than 1 RTTOnly useful for reliable, in order delivery, non-real time applicationsVulnerable to non-congestion related loss (e.g. wireless)Can be unfair to long RTT flows51OutlineWindow Flow ControlAnalysis of TCP Congestion ControlTahoe, Reno, VegasBeyond TCP Congestion Control5
33、2TCP ProblemsWhen TCP congestion control was originally designed in 1988:-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 pr
34、oduct paths-Selfish users-Wireless (or any high error links)53High Bandwidth-Delay Product PathsMotivation-10Gb/s links now common in Internet coreas a result of Wave Division Multiplexing (WDM), link bandwidth 2x/9 months-Some users have access to and need for 10Gb/s end-to-ende.g., very large scie
35、ntific, financial databases-Satellite/Interplanetary links have a high delayProblems-slow start-Additive increase, multiplicative decrease (AIMD)54Slow StartTCP throughput controlled by congestion window (cwnd) sizeIn slow start, window increases exponentially, but may not be enoughexample: 10Gb/s,
36、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 goodLose only one packet drop out of slow start into AIMD (even worse)55AIMDIn AIMD, cwnd increases by
37、 1 packet/ RTTAvailable 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/stime to reach 100% utilization is proportional to available bandwidth-e.g., 5Gb/s ava
38、ilable, 200ms RTT, 1460B payload 17,000s56Simulation 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 DelayB
39、W = 155 Mb/s57Proposed 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
40、.To control fairness: use AIMD which converges to fairness58Characteristics of Solution1.Improved Congestion Control (in high bandwidth-delay & conventional environments):Small queuesAlmost no drops2.Improved Fairness3.Scalable (no per-flow state)4.Flexible bandwidth allocation: min-max fairness, pr
41、oportional fairness, differential bandwidth allocation, 59XCP: An eXplicit Control Protocol1. Congestion Controller2. Fairness Controller60Feedback Round Trip TimeCongestion WindowCongestion HeaderFeedback Round Trip TimeCongestion Window How does XCP Work?Feedback = + 0.1 packet61Feedback = + 0.1 p
42、acket 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?XCP extends ECN and CSFQ63How Does an XCP Router Compute the Feedback?Congestion ControllerFairness
43、 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-can recover original k blocks from any k of the n blocks-n-k blocks of overhead-trade bandwidth for
44、loss-can recover from loss in time independent of link RTTuseful for links that have long RTT (e.g. satellite)-pay n-k overhead whether loss or notneed to adapt n, k depending on current channel conditions83HybridIndirect TCP BB95-Split TCP connection into two parts-regular TCP from fixed host (FH)
45、to base station-modified TCP from base station to mobile host (MH)-base station fails?-wired path faster than wireless path?84HybridTCP Snoop BSK95-Base station snoops TCP packets, infers flow-cache data packets going to wireless side-If dup acks from wireless side, suppress ack and retransmit from
46、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 level retransmissions-802.11b: acks necessary anyway in MAC for collision avoidance-additional del
47、ay is only a few link RTTs (5ms)Satellite-FEC because of long RTT issuesLink layer solutions give adequate, predictable performance, easily deployable86ReferencesW. Stevens. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. RFC 2001, Jan. 1997. S. Floyd and T. Hend
48、erson. 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 PapersDina 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.
