计算机网络英文课件：lecture-12- Congestion Control

《计算机网络英文课件：lecture-12- Congestion Control》由会员分享，可在线阅读，更多相关《计算机网络英文课件：lecture-12- Congestion Control（27页珍藏版）》请在装配图网上搜索。

1、Computer Networking Lecture 12Principles of Congestion ControlApril 14,2017Dr.Qingyao WSome slides are from lectures of Prof.J.F Kurose and K.W.RossTransport Layer3-2Principles of Congestion ControlCongestion:informally:“too many sources sending too much data too fast for network to handle”different

2、 from flow control!manifestations:lost packets(buffer overflow at routers)long delays(queueing in router buffers)a top-10 problem!Transport Layer3-3Causes/costs of congestion:scenario 1 two senders,two receivers one router,infinite buffers no retransmission large delays when congested maximum achiev

3、able throughputunlimited shared output link buffersHost Alin:original dataHost BloutTransport Layer3-4Causes/costs of congestion:scenario 2 one router,finite buffers sender retransmission of lost packetfinite shared output link buffersHost Alin:original dataHost Bloutlin:original data,plus retransmi

4、tted dataTransport Layer3-5Causes/costs of congestion:scenario 2 always:(goodput)“perfect”retransmission only when loss:retransmission of delayed(not lost)packet makes larger(than perfect case)for samelinlout=linloutlinlout“costs”of congestion:rmore work(retrans)for given“goodput”runneeded retransmi

5、ssions:link carries multiple copies of pktR/2R/2linloutb.R/2R/2linlouta.R/2R/2linloutc.R/4R/3Transport Layer3-6Causes/costs of congestion:scenario 3 four sendersmultihop pathstimeout/retransmitlinQ:what happens as and increase?linfinite shared output link buffersHost Alin:original dataHost Bloutlin:

6、original data,plus retransmitted dataTransport Layer3-7Causes/costs of congestion:scenario 3 Another“cost”of congestion:rwhen packet dropped,any“upstream transmission capacity used for that packet was wasted!Host AHost BloutTransport Layer3-8Approaches towards congestion controlEnd-end congestion co

7、ntrol:no explicit feedback from networkcongestion inferred from end-system observed loss,delayapproach taken by TCPNetwork-assisted congestion control:routers provide feedback to end systems single bit indicating congestion(SNA,DECbit,TCP/IP ECN,ATM)explicit rate sender should send atTwo broad appro

8、aches towards congestion control:Transport Layer3-9Case study:ATM ABR congestion controlABR:available bit rate:“elastic service”if senders path“underloaded”:sender should use available bandwidthif senders path congested:sender throttled to minimum guaranteed rateRM(resource management)cells:sent by

9、sender,interspersed with data cellsbits in RM cell set by switches(“network-assisted”)NI bit:no increase in rate(mild congestion)CI bit:congestion indicationRM cells returned to sender by receiver,with bits intact Transport Layer3-10Case study:ATM ABR congestion control two-byte ER(explicit rate)fie

10、ld in RM cell congested switch may lower ER value in cell sender send rate thus maximum supportable rate on path EFCI bit in data cells:set to 1 in congested switch if data cell preceding RM cell has EFCI set,sender sets CI bit in returned RM cellTCP Congestion ControlTransport Layer3-12TCP Congesti

11、on Control sender limits transmission:LastByteSent-LastByteAcked CongWin Roughly,CongWin is dynamic,function of perceived network congestionHow does sender perceive congestion?loss event=timeout or 3 duplicate acks TCP sender reduces rate(CongWin)after loss eventrate=CongWin RTT Bytes/secTransport L

12、ayer3-14TCP Slow Start When connection begins,CongWin=1 MSS Example:MSS=500 bytes&RTT=200 msec initial rate=20 kbps available bandwidth may be MSS/RTT desirable to quickly ramp up to respectable raterWhen connection begins,increase rate exponentially fast until first loss eventTransport Layer3-15TCP

13、 Slow Start(more)When connection begins,increase rate exponentially until first loss event:double CongWin every RTT done by incrementing CongWin for every ACK received Summary:initial rate is slow but ramps up exponentially fastHost Aone segmentRTTHost Btimetwo segmentsfour segmentsTransport Layer3-

14、16TCP Congestion Avoidance Example:Transport Layer3-17RefinementQ:When should the exponential increase switch to linear?A:When CongWin gets to 1/2 of Threshold value before timeout.Implementation:Variable Threshold At loss event,Threshold is set to 1/2 of CongWin just before loss eventTransport Laye

15、r3-18Refinement:inferring loss After 3 dup ACKs:CongWin is cut in half window then grows linearly But after timeout event:CongWin instead set to 1 MSS;window then grows exponentially to a threshold,then grows linearlyq 3 dup ACKs indicates network capable of delivering some segmentsq timeout indicat

16、es a“more alarming”congestion scenarioPhilosophy:Transport Layer3-19TCP sender congestion controlStateEvent TCP Sender Action CommentarySlow Start(SS)ACK receipt for previously unacked data CongWin=CongWin+MSS,If(CongWin Threshold)set state to“Congestion Avoidance”Resulting in a doubling of CongWin

17、every RTTCongestionAvoidance(CA)ACK receipt for previously unacked dataCongWin=CongWin+MSS*(MSS/CongWin)Additive increase,resulting in increase of CongWin by 1 MSS every RTTSS or CALoss event detected by triple duplicate ACKThreshold=CongWin/2,CongWin=Threshold,Set state to“Congestion Avoidance”Fast

18、 recovery,implementing multiplicative decrease.CongWin will not drop below 1 MSS.SS or CATimeoutThreshold=CongWin/2,CongWin=1 MSS,Set state to“Slow Start”Enter slow startSS or CADuplicate ACKIncrement duplicate ACK count for segment being ackedCongWin and Threshold not changedTransport Layer3-20TCP

19、congestion control:additive increase,multiplicative decrease8 Kbytes16 Kbytes24 KbytestimecongestionwindowrApproach:increase transmission rate(window size),probing for usable bandwidth,until loss occursmadditive increase:increase CongWin by 1 MSS every RTT until loss detectedmmultiplicative decrease

20、:cut CongWin in half after loss timecongestion window sizeSaw toothbehavior:probingfor bandwidthTransport Layer3-21Summary:TCP Congestion Control When CongWin is below Threshold,sender in slow-start phase,window grows exponentially.When CongWin is above Threshold,sender is in congestion-avoidance ph

21、ase,window grows linearly.When a triple duplicate ACK occurs,Threshold set to CongWin/2 and CongWin set to Threshold.When timeout occurs,Threshold set to CongWin/2 and CongWin is set to 1 MSS.Transport Layer3-22TCP throughput Whats the average throughout of TCP as a function of window size and RTT?I

22、gnore slow start Let W be the window size when loss occurs.When window is W,throughput is W/RTT Just after loss,window drops to W/2,throughput to W/2RTT.Average throughout:0.75 W/RTTTransport Layer3-23TCP Futures:TCP over“long,fat pipes”Example:1500 byte segments,100ms RTT,want 10 Gbps throughput Re

23、quires window size W=83,333 in-flight segments Throughput in terms of loss rate:L=210-10 Wow New versions of TCP for high-speedLRTTMSS22.1Transport Layer3-24Fairness goal:if K TCP sessions share same bottleneck link of bandwidth R,each should have average rate of R/KTCP connection 1bottleneckrouterc

24、apacity RTCP connection 2TCP FairnessTransport Layer3-25Why is TCP fair?Two competing sessions:Additive increase gives slope of 1,as throughout increasesmultiplicative decrease decreases throughput proportionally RRequal bandwidth shareConnection 1 throughputConnection 2 throughputcongestion avoidan

25、ce:additive increaseloss:decrease window by factor of 2congestion avoidance:additive increaseloss:decrease window by factor of 2Transport Layer3-26Fairness(more)Fairness and UDP Multimedia apps often do not use TCP do not want rate throttled by congestion control Instead use UDP:pump audio/video at

26、constant rate,tolerate packet loss Research area:TCP friendlyFairness and parallel TCP connections nothing prevents app from opening parallel connections between 2 hosts.Web browsers do this Example:link of rate R supporting 9 connections;new app asks for 1 TCP,gets rate R/10 new app asks for 11 TCP

27、s,gets R/2!Transport Layer3-27Summary principles behind transport layer services:multiplexing,demultiplexing reliable data transfer flow control congestion control instantiation and implementation in the Internet UDP TCPNext:leaving the network“edge”(application,transport layers)into the network“core”