3.4 Principles of Reliable Data Transfer

💡 The service abstraction provided to the upper-layer entities is that of a reliable channel through which data can be transferred. With a reliable channel, no transferred data bits are corrupted (flipped from 0 to 1, or vice versa) or lost, and all are delivered in the order in which they were sent.

3.4.1 Building a Reliable Data Transfer Protocol

RDT over perfectly reliable channel: RDT 1.0

Trivial rdt1.0 assumes channel is reliable.

RDT over channel with Bit Error: RDT 2.0

More realistic model of underlying channel may have corrupted bits in a packet. Typically occurs in the physical components.

To make sure message is delivered, receiver uses positive acknowledgment or negative acknowledgment. RDT protocols based on retransmission is known as ARQ (Automatic Repeat reQuest) protocols.

Three capabilities are required in ARQ protocol

1. Error detection → check sum in UDP, need extra bits.
2. Receiver feedback → ACK, NAK packets from the receiver provide feedback to the sender.
3. Retransmission → Packet with error at the receiver must be retransmitted.

While sender is in wait-for-ACK/NAK, rdt_send() cannot occur. →Has to wait until receiver correctly got its packet. Thus, protocols like RDT 2.0 is called stop-and-wait protocol.

What if there is error in the ACK/NAK packets themselves? How to recover? Sender cannot know whats going on…

Solution is to add sequence number. This will tell receiver if its a retransmission for previous ACK-NAK packet or not.

RDT 2.1 has sequence number thus double the FSM status.

RDT 2.2 is NAK free. Receiver send ACK for last correctly received packet.

in rdt 2.2, receiver must include sequence number of packet acknowledged by ACK. (ACK, 0 or ACK, 1) in the make_pkt() in receiver FSM.

So far, rdt 2.x considers channel with corrupted bits only. Now consider channel with loss bits.

RDT over Lossy Channel with Bit Errors: rdt 3.0

How to detect a loss? What to do when loss occurs?

checksum, sequence numbers, ACK packet and retransmission → technique from rdt2.2 will hanle what to do when loss occurs.

But how to detect a loss? Solution is timeout.

💡 Sender judiciously choose time that packet loss has likely (not guaranteed) to have happened. If ACK is not received in this time, packet is retransmitted.

In the case of duplicate data packets, sequence numbers can handle it.

Such time-based retransmission requires countdown timer to interrupt when certain time expired. Therefore sender needs to:

1. Start timer when packet is sent
2. Respond to timer interrupt → (probably retransmit)
3. Stop the timer

💡 Draw rdt 3.0 receiver

Because sequence numbers alternate between 0 and 1, rdt 3.0 is also called alternating-bit protocol.

💡 Checksum, Sequence numbers, timmers, and ACK,NAK packets play essential role in RDT protocol.

To be continued...

3.4.2 Pipelined RDT Protocols

3.4.3 Go-Back-N (GBN)

Go-Back Protocol

GBN animation

3.4.4 Selective Repeat (SR)