Transport Control ProtocolTCP OverviewTCP FeaturesSegment FormatSegment Format (cont)Sequence NumbersSequence Number Wrap AroundConnection EstablishmentConnection TerminationState Transition DiagramReliability in TCPSliding Window RevisitedFlow Control in TCPKeeping the Pipe FullMaking TCP More EfficientKarn/Partridge Algorithm for RTOJacobson/ Karels AlgorithmJacobson/ Karels contd.CS 640 1Transport Control ProtocolOutlineTCP objectives revisitedTCP basicsNew algorithms for RTO calculationCS 640 2TCP Overview•TCP is the most widely used Internet protocol–Web, Peer-to-peer, FTP, telnet, …•A two way, reliable, byte stream oriented end-to-end protocol–Includes flow and congestion control•Closely tied to the Internet Protocol (IP)•A focus of intense study for many years–Our goal is to understand the RENO version of TCP•RENO is most widely used TCP today•RFC 2001 (now expired)•RENO mainly specifies mechanisms for dealing with congestionCS 640 3TCP Features•Connection-oriented•Byte-stream–app writes bytes–TCP sends segments–app reads bytes•Reliable data transferApplication processWritebytesTCPSend bufferSegment Segment SegmentTransmit segmentsApplication processReadbytesTCPReceive buffer………•Full duplex•Flow control: keep sender from overrunning receiver•Congestion control: keep sender from overrunning networkCS 640 4Segment FormatOptions (variable)DataChecksumSrcPort DstPortHdrLen0 FlagsUrgPtrAdvertisedWindowSequenceNumAcknowledgment0 41016 31CS 640 5Segment Format (cont)•Each connection identified with 4-tuple:–(SrcPort, SrcIPAddr, DsrPort, DstIPAddr)•Sliding window + flow control–acknowledgment, SequenceNum, AdvertisedWinow•Flags–SYN, FIN, RESET, PUSH, URG, ACK•Checksum is the same as UDP–pseudo header + TCP header + dataSenderData (SequenceNum)Acknowledgment +AdvertisedWindowReceiverCS 640 6Sequence Numbers•32 bit sequence numbers–Wrap around supported•TCP breaks byte stream from application into packets (limited by Max. Segment Size)•Each byte in the data stream is considered•Each packet has a sequence number–Initial number selected at connection time–Subsequent numbers indicate first data byte number in packet•ACK’s indicate next byte expectedCS 640 7Sequence Number Wrap AroundBandwidth Time Until Wrap AroundT1 (1.5 Mbps) 6.4 hoursEthernet (10 Mbps) 57 minutesT3 (45 Mbps) 13 minutesFDDI (100 Mbps) 6 minutesSTS-3 (155 Mbps) 4 minutesSTS-12 (622 Mbps) 55 secondsSTS-24 (1.2 Gbps) 28 seconds• Protect against this by adding a 32-bit timestamp to TCP headerCS 640 8Connection EstablishmentActive participant(client)Passive participant(server)SYN, SequenceNum = xSYN + ACK, SequenceNum = y,ACK, Acknowledgment = y + 1Acknowledgment = x + 1CS 640 9Connection TerminationActive participant(server)Passive participant(client)FIN, SequenceNum = xAcknowledgment = y + 1Acknowledgment = x + 1FIN, SequenceNum= yCS 640 10State Transition DiagramCLOSEDLISTENSYN_RCVD SYN_SENTESTABLISHEDCLOSE_WAITLAST_ACKCLOSINGTIME_WAITFIN_WAIT_2FIN_WAIT_1Passive open CloseSend/SYNSYN/SYN + ACKSYN + ACK/ACKSYN/SYN + ACKACKClose/FINFIN/ACKClose/FINFIN/ACKACK + FIN/ACKTimeout after two segment lifetimesFIN/ACKACKACKACKClose/FINCloseCLOSEDActive open/SYNCS 640 11Reliability in TCP•Checksum used to detect bit level errors•Sequence numbers used to detect sequencing errors–Duplicates are ignored–Reordered packets are reordered (or dropped)–Lost packets are retransmitted•Timeouts used to detect lost packets–Requires RTO calculation–Requires sender to maintain data until it is ACKedCS 640 12Sliding Window Revisited•Sending side–LastByteAcked < = LastByteSent–LastByteSent < = LastByteWritten–buffer bytes between LastByteAcked and LastByteWrittenSending applicationLastByteWrittenTCPLastByteSentLastByteAckedReceiving applicationLastByteReadTCPLastByteRcvdNextByteExpected•Receiving side–LastByteRead < NextByteExpected–NextByteExpected < = LastByteRcvd +1–buffer bytes between NextByteRead and LastByteRcvdCS 640 13Flow Control in TCP•Send buffer size: MaxSendBuffer•Receive buffer size: MaxRcvBuffer•Receiving side–LastByteRcvd - LastByteRead < = MaxRcvBuffer–AdvertisedWindow = MaxRcvBuffer - (LastByteRcvd - LastByteRead)•Sending side–LastByteSent - LastByteAcked < = AdvertisedWindow–EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)–LastByteWritten - LastByteAcked < = MaxSendBuffer–block sender if (LastByteWritten - LastByteAcked) + y > MaxSenderBuffer•Always send ACK in response to arriving data segment•Persist sending one byte seg. when AdvertisedWindow = 0CS 640 14Keeping the Pipe Full•16-bit AdvertisedWindow controls amount of pipelining•Assume RTT of 100ms•Add scaling factor extension to header to enable larger windowsBandwidth Delay x Bandwidth ProductT1 (1.5 Mbps)18KBEthernet (10 Mbps) 122KBT3 (45 Mbps) 549KBFDDI (100 Mbps) 1.2MBOC-3 (155 Mbps) 1.8MBOC-12 (622 Mbps) 7.4MBOC-24 (1.2 Gbps) 14.8MBCS 640 15Making TCP More Efficient•Silly window syndrome–Early implementations send app data as soon as window opened up, even if by a little–Lead to plenty of small sized packets•Fix 1: receiver opens window in MSS granularity•Fix 2: receiver delays acknowledgements–Delay for about 200ms–Coalesces multiple small packets into one responseCS 640 16Karn/Partridge Algorithm for RTO•Two degenerate cases with timeouts and RTT measurements–Solution: Do not sample RTT when retransmitting •After each retransmission, set next RTO to be double the value of the last –Exponential backoff is well known control theory method –Loss is most likely caused by congestion so be carefulSender ReceiverOriginal transmissionACKSampleRTTRetransmissionSender ReceiverOriginal transmissionACKSampleR TTRetransmissionCS 640 17Jacobson/ Karels Algorithm•In late ’80s, Internet was suffering from congestion collapse•New Calculations for average RTT – Jacobson ’88•Variance is not considered when setting timeout value–If variance is small, we could set RTO = EstRTT–If variance is large, we may need to set RTO > 2 x EstRTT•New algorithm calculates both variance and mean for RTT•Diff = sampleRTT - EstRTT•EstRTT = EstRTT + ( d x Diff)•Dev = Dev + d ( |Diff| - Dev)–Initially settings for EstRTT and Dev will be given to you–where d is a factor between 0 and 1–typical value is 0.125CS 640 18Jacobson/ Karels contd.•TimeOut = x EstRTT + x Dev–where
View Full Document
Unlocking...