11TCP: Reliable, In-Order DeliveryEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Project #1, phase 2 due next Monday @ 11PM• No lecture next Wednesday, Oct 31• Regular office hours next Friday– But not Wednesday– Available via appointment as usual, send email• In case you’re interested, I’ll be giving a talk nextweek, Experiences With Countering InternetAttacks– 1-2PM in the Wozniak lounge (Soda)3Today’s Lecture• How does TCP achieve correct operation?• Reliability in the face of IP’s meager “best effort”service• 3-way handshake to establish connections• 3-way or 4-way handshake to terminateconnections• Retransmission to recover from loss– We’ll only look at timeout-based retransmission today4TCP Service Model• Reliable, in-order, byte-stream delivery– and with good performance• Challenges - the network can– drop packetso Even perhaps a large number– delay packetso Even perhaps for many seconds– deliver packets out-of-ordero Follows from possibility of arbitrary delay– replicate packetso Weird, but it does sometimes happen– corrupt packets– (What’s missing?)5TCP Support for Reliable Delivery• Checksum– Used to detect corrupted data at the receiver– …leading the receiver to drop the packet• Sequence numbers– Used to detect missing data– ... and for putting the data back in order• Retransmission– Sender retransmits lost or corrupted data– Timeout based on estimates of round-trip time– Fast retransmit algorithm for rapid retransmission6TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)Data27TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataThese shouldbe familiar8TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataStartingsequencenumber (byteoffset) of datacarried in thissegment9TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataAcknowledgmentgives seq # justbeyond highestseq. received inorder.If sender sendsN in-order bytesstarting at seq Sthen ack for it willbe S+N.10TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataNumber of 4-bytewords in TCPheader;5 = no options11TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)Data“Must Be Zero”6 bits reserved12TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataWe will get tothese shortly313TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataBuffer spaceavailable forreceiving data.Used for TCP’ssliding window.Interpreted asoffset beyondAcknowledgmentfield’s value.14TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataUsed with URGflag to indicateurgent data (notdiscussed further)15TCP “Stream of Bytes” ServiceByte 0Byte 1Byte 2Byte 3Byte 0Byte 1Byte 2Byte 3Host AHost BByte 80Byte 8016… Provided Using TCP “Segments”Byte 0Byte 1Byte 2Byte 3Byte 0Byte 1Byte 2Byte 3Host AHost BByte 80TCP DataTCP DataByte 80Segment sent when:1. Segment full (Max Segment Size),2. Not full, but times out, or3. “Pushed” by application.17TCP Segment• IP packet– No bigger than Maximum Transmission Unit (MTU)– E.g., up to 1,500 bytes on an Ethernet• TCP packet– IP packet with a TCP header and data inside– TCP header ≥ 20 bytes long• TCP segment– No more than Maximum Segment Size (MSS) bytes– E.g., up to 1460 consecutive bytes from the streamIP HdrIP DataTCP HdrTCP Data (segment)18Sequence NumbersHost AHost BTCP DataTCP DataTCP HDRTCP HDRISN (initial sequence number)Sequencenumber = 1stbyteACK sequencenumber = nextexpected byte419Initial Sequence Number (ISN)• Sequence number for the very first byte– E.g., Why not just use ISN = 0?• Practical issue– IP addresses and port #s uniquely identify a connection– Eventually, though, these port #s do get used again– … ∃ a chance an old packet is still in flight– … and might be associated with new connection• ∴ TCP requires (RFC793) changing ISN over time– Set from 32-bit clock that ticks every 4 microseconds– … only wraps around once every 4.55 hours• To establish a connection, hosts exchange ISNs20Connection Establishment:TCP’s Three-Way Handshake21Establishing a TCP Connection• Three-way handshake to establish connection– Host A sends a SYN (open; “synchronize sequencenumbers”) to host B– Host B returns a SYN acknowledgment (SYN ACK)– Host A sends an ACK to acknowledge the SYN ACKSYNSYN ACKACKABDataDataEach host tellsits ISN to theother host.22TCP HeaderSource port Destination portSequence numberAcknowledgmentAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataFlags:SYNACKFINRSTPSHURGSee /usr/include/netinet/tcp.h on Unix Systems23Step 1: A’s Initial SYN PacketA’s port B’s portA’s Initial Sequence Number(Irrelevant since ACK not set)Advertised window5=20BFlags0Checksum Urgent pointerOptions (variable)Flags:SYNACKFINRSTPSHURGA tells B it wants to open a connection…24Step 2: B’s SYN-ACK PacketB’s port A’s portB’s Initial Sequence NumberACK = A’s ISN plus 1Advertised window20B0Checksum Urgent pointerOptions (variable)Flags:SYNACKFINRSTPSHURGB tells A it accepts, and is ready to hear the next byte…… upon receiving this packet, A can start sending dataFlags525Step 3: A’s ACK of the SYN-ACKA’s port B’s portB’s ISN plus 1Advertised window20BFlags0Checksum Urgent pointerOptions (variable)Flags:SYNACKFINRSTPSHURGA tells B it’s likewise okay to start sendingA’s Initial Sequence Number… upon receiving this packet, B can start sending data26Timing Diagram: 3-Way HandshakingClient
View Full Document