Reliable Data Transfer

RDT 1.0

Assumption: underlying channel is perfect

• No bit errors
• No packet loss

The implementation is straightforward:

• Sender: send data into underlying channel
• Receiver: read data from underlying channel and deliver to upper layer

RDT 2.0

Mental Model

Assumption: underlying channel may introduce bit errors (e.g. flipping bits)

To handle bit errors, we introduce:

• Checksum: to detect bit errors
• ACK / NAK: to tell sender whether packet is received correctly

The mental model is as follows:

• ACKs: receiver explicitly tells sender that packet is received correctly
• NAKs: receiver explicitly tells sender that packet is corrupted
• Sender retransmits packet upon receiving NAK

Stop and Wait Protocol is used here:

sender sends one packet and waits for ACK/NAK before sending the next packet.

Fatal Flaw

What if ACK/NAK is corrupted?

• Sender will not know whether packet is received correctly
• Can’t solve this by retransmitting since may produce duplicate (recv does not know whether packet is new or retransmission)

sequenceDiagram
    participant S as Sender
    participant R as Receiver

    S->>R: [data]

    R-xS: [ACK]
    Note over S: ACK corrupted, unsure if packet received

    S->>R: [data] (retransmission)
    Note over R: Is this new packet or retransmission?

Handling duplicates:

• sender add sequence number to each packet (0 or 1)
• if ACK/NAK is corrupted, sender retransmits packet with same sequence number

RDT 2.1

Same assumptions as RDT 2.0, but add 1 bits sequence number to handle duplicates.

sequenceDiagram
    participant S as Sender
    participant R as Receiver

    S->>R: [data, SEQ = 0]
    Note over R: PKT 0 received, expecting PKT 1

    R-xS: [ACK]
    Note over S: ACK corrupted

    S->>R: [data, SEQ = 0] (retransmission)
    Note over R: expect PKT 1, but received PKT 0 (discard)
    R->>S: [ACK]

Can we further improve it? Actually NAK is not necessary and we can just use ACKs. That leads to RDT 2.2

RDT 2.2

Same assumptions as RDT 2.0, but use only ACKs (no NAKs).

Mental Model

• Sender:

  • send packet with sequence number
  • if ACK received with matching sequence number, send next packet with toggled sequence number
  • if ACK received with non-matching sequence number, resend current packet

• Receiver:

  • if packet received correctly, send ACK with the sequence number of current packet
  • if packet corrupted, resend ACK of sequence number other than current packet (only 1 bit, so 0 -> 1, 1 -> 0)

sequenceDiagram
    participant S as Sender
    participant R as Receiver

    S-xR: [data, SEQ = 0]
    Note over R: PKT 0 corrupted
    R->>S: [ACK = 1]

    S->>R: [data, SEQ = 0] (retransmission)
    Note over R: PKT 0 received correctly
    R->>S: [ACK = 0]

    S->>R: [data, SEQ = 1]
    Note over R: PKT 1 received correctly
    R->>S: [ACK = 1]

RDT 3.0

Assumption: underlying channel may have:

• bit errors and
• packet loss

In this scenario, RDT 2.x version cannot handle packet loss because sender may wait forever for ACK/NAK.

Pitfalls

it is still possible that RDT 3.0 encounter the case that the receiver recognize the re-transmission packet as the new data packet as shown below:

TCP Pipelining

The performance of RDT is pretty bad due to the stop and wait protocol. To improve performance, we can use pipelining.

The core idea of pipelining is to allow sender to send multiple packets without waiting for ACKs.

Let’s assume the window size is , then the utilization rate of the TCP pipelining is:

which scale up with the window size