15 441 Computer Networking Lecture 19 TCP Performance Overview TCP variants TCP modeling TCP details Lecture 19 03 24 2005 2 TCP Variations Tahoe Reno NewReno Vegas TCP Tahoe distributed with 4 3BSD Unix Original implementation of Van Jacobson s mechanisms VJ paper Includes Slow start Congestion avoidance Fast retransmit Lecture 19 03 24 2005 3 Multiple Losses X X Now what X X Sequence No Retransmission Duplicate Acks Packets Acks Time Lecture 19 03 24 2005 4 Tahoe X X X X Sequence No Packets Acks Time Lecture 19 03 24 2005 5 TCP Reno 1990 All mechanisms in Tahoe Addition of fast recovery Opening up congestion window after fast retransmit Delayed acks Header prediction Implementation designed to improve performance Has common case code inlined With multiple losses Reno typically timeouts because it does not see duplicate acknowledgements Lecture 19 03 24 2005 6 Reno X X X Now what timeout X Sequence No Packets Acks Time Lecture 19 03 24 2005 7 SACK Basic problem is that cumulative acks provide little information Ack for just the packet received What if acks are lost carry cumulative also This technique is not used Bitmask of packets received Selective acknowledgement SACK Implemented as a TCP option Set of received byte ranges max of 4 ranges often max of 3 When to retransmit Still need to deal with reordering wait for out of order by 3pkts Lecture 19 03 24 2005 8 SACK X X X X Sequence No Now what send retransmissions as soon as detected Packets Acks Time Lecture 19 03 24 2005 9 Performance Issues Timeout fast rexmit Need 3 dupacks sacks Not great for small transfers Don t have 3 packets outstanding What are real loss patterns like Lecture 19 03 24 2005 10 How to Change Window When a loss occurs have W packets outstanding New cwnd 0 5 cwnd How to get to new state Lecture 19 03 24 2005 11 Fast 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 loss Lecture 19 03 24 2005 12 Fast Recovery Sent for each dupack after W 2 dupacks arrive Sequence No X Packets Acks Time Lecture 19 03 24 2005 13 Overview TCP variants TCP modeling TCP details Lecture 19 03 24 2005 14 TCP 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 03 24 2005 15 TCP Congestion Control Rule for adjusting W Only W packets may be outstanding If an ACK is received If a packet is lost Source W W 1 W W W 2 Dest Window size Wmax Wmax 2 t Lecture 19 03 24 2005 16 Single TCP Flow Router without buffers Lecture 19 03 24 2005 17 Summary Unbuffered Link W Minimum window for full utilization t The router can t fully utilize the link If the window is too small link is not full If the link is full next window increase causes drop With no buffer it still achieves 75 utilization Lecture 19 03 24 2005 18 TCP Performance In the real world router queues play important role Window is proportional to rate RTT But RTT changes as well the window Window to fill links propagation RTT bottleneck bandwidth If window is larger packets sit in queue on bottleneck link Lecture 19 03 24 2005 19 TCP Performance If we have a large router queue can get 100 utilization But router queues can cause large delays How big does the queue need to be Windows vary from W W 2 Must make sure that link is always full W 2 RTT BW W RTT BW Qsize Therefore Qsize RTT BW Ensures 100 utilization Delay Varies between RTT and 2 RTT Lecture 19 03 24 2005 20 Single TCP Flow Router with large enough buffers for full link utilization Lecture 19 03 24 2005 21 Summary Buffered Link W Minimum window for full utilization Buffer t With sufficient buffering we achieve full link utilization The window is always above the critical threshold Buffer absorbs changes in window size Buffer Size Height of TCP Sawtooth Minimum buffer size needed is 2T C This is the origin of the rule of thumb Lecture 19 03 24 2005 22 TCP Modeling Given the congestion behavior of TCP can we predict what type of performance we should get What are the important factors Loss rate Affects how often window is reduced RTT Affects increase rate and relates BW to window RTO Affects performance during loss recovery MSS Affects increase rate Lecture 19 03 24 2005 23 Overall TCP Behavior Let s concentrate on steady state behavior with no timeouts and perfect loss recovery Packets transferred area under curve Window Time Lecture 19 03 24 2005 24 Transmission Rate What is area under curve W pkts RTT T RTTs A avg window time W T What was bandwidth BW A T W W In packets per RTT Need to convert to bytes per second BW W MSS RTT W 2 Time What is W Depends on loss rate Lecture 19 03 24 2005 25 Simple TCP Model Some additional assumptions Fixed RTT No delayed ACKs In steady state TCP losses packet each time window reaches W packets Window drops to W 2 packets Each RTT window increases by 1 packet W 2 RTT before next loss Lecture 19 03 24 2005 26 Simple Loss Model What was the loss rate Packets transferred W RTT W 2 RTT 3W2 8 1 packet lost loss rate p 8 3W2 8 W 3p BW W MSS RTT W 8 4 3 3p 3 2p BW MSS RTT 2 p 3 Lecture 19 03 24 2005 27 Fairness BW proportional to 1 RTT Do flows sharing a bottleneck get the same bandwidth NO TCP is RTT fair If flows share a bottleneck and have the same RTTs then they get same bandwidth Otherwise in inverse proportion to the RTT Lecture 19 03 24 2005 28 TCP Friendliness What does it mean to be TCP friendly TCP is not going away Any new congestion control must compete with TCP flows Should not clobber TCP flows and grab bulk of link Should also be able to hold its own i e grab its fair share or it will never become popular How is this quantified shown Has evolved into evaluating loss throughput behavior If it shows 1 sqrt p behavior it is ok But is this really true Lecture 19 03 24 2005 29 Overview TCP variants TCP modeling TCP details Lecture 19 03 24 2005 30 Delayed ACKS Problem In request response programs you send separate ACK and Data packets for each transaction Solution Don t ACK data immediately Wait 200ms must be less than …
View Full Document