Advanced Computer Networks TCPTCP: OverviewTCP segment structureTCP services/componentsTCP seq. #’s and ACKsTCP Round Trip Time and TimeoutAdaptive Retransmission (Original Algorithm)Karn/Partridge AlgorithmJacobson/ Karels AlgorithmTCP reliable data transfer (rdt)TCP sender events:TCP sender (simplified)TCP: transmission scenariosTCP transmission scenarios (more)TCP ACK generation [RFC 1122, RFC 2581]Fast RetransmitFast retransmit algorithm:TCP Flow ControlSlide 19TCP Flow control: how it worksTCP Flow controlTCP Connection ManagementTCP Connection Management (cont.)Slide 24TCP Connection Management (cont)Protection Against Wrap AroundKeeping the Pipe FullTCP ExtensionsAdvanced Computer NetworksTCPTCP: OverviewEnd-to-end issues for providing end-to-end reliable and ordered data transferLogical connection between two remote hostsRTT is not fixed, even during a connectionPacket re-ordering is an issue•MSL: Maximum Segment LifetimeResource discovery •Available bandwidth•Buffer spaceCongestion issues in the networkTCP 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)TCP services/componentsReliabilitySequence numbers and ACKsTime out mechanismFlow controlConnection managementCongestion controlTCP seq. #’s and ACKsSeq. #’s:byte stream “number” of first byte in segment’s dataACKs:seq # of next byte expected from other sidecumulative ACKHost AHost BSeq=42, ACK=79, data = ‘ABC’Seq=79, ACK=45, data = ‘ABC’Seq=45, ACK=82Usertypes‘ABC’host ACKsreceipt of echoed‘ABC’timesimple telnet scenarioACKs are piggybackedhost ACKsreceipt of‘ABC’, echoesback ‘ABC’TCP Round Trip Time and TimeoutQ: how to set TCP timeout value?longer than RTTbut RTT variestoo short: premature timeoutunnecessary retransmissionstoo long: slow reaction to segment lossQ: how to estimate RTT?SampleRTT: measured time from segment transmission until ACK receiptignore retransmissions(Karn/Partridge algr)SampleRTT will vary, want estimated RTT “smoother”average several recent measurements, not just current SampleRTTAdaptive Retransmission(Original Algorithm)Measure SampleRTT for each segment/ ACK pairCompute weighted average of RTTEstRTT = EstRTT + x SampleRTTSet timeout based on EstRTTTimeOut = 2 x EstRTTKarn/Partridge AlgorithmDo not sample RTT when retransmitting Double timeout after each retransmission Sender ReceiverOriginal transmissionACKSampleRTTRetransmissionSender ReceiverOriginal transmissionACKSampleR TTRetransmissionJacobson/ Karels AlgorithmConsider variance when setting timeout valueNew Calculations for average RTTDiff = SampleRTT - EstRTTEstRTT = EstRTT + ( x Diff)Dev = Dev + ( |Diff| - Dev)where is a factor between 0 and 1TimeOut = x EstRTT + x Devwhere = 1 and = 4Notesaccurate timeout mechanism important to congestion control (later)TCP reliable data transfer (rdt)TCP creates rdt service on top of IP’s unreliable serviceCumulative acksTCP uses single retransmission timerRetransmissions are triggered by:timeout eventsduplicate acksInitially consider simplified TCP sender:ignore duplicate acksignore flow control, congestion controlTCP sender events:data rcvd from app:Create segment with seq #seq # is byte-stream number of first data byte in segmentstart timer if not already running (think of timer as for oldest unacked segment)expiration interval: TimeOutInterval timeout:retransmit segment that caused timeoutrestart timer Ack rcvd:If acknowledges previously unacked segmentsupdate what is known to be ackedstart timer if there are outstanding segmentsTCP sender(simplified) NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) { switch(event) event: data received from application above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer pass segment to IP NextSeqNum = NextSeqNum + length(data) event: timer timeout retransmit not-yet-acknowledged segment with smallest sequence number start timer event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } } /* end of loop forever */ Comment:• SendBase-1: last cumulatively ack’ed byteExample:• SendBase-1 = 71;y= 73, so the rcvrwants 73+ ;y > SendBase, sothat new data is ackedTCP: transmission scenariosHost ASeq=100, 20 bytes dataACK=100timepremature timeoutHost BSeq=92, 8 bytes dataACK=120Seq=92, 8 bytes dataSeq=92 timeoutACK=120Host ASeq=92, 8 bytes dataACK=100losstimeoutlost ACK scenarioHost BXSeq=92, 8 bytes dataACK=100timeSeq=92 timeoutSendBase= 100SendBase= 120SendBase= 120Sendbase= 100TCP transmission scenarios (more)Host ASeq=92, 8 bytes dataACK=100losstimeoutCumulative ACK scenarioHost BXSeq=100, 20 bytes dataACK=120timeSendBase= 120TCP ACK generation [RFC 1122, RFC 2581]Event at ReceiverArrival of in-order segment withexpected seq #. All data up toexpected seq # already ACKedArrival of in-order segment withexpected seq #. One other segment has ACK pendingArrival of out-of-order segmenthigher-than-expect seq. # .Gap detectedArrival of segment that partially or completely fills gapTCP Receiver actionDelayed ACK. Wait up to 500msfor next segment. If no next segment,send ACKImmediately send single cumulative ACK, ACKing both in-order segments Immediately send duplicate ACK, indicating seq. # of next expected byteImmediate send ACK, provided thatsegment starts at lower end of gapFast RetransmitTime-out period often relatively long:long delay before resending lost packetDetect lost segments via duplicate ACKs.Sender often sends many segments back-to-backIf segment is lost, there will likely be many
View Full Document