1 of 25

Computer Networks

Sina Keshvadi

Fall 2021

University of Calgary

Lecture No. 14

Oct 08, 2021

Principles of Reliable Data Transfer (Part 1)

Transport Layer: 3-1

Today’s Agenda:

Principles of reliable data transfer

Midterm Reminder + Q/A
Assignment 2’ Demo + Q/A

2 of 25

Principles of reliable data transfer

Transport Layer: 3-2

sending process

data

receiving process

data

reliable channel

application

transport

reliable service abstraction

3 of 25

Principles of reliable data transfer

Transport Layer: 3-3

sending process

data

receiving process

data

application

transport

reliable service implementation

unreliable channel

network

transport

sender-side of

reliable data transfer protocol

receiver-side

of reliable data transfer protocol

sending process

data

receiving process

data

reliable channel

application

transport

reliable service abstraction

4 of 25

Principles of reliable data transfer

Transport Layer: 3-4

sending process

data

receiving process

data

application

transport

reliable service implementation

unreliable channel

network

transport

sender-side of

reliable data transfer protocol

receiver-side

of reliable data transfer protocol

Complexity of reliable data transfer protocol will depend (strongly) on characteristics of unreliable channel (lose, corrupt, reorder data?)

5 of 25

Principles of reliable data transfer

Transport Layer: 3-5

sending process

data

receiving process

data

application

transport

reliable service implementation

unreliable channel

network

transport

sender-side of

reliable data transfer protocol

receiver-side

of reliable data transfer protocol

Sender, receiver do not know the “state” of each other, e.g., was a message received?

unless communicated via a message

Here’s a point of view to keep in mind – it’s easy for US to look at sender and receiver together and see what is happening. OH – that message sent was lost.

But think about it say from senders POV How does the sender know if its transmitted message over the unreliable channel got though?? ONLY if receiver somehow signals to the sender that it was received.

The key point here is that one side does NOT know what is going on at the other side – it’s as if there’s a curtain between them. Everything they know about the other can ONLY be learned by sending/receiving messages.

Sender process wants to make sure a segment got through. But it can just somehow magically look through curtain to see if receiver got it. It will be up to the receiver to let the sender KNOW that it (the receiver) has correctly received the segment.

How will the sender and receiver do that – that’s the PROTOCOL.

Before starting to develop a protocol, let’s look more closely at the interface (the API if you will)

6 of 25

Reliable data transfer protocol (rdt): interfaces

Transport Layer: 3-6

sending process

data

receiving process

data

unreliable channel

sender-side

implementation of rdt reliable data transfer protocol

receiver-side

implementation of rdt reliable data transfer protocol

rdt_send()

udt_send()

rdt_rcv()

deliver_data()

data

Header

data

Header

rdt_send(): called from above, (e.g., by app.). Passed data to deliver to receiver upper layer

udt_send(): called by rdt

to transfer packet over

unreliable channel to receiver

rdt_rcv(): called when packet arrives on receiver side of channel

deliver_data(): called by rdt to deliver data to upper layer

Bi-directional communication over unreliable channel

data

packet

7 of 25

Reliable data transfer: getting started

Transport Layer: 3-7

We will:

incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)
consider only unidirectional data transfer

but control info will flow in both directions!

state

1

state

2

event causing state transition

actions taken on state transition

state: when in this “state” next state uniquely determined by next event

event

actions

use finite state machines (FSM) to specify sender, receiver

SO let’s get started in developing our reliable data transfer protocol, which we’ll call rdt (need a good acronym for protocol – like HTTP, TCP, UDP, IP)

Bullet points 1 and 2

NOW if we are going to develop a protocol, so we’ll need some way to SPECIFY a protocol. How do we do that?

We could write text, but as all know, that’s prone to misinterpretation, and might be incomplete. You might write a specification, and then think “oh yeah – I forgot about that case”

What we need is more formal way to specify a protocol. In fact, with a formal specification there may be ways to PROVE PROPERTIES about a specification. But that’s an advanced topic we won’t get into here. We’ll start here by adopting a fairly simple protocol specification technique known as finite state machines (FSM)

And as the name might suggest, a central notion of finite state machines is the notion of STATE

8 of 25

Transport Layer: 3-8

9 of 25

rdt1.0: reliable transfer over a reliable channel

Transport Layer: 3-9

underlying channel perfectly reliable

no bit errors
no loss of packets

packet = make_pkt(data)

udt_send(packet)

rdt_send(data)

extract (packet,data)

deliver_data(data)

rdt_rcv(packet)

Wait for call from below

receiver

separate FSMs for sender, receiver:

sender sends data into underlying channel
receiver reads data from underlying channel

sender

Wait for call from above

10 of 25

rdt2.0: channel with bit errors

Transport Layer: 3-10

underlying channel may flip bits in packet

checksum (e.g., Internet checksum) to detect bit errors

the question: how to recover from errors?

How do humans recover from “errors” during conversation?

11 of 25

rdt2.0: channel with bit errors

Transport Layer: 3-11

underlying channel may flip bits in packet

checksum to detect bit errors

the question: how to recover from errors?

acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors
sender retransmits pkt on receipt of NAK

stop and wait

sender sends one packet, then waits for receiver response

12 of 25

rdt2.0: FSM specifications

Transport Layer: 3-12

Wait for call from above

udt_send(sndpkt)

Wait for ACK or NAK

udt_send(NAK)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

Wait for call from below

extract(rcvpkt,data)

deliver_data(data)

udt_send(ACK)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

snkpkt = make_pkt(data, checksum)

udt_send(sndpkt)

rdt_send(data)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

sender

receiver

rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

13 of 25

rdt2.0: FSM specification

Transport Layer: 3-13

Wait for call from above

udt_send(sndpkt)

Wait for ACK or NAK

udt_send(NAK)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

Wait for call from below

extract(rcvpkt,data)

deliver_data(data)

udt_send(ACK)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

snkpkt = make_pkt(data, checksum)

udt_send(sndpkt)

rdt_send(data)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

sender

receiver

Note: “state” of receiver (did the receiver get my message correctly?) isn’t known to sender unless somehow communicated from receiver to sender

that’s why we need a protocol!

rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

isACK(rcvpkt)

14 of 25

rdt2.0: operation with no errors

Transport Layer: 3-14

Wait for call from above

snkpkt = make_pkt(data, checksum)

udt_send(sndpkt)

udt_send(NAK)

Wait for ACK or NAK

Wait for call from below

rdt_send(data)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

extract(rcvpkt,data)

deliver_data(data)

udt_send(ACK)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

sender

receiver

rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

15 of 25

rdt2.0: corrupted packet scenario

Transport Layer: 3-15

Wait for call from above

snkpkt = make_pkt(data, checksum)

udt_send(sndpkt)

rdt_rcv(rcvpkt) &&

isNAK(rcvpkt)

Wait for ACK or NAK

Wait for call from below

rdt_send(data)

udt_send(NAK)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

extract(rcvpkt,data)

deliver_data(data)

udt_send(ACK)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

sender

receiver

16 of 25

rdt2.0 has a fatal flaw!

Transport Layer: 3-16

what happens if ACK/NAK corrupted?

sender doesn’t know what happened at receiver!
can’t just retransmit: possible duplicate

handling duplicates:

sender retransmits current pkt if ACK/NAK corrupted
sender adds sequence number to each pkt
receiver discards (doesn’t deliver up) duplicate pkt

stop and wait

sender sends one packet, then waits for receiver response

17 of 25

rdt2.1: sender, handling garbled ACK/NAKs

Transport Layer: 3-17

Wait for call 0 from above

Wait for ACK or NAK 0

sndpkt = make_pkt(0, data, checksum)

udt_send(sndpkt)

rdt_send(data)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||

isNAK(rcvpkt) )

sndpkt = make_pkt(1, data, checksum)

udt_send(sndpkt)

rdt_send(data)

udt_send(sndpkt)

rdt_rcv(rcvpkt)

&& (corrupt(rcvpkt) ||

isNAK(rcvpkt) )

Wait for

call 1 from above

Wait for ACK or NAK 1

rdt_rcv(rcvpkt)

&& notcorrupt(rcvpkt)

&& isACK(rcvpkt)

Λ

rdt_rcv(rcvpkt)

&& notcorrupt(rcvpkt) && isACK(rcvpkt)

Λ

18 of 25

rdt2.1: receiver, handling garbled ACK/NAKs

Transport Layer: 3-18

Wait for

0 from below

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

&& has_seq1(rcvpkt)

extract(rcvpkt,data)

deliver_data(data)

sndpkt = make_pkt(ACK, chksum)

udt_send(sndpkt)

Wait for

1 from below

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

&& has_seq0(rcvpkt)

extract(rcvpkt,data)

deliver_data(data)

sndpkt = make_pkt(ACK, chksum)

udt_send(sndpkt)

sndpkt = make_pkt(NAK, chksum)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt)

rdt_rcv(rcvpkt) &&

not corrupt(rcvpkt) &&

has_seq0(rcvpkt)

sndpkt = make_pkt(ACK, chksum)

udt_send(sndpkt)

rdt_rcv(rcvpkt) &&

not corrupt(rcvpkt) &&

has_seq1(rcvpkt)

sndpkt = make_pkt(ACK, chksum)

udt_send(sndpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt)

sndpkt = make_pkt(NAK, chksum)

udt_send(sndpkt)

19 of 25

What do you call a running turkey?

Fast food :)

Transport Layer: 3-19

20 of 25

rdt2.1: discussion

Transport Layer: 3-20

sender:

seq # added to pkt
two seq. #s (0,1) will suffice. Why?
must check if received ACK/NAK corrupted
twice as many states

state must “remember” whether “expected” pkt should have seq # of 0 or 1

receiver:

must check if received packet is duplicate

state indicates whether 0 or 1 is expected pkt seq #

note: receiver can not know if its last ACK/NAK received OK at sender

21 of 25

rdt2.2: a NAK-free protocol

Transport Layer: 3-21

same functionality as rdt2.1, using ACKs only
instead of NAK, receiver sends ACK for last pkt received OK

receiver must explicitly include seq # of pkt being ACKed

duplicate ACK at sender results in same action as NAK: retransmit current pkt

As we will see, TCP uses this approach to be NAK-free

22 of 25

23 of 25

24 of 25

rdt2.2: sender, receiver fragments

Transport Layer: 3-24

Wait for call 0 from above

sndpkt = make_pkt(0, data, checksum)

udt_send(sndpkt)

rdt_send(data)

udt_send(sndpkt)

rdt_rcv(rcvpkt) &&

( corrupt(rcvpkt) ||

isACK(rcvpkt,1) )

rdt_rcv(rcvpkt)

&& notcorrupt(rcvpkt)

&& isACK(rcvpkt,0)

Wait for ACK

0

sender FSM

fragment

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

&& has_seq1(rcvpkt)

extract(rcvpkt,data)

deliver_data(data)

sndpkt = make_pkt(ACK1, chksum)

udt_send(sndpkt)

Wait for

0 from below

rdt_rcv(rcvpkt) &&

(corrupt(rcvpkt) ||

has_seq1(rcvpkt))

udt_send(sndpkt)

receiver FSM

fragment

Λ

25 of 25

What do you call a running turkey?

Fast food :)

Transport Layer: 3-25