1Transport Layer1TCP and Congestion ControlEECS 122Valentine’s Day, 2006Transport Layer2 HW 2: Ethereal LabsLecture today:Wrap up on reliable data transfer.See how principles are applied to TCPTalk about congestion control.Transport Layer3Forward Erasure/Error Correction:A Different Approach to RDT Our approach to reliable data delivery is 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.Transport Layer4Error Dectection and Loss RecoveryMessage to Hong Kong: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 Layer5Example: Fountain CodesTransport Layer6TCP Overview Reliable data transfer Flow control Congestion control2Transport Layer7TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581 full duplex data: bi-directional data flow in same connection MSS: maximum segment size connection-oriented: handshaking (exchange of control msgs) init’ssender, receiver state before data exchange flow controlled: sender will not overwhelm receiver point-to-point: one sender, one receiver reliable, in-order byte steam: no “message boundaries” pipelined: TCP congestion and flow control set window sizesend & receive bufferssocketdoorTCPsend bufferTCPreceive buffersocketdoorsegmentapplicationwrites dataapplicationreads dataTransport Layer8TCP segment structuresource port #dest port #32 bitsapplicationdata (variable length)sequence numberacknowledgement numberReceive windowUrg data pnterchecksumFSRPAUheadlennotusedOptions (variable length)URG: urgent data (generally not used)ACK: ACK #validPSH: push data now(generally not used)RST, SYN, FIN:connection estab(setup, teardowncommands)# bytes rcvr willingto acceptcountingby bytes of data(not segments!)Internetchecksum(as in UDP)Transport Layer9TCP seq. #’s and ACKsSeq. #’s: byte stream “number” of first byte in segment’s dataACKs: seq # of next byte expected from other side cumulative ACKFull-duplex:ACK’s for one direction are piggybacked on data segments in the other directionHost AHost BSeq=42, ACK=79, data = ‘C’Seq=79, ACK=43, data = ‘C’Seq=43, ACK=80Usertypes‘C’host ACKsreceipt of echoed‘C’host ACKsreceipt of‘C’, echoesback ‘C’timesimple telnet scenarioTransport Layer10TCP reliable data transfer TCP creates rdtservice on top of IP’s unreliable service Pipelined segments Cumulative acks TCP uses single retransmission timer Retransmissions are triggered by: timeout events duplicate acks (fast retransmit) TimeOut intervals often doubled after a timeout.Transport Layer11TCP sender events: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: TimeOutIntervaltimeout: retransmit segment that caused timeout restart timerAck rcvd: If acknowledges previously unackedsegments update what is known to be acked start timer if there are outstanding segmentsTransport Layer12TCP= Hybrid Go-Back-N and Selective Repeat Cumulative ACK (like GBN) Out-of-order segments often buffered at receiver and not discarded (but no individual ACK sent)3Transport Layer13TCP Round Trip Time and TimeoutQ: how to set TCP timeout value? longer than RTT but RTT varies too short: premature timeout unnecessary retransmissions too long: slow reaction to segment lossQ: how to estimate RTT? SampleRTT: measured time from segment transmission until ACK receipt ignore retransmissions SampleRTT will vary, want estimated RTT “smoother” average several recent measurements, not just current SampleRTTTransport Layer14TCP Round Trip Time and TimeoutEstimatedRTT = (1- αααα)*EstimatedRTT + αααα*SampleRTT Exponential weighted moving average influence of past sample decreases exponentially fast typical value: αααα = 0.125Transport Layer15Example RTT estimation:RTT: gaia.cs.umass.edu to fantasia.eurecom.fr1001502002503003501 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106time (seconnds)RTT (milliseconds)SampleRTT Estimated RTTTransport Layer16TCP Round Trip Time and TimeoutSetting the timeout EstimtedRTT plus “safety margin” large variation in EstimatedRTT -> larger safety margin first estimate of how much SampleRTT deviates from EstimatedRTT: TimeoutInterval = EstimatedRTT + 4*DevRTTDevRTT = (1-ββββ)*DevRTT +ββββ*|SampleRTT-EstimatedRTT|(typically, ββββ = 0.25)Then set timeout interval:Transport Layer17Fast Retransmit Time-out period often relatively long: long delay before resending lost packet Detect lost segments via duplicate ACKs. Sender often sends many segments back-to-back 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 ACKeddata was lost: fast retransmit: resend segment before timer expiresTransport Layer18TCP Flow Control receive side of TCP connection has a receive buffer: speed-matching service: matching the send rate to the receiving app’s drain rate app process may be slow at reading from buffersender won’t overflowreceiver’s buffer bytransmitting too much,too fastflow control4Transport Layer19TCP Flow control: how it works(Suppose TCP receiver discards out-of-order segments) spare room in buffer= RcvWindow= RcvBuffer-[LastByteRcvd -LastByteRead] Rcvr advertises spare room by including value of RcvWindow in segments Sender limits unACKeddata to RcvWindow guarantees receive buffer doesn’t
View Full Document