115-441 Computer NetworkingLecture 16 – Transport ProtocolsLecture 16: 03-15-2005 2Announcements• Mid-semester grades• If you got a D or F Æ must meet with Dave or me• 57.5% of class grade still left!• HW 3• Due 3/29• Longer Æ start soon• Project 2• Draft will be posted in the next day or two• Mostly accurateLecture 16: 03-15-2005 3Outline• Transport introduction• Error recovery• TCP flow controlLecture 16: 03-15-2005 4Transport Protocols• Lowest level end-to-end protocol.• Header generated by sender is interpreted only by the destination• Routers view transport header as part of the payload776655776655TransportTransportIPIPDatalinkDatalinkPhysicalPhysicalTransportTransportIPIPDatalinkDatalinkPhysicalPhysicalIPIProuter222211112Lecture 16: 03-15-2005 5Functionality Split• Network provides best-effort delivery• End-systems implement many functions• Reliability• In-order delivery• Demultiplexing• Message boundaries• Connection abstraction• Congestion control• …Lecture 16: 03-15-2005 6Transport Protocols• UDP provides just integrity and demux• TCP adds…• Connection-oriented• Reliable• Ordered• Point-to-point• Byte-stream• Full duplex• Flow and congestion controlledLecture 16: 03-15-2005 7UDP: User Datagram Protocol [RFC 768]• “No frills,” “bare bones”Internet transport protocol• “Best effort” service, UDP segments may be:• Lost• Delivered out of order to app• Connectionless:• No handshaking between UDP sender, receiver• Each UDP segment handled independently of othersWhy is there a UDP?• No connection establishment (which can add delay)• Simple: no connection state at sender, receiver• Small header• No congestion control: UDP can blast away as fast as desiredLecture 16: 03-15-2005 8UDP, cont.• Often used for streaming multimedia apps• Loss tolerant• Rate sensitive• Other UDP uses (why?):• DNS, SNMP• Reliable transfer over UDP• Must be at application layer• Application-specific error recoverySource port # Dest port #32 bitsApplicationdata (message)UDP segment formatLengthChecksumLength, inbytes of UDPsegment,includingheader3Lecture 16: 03-15-2005 9UDP ChecksumSender:• Treat segment contents as sequence of 16-bit integers• Checksum: addition (1’s complement sum) of segment contents• Sender puts checksum value into UDP checksum fieldReceiver:• Compute checksum of received segment• Check if computed checksum equals checksum field value:• NO - error detected• YES - no error detectedBut maybe errors nonethless?Goal: detect “errors” (e.g., flipped bits) in transmitted segment – optional use!Lecture 16: 03-15-2005 10High-Level TCP Characteristics• Protocol implemented entirely at the ends• Fate sharing• Protocol has evolved over time and will continue to do so• Nearly impossible to change the header• Use options to add information to the header• Change processing at endpoints• Backward compatibility is what makes it TCP Lecture 16: 03-15-2005 11TCP HeaderSource port Destination portSequence numberAcknowledgementAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataFlags:SYNFINRESETPUSHURGACKLecture 16: 03-15-2005 12Evolution of TCP1975 1980198519901982TCP & IPRFC 793 & 7911974TCP described byVint Cerf and Bob KahnIn IEEE Trans Comm1983BSD Unix 4.2supports TCP/IP1984Nagel’s algorithmto reduce overheadof small packets;predicts congestion collapse1987Karn’s algorithmto better estimate round-trip time1986Congestion collapseobserved1988Van Jacobson’s algorithmscongestion avoidance and congestion control(most implemented in 4.3BSD Tahoe)19904.3BSD Renofast retransmitdelayed ACK’s1975Three-way handshakeRaymond TomlinsonIn SIGCOMM 754Lecture 16: 03-15-2005 13TCP Through the 1990s1993199419961994ECN(Floyd)Explicit CongestionNotification1993TCP Vegas (Brakmo et al)real congestion avoidance1994T/TCP(Braden)TransactionTCP1996SACK TCP(Floyd et al)Selective Acknowledgement1996HoeImproving TCP startup1996FACK TCP(Mathis et al)extension to SACKLecture 16: 03-15-2005 14Outline• Transport introduction• Error recovery & flow control• TCP flow controlLecture 16: 03-15-2005 15Stop and WaitTimePacketACKTimeout• ARQ• Receiver sends acknowledgement (ACK) when it receives packet• Sender waits for ACK and timeouts if it does not arrive within some time period• Simplest ARQ protocol• Send a packet, stop and wait until ACK arrives Sender ReceiverLecture 16: 03-15-2005 16Recovering from ErrorPacketACKTimeoutPacketACKTimeoutPacketTimeoutPacketACKTimeoutTimePacketACKTimeoutPacketACKTimeoutACK lost Packet lostEarly timeoutDUPLICATEPACKETS!!!5Lecture 16: 03-15-2005 17• How to recognize a duplicate• Performance• Can only send one packet per round tripProblems with Stop and WaitLecture 16: 03-15-2005 18How to Recognize Resends?• Use sequence numbers• both packets and acks• Sequence # in packet is finite Æ How big should it be? • For stop and wait?• One bit – won’t send seq #1 until received ACK for seq #0Pkt0ACK 0Pkt0ACK 1Pkt1ACK 0Lecture 16: 03-15-2005 19How to Keep the Pipe Full?• Send multiple packets without waiting for first to be acked• Number of pkts in flight = window• Reliable, unordered delivery• Several parallel stop & waits• Send new packet after each ack• Sender keeps list of unack’ed packets; resends after timeout• Receiver same as stop & wait• How large a window is needed?• Suppose 10Mbps link, 4ms delay, 500byte pkts•1? 10? 20?• Round trip delay * bandwidth = capacity of pipeLecture 16: 03-15-2005 20Sliding Window• Reliable, ordered delivery• Receiver has to hold onto a packet until all prior packets have arrived• Why might this be difficult for just parallel stop & wait?• Sender must prevent buffer overflow at receiver• Circular buffer at sender and receiver• Packets in transit ≤ buffer size • Advance when sender and receiver agree packets at beginning have been received6Lecture 16: 03-15-2005 21ReceiverReceiverSenderSenderSender/Receiver State……Sent & Acked Sent Not AckedOK to Send Not Usable……Max acceptableReceiver window Max ACK received Next seqnumReceived & Acked Acceptable PacketNot UsableSender windowNext expectedLecture 16: 03-15-2005 22Window Sliding – Common Case• On reception of new ACK (i.e. ACK for something that was not acked earlier)• Increase sequence of max ACK received• Send next packet• On reception of new
View Full Document
Unlocking...