MIT 6.02 DRAFT Lecture NotesFall 2010 (Last update: November 22, 2010)Comments, questions or bug reports?Please contact [email protected] 20Reliable Data Transport ProtocolsPackets in a best-effort network lead a rough life. They can be lost for any number of rea-sons, including queue overflows at switches because of congestion, repeated collisionsover shared media, routing failures, etc. In addition, packets can arrive out-of-order at thedestination because different packets sent in sequence take different paths or because someswitch en route reorders packets for some reason. They usually experience variable delays,especially whenever they encounter a queue. In some cases, the underlying network mayeven duplicate packets.Many applications, such as Web page downloads, file transfers, and interactive termi-nal sessions would like a reliable, in-order stream of data, receiving exactly one copy ofeach byte in the same order in which it was sent. A reliable transport protocol does the jobof hiding the vagaries of a best-effort network—packet losses, reordered packets, and du-plicate packets—from the application, and provides it the abstraction of a reliable packetstream. We will develop protocols that also provide in-order delivery.A large number of protocols have been developed that various applications use, andthere are several ways to provide a reliable, in-order abstraction. This lecture will notsurvey them all, but will instead discuss two protocols in some detail. The first protocol,called stop-and-wait, will solve the problem in perhaps the simplest possible way thatworks, but do so somewhat inefficiently. The second protocol will augment the first onewith a sliding window to significantly improve performance.All reliable transport protocols use the same powerful ideas: redundancy to cope withlosses and receiver buffering to cope with reordering, and most use adaptive timers. The trickypart is figuring out exactly how to apply redundancy in the form of packet retransmis-sions, in working out exactly when retransmissions should be done, and in achieving goodperformance. This chapter will study these issues, and discuss ways in which a reliabletransport protocol can achieve high throughput.� 20.1 The ProblemThe problem we’re going to solve is relatively easy to state. A sender application wantsto send a stream of packets to a receiver application over a best-effort network, which12 CHAPTER 20. RELIABLE DATA TRANSPORT PROTOCOLScan drop packets arbitrarily, reorder them arbitrarily, delay them arbitrarily, and possiblyeven duplicate packets. The receiver wants the packets in exactly the same order in whichthe sender sent them, and wants exactly one copy of each packet.1Our goal is to devisemechanisms at the sending and receiving nodes to achieve what the receiver wants. Thesemechanisms involve rules between the sender and receiver, which constitute the proto-col. In addition to correctness, we will be interested in calculating the throughput of ourprotocols, and in coming up with ways to maximize it.All mechanisms to recover from losses, whether they are caused by packet drops orcorrupted bits, employ redundancy. We have already looked at using error-correcting codessuch as linear block codes and convolutional codes to mitigate the effect of bit errors. Inprinciple, one could apply such (or similar) coding techniques over packets (rather thanover bits) to recover from packet losses (as opposed to bit corruption). We are, however,interested not just in a scheme to reduce the effective packet loss rate, but to eliminatetheir effects altogether, and recover all lost packets. We are also able to rely on feedbackfrom the receiver that can help the sender determine what to send at any point in time, inorder to achieve that goal. Therefore, we will focus on carefully using retransmissions torecover from packet losses; one may combine retransmissions and error-correcting codesto produce a protocol that can further improve throughput under certain conditions. Ingeneral, experience has shown that if packet losses are not persistent and occur in bursts,and if latencies are not excessively long (i.e., not multiple seconds long), retransmissionsby themselves are enough to recover from losses and achieve good throughput. Mostpractical reliable data transport protocols running over Internet paths today use only re-transmissions on packets (individual links usually use the error correction methods, suchas the ones we studied earlier).We will develop the key ideas in the context of two protocols: stop-and-wait and slid-ing window with a fixed window size. We will use the word “sender” to refer to thesending side of the transport protocol and the word “receiver” to refer to the receivingside. We will use “sender application” and “receiver application” to refer to the processesthat would like to send and receive data in a reliable, in-order manner.� 20.2 Stop-and-Wait ProtocolThe high-level idea is quite simple. The sender attaches a transport-layer header to everypacket (distinct from the network-layer packet header that contains the destination address,hop limit, and header checksum discussed in the previous lectures), which includes aunique identifier for the packet. Ideally, this identifier will never be reused for two dif-ferent packets on the same stream.2The receiver, upon receiving the packet with identifierk, will send an acknowledgment (ACK) to the sender; the header of this ACK contains k, so1The reason for the “exactly one copy” requirement is that the mechanism used to solve the problem willend up retransmitting packets, so duplicates may occur that need to be filtered out. In some networks, it ispossible that some links may end up duplicating packets because of mechanisms they employ to improve thepacket delivery probability or bit-error rate over the link.2In an ideal implementation, such reuse will never occur. In practice, however, a transport protocol mayuse a sequence number field whose width is not large enough and sequence numbers may wrap-around. Inthis case, it is important to ensure that two distinct unacknowledged packets never have the same sequencenumber.SECTION 20.2. STOP-AND-WAIT PROTOCOL 3 1 RTT Sender Receiver Data 1 Data 2 ACK 1 Normal behavior (no losses) ACK 2 Data 3 ACK 3 Data 1 X Data 1 Timeout Retransmit Data 1 X Data 1 S R S R Data loss + retransmission Duplicate packet reception ACK 1 lost Figure 20-1: The