Building a Reliable Data Transfer Protocol

Building a Reliable Data Transfer Protocol

We now consider a series of protocols, each one becoming more complicated, arriving at a flawless, reliable data transfer protocol.

Reliable Data Transfer over a Perfectly Reliable Channel: rdt1.0


We first examine the simplest case, in which the underlying channel is completely reliable. The protocol itself, which we'll call rdt1.0, is trivial. The finite-state machine (FSM) definitions for the rdt1.0 sender and receiver are shown in Figure 1. The FSM in Figure 1(a) defines the operation of the sender, while the FSM in Figure 1(b) defines the operation of the receiver. It is important to note that there are separate FSMs for the sender and for the receiver. The sender and receiver FSMs in Figure 1 each have just one state. The arrows in the FSM description indicate the transition of the protocol from one state to another. (Since each FSM in Figure 1 has just one state, a transition is necessarily from the one state back to itself; we'll see more complicated state diagrams shortly). The event causing the transition is shown above the horizontal line labeling the transition, and

A protocol for a completely reliable channel

the actions taken when the event takes place are shown below the horizontal line. When no action is taken on an event, or no event takes place and an action is taken, well use the symbol Λ below or above the horizontal, respectively, to clearly denote the lack of an action or event. The initial state of the FSM is indicated by the dashed arrow. Although the FSMs in Figure 1 have but one state, the FSMs we will see shortly have several states, so it will be important to identify the initial state of each FSM.

The sending side of rdt simply accepts data from the upper layer via the rdt_send (data) event, creates a packet containing the data (via the action make_pkt (data)) and sends the packet into the channel. In practice, the rdt_send (data) event would result from a procedure call (for example, to rdt_send ( )) by the upper_layer application.

On the receiving side, rdt receives a packet from the underlying channel via the rdt_rcv (packet event, removes the data from the packet (via the action extract (packet, data)) and passes the data up to the upper layer (via the action deliver_data (data)). In practice, the rdt_rcv (packet) event would result from a procedure call (for example, to rdt_rcv ( )) from the lower-layer protocol.

In this simple protocol, there is no difference between a unit of data and a packet. Also, all packet flow is from the sender to receiver; with a perfectly reliable channel there is no need for the receiver side to provide any feedback to the sender since nothing can go wrong. Note that we have also supposed that the receiver is able to receive data as fast as the sender happens to send data. Therefore, there is no need for the receiver to ask the sender to slow down.

Reliable Data Transfer over a Channel with Bit Errors: rdt2.0


A more practical model of the underlying channel is one in which bits in a packet may be corrupted. Such bit errors normally take place in the physical components of a network as a packet is transmitted, propagates, or is buffered. We'll continue to assume for the moment that all transmitted packets are received (although their bits may be corrupted) in the order in which they were sent.

Before developing a protocol for reliably communicating over such a channel, first look at how people might deal with such a situation.  Consider how you yourself might dictate a long message over the phone. In a typical scenario, the message taker might say "Ok" after each sentence has been heard, understood, and recorded. If the message taker hears a grabled sentence, you're asked to repeat the garbled sentence. This message-dictation protocol uses both positive acknowledgments ("OK") and negative acknowledgments ("Please repeat that"). These control messages allow the receiver to let the sender know what has been received correctly, and what has been received in error and thus requires repeating. In a computer network setting, reliable data transfer protocols based on such retransmission are known as ARQ (Automatic Repeat reQuest) protocols.

Basically, three additional protocol capabilities are required in ARQ protocols to handle the presence of bit errors: 

  • ●  Error detection. First, a mechanism is required to allow the receiver to detect when bit errors have occurred. Recall from the previous section that UDP uses the Internet checksum field for exactly this purpose. In "The Link Layer and Local Area Networks" we'll study error-detection and -correction techniques in greater detail; these techniques allow the receiver to detect and possibly correct packet bit errors. For now, we need only know that these techniques require that extra bits (beyond the bits of original data to be transferred) be sent from the sender to the receiver; these bits will be gathered into the packet checksum field of the rdt2.0 data packet.


  • ●  Receiver feedback. Since the sender and receiver are usually executing on different end systems, maybe separated by thousands of miles, the only way for the sender to learn of the receiver's view of the world (in this case, whether or not a packet was received correctly) is for the receiver to provide explicit feedback to the sender. The positive (ACK) and negative (NAK) acknowledgment replies in the message-dictation scenario are examples of such feedback. Our rdt2.0 protocol will likewise send ACK and NAK packets back from the receiver to the sender. In principle, these packets need only be one bit long; for instance, a 0 value could indicate a NAK and a value of 1 could indicate an ACK.


  • ●  Retransmission. A packet that is received in error at the receiver will be retransmitted by the sender.

Figure 2 shows the FSM representation of rdt2.0, a data transfer protocol employing error detection, positive acknowledgments, and negative acknowledgments. The send side of rdt2.0 has two states. In the leftmost state, the send-side protocol is waiting for data to be passed down from the upper layer. When the rdt_send (data) event occurs, the sender will create a packet (sndpkt) containing the data to be sent, along with a packet checksum (for instance, as discussed in "UDP Segment Structure" for the case of a UDP segment), and then send the packet via the udt_send (sndpkt) operation. In the rightmost state, the sender protocol is waiting for an ACK or a NAK packet from the receiver. If an ACK packet is received (the notation rdt_rcv (rcvpkt) && isACK (rcvpkt) in Figure 2 corresponds to this event), the sender knows that the most recently transmitted packet has been received correctly and thus the protocol returns to the state of waiting for data from the upper layer. If a NAK is received, the protocol retransmits the last packet and waits for an ACK or NAK to be returned by the receiver in response to the retransmitted data packet. It is important to note that when the sender is in the wait-for-ACK-or-NAK state, it cannot get more data from the upper layer; that is, the rdt_send ( ) event cannot occur; that will happen only after the sender receives an ACK and leaves this state. In this way, the sender will not send a new piece of data until it is sure that the receiver has

A protocol for a channel with bit errors

correctly received the current packet. Because of this behavior, protocol such as rdt2.0 are known as stop-and-wait protocols.

The receiver-side FSM for rdt2.0 still has a single state. On packet arrival, the receiver replies with either an ACK or a NAK, depending on whether or not the received packet is corrupted. In Figure 2, the notation rdt_rcv (rcvpkt) && corrupt (rcvpkt) corresponds to the event in which a packet is received and is found to be in error.

Protocol rdt2.0 may look as if it works but, unfortunately, it has a fatal flaw. Particularly, we haven't accounted for the possibility that the ACK or NAK packet could be corrupted! (Before proceeding on, you should think about how this problem may be fixed). Unfortunately, our slight oversight is not as innocuous as it may seem. Minimally, we will need to add checksum bits to ACK/NAK packets in order to detect such errors. The more difficult question is how the protocol should recover from errors in ACK or NAK packets. The difficulty here is that if an ACK or NAK is corrupted, the sender has no way of knowing whether or not the receiver has correctly received the last piece of transmitted data.

Consider three possibilities for handling corrupted ACKs or NAKs:

  • ●  For the first possibility, consider what a human might do in the message-dictation scenario. If the speaker didn't understand the "OK" or  "Please repeat that" reply from the receiver, the speaker would probably ask, "What did you say?" (thus introducing a new type of sender-to-receiver packet to our protocol). The speaker would then repeat the reply. But what if the speaker's "What did you say?" is corrupted?  The receiver, having no idea whether the garbled sentence was part of the dictation or a quest to repeat the last reply, would probably then respond with "What did you say?" And then, of course, that response might be garbled. Clearly, we're heading down a difficult path.


  • ●  A second alternative is to add enough checksum bits to allow the sender not only to detect, but also to recover from, bit errors. This solves the immediate problem for a channel that can corrupt packets but not lose them.


  • ●  A third approach is for the sender simply to resend the current data packet when it receives a garbled ACK or NAK packet. This approach, however, introduces duplicate packets into the sender-to-receiver channel. The fundamental difficulty with duplicate packets is that the receiver doesn't know whether the ACK or NAK it last sent was received correctly at the sender. Thus, it cannot know a priori whether an arriving packet contains new data or is a retransmission.

A simple solution to this new problem (and one adopted in almost all existing data transfer protocols, including TCP) is to add a new field to the data packet and have the sender number its data packets by putting a sequence number into this field. The receiver then need only check this sequence number to determine whether or not the received packet is a retransmission. For this simple case of a stop-and-wait protocol, a 1-bit sequence number will be sufficient, since it will allow the receiver to know whether the sender is resending the previously transmitted packet (the sequence number of the received packet has the same sequence number as the most recently received packet) or a new packet (the sequence number changes, moving "forward" in modulo-2 arithmetic). Since we are currently assuming a channel that does not lose packets, ACK and NAK packets do not themselves need to indicate the sequence number of the packet they are acknowledging. The sender knows that a received ACK or NAK packet (whether garbled or not) was generated in response to its most recently transmitted data packet.

Figures 3 and 4 show the FSM description for rdt2.1, our fixed version of rdt2.0. The rdt2.1 sender and receiver FSMs each now have twice as many states as before. This is because the protocol state must now reflect whether the packet currently being sent (by the sender) or expected (at the receiver) should have a sequence number of 0 or 1. Note that the actions in those states where a 0-numbered packet is being sent or expected are mirror images of those where a 1-numbered packet is being sent or expected; the only differences have to do with the handling of the sequence number.

Protocol rdt2.1 uses both positive and negative acknowledgments from the receiver to the sender. When an out-of-order packet is received, the receiver sends a positive acknowledgment for the packet it has received. When a corrupted packet is received, the receiver sends a negative acknowledgment. We can accomplish the same effect as a NAK if, instead of sending a NAK, we send an ACK for the last correctly received packet. A sender that receives two ACKs for the same packet (that is, receives duplicate ACKs) knows that the receiver did not correctly receive the packet following the packet that is being ACKed twice. Our NAK-free reliable data

rdt2.1 sender

rdt2.1 receiver

transfer protocol for a channel with bit errors is rdt2.2, shown in Figure 5 and 6. One subtle change between rdt2.1 and rdt2.2 is that the receiver must now include the sequence number of the packet being acknowledged by an ACK message (this is done by including the ACK,0 or ACK,1 argument in make_pkt ( ) in the receiver FSM), and the sender must now cheek the sequence number of the packet being acknowledged by a received ACK message (this is done by including the 0 or 1 argument in isACK ( ) in the sender FSM).

Reliable Data Transfer over a Lossy Channel with Bit Errors: rdt3.0


Assume now that in addition to corrupting bits, the underlying channel can lose packets as well, a not-uncommon event in today's computer networks (including the internet). Two additional concerns must now be addressed by the protocol: how to detect packet loss and what to do when packet loss occurs. The use of checksumming, sequence numbers, ACK packets, and retransmissions-the techniques already developed in rdt2.2 - will allow us to answer the latter concern. Handling the first concern will require adding a new protocol mechanism.

There are many possible approaches toward dealing with packet loss. Here, well put the burden of detecting and recovering from lost packets on the sender.

rdt2.2 sender

Assume that the sender transmits a data packet and either that packet, or the receiver's ACK of the packet, gets lost. In either case, no reply is forthcoming at the sender from the receiver. If the sender is willing to wait long enough so that it is certain that a packet has been lost, it can simply retransmit the data packet. You should convince yourself that this protocol does indeed work.

But how long must the sender wait to be certain that something has been lost? The sender must clearly wait at least as long as a round-trip delay between the sender and receiver (which may contain buffering at intermediate routers) plus whatever amount of time is required to process a packet at the receiver. In many networks, this worst-case maximum delay is very difficult even to estimate, much less know with certainty. In addition, the protocol should ideally recover from packet loss as soon as possible; waiting for a worst-case delay could mean a long wait until error recovery is initiated. The approach thus adopted in practice is for the sender to judiciously choose a time value such that packet loss is likely, although not guaranteed, to have happened. If an ACK is not received within this time, the packet is retransmitted. Note that if a packet experiences a particularly large delay, the sender may retransmit the packet even though neither the data packet nor its ACK have been lost.

rdt2.2 receiver

This introduces the possibility of duplicate data packets in the sender-to-receiver channel. Happily, protocol rdt 2.2 already has enough functionality (that is, sequence numbers) to handle the case of duplicate packets.

From the sender's point of view, retransmission is a panacea. The sender does not know whether a data packet was lost, an ACK was lost, or if the packet or ACK was simply overly delayed. In all cases, the action is the same: retransmit. Implementing a time-based retransmission mechanism requires a countdown timer that can interrupt the sender after a given amount of time has expired. The sender will therefore need to be able to (1) start the timer each time a packet (either a first-time packet or a retransmission) is sent, (2) respond to a timer interrupt (taking appropriate actions), and (3) stop the timer.

Figure 7 shows the sender FSM for rdt3.0, a protocol that reliably transfers data over a channel that can corrupt or loss packets. "Pipelined Reliable Data Transfer Protocol" Figure 1 shows how the protocol operates with no lost or delayed packets and how it handles lost data packets. In "Pipelined Reliable Data Transfer Protocol" Figure 1, time moves forward from the top of the diagram toward the bottom of the diagram; note that a receive time for a packet is necessarily later than the send time for a packet as a result of transmission and propagation delays. In "Pipelined Reliable Data Transfer Protocol" Figure 1(b)-(d), the send-side brackets indicate the times at which a timer is set and later times out. Because packet sequence numbers alternate between 0 and 1, protocol rdt3.0 is sometimes known as the alternating-bit protocol.

rdt 3.0 sender

We have now assembled the key elements of a data transfer protocol. Checksums, sequence numbers, timers, and positive and negative acknowledgment packet each play a crucial and necessary role in the operation of the protocol. We now have a working reliable data transfer protocol.


Tags

protocol, fsm, arq, data packet, countdown timer, checksums, data transfer, transport layer

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.