08-Congestion controlTransport Layer3-1Principles of Congestion ControlpfgCongestion:Congestion: informally: “too many sources sending too much data too fast for networkto handle” different from flow control!Transport Layer3-2Costs of congestion: scenario 1Costs of congestion scenario 1 two senders, two iHost Aλin : original dataλoutreceivers one router, infinite buffers unlimited shared output link buffersHost Binfinite buffers no retransmissionAs the link capacity R is approached, the delay in the system increases.Transport Layer3-3Costs of congestion: scenario 2Costs of congestion scenario 2 one router, finitebuffers, reliable data transfertransfer sender retransmission of lost packetHtAλHost Aλin : original dataλoutλ'in : original data, plus retransmitted data (offered load)finite shared output link buffersHost BTransport Layer3-4Costs of congestion: scenario 2Costs of congestion scenario 2Reduced transmission rateReduced transmission rate With finite buffers, packets will be dropped and re-transmissions are required D di th l th f ti t i t l t i i Depending on the length of timeout interval, retransmissions may occur for packets that are delayed (not lost) and hence the transmission rate decreases.Transport Layer3-5Causes/costs of congestion: scenario 3Causes/costs of congest on scenar o 3 four senders multihop pathsConsider what happens when 2 senders competepp timeout/retransmitHost Awhen 2 senders competeHost Cfinite shared output link bufferslink buffersHost BHost DHost DTransport Layer3-6Costs of congestion: scenario 3Costs of congestion scenario 3 when packet dropped, any “upstream" transmission capacity used for that packet was wasted!Transport Layer3-7Approaches towards congestion controlpp gTwo broad approaches towards congestion control:End-to-end congestion control:Network-assisted congestion control: no explicit feedback from network congestion inferred from routers provide feedback to end systems bits indicating gffmend-system observed loss, delay approach taken by TCPgcongestion explicit rate sender should send atpp yTransport Layer3-8TCP Congestion Control end-end control (no network TCP Congest on ControlHow does sender (assistance) perceive congestion? loss event = timeout or3 d li t ksHow does sender limit the rate?CongWin(congestion window)3 duplicate acksThree mechanisms to CongWin (congestion window)is dynamic, function of perceived network congestionThree mechanisms to adapt CongWin: AIMDl LastByteSent-LastByteAcked≤ CongWin slow start conservative after timeout eventsTransport Layer3-9TCP AIMDmultiplicative decrease:cut CongWin in half ft l tadditive increase:increase CongWin by 1 MSS RTT i congestionwindowafter loss event1 MSS every RTT in the absence of loss events24 Kbyteswindow8 Kbytes16 Kbytes8bytestimeTransport Layer3-10Long-lived TCP connectionTCP Slow StartTCP Slow Start When connection begins, When connection begins, g,CongWin = 1 MSS available bandwidth may b MSS/RTTWg,increase rate exponentially fast until first loss eventbe >> MSS/RTT desirable to quickly ramp up to respectable ratefirst loss event For every successful ACK, send two packets.Transport Layer3-11TCP Slow Start (more)TCP Slow Start (more) When connection Host AHost Bbegins, increase rate exponentially until first loss event:Host ARTTHost Bfirst loss event: double CongWin every RTTd b i ti done by incrementing CongWin for every ACK receivediiil Summary:initial rate is slow but ramps up exponentially fasttimeTransport Layer3-12pyRefinementRef nement After 3 dup ACKs: (AIMD)• 3 dup ACKs indicates t k bl f Philosophy: CongWin is cut in half window then grows li lnetwork capable of delivering some segments• timeout before 3 dup linearly But after timeout event:CongWininstead set to pACKs is “more alarming”CongWininstead set to 1 MSS; window then grows exponentially to a threshold, then grows linearlyTransport Layer3-13linearlyRefinement (more)Q: When should the exponential i ith t increase switch to linear? A: When CongWint t 1/2 f it gets to 1/2 of its value before timeout.Implementation: Variable Threshold At l t Th h ld i At loss event, Threshold is set to 1/2 of CongWin just before loss eventTransport Layer3-14S TCP Cti CtlSummary: TCP Congestion ControlWhen CongWinis below Threshold sender in When CongWinis below Threshold, sender in slow-start phase, window grows exponentially.When CongWinis above Threshold sender is in When CongWinis above Threshold, sender is in congestion-avoidance phase, window grows linearly.When a triple duplicate ACKoccurs ThresholdWhen a triple duplicate ACKoccurs, Thresholdset to CongWin/2 and CongWin set to Threshold. When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS.Transport
View Full Document