Federico Mengozzi

Transport Layer

Principles of Reliable Data Transfer

Reliable Data Transfer Protocol concept

The first improvement over a simple protocol built on top of the network layer is the introduction of packets acknowledgment, protocol that implement those feature are called ARQ (Automatic Repeat reQuest). To implement acknowledgement such protocol would require additional capabilities

  • Error detection - Allow a sender to recognize a corrupted packet
  • Receiver feedback - A feedback message is response of a received packet: ACK in case the packet was received correctly and NACK otherwise. Since also those packets could be corrupter an ACK feedback would consists in only an uncorrupted ACK, everything else is considered a NACK
  • Retransmissions - If a packet is corrupted the protocol need to be able to resend packets

The retransmissions of feedback packet require a way to pair every one of them to the correct sent data packet. A possible solution is to introduce a sequence number in this way the pairing is done by checking the sequence number. In a stop-and-wait protocol it’s sufficient 1 bit for identify the sequence number (the protocol move on the next sequence after the data packet is sent and the feedback packet is received), this protocol is called alternating-bit protocol.

To avoid the introduction of a new packet, the receiver could simply keep sending an ACK packet relative to the last uncorrupted packet received.

The second improvement consist in packet loss recovering. If packet get lost on the network the receiver won’t send any feedback to the sender. The sender could introduce a timer to handle the situation; if the feedback is not received within the time frame the packet is simply resent. Obviously the timer should be at least grater than the round trip delay

Pipelined Reliable Data Transfer Protocols

Rather than operate in a stop-and-wait manner, if the protocol would allow a sender to send multiple packet without waiting for the feedback, the performance could drastically improve. This technique is called pipeling and require the protocol to increase the sequence number, buffer more than just one packet.

Two basic approach can be identified

Go-Back-N (GBN)

This protocol allows the sender to have a window of $N$ unacknowledged packets in the pipeline. Defining $base$ as the first unacknowledged packet and $nextSeqNum$ as the smallest unused sequence number, then $4$ interval can be recognized in every moment

  • $[0, base - 1]$ - Is the interval of all sent and acknowledged packet
  • $[base, nextSeqNum - 1]$ - Is the interval of send bt not yet acknowledged packet
  • $[nextSeqNum, base + N - 1]$ - Is the interval of sequence number that can be used for packet that can be sent immediately
  • $[base + N, \infty]$ - Are the sequence numbers that cannot be used yet

The GBN protocol can be define as sliding-window protocol because of the $N$ sized window represent the current processed packets. If the sequence number is represented by $k$ bits, then the range of the sequence number is $[0, 2^k-1]$ and all operations regarding the sequence number should be done in modulo $2^k$.

The protocol must be able to respond to three types of events:

  • Invocation from the application - If the window is full, the protocol send back the data to indicate unavailability, otherwise a packet is create, placed in the window and sent.
  • Receipt of ACK - The protocol utilize comulative acknowledgement, it means that if it’s received an ACK specific to sequence number $k$ than all previous $k$ are being correctly received. Once such ACK is received the window is slided $k$ position forward.
  • Timeout event - Whenever and ACK is received the times is reset. If a timeout occur the protocol will send all packets not yet acknowledged.

GBN usually doesn’t accept out-of order packets, it simply discard them as it does with corrupted ones (this solution consider the memory needed to store out-of order packets).

Selective Repeat (SR)

The drawback of the GBN protocol is the need to resend in bulk all $N-k$ packets if the $k$-th packet is not acknowledged. Selective Repeat on the other hand acknowledge and store every uncorrupted packet (out-of order packets are store for later usage).

Go to top