Question

In a communication system, the transmission rate is 1Mbps, the two ways propagation delay is 1ms, and the processing delay is negligible. Given the frame length of nf=1250 bytes, ACK frame and frame overhead of 25 bytes, please find the Stop&Wait ARQ protocol efficiency with channel bit error rate of 10^-5 .

Answer 1

(a) The number of images that can be transmitted per second is
 images/second (1)
(b) The total time to get an acknowledgment from earth, assuming that is
 sec/img (2)
Note if each image is transmitted in a single block, becomes insignificant compared to .
(c) The difficulty here is that if we transmit an entire image as a single block, then the average
number of errors in a block is 48 x 108
 x 10-5 = 48000. Thus every transmission fails. Clearly we
need to transmit using a smaller frame size, say n. Qualitatively, the following happens as we vary
n. If n is very small, then the probability of frame error is small, but the overhead due to the
header no will become significant. If n becomes too large, then the efficiency drops because of
frequent retransmissions. Thus there must be an intermediate value of n that optimizes efficiency.
We will find this value by trial and error. We will assume a header overhead of 64 bits in a frame
of size n greater than 64 bits. Each frame carries n bits of information, so the required window
size for a propagation delay of 2.5 seconds is then Ws=2.5x106
/n+1 The probability of frame error
is then
10–5
n
10–6
100002
× 16 3 ×
-------------------------------------- 2.1 10–4 = ×
t
ACK t
f ≤
t
o t
f 2t
prop == = + 4800 2.5 + 4802.5
t
prop t
f
2
(3)
The efficiency for Go-Back-N is given by
(4)
Using similar assumptions, the efficiency of Selective Repeat ARQ is given by
(5)
The figure above shows the efficiency of Go-Back-N and Selective Repeat ARQ as a function
of frame size. Go-Back-N has very low efficiency (always below 10%) for all values of n. Selective Repeat achieves a maximum of about 95% efficiency at around n=2500 bits. Note that the
optimum value of n is dependent on the value of no.
Problem 2. Find the optimum frame length that maximized transmission efficiency for a channel with random bit errors by taking the derivative and setting it to zero for the following protocols:
(a) Stop-and-Wait ARQ
(b) Go-Back-N ARQ
(c) Selective Repeat ARQ
Pf 1 1 10–5 ( ) – n – 1 e n10–5 – = ≈ –
ηGBN
1 Pf ( ) – 1 64
n – -----    
1 Ws ( ) – 1 Pf + ---------------------------------------
1 64
n – -----     e n10–5 –
1 2.5 106
×
n ---------------------- 1 e n10–5 – + ( ) –
= = --------------------------------------------------------------
ηSR 1 Pf ( ) – 1 64
n – -----     1 64
n – -----     e n10–5 – = =
0 200 400 600 800 1000 1200 1400 1600 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Frame Size (bytes)
Transmission Efficiency
Transmission efficiency vs. frame size
Go-Back-N
Selective Repeat
nf
3
(d) Find the optimum frame length for a 1 Mbps channel with 10 ms reaction time, 25-byte overhead, 25-byte ACK frame, and , and .
[Solution]
(a) Stop-and-wait ARQ
(6)
Let ,
(7)
(8)
(9)
(b) Go-back-N ARQ
(10)
Let , and use the approximation (which
is valid when ), then
(11)
Take the derivative and equating the numerator to zero, we find that
(12)
which leads to the quadratic equation
(13)
which give the solution
(14)
(c) Selective repeat
p 10–4 = 10–5 10–6
η 1 Pb ( ) – nf nf no –
nf na 2 t
proc t
prop
+ + ( ) + R = -----------------------------------------------------------------
a 1 Pb = – b na 2 t
proc t
prop = + ( ) + R
nf d
d
a
nf
nf no –
nf + b --------------- a
nf a nf no [ ] ln ( ) – + 1 nf ( ) + b a
nf nf no – ( ) –
nf ( ) + b 2 = = -------------------------------------------------------------------------------------------------------- 0
nf
2 b no ( ) – nf
b no +
lna -------------- no + + – b = 0
nf
no – b b no ( ) – 2 4
b no +
lna -------------- no – b     ± –
2 = --------------------------------------------------------------------------------------------
η 1 Pb ( ) – nf nf no –
nf nf 1 1 Pb ( ) – nf [ ] – 2R tproc t
prop ( ) +
nf
+ ------------------------------------------
= ------------------------------------------------------------------------------------------------
a 1 Pb = – b 2R tproc t
prop = ( ) + 1 1 Pb ( ) – nf – nf
Pb ≈
nf
Pb « 1
η
a
nf nf no ( ) –
nf 1 Pb ( ) + b = ----------------------------
a
nf nf no ( ) – lna a
nf ( ) + nf a
nf nf no – ( ) –
nf
2
---------------------------------------------------------------------------------------------- 0 =
nf
2
nonf – no + ⁄ lna = 0
nf
no no. Does the receiver send an OFF signal to avoid packet loss at any of these time
instants?
a. 1.025 sec
Table 1: Optimum packet size
Pb 10-4 10-5 10-6
Stop-and-wait 7550 36304 133190
Go-back-N 1517 4573 14240
Selective Repeat 1517 4573 14240
η 1 Pb ( ) – nf 1
no
nf
– -----       =
nf d
dη = 0
nf
2
nf
no – no 1 Pb + ⁄ ln( ) – = 0
nf
no no
2 4no 1 Pb + – ⁄ ln( ) –
2 ------------------------------------------------------------------
no no
2 4no
lna
+ – --------
2 = = ------------------------------------ a 1 Pb = –
R 106 =
no = 200
na = 200
Pb 10–4 10–5 10–6 = , ,
a 1 Pb = –
t
proc t
prop
+ = 10
b na 2 t
proc t
prop = = + ( ) + R 20200
Rrcv
t=0 t=1sec
Rrcv = 1.5Mbps Rrcv = 0.7Mbps
t=2sec
Rrcv = 1.5Mbps
5
b. 1.06 sec
c. 2.06 sec
d. 1.13 sec
2. How full is the receiver buffer at t=1sec?
a. 4000 bytes
b. 6000 bytes
c. 10000 bytes
d. 2 frames
[Solution]
When the buffer at the receiver has only bytes left, it will send an OFF signal. This number is bytes.
The sender sends at 1.5Mbps and the receiver empties its buffer at the same rate up to t=1 sec.
From 1 sec, the latter rate drops to 0.7Mbps. Therefore it will take
µs for the receiver buffer to reach a point when there is only
space for 4000 bytes left in the buffer. Therefore at t=1sec+60ms, the receiver will generate an
OFF signal.
Answer to part 2 is 0 bytes since the receiver buffer is being depleted at the same rate as the
sender.
2t
prop Rsnd Rrcv ( ) –
2 20 0.8 103
× × ×
8 ------------------------------------------- 4000 =
t ( ) 10000 4000 – × 8
( ) 1.5 0.7 – = = ---------------------------------------------- 60000
2 4no
lna
+ – --------
2 = ------------------------------------
4
(15)
 leads to
, then (16)
, where . (17)
(d)
 ms
Problem 3. A data-link layer protocol that uses ON/OFF control executes on a 1.5Mbps link. The
sender emits data at this full data rate and uses frames of size 1000 bytes. One-way propagation
delay is 20ms. The rate at which the receiver empties its buffer, , is shown in the figure below
for different time intervals. Assume the receiver buffer siz