15-441 Computer NetworkingLecture 19 – TCP PerformanceLecture 19: TCP Congestion Control 2Outline• TCP congestion avoidance• TCP slow start• TCP modeling•Both X1 and X2 increase/ decrease by the same amount over time• Additive increase improves fairness and additive decrease reduces fairnessLecture 19: TCP Congestion Control 3Additive Increase/DecreaseT0T1Efficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2Lecture 19: TCP Congestion Control 4Muliplicative Increase/Decrease•Both X1 and X2 increase by the same factor over time• Extension from origin – constant fairnessT0T1Efficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2Lecture 19: TCP Congestion Control 5What is the Right Choice?• Constraints limit us to AIMD• Improves or keeps fairness constant at each step• AIMD moves towards optimal pointx0x1x2Efficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2Lecture 19: TCP Congestion Control 6TCP Congestion Control• Changes to TCP motivated by ARPANET congestion collapse• Basic principles• AIMD• Packet conservation• Reaching steady state quickly• ACK clockingLecture 19: TCP Congestion Control 7AIMD• Distributed, fair and efficient• Packet loss is seen as sign of congestion and results in a multiplicative rate decrease • Factor of 2• TCP periodically probes for available bandwidth by increasing its rateTimeRateLecture 19: TCP Congestion Control 8Implementation Issue• Operating system timers are very coarse – how to pace packets out smoothly?• Implemented using a congestion window that limits how much data can be in the network.• TCP also keeps track of how much data is in transit• Data can only be sent when the amount of outstanding data is less than the congestion window.• The amount of outstanding data is increased on a “send” and decreased on “ack”• (last sent – last acked) < congestion window• Window limited by both congestion and buffering• Sender’s maximum window = Min (advertised window, cwnd)Lecture 19: TCP Congestion Control 9Congestion Avoidance• If loss occurs when cwnd = W• Network can handle 0.5W ~ W segments• Set cwnd to 0.5W (multiplicative decrease)• Upon receiving ACK• Increase cwnd by (1 packet)/cwnd•What is 1 packet? ! 1 MSS worth of bytes•After cwnd packets have passed by ! approximately increase of 1 MSS• Implements AIMDLecture 19: TCP Congestion Control 10Congestion Avoidance Sequence PlotTimeSequence NoPacketsAcksLecture 19: TCP Congestion Control 11Congestion Avoidance BehaviorTimeCongestionWindowPacket loss+ retransmitGrabbingback BandwidthCutCongestionWindowand RateLecture 19: TCP Congestion Control 12Packet Conservation• At equilibrium, inject packet into network only when one is removed• Sliding window and not rate controlled•But still need to avoid sending burst of packets ! would overflow links• Need to carefully pace out packets• Helps provide stability • Need to eliminate spurious retransmissions• Accurate RTO estimation• Better loss recovery techniques (e.g. fast retransmit)Lecture 19: TCP Congestion Control 13TCP Packet Pacing• Congestion window helps to “pace” the transmission of data packets• In steady state, a packet is sent when an ack is received• Data transmission remains smooth, once it is smooth• Self-clocking behaviorPrPbArAbReceiverSenderAsLecture 19: TCP Congestion Control 14How to Change Window• When a loss occurs have W packets outstanding• New cwnd = 0.5 * cwnd• How to get to new state without losing ack clocking?Lecture 19: TCP Congestion Control 15Fast Recovery• Each duplicate ack notifies sender that single packet has cleared network• When < cwnd packets are outstanding• Allow new packets out with each new duplicate acknowledgement• Behavior• Sender is idle for some time – waiting for ! cwnd worth of dupacks• Transmits at original rate after wait• Ack clocking rate is same as before lossLecture 19: TCP Congestion Control 16Fast Recovery TimeSequence NoSent for each dupack afterW/2 dupacks arriveXPacketsAcksLecture 19: TCP Congestion Control 17Outline• TCP congestion avoidance• TCP slow start• TCP modelingLecture 19: TCP Congestion Control 18Congestion Avoidance BehaviorTimeCongestionWindowPacket loss+ retransmitGrabbingback BandwidthCutCongestionWindowand RateLecture 19: TCP Congestion Control 19Reaching Steady State• Doing AIMD is fine in steady state but slow…• How does TCP know what is a good initial rate to start with?• Should work both for a CDPD (10s of Kbps or less) and for supercomputer links (10 Gbps and growing)• Quick initial phase to help get up to speed (slow start)Lecture 19: TCP Congestion Control 20Slow Start Packet Pacing• How do we get this clocking behavior to start?• Initialize cwnd = 1• Upon receipt of every ack, cwnd = cwnd + 1• Implications• Window actually increases to W in RTT * log2(W)• Can overshoot window and cause packet lossLecture 19: TCP Congestion Control 21Slow Start Example1One RTTOne pkt time0R21R342R56783R910111213141512 34 5 6 7Lecture 19: TCP Congestion Control 22Slow Start Sequence PlotTimeSequence No...PacketsAcksLecture 19: TCP Congestion Control 23Return to Slow Start• If packet is lost we lose our self clocking as well• Need to implement slow-start and congestion avoidance together• When retransmission occurs set ssthresh to 0.5w• If cwnd < ssthresh, use slow start• Else use congestion avoidanceLecture 19: TCP Congestion Control 24TCP Saw Tooth BehaviorTimeCongestionWindowInitialSlowstartFast Retransmitand RecoverySlowstartto pacepacketsTimeoutsmay stilloccurLecture 19: TCP Congestion Control 25Outline• TCP congestion avoidance• TCP slow start• TCP modelingLecture 19: TCP Congestion Control 26TCP Performance• Can TCP saturate a link?• Congestion control• Increase utilization until… link becomes congested• React by decreasing window by 50%• Window is proportional to rate * RTT• Doesn’t this mean that the network oscillates between 50 and 100% utilization?• Average utilization = 75%??• No…this is *not* right!Lecture 19: TCP Congestion Control 27TCP Congestion ControlOnly ! packets may be outstandingRule for adjusting !• If an ACK is received: W " W+1/W• If a packet is lost: W " W/2Source DesttWindow sizeLecture 19: TCP Congestion Control 28Single TCP FlowRouter without buffersLecture 19: TCP Congestion Control
View Full Document
Unlocking...