15-441 Computer NetworkingFunctionality SplitOverviewTransport ProtocolsUDP: User Datagram Protocol [RFC 768]Multiplexing & DemultiplexingSlide 7UDP, cont.UDP ChecksumHigh-Level TCP CharacteristicsTCP HeaderEvolution of TCPTCP Through the 1990sSlide 14Transport vs. Link LayersError RecoveryStop and WaitRecovering from ErrorProblems with Stop and WaitHow to Recognize Resends?How to Keep the Pipe Full?Sliding WindowSender/Receiver StateWindow Sliding – Common CaseLoss RecoveryGo-Back-N in ActionSelective RepeatSelective Repeat: Sender, Receiver WindowsSequence NumbersSlide 30Sequence Number SpaceTCP Flow ControlWindow Flow Control: Send SideSlide 34Window Flow Control: Receive SideTCP PersistPerformance ConsiderationsSlide 38Connection EstablishmentSequence Number SelectionConnection SetupConnection Tear-downTear-down Packet ExchangeSlide 44Detecting Half-open ConnectionsObserved TCP ProblemsSilly Window SyndromeNagel’s AlgorithmWhy is Selecting ISN Important?Time Wait IssuesSlide 51Reliability ChallengesTCP = Go-Back-N VariantRound-trip Time EstimationInitial Round-trip EstimatorJacobson’s Retransmission TimeoutRetransmission AmbiguityKarn’s RTT EstimatorTimestamp ExtensionTimer GranularityDelayed ACKSTCP ACK Generation [RFC 1122, RFC 2581]15-441 Computer NetworkingTransport LayerLecture 14: 10-23-01 2Functionality Split•Network provides best-effort delivery•End-systems implement many functions•Reliability•In-order delivery•Demultiplexing•Message boundaries•Connection abstraction•Congestion control•…Lecture 14: 10-23-01 3Overview•Transport introduction•Error recovery•TCP flow control•TCP connection setup/data transfer•TCP reliabilityLecture 14: 10-23-01 4Transport Protocols•UDP provides just integrity and demux•TCP adds…•Connection-oriented•Reliable•Ordered•Point-to-point•Byte-stream•Full duplex•Flow and congestion controlledLecture 14: 10-23-01 5UDP: 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 segment header•No congestion control: UDP can blast away as fast as desiredLecture 14: 10-23-01 6applicationtransportnetworkMP2applicationtransportnetworkMultiplexing & Demultiplexing•Recall: segment - unit of data exchanged between transport layer entities •Aka TPDU: transport protocol data unitReceiverHtHnDemultiplexing: delivering received segments to correct app layer processessegmentsegmentMapplicationtransportnetworkP1MMMP3P4segmentheaderapplication-layerdataLecture 14: 10-23-01 7Multiplexing & Demultiplexing•Based on sender, receiver port numbers, IP addresses•Source, dest port #s in each segment•Recall: well-known port numbers for specific applicationsGathering data from multiple app processes, enveloping data with header (later used for demultiplexing)Source port # Dest port #32 bitsApplicationdata (message)Other header fieldsTCP/UDP segment formatMultiplexing:Lecture 14: 10-23-01 8UDP, cont.•Often used for streaming multimedia apps•Loss tolerant•Rate sensitive•Other UDP uses (why?):•DNS•SNMP•Reliable transfer over UDP: add reliability at application layer•Application-specific error recover!Source port # Dest port #32 bitsApplicationdata (message)UDP segment formatLengthChecksumLength, inbytes of UDPsegment,includingheaderLecture 14: 10-23-01 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 detected. But maybe errors nonethless? Goal: detect “errors” (e.g., flipped bits) in transmitted segmentLecture 14: 10-23-01 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•Uses options to add information to the header•Change processing at endpoints•Backward compatibility is what makes it TCPLecture 14: 10-23-01 11TCP HeaderSource port Destination portSequence numberAcknowledgementAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataFlags:SYNFINRESETPUSHURGACKLecture 14: 10-23-01 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 75Lecture 14: 10-23-01 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 14: 10-23-01 14Overview•Transport introduction•Error recovery•TCP flow control•TCP connection setup/data transfer•TCP reliabilityLecture 14: 10-23-01 15Transport vs. Link Layers•Logical link vs. physical link•Must establish connection•Variable RTT•May vary within a connection•Reordering•How long can packets live max segment lifetime•Can’t expect endpoints to exactly match link•Buffer space availability•Transmission rate•Don’t directly know transmission rateLecture 14: 10-23-01 16Error Recovery•Two forms of error recovery•Forward Error Correction (FEC)•Automatic Repeat Request (ARQ)•FEC•Use error correcting codes to repair losses•ARQ•Receiver sends acknowledgement (ACK) when it receives packet•Sender waits for ACK and timeouts if it does not arrive within some time periodLecture 14: 10-23-01 17Stop and WaitTimePacketACKTimeout•Simplest ARQ protocol•Send a packet, stop and wait until acknowledgement arrives Sender
View Full Document