UoL CS Notes
Menu

Reliable Data Transfer (Stop & Wait)

COMP211 Lectures

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Calculating Utilisation

Stop and wait protocols are inefficient as ideally they can only send one packet per round trip time.

To calculate the time to transmit a 1 MB packet into a 1 Gbps channel:

\[D_\text{trans}=\frac LR=\frac{8000\text{ bits}}{10^9\text{ bits/sec}}=8\mu s\]

Where:

  • $D$ - Time to transmit packet.
  • $L$ - Length of the packet.
  • $R$ - Rate of transfer.

To find the utilisation of the medium we can use the following:

\[U_\text{sender}=\frac{\frac LR}{\text{RTT}+\frac LR}\]

With the previous packet, link speed, 30 ms rtt and a stop and wait protocol we can calculate the following:

\[U_\text{sender}=\frac{0.008}{30+0.008}=0.00027\]

This is only 0.027% utilisation.

Pipelining

This allows us to send multiple packets before the first one is acknowledged. There are two main families of protocols:

Go-Back-N Protocol

Sender

There is a window of up to $N$, consecutive transmitted but unACKed packets:

  • Cumulative ACK - We must acknowledge all packets up to and including the sequence number included in the client’s ACK.
  • On receiving ACK(n) - Move window forward to begin at $n+1$.
  • Timer is used for the oldest in-flight packet.
    • When the timer runs out, re-transmit packet $n$ and all higher sequence number packets in the window.

Due the reuse of sequence numbers we use sequence numbers of $>2N$ (more than 2 times the window size).

Receiver

This is ACK only:

  • Always send ACK for correctly-received packet so far, with highest in-order sequence number.
  • May generate duplicate ACKs
  • Need only remember the next expected sequence number.

On receipt of out-of-order packet:

  • Can discard (don’t buffer) or buffer for later.

    This is an implementation decision.

  • Re-ACK packet with highest in-order sequence number.

Selective Repeat Protocol

In this method the receiver individually acknowledges all correctly received packets.

  • Buffers packets, as needed, for eventual in-order delivery to the upper layer.

The sender times-out/re-transmits individually for each unACKed packet:

  • Sender maintains timer for each unACKed packet.

The sender window:

  • Has a size of $N$ consecutive seq numbers.
  • The timers keep track of unACKed packets.

Sender

Data from above:

  • If next available sequence number in window, send packet.

Timeout(n):

  • Resend packet $n$, restart timer.

ACK(n) in [sendbase,sendbase+N]:

  • Mark packet $n$ as received.
  • If $n$ smallest unACKed packet, advance window base to next unACKed sequence number.

Receiver

Packet $n$ in [rcvbase, rcvbase+N-1]:

  • send ACK(n)
    • Out-of-order - buffer.
    • In-order - deliver (also deliver buffered, in-order packets), advance window to next not-yet-received packet.

Packet $n$ in [rcvbase-N,rcvbase-1] (already received):

  • ACK(n)

Otherwise:

  • Ignore