Internet 101
Download
Report
Transcript Internet 101
Transmission & Error control
ARQ
Giuseppe Bianchi
Two scenarios
network
End to End
(transport protocol issue)
Hop by Hop
(datalink protocol issue)
Giuseppe Bianchi
Coping with rx errors
Forward Error Correction
Extra overhead capable of CORRECTING errors
Large overhead depending on protection capability
Retransmission
Extra overhead capable of DETECTING errors
Small constant overhead (2-4 bytes)
Called:
» Frame Check Sequence
» Cyclic Redundance Check
Giuseppe Bianchi
Retransmission scenarios
referred to as ARQ schemes (Automatic Retransmission reQuest)
COMPONENTS: a) error checking at receiver; b) feedback to sender; c) retx
SRC
SRC
DST
DST
Error
Check:
OK
Error
Check:
corrupted
Automatic
retransmit
Basic ACK idea
SRC
Basic NACK idea
SRC
DST
DST SRC
Retx
Timeout
(RTO)
DST
Error
Check:
corrupted
Basic ACK/Timeout idea
Giuseppe Bianchi
Sequence numbers – a must
Sender side:
Receiver side:
RTO
DATALINK
or
NETWORK
(ACK lost)
rtx
Need to univocally “label” all packets circulating
in the network between two end points.
1 bit (0-1) enough for Stop-and-wait
Giuseppe Bianchi
New data?
Old data?
Link-level model
C bits/sec
In e2e scenario, C approximated by bottleneck link rate
Stop & Wait
one frame/packet at a time
Pipelining (continuous ARQ)
more than one frame/packet
Giuseppe Bianchi
Stop & Wait
Giuseppe Bianchi
sender
receiver
stop-and-wait
One way delay
MSG/C
RTT
ACK/C
For simplicity all MSG of same
size; extension to != size use
mean value
MSG
thr
RTT MSG / C ACK / C 2
time
time
Giuseppe Bianchi
REMARK: throughput always lower than
Available link rate!
Upper bound
No processing
= 0
ACK size negligible
ACK = 0
MSG
thr
RTT MSG / C
1
efficiency thr / C
1
RTT
1
MSG / C
Giuseppe Bianchi
stop-and-wait: upper bound /1
MSG = 1500 bytes
Under-utilization with: 1) high capacity links, 2) large RTT links
Giuseppe Bianchi
stop-and-wait: upper bound /2
MSG = 1500 bytes
Under-utilization with: 1) high capacity links, 2) large RTT links
Giuseppe Bianchi
Example
MSG = 1500 bytes
RTT = 10 ms
RTT=100 ms
Link rate (kbps) throughput efficiency throughput efficiency
33
32,12
97,32%
25,88
78,43%
128
115,66
90,36%
61,94
48,39%
1.000
545,45
54,55%
107,14
10,71%
10.000
1071,43
10,71%
118,58
1,19%
100.000
1185,77
1,19%
119,86
0,12%
1.000.000
1198,56
0,12%
119,99
0,01%
INFINITE
1200,00
N/A
120,00
N/A
MSG
MSG
thr lim
C RTT MSG / C
RTT
Giuseppe Bianchi
Dealing with errors
sender
receiver
IMPORTANT ISSUE: setting the Time Out right!
Too short unnecessary rtx
Too short inconsistent protocol operation
Too long waste of time
TO
Ideally: TO = RTT+ACK/C
(+2 )
Easy to say, but harder to do if RTT is not
known (e.g. in e2e scenario)
Giuseppe Bianchi
Inconsistent protocol operation
sender
receiver
M=1
M=2 will be NEVER received!
M=1
Consequence: ACK MUST be also numbered
To always guarantee consistent operation
TO
M=2
M=3
Giuseppe Bianchi
Performance with loss
(upper bound)
No processing time, negligible ACK
Per packet loss probability P
Assumed indipendent
P(immediate success) = (1-P)
P(success at second tx) = P(1-P)
P(success at third tx) = P2(1-P)
size of message
MSG
thr
E[message delivery time] E[# tx] ( RTT MSG / C )
MSG
MSG (1 P)
1
( RTT MSG / C ) RTT MSG / C
1 P
Giuseppe Bianchi
Pipelining
(Continuous ARQ)
Giuseppe Bianchi
Pipelining idea
Up to W>1 frames can be “in fly”
In fly = frames transmitted but not yet ACKed
Sliding Window
Size W
Window “slides” forward at each received
ACK
Giuseppe Bianchi
Pipelining cases
RTT
(+1tx)
W=4
?
W=10
time
time
WINDOW SIZING that allows
UNDER-SIZED
WINDOW: THROUGHPUT INEFFICIENCY CONTINUOUS TRANSMISSION
W MSG
thr min C ,
RTT MSG / C
Giuseppe Bianchi
Continuous transmission /1
Condition in which link rate is fully utilized
MSG
W
C
Time to transmit
W frames
Giuseppe Bianchi
MSG
RTT
C
Time to receive
Ack of first frame
Example
2 ms
MSG=500 bytes
W=4
C= 2 Mbps
Propagation = 16 ms
16 ms
Question 1: assuming no errors, compute
time needed to transmit K=6 messages.
4 ms
MSG
MSG
K 1
TTX
RTT
1
K
1
RTT 16 ms
mod W
W
C
C
Question 2: which min message size for continuous tx?
W MSG MSG
RTT
C
C
MSG
Giuseppe Bianchi
RTT C
W 1
1334 bytes
Continuous transmission /2
We may elaborate:
W MSG RTT C MSG RTT C
Condition in which link rate is fully utilized
Wbit
C RTT
W x MSG =
W expressed in “bit”
Bandwidth-delay
product
Conclusion: full link utilization is possible when window size (in bits) is
greater than the bandwidth (C bit/s) delay (RTT s) product!
Giuseppe Bianchi
Bandwidth-delay product
D
C
Network: like a pipe
C [bit/s] x D [s]
number of bits “flying” in the
network
number of bits injected in the
network by the tx, before that
the first bit is rxed
64Kbps
A 15360 (64000x0.240) bits
“worm” in the air!!
bandwidth-delay product = no of bytes that saturate network pipe
Giuseppe Bianchi
Long Fat Networks
LFNs (el-ef-an(t)s): large bandwidth-delay product
NETWORK
Ethernet
T1, transUS
T1 satellite
RTT (ms)
3
60
480
rate (kbps)
10.000
1.544
1.544
BxD (bytes)
3.750
11.580
92.640
T3 transUS
Gigabit transUS
60
60
45.000
1.000.000
337.500
7.500.000
Giuseppe Bianchi
Throughput with pipelining
MSS = 1500 bytes
Giuseppe Bianchi
Maximum achievable throughput
(assuming infinite speed link…)
Wbytes = 65535
Giuseppe Bianchi
ARQ protocols
details
Giuseppe Bianchi
Go Back N protocol
Sequence number:
b bits
N=2b values
Repeated modulo N
Sender window
Ws=N-1 number of possible sequence numbers minus 1
Receiver rules
RX: accept frames only if received in strict sequence!!
If out of order frame, reply with NACK
NACK(i) = I have received ALL frames up to
(i-1) mod N, but I haven’t received i-th frame
Giuseppe Bianchi
GBN example
4 5 6 7 0 1 2 3 4 5 6 7
4
4 5 6 7 0 1 2 3 4 5 6 7
5
4 5 6 7 0 1 2 3 4 5 6 7
6
4
4 5 6 7 0 1 2 3 4 5 6 7
7
5
4 5 6 7 0 1 2 3 4 5 6 7
0
6
4 5 6 7 0 1 2 3 4 5 6 7
1
4 5 6 7 0 1 2 3 4 5 6 7
2
4 5 6 7 0 1 2 3 4 5 6 7
3
4 5 6 7 0 1 2 3 4 5 6 7
7
4 5 6 7 0 1 2 3 4 5 6 7
0
4 5 6 7 0 1 2 3 4 5 6 7
1
4 5 6 7 0 1 2 3 4 5 6 7
Giuseppe Bianchi
NACK 7
7
Piggybacking
Frame 1
ACK =
overhead on
return channel
Idea: embed
ACK inside a
frame
transmitted on
the opposite
direction
Frame 2
ACK 2
Important: cumulative ACK!
ACK 2 = ACK frame 2 + frame 1 + all previous
Giuseppe Bianchi
Why Ws = N-1?
W=N=4
Frame X-1
= ACK 1
Frame 2
Frame 3
Frame 2
Frame 3
Frame 0
Frame 0
Frame 1
Frame 1
W=N=4
Frame X
= ACK 1
All successful OR all lost???????????????
Giuseppe Bianchi
Frame X-1
= ACK 1
Frame X
= ACK 1
Selective Repeat
Key RX difference:
Received frames
buffered also if out of
order
New parameter:
Receiver Window Wr
New window sizing
rule:
GBN: Ws < N
SR: Ws + Wr ≤ N
GBN = special case Wr=1
Giuseppe Bianchi
N=4; Ws=3; Wr=2 Rx window
2
2 3 0 1 2 3
3
2 3 0 1 2 3
0
2 3 0 1 2 3
2 3 0 1 2 3
ACK 0
TO
2 reTX
NEW!!
Choice of windows
N=8
Wr > 4 not useful
not enough “in-fly” frames since Ws<4
Ws > 4 out of order may harm
not enough RX window size to capture all
possible out of order cases
Most appropriate choice: Wr=Ws=4
but remember throughput limits, though!
Giuseppe Bianchi
SR example and TX operation
4 5 6 7 0 1 2 3 4 5 6 7
4
4 5 6 7 0 1 2 3 4 5 6 7
5
4 5 6 7 0 1 2 3 4 5 6 7
6
4
4 5 6 7 0 1 2 3 4 5 6 7
7
5
4 5 6 7 0 1 2 3 4 5 6 7
0
6
4 5 6 7 0 1 2 3 4 5 6 7
1
4 5 6 7 0 1 2 3 4 5 6 7
2
4 5 6 7 0 1 2 3 4 5 6 7
3
4 5 6 7 0 1 2 3 4 5 6 7
7
4 5 6 7 0 1 2 3 4 5 6 7
4
4 5 6 7 0 1 2 3 4 5 6 7
4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3
Giuseppe Bianchi
5
6
NACK 7
ACK 3 7,0,1,2,3