Computer Networks
Principles of Reliable Data Transfer
Based on Computer Networking, 4th Edition by Kurose and Ross
Stan Kurkovsky
Principles of reliable data transfer
• important in app., transport, link layers
• top-10 list of important networking topics!
• characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)
Stan Kurkovsky
1
Reliable data transfer: getting started
rdt_send(): called from above, (e.g., by app.). Passed data to deliver to receiver upper layer
deliver_data(): called by rdt to deliver data to upper
send receive side side
udt_send(): called by rdt, to transfer packet over unreliable channel to receiver
rdt_rcv(): called when packet arrives on rcv-side of channel
Stan Kurkovsky
Reliable data transfer: getting started
We’ll:
• incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)
• consider only unidirectional data transfer
• but control info will flow on both directions!
• use finite state machines (FSM) to specify sender, receiver
event causing state transition actions taken on state transition
state: when in this “state” next state uniquely determined by next event
state 1
event actions
state 2
Stan Kurkovsky
2
Rdt 1.0: reliable transfer over a reliable channel
• underlying channel perfectly reliable
• no bit errors
• no loss of packets
• separate FSMs for sender, receiver:
• •
sender sends data into underlying channel receiver read data from underlying channel
Wait for call from above
rdt_send(data)
packet = make_pkt(data) udt_send(packet)
sender
Wait for call from below
rdt_rcv(packet)
extract (packet,data) deliver_data(data)
receiver
Stan Kurkovsky
Rdt 2.0: channel with bit errors
• 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
• new mechanisms in rdt2.0 (beyond rdt1.0):
• error detection
• receiver feedback: control msgs (ACK,NAK) rcvr->sender
Stan Kurkovsky
3
Rdt 2.0: FSM specification
rdt_send(data)
snkpkt = make_pkt(data, checksum)
receiver
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && isNAK(rcvpkt)
udt_send(sndpkt) rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
sender
Wait for call from above
Wait for ACK or NAK
udt_send(NAK)
Wait for call from below
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
extract(rcvpkt,data) deliver_data(data) udt_send(ACK)
Stan Kurkovsky
Rdt 2.0 has a fatal flaw!
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 garbled
• 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
Stan Kurkovsky
4
Rdt 2.1: sender, handles garbled ACK/NAKs
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) )
udt_send(sndpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) )
udt_send(sndpkt)
Wait for call 0 from above
Wait for ACK or NAK 1
rdt_send(data)
sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt)
Wait for ACK or NAK 0
Wait for call 1 from above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt)
L
Stan Kurkovsky
Rdt 2.1: receiver, handles garbled ACK/NAKs
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) && has_seq1(rcvpkt)
sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)
extract(rcvpkt,data) deliver_data(data)
sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)
Wait for 0 from below
Wait for 1 from below
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) && has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)
Stan Kurkovsky
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)
extract(rcvpkt,data) deliver_data(data)
sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)
5
Rdt 2.1: discussion
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 “current” pkt has 0 or 1 seq. #
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
Stan Kurkovsky
Rdt 2.2: a NAK-free protocol
• 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
Stan Kurkovsky
6
Rdt 2.2: sender, receiver fragments
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||
isACK(rcvpkt,1) ) udt_send(sndpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt,0)
Wait for call 0 from above
Wait for ACK
rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||
has_seq1(rcvpkt)) udt_send(sndpkt)
Wait for 0 from below
receiver FSM fragment
L
sender FSM fragment
0
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)
extract(rcvpkt,data) deliver_data(data)
sndpkt = make_pkt(ACK1, chksum) udt_send(sndpkt)
Stan Kurkovsky
Rdt 3.0: channels with errors and loss
New assumption: underlying channel can also lose packets (data or ACKs) • checksum, seq. #, ACKs, retransmissions will be of help, but not enough
Approach: sender waits “reasonable” amount of time for ACK
• retransmits if no ACK received in this time
• if pkt (or ACK) just delayed (not lost):
• retransmission will be duplicate, but use of seq. #’s already handles this
• receiver must specify seq # of pkt being ACKed • requires countdown timer
Stan Kurkovsky
7
Rdt 3.0 sender
rdt_rcv(rcvpkt)
L
rdt_send(data)
sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) L
timeout udt_send(sndpkt) start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt,0) stop_timer
Wait for call 0from above
Wait for ACK0
Wait for call 1 from above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt,1)
stop_timer timeout
Wait for
udt_send(sndpkt) ACK1 start_timer
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) )
L
rdt_send(data)
rdt_rcv(rcvpkt)
L
sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt)
start_timer
Stan Kurkovsky
Rdt 3.0 in action
Stan Kurkovsky
8
Rdt 3.0 in action
Stan Kurkovsky
Rdt 3.0: stop-and-wait operation
• • •
L = packet length in bits
R = transmission rate, bps
U = utilization – fraction of time sender busy sending
sender first packet bit transmitted, t = 0
receiver
last packet bit transmitted, t = L / R RT
ACK arrives, send next packet, t = RTT + L / R
Usender= L / R RTT + L / R
first packet bit arrives
last packet bit arrives, send ACK
T
=
.008 30.008
=
0.00027 microsec onds
Stan Kurkovsky
9
Pipelined protocols
Pipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pkts
• range of sequence numbers must be increased
• buffering at sender and/or receiver
• Two generic forms of pipelined protocols: go-Back-N, selective repeat
Stan Kurkovsky
Pipelining: increased utilization
sender receiver
first packet bit transmitted, t = 0 last bit transmitted, t = L / R
RT
ACK arrives, send next packet, t = RTT + L / R
first packet bit arrives
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK
Increase utilization by a factor of 3!
T
Usender= 3*L/R = .024 = 0.0008 RTT + L / R 30.008 microsecon
ds
Stan Kurkovsky
10
Go-Back-N
Sender:
• k-bit seq # in pkt header
• “window” of up to N, consecutive unack’ed pkts allowed
• ACK(n): ACKs all pkts up to, including seq # n – “cumulative ACK”
• may receive duplicate ACKs (see receiver)
• timer for each in-flight pkt
• timeout(n): retransmit pkt n and all higher seq # pkts in window
Stan Kurkovsky
GBN: sender extended FSM
rdt_send(data)
if (nextseqnum < base+N) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum])
if (base == nextseqnum)
L
base=1 nextseqnum=1
rdt_rcv(rcvpkt)
&& corrupt(rcvpkt)
start_timer nextseqnum++ }
else refuse_data(data)
Wait
timeout
start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1])
... udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1 If (base == nextseqnum)
stop_timer else
start_timer
Stan Kurkovsky
11
GBN: receiver extended FSM
default udt_send(sndpkt)
rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
L
expectedseqnum=1 sndpkt =
Wait extract(rcvpkt,data) deliver_data(data)
make_pkt(expectedseqnum,ACK,chksum)
sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt)
expectedseqnum++
• ACK-only: always send ACK for correctly-received pkt with highest in- order seq #
• may generate duplicate ACKs
• need only remember expectedseqnum
• out-of-order pkt:
• discard (don’t buffer) -> no receiver buffering!
• Re-ACK pkt with highest in-order seq #
Stan Kurkovsky
GBN in action
Stan Kurkovsky
12
Selective Repeat
• receiver individually acknowledges all correctly received pkts
• buffers pkts, as needed, for eventual in-order delivery to upper layer
• sender only resends pkts for which ACK not received • sender timer for each unACKed pkt
• sender window
• N consecutive seq #’s
• again limits seq #s of sent, unACKed pkts
Stan Kurkovsky
Selective repeat: sender, receiver windows
Stan Kurkovsky
13
Selective repeat
Sender
data from above :
• if next available seq # in window, send pkt
timeout(n):
• resend pkt n, restart timer ACK(n) in [sendbase,sendbase+N]:
• mark pkt n as received
• if n smallest unACKed pkt, advance window base to next unACKed seq #
Receiver
pkt n in [rcvbase, rcvbase+N-1]
• send ACK(n)
• out-of-order: buffer
• in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pkt
pkt n in [rcvbase-N,rcvbase-1]
• ACK(n)
otherwise:
• ignore
Stan Kurkovsky
Selective repeat in action
Stan Kurkovsky
14
Selective repeat: dilemma
Example:
• seq #’s: 0, 1, 2, 3
• window size=3
• receiver sees no difference in two scenarios!
• incorrectly passes duplicate data as new in (a)
Q: what relationship between seq # size and window size?
Stan Kurkovsky
15