11TCP: Reliable, In-Order DeliveryEE 122: Intro to Communication NetworksFall 2006 (MW 4-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Sukun is away this week. Dilip will cover hissection and office hours.• Dilip’s office has moved to 751 Soda (alcove).His office hours remain Fri 11-12.• Today is the deadline for requesting discussion /possible regarding of midterm questions. Sendemail to do so.• Project #3 out on Wednesday– Can do individual or in a team of 2 people– First phase due November 16 - no slip days– Exercise good (better) time management3Today’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 terminate conn.• Retransmission to recover from loss– We’ll only look at timeout-based retransmission today• State diagrams as a tool for understandingcomplex protocol operation4TCP Service Model• Reliable, in-order, byte-stream delivery– and with good performance• Challenges - the network can– drop packets Even perhaps a large number– delay packets Even perhaps for many seconds– deliver packets out-of-order Follows from possibility of arbitrary delay– replicate packets 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
View Full Document