IST362: Reliable Data Transfer

Reliable Data Transfer v1.0 (over a perfectly reliable channel)

**Sender 1.0**
#	State	Conditions	Action
0	wait for data from above	data received	make packet (data) send packet return to state 0

**Receiver 1.0**
#	State	Conditions	Action
0	wait for packet from below	packet received	extract data (packet) pass data up return to state 0

Reliable Data Transfer v2.0 (over a channel with bit errors)

Additional protocol capabilities:

Error detection

Receiver feedback (ACK or NAK)

Retransmission

**Sender 2.0**
#	State	Conditions	Action
0	wait for data from above	data received	make packet (data, checksum) send packet goto to state 1
1	wait for receiver feedback	received NAK	send packet goto to state 1
1	wait for receiver feedback	received ACK	goto to state 0

**Receiver 2.0**
#	State	Conditions	Action
0	wait for packet from below	received packet is corrupted	send `NAK` return to state 0
0	wait for packet from below	received packet is OK	send `ACK` extract data pass data up return to state 0

This is stop-and-wait protocol because when the sender is in the state 1 it's not able to get data from the upper level.

Problem: feedback can also be corrupted.
Reaction:

ask for retransmission of ACK/NAK or

add such a checksum that allows to recover from the corruption or

retransmit the same packet (Problem: receiver needs to distinguish first-time packets from retransmitted)

**Sender 2.1**
#	State	Conditions	Action
0	wait for data from above	data received	make packet (data, checksum, seq#=0) send packet goto to state 1
1	wait for receiver feedback	feedback corrupted or NAK	send packet goto to state 1
1	wait for receiver feedback	received non-corrupted ACK	goto to state 2
2	wait for data from above	data received	make packet (data, checksum, seq#=1) send packet goto to state 3
3	wait for receiver feedback	feedback corrupted or NAK	send packet goto to state 3
3	wait for receiver feedback	received non-corrupted ACK	goto to state 0

**Receiver 2.1**
#	State	Conditions	Action
0	wait for packet from below	received packet is corrupted	make packet (`NAK`, checksum) send packet return to state 0
		received non-corrupted packet with seq#=1	make packet (`ACK`, checksum) send packet return to state 0
		received non-corrupted packet with seq#=0	make packet (`ACK`, checksum) send packet extract data from received packet pass data up go to state 1
1	wait for packet from below	received packet is corrupted	make packet (`NAK`, checksum) send packet return to state 1
		received non-corrupted packet with seq#=0	make packet (`ACK`, checksum) send packet return to state 1
		received non-corrupted packet with seq#=1	make packet (`ACK`, checksum) send packet extract data from received packet pass data up go to state 0

We can actually get rid of negative acknowledgment -- instead we will send ACK for the last correctly received packet.
Sender 2.2
# State Conditions Action

0 wait for data from above data received
make packet (data, checksum, seq#=0)
send packet
goto to state 1

1 wait for receiver feedback feedback corrupted or ACK seq#=1
send packet
return to state 1

received non-corrupted ACK and seq#=0
goto to state 2

2 wait for data from above data received
make packet (data, checksum, seq#=1)
send packet
goto to state 3

3 wait for receiver feedback feedback corrupted or ACK seq#=0
send packet
return to state 3

received non-corrupted ACK with seq#=1
goto to state 0

**Receiver 2.2**
#	State	Conditions	Action
0	wait for packet from below	received packet is corrupted or has seq#1	send packet return to state 0
0	wait for packet from below	received non-corrupted packet with seq#=0	make packet (`ACK`, checksum, seq#=0) send packet extract data from received packet pass data up go to state 1
1	wait for packet from below	received packet is corrupted or has seq#=0	send packet return to state 1
1	wait for packet from below	received non-corrupted packet with seq#=1	make packet (`ACK`, checksum, seq#=1) send packet extract data from received packet pass data up go to state 0

Reliable Data Transfer v3.0 (over a lossy channel with bit errors)

Now our protocol should be able to deal with a situation when either data packet or ACK packet got lost. How to deal with this? Retransmit the data packet after a certain time-out. (How long this time-out should be?) If the time-out is not big enough and packet wasn't lost (just delayed), then the protocol should deal with duplicate data packet.

We actually already had a mechanism to deal with duplicate packets (see RDT v2.2). To implement a time-based retransmission, a count-down timerwill be needed that can interrupt the sender after a given period of time has expired.
Sender 3.0
# State Conditions Action

0 wait for data from above data received
make packet (data, checksum, seq#=0)
send packet
start timer
goto to state 1

packet received
ignore the packet
return to the state 0

1 wait for receiver feedback feedback corrupted or ACK seq#=1
ignore the packet
return to state 1

timeout expired
send the packet
start timer
return to state 1

received non-corrupted ACK and seq#=0
stop timer
goto to state 2

2 wait for data from above data received
make packet (data, checksum, seq#=1)
send packet
start timer
goto to state 3

packet received
ignore the packet
return to the state 2

3 wait for receiver feedback feedback corrupted or ACK seq#=0
ignore the packet
return to state 3

timeout expired
send the packet
start timer
return to state 3

received non-corrupted ACK and seq#=1
stop timer
goto to state 0

Luckily, we don't have to invent anything for the receiver. Receiver v 2.2 works just fine over such channels.