Error Dectection and Loss Recovery TCP and Congestion Control Message to Hong Kong EECS 122 Valentine s Day 2006 Hope this will be our last Valentine s Day apart One extra parity check word can detect error It can also recover from a single loss With more parity check words one can recover from multiple losses Transport Layer 1 Transport Layer 4 Transport Layer 5 Transport Layer 6 Example Fountain Codes HW 2 Ethereal Labs Lecture today Wrap up on reliable data transfer See how principles are applied to TCP Talk about congestion control Transport Layer 2 Forward Erasure Error Correction A Different Approach to RDT TCP Our approach to reliable data delivery is Overview based on ACKs and retransmissions i e feedback Long RTTs long delays and or low throughput An alternative approach is via forward corrections for errors and losses Reliable data transfer Transport Layer Flow control Congestion control 3 1 TCP Overview point to point one sender one receiver reliable in order byte no message boundaries pipelined send receive buffers socket door application writes data application reads data TCP send buffer TCP receive buffer handshaking exchange of control msgs init s sender receiver state before data exchange Retransmissions are triggered by timeout events duplicate acks fast retransmit TimeOut intervals often doubled after a timeout flow controlled socket door bi directional data flow in same connection MSS maximum segment size connection oriented TCP congestion and flow control set window size TCP creates rdt service on top of IP s unreliable service Pipelined segments Cumulative acks TCP uses single retransmission timer full duplex data steam TCP reliable data transfer RFCs 793 1122 1323 2018 2581 sender will not overwhelm receiver segment Transport Layer 32 bits ACK ACK valid PSH push data now generally not used RST SYN FIN connection estab setup teardown commands source port counting by bytes of data not segments dest port sequence number acknowledgement number head not len used U A P R S F checksum Receive window bytes rcvr willing to accept Urg data pnter Options variable length Internet checksum as in UDP application data variable length Transport Layer Seq 4 2 AC K 79 Host B data C ata 43 d CK 79 A Seq host ACKs receipt of echoed C timeout retransmit segment that caused timeout restart timer Ack rcvd If acknowledges previously unacked segments update what is known to be acked start timer if there are outstanding segments Transport Layer 11 TCP Hybrid Go Back N and Selective Repeat Host A User types C data rcvd from app Create segment with seq seq is byte stream number of first data byte in segment start timer if not already running think of timer as for oldest unacked segment expiration interval TimeOutInterval 8 TCP seq s and ACKs Seq s byte stream number of first byte in segment s data ACKs seq of next byte expected from other side cumulative ACK Full duplex ACK s for one direction are piggybacked on data segments in the other direction 10 TCP sender events TCP segment structure URG urgent data generally not used Transport Layer 7 C Cumulative ACK like GBN Out of order segments often buffered at receiver and not discarded but no individual ACK sent host ACKs receipt of C echoes back C Seq 4 3 AC K 80 time simple telnet scenario Transport Layer 9 Transport Layer 12 2 TCP Round Trip Time and Timeout Q how to set TCP timeout value Q how to estimate RTT Setting the timeout SampleRTT measured time from EstimtedRTT plus safety margin segment transmission until ACK receipt ignore retransmissions SampleRTT will vary want estimated RTT smoother average several recent measurements not just current SampleRTT longer than RTT TCP Round Trip Time and Timeout but RTT varies too short premature timeout unnecessary retransmissions too long slow reaction to segment loss large variation in EstimatedRTT larger safety margin first estimate of how much SampleRTT deviates from EstimatedRTT DevRTT 1 DevRTT SampleRTT EstimatedRTT typically 0 25 Then set timeout interval TimeoutInterval EstimatedRTT 4 DevRTT Transport Layer Transport Layer 13 TCP Round Trip Time and Timeout Fast Retransmit EstimatedRTT 1 EstimatedRTT SampleRTT Exponential weighted moving average Time out period often relatively long influence of past sample decreases exponentially fast typical value 0 125 long delay before resending lost packet Sender often sends many segments back toback If segment is lost there will likely be many duplicate ACKs If sender receives 3 ACKs for the same data it supposes that segment after ACKed data was lost fast retransmit resend segment before timer expires Transport Layer 14 17 TCP Flow Control Example RTT estimation flow control RTT gaia cs umass edu to fantasia eurecom fr 350 300 RTT milliseconds Detect lost segments via duplicate ACKs Transport Layer 16 sender won t overflow receiver s buffer by transmitting too much too fast receive side of TCP connection has a receive buffer 250 200 150 100 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 time seconnds SampleRTT app process may be slow at reading from buffer speed matching service matching the send rate to the receiving app s drain rate Estimated RTT Transport Layer 15 Transport Layer 18 3 TCP Flow control how it works Rcvr advertises spare room by including value of RcvWindow in segments Sender limits unACKed data to RcvWindow Suppose TCP receiver discards out of order segments spare room in buffer guarantees receive buffer doesn t overflow RcvWindow RcvBuffer LastByteRcvd LastByteRead Transport Layer 19 4
View Full Document
Unlocking...