15-441 Computer NetworkingLast Question of Mid TermTransport ProtocolsFunctionality SplitWhat Problems Reliable Transport Solution Try to Solve?Mechanisms used in Reliable TransportAutomatic Repeat Request (ARQ) AlgorithmsStop-and-WaitWhat Can Go Wrong?How to Recognize Retransmissions?Stop-and-Wait DisadvantageStop-and-Go Disadvantage (cont’d)How to Keep the Pipe Full?Sliding Window Protocol: SenderExampleSliding Window Protocol: ReceiverSlide 17Sender/Receiver StateSequence NumbersCumulative ACK + Go-Back-NLoss RecoveryGo-Back-N in ActionSelective Ack + Selective RepeatSelective Repeat: Sender, Receiver WindowsSummary of ARQ ProtocolsMany Nuances15-441 Computer NetworkingLecture 16 – Reliable Transport10-24-2006 Lecture 16: Transport Protocols 2Last Question of Mid Term10-24-2006 Lecture 16: Transport Protocols 3Transport 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 payload776655776655TransportTransportIPIPDatalinkDatalinkPhysicalPhysicalTransportTransportIPIPDatalinkDatalinkPhysicalPhysicalIPIProuter2222111110-24-2006 Lecture 16: Transport Protocols 4Functionality Split•Network provides best-effort delivery•End-systems implement many functions•Reliability•In-order delivery•Demultiplexing•Message boundaries•Connection abstraction•Congestion control•…10-24-2006 Lecture 16: Transport Protocols 5What Problems Reliable Transport Solution Try to Solve? •Best effort network layer•Packets can get corrupted •Packets can get lost •Packets can get re-ordered10-24-2006 Lecture 16: Transport Protocols 6Mechanisms used in Reliable Transport •Packets can get corrupted •CRC or Checksum to detect, retransmission to recover •Error correction code to recover•Packets can get lost •Acknowledgement + Timeout to detect, retransmission to recover •Packets can get re-ordered •Sequence number to detect, receiver buffer to re-order10-24-2006 Lecture 16: Transport Protocols 7Automatic Repeat Request (ARQ) Algorithms•Use two basic techniques: •Acknowledgements (ACKs)•Timeouts•Two examples:•Stop-and-Wait•Sliding window10-24-2006 Lecture 16: Transport Protocols 8Stop-and-Wait•Receiver: send an acknowledge (ACK) back to the sender upon receiving a packet (frame)•Sender: excepting first packet, send a packet only upon receiving the ACK for the previous packetTimeSender ReceiverframeframeACKACK10-24-2006 Lecture 16: Transport Protocols 9What Can Go Wrong?Sender ReceiverframeframeACKTimeoutFrame lost resent it on TimeoutSender ReceiverframeframeACKACKTimeoutACK lost resent packet Need a mechanisms todetect duplicate packetSender ReceiverframeframeACKACKTimeoutACK delayed resent packet Need a mechanism to differentiate between ACK for currentand previous packet10-24-2006 Lecture 16: Transport Protocols 10How to Recognize Retransmissions?•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 010-24-2006 Lecture 16: Transport Protocols 11Stop-and-Wait Disadvantage•May lead to inefficient link utilization•Example: assume•One-way propagation = 15 ms•Bandwidth = 100 Mbps•Packet size = 1000 bytes transmit = (8*1000)/108 = 0.08ms•Neglect queue delay Latency = approx. 15 ms; RTT = 30 msPropagation = 15 msBandwidth = 100 Mbps10-24-2006 Lecture 16: Transport Protocols 12Stop-and-Go Disadvantage (cont’d)•Send a message every 30 ms Throughput = (8*1000)/0.03 = 0.2666 Mbps•Thus, the protocol uses less than 0.3% of the link capacity!SenderReceiverframeframeACKACK30 ms30 ms10-24-2006 Lecture 16: Transport Protocols 13How 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?10-24-2006 Lecture 16: Transport Protocols 14Sliding Window Protocol: Sender•Each packet has a sequence number•Assume infinite sequence numbers for simplicity•Sender maintains a window of sequence numbers•SWS (sender window size) – maximum number of packets that can be sent without receiving an ACK•LAR (last ACK received) •LFS (last frame sent)seq. numbersLARLFSAcknowledged packets Packets not acknowledged yet10-24-2006 Lecture 16: Transport Protocols 15Example•Assume SWS = 3Sender Receiverframe 11frame 2frame 32 31ACK 12 31frame 42 3 41ACK 2frame 52 3 4 51Note: usually ACK contains the sequence number of the first packet in sequence expected by receiver10-24-2006 Lecture 16: Transport Protocols 16Sliding Window Protocol: Receiver•Receiver maintains a window of sequence numbers•RWS (receiver window size) – maximum number of out-of-sequence packets that can received•LFR (last frame received) – last frame received in sequence •LAF (last acceptable frame) •LAF – LFR <= RWS10-24-2006 Lecture 16: Transport Protocols 17Sliding Window Protocol: Receiver•Let seqNum be the sequence number of arriving packet•If (seqNum <= LFR) or (seqNum >= LAF)•Discard packet•Else •Accept packet•ACK largest sequence number seqNumToAck, such that all packets with sequence numbers <= seqNumToAck were received seq. numbersLFRLAFPackets in sequence Packets out-of-sequence10-24-2006 Lecture 16: Transport Protocols 18ReceiverReceiverSenderSenderSender/Receiver State… …Sent & Acked Sent Not AckedOK to Send Not Usable… …Max acceptableReceiver window Max ACK received Next seqnumReceived & Acked Acceptable PacketNot UsableSender windowNext expected10-24-2006 Lecture 16: Transport Protocols 19Sequence Numbers•How large do sequence numbers need to be?•Must be able to detect wrap-around•Depends on sender/receiver window size•E.g.•Max seq = 7, send win=recv win=7•If pkts 0..6 are sent succesfully and all acks lost•Receiver expects 7,0..5, sender retransmits old 0..6!!!•Max sequence must be send window + recv window10-24-2006 Lecture 16: Transport Protocols 20Cumulative ACK + Go-Back-N•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 in-order data
View Full Document
Unlocking...