Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 2915-441 Computer NetworkingLecture 16 – Transport Protocols2Lecture 16: Transport ProtocolsAnnouncements•Mid-semester grades•Based on project1 + midterm + HW1 + HW2 •42.5% of class•If you got a D+,D, D- or F must meet with Dave or me•Much of class grade remains!•Discussion about the midterm next time•One or two people still haven’t taken it3Lecture 16: Transport ProtocolsOutline•Transport introduction•Error recovery & flow control4Lecture 16: Transport ProtocolsTransport 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 payload765765TransportIPDatalinkPhysicalTransportIPDatalinkPhysicalIProuter2 21 15Lecture 16: Transport ProtocolsFunctionality Split•Network provides best-effort delivery•End-systems implement many functions•Reliability•In-order delivery•Demultiplexing•Message boundaries•Connection abstraction•Congestion control•…6Lecture 16: Transport ProtocolsTransport Protocols•UDP provides just integrity and demux•TCP adds…•Connection-oriented•Reliable•Ordered•Point-to-point•Byte-stream•Full duplex•Flow and congestion controlled7Lecture 16: Transport ProtocolsUDP: 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 desired8Lecture 16: Transport ProtocolsUDP, 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,includingheader9Lecture 16: Transport ProtocolsUDP 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!10Lecture 16: Transport ProtocolsHigh-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 TCP11Lecture 16: Transport ProtocolsTCP HeaderSource port Destination portSequence numberAcknowledgementAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataFlags:SYNFINRESETPUSHURGACK12Lecture 16: Transport ProtocolsEvolution 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 7513Lecture 16: Transport ProtocolsTCP Through the 1990s1993199419961994ECN(Floyd)Explicit CongestionNotification1993TCP Vegas (Brakmo et al)delay-based congestion avoidance1994T/TCP(Braden)TransactionTCP1996SACK TCP(Floyd et al)Selective Acknowledgement1996HoeNewReno startup and loss recovery1996FACK TCP(Mathis et al)extension to SACK14Lecture 16: Transport ProtocolsOutline•Transport introduction•Error recovery & flow control15Lecture 16: Transport ProtocolsStop 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 Receiver16Lecture 16: Transport ProtocolsRecovering from ErrorPacketACKTimeoutPacketACKTimeoutPacketTimeoutPacketACKTimeoutTimePacketACKTimeoutPacketACKTimeoutACK lost Packet lostEarly timeoutDUPLICATEPACKETS!!!17Lecture 16: Transport Protocols•How to recognize a duplicate•Performance•Can only send one packet per round tripProblems with Stop and Wait18Lecture 16: Transport ProtocolsHow 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 #0Pkt 0ACK 0Pkt 0ACK 1Pkt 1ACK 019Lecture 16: Transport ProtocolsHow 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 pipe20Lecture 16: Transport ProtocolsSliding 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 received21Lecture 16: Transport ProtocolsReceiverSenderSender/Receiver State… …Sent & Acked Sent Not AckedOK to Send Not Usable… …Max acceptableReceiver window Max ACK received Next seqnumReceived & Acked Acceptable PacketNot UsableSender
View Full Document
Unlocking...