Simplex Stop and Wait Protocol

Introduction

In the previous episode "Utopian Simplex Protocol" in this series of data link protocols we didn't deal with the problem of preventing the sender from flooding the receiver with frames faster than the latter is able to process them.
This situation is common in practice.
There are two variants of this protocol according to the communication channel.

• Error-free Channel: in which the channel is still assumed to be error free.
• Noisy Channel: Frames may be either damaged or lost completely. The data traffic is still simplex in both.

Error-free Channel:

A trivial solution is to build a powerful receiver to process a continuous stream of back-to-back frames. or make the data link layer of the sender slow enough so that the receiver can keep up.

this way the receiver must have sufficient buffering and processing abilities to run at the line rate and must be able to pass the frames received to the network layer quickly enough.

this is a worst-case solution. It requires dedicated hardware and can be wasteful of resources if the utilization of the link is mostly low. Moreover, it just shifts the problem of dealing with a sender that is too fast elsewhere. in this case to the network layer.

A more general solution to this problem is for the receiver provide feedback to the sender.
After having passed a packet to its network layer, the receiver
sends a little dummy frame back to the sender which, in effect, gives the sender permission to transmit the next frame.
After having sent a frame, the sender is required by the protocol to bide its time until the little dummy (i.e., acknowledgement) frame arrives.
This delay is a simple example of a flow control protocol.

Hence, it's called stop and wait because the sender sends one frame and waits for an acknowledgement before proceeding.

Although data traffic in this example is simplex ( going one way only from the sender to the receiver, frames do travel in both directions. But one after the other: the sender then the receiver then the sender and so on.
A half duplex channel would be enough here.

The Sender

• fetch a packet from the network layer.
• use it to construct a frame.
• send it on its way.
• wait until an acknowledgement frame arrives before looping back and fetching the next packet from the network layer.

The sending data link layer need not even inspect the incoming frame as there is only one possibility. The incoming frame is always an acknowledgement.

The Receiver

After delivering a packet to the network layer, the receiver sends an acknowledgement frame back to the sender before entering the wait loop again.
the receiver need not put any particular information in it. As only its arrival is important.

The Code

/* Protocol 2 (Stop-and-wait) also provides for a one-directional flow of data from
sender to receiver. The communication channel is once again assumed to be error
free, as in protocol 1. However, this time the receiver has only a finite buffer
capacity and a finite processing speed, so the protocol must explicitly prevent
the sender from flooding the receiver with data faster than it can be handled. */

typedef enum {frame arrival} event type;
#include "protocol.h"

void sender2(void){
  frame s; /* buffer for an outbound frame */
  packet buffer; /* buffer for an outbound packet */
  event type event; /* frame arrival is the only possibility */
  while (true) {
    from network layer(&buffer); /* go get something to send */
    s.info = buffer; /* copy it into s for transmission */
    to physical layer(&s); /* bye-bye little frame */
    /* do not proceed until given the go ahead */
    wait for event(&event);
  }
}

void receiver2(void){
  frame r, s; /* buffers for frames */
  event type event; /* frame arrival is the only possibility */
  while (true) {
    /* only possibility is frame arrival */
    wait for event(&event);
    from physical layer(&r); /* go get the inbound frame */
    /* pass the data to the network layer */
    to network layer(&r.info);
    /* send a dummy frame to awaken sender */
    to physical layer(&s);
  }
}

Note that if the channel is noisy the ACK can be lost and the sender will hang forever.
Next, we look at how to deal with this situation.

Noisy Channel:

we assume that if a frame is damaged in transit, the receiver hardware will detect this when it computes the checksum.

NOTE: If the frame is damaged in such a way that the checksum is nevertheless correct — an unlikely occurrence — this protocol (and all other protocols) can fail (i.e., deliver an incorrect packet to the network layer).

A simple approach to deal with noisy channel can be just adding a timer. If the packet arrives in error the receiver can discard it as if its lost, and after a timeout the sender will send it again.
But there is a fatal problem, if the ACK is lost the sender will sent the same packet again and it will be duplicated at the receiver.
And here shine the idea of having the sender put a sequence number in the header of each frame it sends.
Then the receiver can check the sequence number of each arriving
frame to see if it is a new frame or a duplicate to be discarded.
The important point is that it must carry sequence numbers that
are large enough for the protocol to work correctly.

The only ambiguity in this protocol is between a frame, m, and its direct successor, m + 1. A 1-bit sequence number (0 or 1) is therefore sufficient.

Protocols in which the sender waits for a positive acknowledgement before advancing to the next data item are often called ARQ (Automatic Repeat reQuest) or PAR (Positive Acknowledgement with Retransmission).

This protocol differs from its predecessors in that both sender and receiver have a variable whose value is remembered while the data link layer is in the wait state.

The sender remembers the sequence number of the next frame to send in next_frame_to_send. the receiver remembers the sequence number of the next frame expected in frame_expected.
Each protocol has a short initialization phase before entering the infinite loop.

The Sender

The sender transmits the frame, starts the timer, and waits.
Three possibilities exist:

• ACK frame arrives undamaged: the sender fetches the next packet from its network layer and puts it in the buffer, overwriting the previous packet and advances the sequence number.
• Damaged ACK frame arrives.
• Timer expires. In the last two cases neither the buffer nor the sequence number is changed so that a duplicate can be sent. In all cases, the contents of the buffer (either the next packet or a duplicate) are then sent. The timer interval is the sum of time for the frame to get to the receiver, for the receiver to process it in the worst case, and for the acknowledgement frame to propagate back to the sender. If the timeout interval is set too short, the sender will transmit unnecessary frames. While these extra frames will not affect the correctness of the protocol, they will hurt performance.

The receiver

When a valid frame arrives at the receiver, its sequence number is checked to see if it is a duplicate.
If not, it is accepted, passed to the network layer, and an acknowledgement is generated.
Duplicates and damaged frames are not passed to the network layer, but they do cause the last correctly received frame to be acknowledged to signal the sender to advance to the next frame or retransmit a damaged frame.

The Code

/* Protocol 3 (PAR) allows unidirectional data flow over an unreliable channel. */

#define MAX SEQ 1 /* must be 1 for protocol 3 */
typedef enum {frame_arrival, cksum_err, timeout} event type;
#include "protocol.h"

void sender3(void){
  /* seq number of next outgoing frame */
  seq_nr next_frame_to_send;
  frame s; /* scratch variable */
  packet buffer; /* buffer for an outbound packet */
  event_type event;
  /* initialize outbound sequence numbers */
  next_frame_to_send = 0;
  from_network_layer(&buffer); /* fetch first packet */
  while (true) {
    s.info = buffer; /* construct a frame for transmission */
    /* insert sequence number in frame */
    s.seq = next_frame_to_send;
    to_physical_layer(&s); /* send it on its way */
    start_timer(s.seq); /* if answer takes too long, time out */
    /* frame arrival, cksum err, timeout */
    wait_for_event(&event);
    if (event == frame_arrival) {
      from_physical_layer(&s); /* get the acknowledgement */
      if (s.ack == next_frame_to_send) {
        stop_timer(s.ack); /* turn the timer off */
        /* get the next one to send */
        from_network_layer(&buffer);
        inc(next_frame_to_send); /* invert next frame to send */
      }
    }
  }
}

void receiver3(void){
  seq_nr frame_expected;
  frame r, s;
  event_type event;
  frame_expected = 0;
  while (true) {
    /* possibilities: frame_arrival, cksum_err */
    wait for event(&event);
    if (event == frame_arrival) { /* a valid frame has arrived */
      /* go get the newly arrived frame */
      from_physical_layer(&r);
      /* this is what we have been waiting for */
      if (r.seq == frame_expected) { 
        /* pass the data to the network layer */
        to_network_layer(&r.info);
        /* next time expect the other sequence_nr */
        inc(frame_expected);
      }
      /* tell which frame is being acked */
      s.ack = 1 − frame_expected;
      to_physical_layer(&s); /* send acknowledgement */
    }
  }
}

References and Credits

• "Computer Networks Book by Andrew S. Tanenbaum" 5th edition.