Transcript Week3

Reliable Data Transfer
1
Reliable Data Transfer
 Problem: Reliability
 Want an abstraction of a reliable link even
though packets can be corrupted or get lost
 Solution: keep track of the packets
 Not as simple as one would expect
2
Themes
 Principles for Reliable transfer
 Protocols as State machines
 More Pipelining
 Protocols
 ABP, Go-back N, Selective repeat
3
Principles of Reliable data transfer
 important in app, transport, link layers
 top-10 list of important networking topics!
4
Reliable data transfer: getting started
rdt_send(): called from above,
(e.g., by app.). Passed data to
deliver to receiver upper layer
send
side
udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver
deliver_data(): called by
rdt to deliver data to upper
receive
side
rdt_rcv(): called when packet
arrives on rcv-side of channel
5
Reliable data transfer: getting started
 Consider only unidirectional data transfer
 but control info will flow on both directions!
 Characteristics of unreliable channel will
determine complexity of reliable data transfer
protocol (rdt)

incrementally develop sender, receiver sides of
reliable data transfer protocol (rdt)
6
Reliable transmission &Flow Control
 What to do when there is a packet loss?
 On the link (in the network)
 At the receiver (buffer overflow)
 Need to recoup losses
 What happens if the packet is lost in the network?
 A random event, retransmit
 What happens if the sender tries to transmit
faster than the receiver can accept?

Data will be lost unless flow control is implemented
7
Controlling the Flow of Data
Slow Joe
Fast Frank
8
Some Flow Control Algorithms
Flow control for the ideal network
 Stop and Wait for noiseless channels
 Stop and Wait for noisy channels
 Sliding window protocols
 Sliding window with error control

• Go Back N
• Selective Repeat
9
Flow control in the ideal
network
Assumptions:
Error free transmission link,
Infinite buffer at the receiver
No acknowledgement of frames necessary
Since the data link is error-free and the receiver can
buffer as many frames as it likes, no frame will ever
be lost
10
Flow control in the ideal
network (cont’d)
Slow Joe
Fast Frank
Infinite bucket
11
Stop and Wait with Noiseless
Channels
Assumptions:
Error free transmission link,
Finite buffer at the receiver
Problem of Buffer overflow at the receiver

Buffer overflow may happen at the receiver when
the sending router sends frames at a rate faster
than the receiving router
12
stop-and-wait operation
sender
receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R
RTT
first packet bit arrives
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
13
Performance of stop and wait
 example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:
Ttransmit =
U



L (packet length in bits)
8kb/pkt
=
= 8 microsec
R (transmission rate, bps)
10**9 b/sec
=
sender
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
U sender: utilization – fraction of time sender busy sending
1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link
network protocol limits use of physical resources!
14
Stop and Wait with Noiseless
Channels (cont’d)
Slow Joe
Fast Frank
Finite bucket
(once full, ball is lost)
15
Stop and Wait with Noiseless
Channels (cont’d)
 Solution: Stop-and-Wait
 The receiver sends an acknowledgement frame
telling the sender to transmit the next data
frame.
 The sender waits for the ACK, and if the ACK
comes, it transmits the next data frame.
 Use 0/1 as sequence numbers
 Also known as Alternating bit protocol (ABP)
16
Stop and Wait with Noiseless
Channels (cont’d)
Data
ACK
Data
17
Stop and Wait (cont’d)
 Note that we assume an error-free transmission
link and therefore ACK frames will not be lost
 In this flow control protocol, there are two types
of frames: data frames and ACK frames. The ACK
frames don’t contain any particular information,
since only the arrival of the ACK frame at the
sender is important.
18
Stop and Wait for Noisy Channels
Assumptions:
Transmission link may cause errors in frames,
Finite buffer at the receiver
ACK frames may now be lost
19
Problems introduced by a noisy line
Problem 1: Loss of a data or ACK frame

Since the transmission link is not error-free, a
data or ACK frame may be lost, causing the
sender to wait indefinitely for an ACK
20
Loss of an ACK frame
Data
ACK
error
?
21
Problems introduced by a noisy line
Can we solve problem 1 by introducing a timeout
period for the sender? Yes, but...
Problem 2: Duplicated frames

If the ACK frame for a certain data frame is lost, the
sender will retransmit the same frame after a time-out
period, and the receiver will then have two copies of the
same frame
22
Duplicated data frames
Data
ACK
Data
Duplicate data
Timed
Out
23
Stop and Wait for Noisy Channels
(cont’d)
 Solution:
 The sender uses a timer to retransmit data
frames when an ACK has not arrived
 The sender includes a sequence number in each
frame to distinguish one frame from another.
This way, the receiver knows when it has
received duplicate frames.
24
Stop and Wait for Noisy Channels
(cont’d)
Data
1
1
ACK
receiver
knows to
discard this
data
Data
1
Timed
Out
1
1
25
Is Stop and Wait the best we can
do?
Stop and Wait is an effective form of flow control, but…
It’s not very efficient.
1. Only one data frame can be in transit on the link at
time
2. When waiting for an acknowledgement, the sender
cannot transmit any frames
a
Better solution? Sliding Window
26
Pipelined protocols
Pipelining: sender allows multiple, “in-flight”, yet-tobe-acknowledged pkts
27
Sliding Window Protocols
Definitions
Sequence Number: Each frame is assigned a sequence number that is
incremented as each frame is transmitted
Sender Window: Keeps track of sequence numbers for frames that
have been sent but not yet acknowledged
Receiver Window: Keeps track of sequence numbers for frames the
receiver is allowed to accept
Maximum Sender Window size: The maximum number of frames the
sender may transmit without receiving any acknowledgements
Maximum Receiver Window size: The maximum number of frames the
receiver may receive before returning an acknowledgement to the
sender
28
Simple Sliding Window with
Window Size of 1
A sliding window with a maximum window size of 1 frame
7
0
1
6
Window for a 3-bit sequence number
2
5
4
3
29
Sliding Window example
Sender window
7
7
0
6
1
5
2
6
1
5
3
4
7
0
2
6
1
5
3
4
7
0
2
6
1
5
3
4
0
2
3
4
Receiver window
7
7
0
6
1
5
2
3
4
(a)
7
0
6
1
5
2
3
4
(b)
7
0
6
1
5
2
3
4
(c)
0
6
1
5
2
3
4
(d)
(a) Initial state, no frames transmitted, receiver expects frame 0
(b) Sender transmits frame 0, receiver buffers frame 0
(c) Receiver ACKS frame 0
(d) Sender receives ACK, removes frame 0
30
Simple Sliding Window with
Window size 1 (cont’d)
This protocol behaves identically to stop and
wait for a noisy channel
31
Sliding Window Protocols
General Remarks
 The sending and receiving windows do not necessarily have
the same maximum size
 Any frame whose sequence number falls outside the receiver
window is discarded at the receiver
 The sender window’s size grows and shrinks as frames are
transmitted and acknowledged
 Unlike the sender window, the receiver window always
remains at its maximum size
32
Sliding Window Protocols
Piggybacking Acknowledgements
Since we have full duplex transmission, we can “piggyback” an
ACK onto the header of an outgoing data frame to make
better use of the channel
When a data frame arrives at a router, instead of
immediately sending a separate ACK frame, the
router waits until it is passed the next data frame to
send. The acknowledgement is attached to the
outgoing data frame.
33
Sliding Window with
Maximum Sender Window Size WS
With a maximum window size of 1, the sender waits for an ACK
before sending another frame
With a maximum window size of WS, the sender can transmit up
to WS frames before “being blocked”
This allows the sender to transmit several frames before
waiting for an acknowledgement
34
Sender-Side Window with WS=2
7
7
0
6
1
5
2
6
1
5
3
4
2
6
7
1
5
2
3
4
1
5
2
6
7
1
5
2
3
4
(e)
(a) Initial window state
(b) Send frame 0
(c) Send frame 1
(d) ACK for frame 0 arrives
(f)
1
5
2
(d)
7
0
6
1
5
2
3
4
(g)
3
4
(c)
0
0
6
3
4
(b)
0
7
0
6
3
4
(a)
7
7
0
0
6
1
5
2
3
4
(h)
(e) Send frame 2
(f ) ACK for frame 1 arrives
(g) ACK for frame 2 arrives, send frame 3
(h) ACK for frame 3 arrives
35
Pipelining
Sliding window with WS > 1 is also called “pipelined”
communication
data stream
99
A
0
51
1
50
49
B
ACK stream
By allowing several frames onto the link before receiving
an acknowledgement, pipelining keeps the link from
being idle
36
Pipelining Example: increased
utilization
sender
receiver
first packet bit transmitted, t = 0
last bit transmitted, t = 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
RTT
ACK arrives, send next
packet, t = RTT + L / R
Increase utilization
by a factor of 3!
U
sender
=
3*L/R
RTT + L / R
=
.024
30.008
= 0.0008
microsecon
ds
37
Sliding Window with
Maximum Receiver Window Size WR
With a maximum window size of 1, the receiver must receive
and process every frame in sequence
With a maximum window size of WR, the receiver can receive
and process up to WR frames before acknowledging them
This is useful when frames are lost: the receiver can still
accept and buffer frames after the missing frame
38
Receiver-Side Window with WR=2
7
7
0
6
1
5
2
6
1
5
3
4
2
6
7
1
5
2
3
4
(e)
1
5
2
6
7
1
5
2
3
4
1
5
2
(f)
(a) Initial window state
(b) Nothing happens
(c) Frame 0 arrives, ACK frame 0
(d) Nothing happens
(d)
7
0
6
1
5
2
3
4
(g)
3
4
(c)
0
0
6
3
4
(b)
0
7
0
6
3
4
(a)
7
7
0
0
6
1
5
2
3
4
(h)
(e) Frame 1 arrives, ACK frame 1
(f) Frame 2 arrives, ACK frame 2
(g) Nothing happens
(h) Frame 3 arrives, ACK frame 3
39
What about Errors?
What if a data or acknowledgement frame is
lost when using a sliding window protocol?
Two Solutions:
Go Back N
Selective Repeat
40
Pipelined protocols - how?
Pipelining: sender allows multiple, “in-flight”, yet-tobe-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
41
Sliding Window with
Go Back N
 When the receiver notices a missing or erroneous
frame, it simply discards all frames with greater
sequence numbers and sends no ACK
 The sender will eventually time out and retransmit
all the frames in its sending window
42
Go Back N
Timeout interval
Sender
0
1
2
3
4
2
3
4
5
6
Maximum
window size = 8
Receiver
Maximum
window size = 8
0
1
E
D
D
2
3
4
5
6
Discarded by
receiver
Frame with
error
Time
43
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 seq # n - “cumulative ACK”
 timeout(n): retransmit pkt n and all higher seq # pkts in window
 One timer for all in-flight pkts
44
Go Back N (cont’d)
Go Back N can recover from erroneous or
missing frames
But…
It is wasteful. If there are errors, the
sender will spend time retransmitting
frames the receiver has already seen
45
Sliding Window with
Selective Repeat
The sender retransmits only the frame with errors
 The receiver stores all the correct frames that arrive
following the bad one. (Note that the receiver requires a
frame buffer for each sequence number in its receiver
window.)
 When the receiver notices a skipped sequence number, it
keeps acknowledging the last good sequence number
 When the sender times out waiting for an acknowledgement,
it just retransmits the one unacknowledged frame, not all its
successors.
46
Selective Repeat
Timeout interval
Sender
0
1
2
3
4
2
5
6
Maximum
window size = 8
Receiver
Maximum
window size = 8
0
1
E
3
4
2
5
6
Buffered by
receiver
Frame with
error
Time
47
Selective repeat: sender, receiver windows
48