115-441 Computer NetworkingLecture 19 – TCP PerformanceOutlineTCP ti id•TCP congestion avoidance• TCP slow start11-01-07Lecture 19: TCP Congestion Control 2• TCP modelingAdditive Increase/Decrease• Both X1and X2increase/ decrease T0T1Fairness LineUser 2’s Allocation x2by the same amount over time• Additive increase improves fairness and additive decrease reduces fairness11-01-07Lecture 19: TCP Congestion Control 3Efficiency LineUser 1’s Allocation x1Muliplicative Increase/Decrease• Both X1and X2increase by theincrease by the same factor over time• Extension from origin – constant fairnessT0T1Fairness LineUser 2’s Allocation x211-01-07Lecture 19: TCP Congestion Control 4Efficiency LineUser 1’s Allocation x12What is the Right Choice?• Constraints limit tAIMDus to AIMD• Improves or keeps fairness constant at each step• AIMD moves x0x1x2Fairness LineUser 2’s Allocation x211-01-07Lecture 19: TCP Congestion Control 5towards optimal pointEfficiency LineUser 1’s Allocation x1TCP Congestion Control• Changes to TCP motivated by ARPANET congestion collapsecongestion collapse• Basic principles• AIMD• Packet conservation•Reaching steady state quickly11-01-07Lecture 19: TCP Congestion Control 6Reaching steady state quickly• ACK clockingAIMD• Distributed, fair and efficient• Packet loss is seen as sign of congestion and results in a ggmultiplicative rate decrease • Factor of 2• TCP periodically probes for available bandwidth by increasing its rate11-01-07Lecture 19: TCP Congestion Control 7TimeRateImplementation Issue• Operating system timers are very coarse – how to pace packets out smoothly?py• 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”and11-01-07Lecture 19: TCP Congestion Control 8The 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)3Congestion Avoidance• If loss occurs when cwnd = W•Network can handle 0.5W~W segmentsNetwork 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 f1MSS11-01-07Lecture 19: TCP Congestion Control 9of 1 MSS• Implements AIMDCongestion Avoidance Sequence PlotSequence No11-01-07Lecture 19: TCP Congestion Control 10TimePacketsAcksCongestion Avoidance BehaviorCongestionWindow11-01-07Lecture 19: TCP Congestion Control 11TimePacket loss+ retransmitGrabbingback BandwidthCutCongestionWindowand RatePacket Conservation• At equilibrium, inject packet into network only when one is removedwhen 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 Ndli i i i i11-01-07Lecture 19: TCP Congestion Control 12•Need to eliminate spurious retransmissions• Accurate RTO estimation• Better loss recovery techniques (e.g. fast retransmit)4TCP Packet Pacing• Congestion window helps to “pace” the transmission of data packetsp• In steady state, a packet is sent when an ack is received• Data transmission remains smooth, once it is smooth• Self-clocking behaviorPPb11-01-07Lecture 19: TCP Congestion Control 13PrArAbReceiverSenderAsHow to Change Window• When a loss occurs have W packets outstanding•New cwnd = 0 5*cwnd•New cwnd = 0.5 cwnd• How to get to new state without losing ack clocking?11-01-07Lecture 19: TCP Congestion Control 14Fast Recovery• Each duplicate ack notifies sender that single packet has cleared networkp• 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 dupacks11-01-07Lecture 19: TCP Congestion Control 15of dupacks• Transmits at original rate after wait• Ack clocking rate is same as before lossFast Recovery Sequence NoSent for each dupack afterW/2 dupacks arriveX11-01-07Lecture 19: TCP Congestion Control 16TimePacketsAcks5OutlineTCP ti id•TCP congestion avoidance• TCP slow start11-01-07Lecture 19: TCP Congestion Control 17• TCP modelingCongestion Avoidance BehaviorCongestionWindow11-01-07Lecture 19: TCP Congestion Control 18TimePacket loss+ retransmitGrabbingback BandwidthCutCongestionWindowand RateReaching Steady State• Doing AIMD is fine in steady state but slow…•How does TCP know what is a good initial rate to•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)11-01-07Lecture 19: TCP Congestion Control 19start)Slow Start Packet Pacing• How do we get this clocking behavior to start?Iitili d 1•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 loss11-01-07Lecture 19: TCP Congestion Control 20cause packet loss6Slow Start ExampleOne RTT0R1One pkt time21R32R12 311-01-07Lecture 19: TCP Congestion Control 21456783R91011121314154 5 6 7Slow Start Sequence Plot...Sequence No11-01-07Lecture 19: TCP Congestion Control 22TimePacketsAcksReturn to Slow Start• If packet is lost we lose our self clocking as well•Need to implement slow-start and congestion•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 avoidance11-01-07Lecture 19: TCP Congestion Control 23TCP Saw Tooth BehaviorCongestionWindowTimeoutsmay stillmay stilloccur11-01-07Lecture 19: TCP Congestion Control 24TimeInitialSlowstartFast Retransmitand RecoverySlowstartto pacepackets7OutlineTCP ti id•TCP congestion avoidance• TCP slow start11-01-07Lecture 19: TCP Congestion Control 25• TCP modelingTCP Performance• Can TCP saturate a link?•Congestion control•Congestion control• Increase utilization
View Full Document
Unlocking...