Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

9.3 Go-Back-N (GBN ARQ) Protocol 309

9.3.1 Modeling the GBN ARQ Protocol

In this section, we perform Markov chain analysis of the GBN ARQ protocol. We

make the following assumptions for our analysis of the go-back-N protocol.

1. Each window contains N frames.

2. The average length of a frame is n bits.

3. The forward channel has random noise and the probability that a bit will be

received in error is . Another name for  is bit error rate (BER).

4. The feedback channel is assumed noise-free so that acknowledgment signals

from the receiving station will always be transmitted to the sending station.

5. The maximum number of retransmissions is k

after which the sender will de-

clare the channel to be not functioning.

The state of the sender while attempting to transmit a frame depends only on the

outcome of the frame just sent. Hence we can represent the state of the sender as a

Markov chain having the following properties:

1. The states of the Markov chain are grouped into the sets T , R

, R

, etc. These

sets are explained below.

2. The number of states is infinite since no upper bound is placed on the number of

retransmissions.

3. The time step is taken equal to the sum of transmission delay of one frame

T = τ

. Thus, a window that contains N frames will require N time steps to

be transmitted.

The set T represents the states of the sender while it is transmitting a window for

freshly arrived N frames:

T =



···t



(9.16)

The set R

represents the states of the sender while it is retransmitting frames for

the first time due to a damaged or lost frame. This set is the union of several subsets

= R

1,1

∪ R

1,2

∪···∪R

1,N

(9.17)

where subset R

1,i

is the subset of R

that contains i states corresponding to retrans-

mitting i frames for the first time. In other words, the first N −i frames have been

correctly received. With the help of (9.23) below, we can verify that all states in

subset R

1,i

are equal so that we can write the i states associated with R

1,i



1,i

···r

1,i



(9.18)

310 9 Modeling Error Control Protocols

Thus R

has N unique subsets such that subset R

1,i

has i equal states r

1,i

1,1

corresponding to last frame in error

1,2

corresponding to frame before last in error

1,N

corresponding first frame in error

Similarly, the set R

represents the states of the sender while it is retransmitting

frames for the second time. This set is the union of several subsets

= R

2,1

∪ R

2,2

∪···∪R

1,N

(9.19)

where subset R

2,i

is the subset of R

that contains i states corresponding to retrans-

mitting i frames for the second time. With the help of (9.23), we can verify that

all states in subset R

2,i

are equal so that we can write the i states associated with

2,i



2,i

···r

2,i



(9.20)

Thus R

has N unique subsets such that subset R

2,i

has i equal states r

2,i

2,1

corresponding to last frame in error

2,2

corresponding to frame before last in error

2,N

corresponding first frame in error

The state transition diagram for the GBN ARQ protocol is shown in Fig. 9.4. The

sets of states T , R

, and R

are shown. To reduce clutter, only transitions in and out

of R

are indicated. The thick lines indicate multiple transitions lumped together.

However, (9.23) shows all the transitions between states.

In the figure, all states in each column are equal due to the fact that the transition

probabilities between them is 1.

Fig. 9.4 State transition

diagram of a sending station

using the GBN ARQ error

control protocol. Only

transitions in and out of R

are indicated

...

First set of

retransmit

states

Second set of

retransmit

states

9.3 Go-Back-N (GBN ARQ) Protocol 311

We organize the state distribution vector in the following order:

s =



T R

···



(9.21)

For the case when N = 2, the distribution vector can be written as

s =



tt | r

1,1

1,2

| r

2,1

2,2

| ···



(9.22)

The corresponding transition matrix of the sender for the case when N = 2is

given by

P =

⎡

⎢

⎣

0 p

2,0

1,0

0 p

2,0

1,0

0 p

2,0

···

10 000 000···

0 p

2,1

000 000···

0 p

2,2

000 000···

00 010 000···

00p

1,1

0 p

2,1

000···

00 00p

2,2

000···

00 000 010···

⎤

⎥

⎦

(9.23)

In the above matrix, the transition probability p

i, j

is the probability that the last

j frames need to be retransmitted, given that a frame of i frames was sent. For

instance, p

5,2

indicates the probability that the last two frames have to be retrans-

mitted, given that five frames were sent and the first three frames were received

without error. p

i, j

is given by the expression

i, j

(

1 −e

)

i−j

e (9.24)

where e is the probability that a frame contained one or more errors:

e = 1 −(1 −)

(9.25)

At equilibrium, the distribution vector is obtained by solving the two equations

Ps = s (9.26)



s = 1 (9.27)

When k

is the maximum number of retransmissions, the dimension of s would

be given by

dim (s) = N +

N(N +1)

(9.28)

312 9 Modeling Error Control Protocols

As an example, for a window size N = 32 frames and the maximum number

of retransmissions is k

= 16, the size of s would be 33,344 and the state transi-

tionmatrixwouldbeofsize33, 344 × 33, 344. We can use MATLAB to find the

distribution vector s.

9.3.2 Using Iterations to Find s

An alternative approach is to find s using iterations. From the structure of the matrix

P, we can easily prove that all transmit states in the set T are equal:

t = t

= t

=···=t

(9.29)

In fact, all states in any column of the matrix are equal. For example, we can

write the N unique states of R

1,N

= tp

N,N

(9.30)

1,N −1

= tp

N,N−1

(9.31)

1,N −2

= tp

N,N−2

(9.32)

1,1

= tp

N,1

(9.33)

In general, we have

1, j

= tp

N, j

j = 1, 2,..., N (9.34)

In that case, state r

1,1

will be repeated once. State r

1,2

will be repeated twice, and

finally r

1,N

will be repeated N times.

For the rest of the retransmission states, we use iterative expressions as follows.

The N unique states of R

are expressed in terms of the unique states of R

2,N

= r

1,N

N,N

(9.35)

2,N −1



i=N−1

1,i

i,N−1

(9.36)

2,N −2



i=N−2

1,i

i,N−2

(9.37)

2,1



i=1

1,i

i,1

(9.38)

9.3 Go-Back-N (GBN ARQ) Protocol 313

In general, we have

2, j



i=j

1,i

i, j

j = 1, 2, ..., N (9.39)

The states associated with the kth retransmission R

are given by the iterative

expression

k, j



i=j

k−1,i

i, j

k = 2, 3,...

j = 1, 2,...,N

(9.40)

with the initial condition

1, j

= tp

N, j

j = 1, 2, ··· N (9.41)

9.3.3 Algorithm for Finding s by Iterations

The above iterations express all the retransmission states in terms of the transmit

state t. In order to find the distribution vector s, we follow this algorithm:

1. Assign to each transmit state some value, for example,

t = 1 (9.42)

2. Estimate the retransmit states for R

using the iterative expression (9.34).

3. Estimate the values of the other retransmit states R

using the iterative

expression (9.40).

4. Find the sum of all states

S = Nt+



k=1



j=1

k, j

(9.43)

5. The normalized value of the distribution vector is given by the following

equation:

s =



tt | r

1,1

1,2

| r

2,1

2,2

| ···



(9.44)

314 9 Modeling Error Control Protocols

9.3.4 GBN ARQ Performance

As long as the sender keeps retransmitting frames that were received in error, the

next frame cannot be sent. Therefore, we are interested in estimating the average

number of retransmissions for a given frame (R

), the average number of frames

sent in each retransmission attempt (N

), and the average delay a frame takes to be

transmitted when errors are present (T

Estimating average number of retransmissions R

The probability that the source is in the kth retransmission state is given by



j=1

k, j

(9.45)

is also equal to the average number of frames sent at the kth retransmission

The average number of retransmissions by the source for a given frame is

given by



k=1

k α

(9.46)

Estimating average delay T

The delay associated with the kth retransmission is given by the accumulation of all

the frames that were previously sent by earlier retransmissions. Thus, we can write



j=1

(9.47)

The average delay for transmitting a given frame is given by



k=1

(9.48)

Estimating the average number of frames sent N

The average number of frames sent due to all retransmissions is given by



k=1

(9.49)

9.3 Go-Back-N (GBN ARQ) Protocol 315

GBN ARQ efficiency η and throughput (Th)

The efficiency of the GBN ARQ protocol is the ratio of frame size to the total

number of frames transmitted:

η =

N + N

(9.50)

When there are no errors, N

= 0 and we get 100% efficiency.

The throughput of the transmitter can be expressed as

Th = η frames/time step (9.51)

Thus for an error-free channel, η = 1 and arriving frames are guaranteed to be

transmitted on the first try.

When errors are present in the channel, η<1 and so is the system throughput.

Example 9.2 Assume a GBN ARQ protocol with the following parameters.

n = 500 bits

N = 8 frames

 = 10

−4

= 16

Find the performance of the GBN ARQ protocol for this channel.

Using the technique in Section 9.3.2, the average number of retransmissions for

a given frame is

= 0.2195

the average delay for a given frame is

= 0.0306

the average number of retransmitted frames for a given frame is

= 0.026

and the efficiency is

η = 99.68%

316 9 Modeling Error Control Protocols

9.4 Selective-Repeat (SR ARQ) Protocol

The selective-repeat protocol is a general strategy for handling frame transmis-

sion errors when the round-trip time for frame transmission and reception of the

acknowledgment is comparable to frame transmission time. SR ARQ is used by

the TCP transport protocol. In this protocol, the transmitter groups the frames into

windows so that each window contains N frames. When the sender sends frames

within a window, the receiver stores the frames of the current window and checks

for errors. After a complete window has been received, or after the proper timeout

period, the receiver instructs the transmitter to resend only the frames that contained

errors. That results in a more efficient protocol compared to GBN ARQ that resends

frames in error as well as error-free frames.

Figure 9.5 shows an example of transmitting several frames using selective-

repeat protocol where the buffer size is N = 3. Solid arrows indicate ACK signals

and grey arrows indicate NAK signals. Frame 1 was correctly received while frame

2 was received in error. We see that the transmitter starts to send frame 2 as soon as

the corresponding NAK is received. Frame 4 was also received in error, and we can

see that it is retransmitted as soon as its NAK signal was received.

9.4.1 Modeling the SR ARQ Protocol

In this section, we perform Markov chain analysis of the SR ARQ protocol. We

make the following assumptions for our analysis of the selective-repeat protocol.

1. Each window contains N frames.

2. The average length of a frame is n bits.

3. The forward channel has random noise and the probability that a bit will be

received in error is . Another name for  is bit error rate (BER).

4. The feedback channel is assumed noise-free so that acknowledgment signals

from the receiving station will always be transmitted to the sending station.

5. The maximum number of retransmissions is k

after which, the sender will de-

clare the channel to be not functioning.

Fig. 9.5 Selective-repeat

ARQ protocol with buffer

size N = 3. Solid arrows

indicate ACK signals and

grey arrows indicate NAK

signals

...

1 2

Window Size

Receiver

Transmitter

Channel

Time

3 4 2 5 4 6 8

Error Error

9.4 Selective-Repeat (SR ARQ) Protocol 317

The state of the sender while attempting to transmit a frame depends only on the

outcome of the frame just sent. Hence we can represent the state of the sender as a

Markov chain having the following properties:

1. The states of the Markov chain are grouped into the sets T , R

, R

, etc. These

sets are explained below.

2. The number of states is infinite since no upper bound is placed on the number of

retransmissions.

3. The time step is taken equal to the sum of transmission delay of one frame

T = τ

. Thus, a window that contains N frames will require N time steps to

be transmitted.

The set T represents the states of the sender while it is transmitting a window for

freshly arrived N frames:

T =



··· t



(9.52)

The set R

represents the states of the sender while it is retransmitting frames for

the first time. This set is the union of several subsets

= R

1,1

∪ R

1,2

∪···∪R

1,N

(9.53)

where subset R

1,i

is the subset of R

that contains i states corresponding to re-

transmitting i frames for the first time. With the help of (9.59), we can verify that

all states in subset R

1,i

are equal so that we can write the i states associated with

1,i



1,i

··· r

1,i



(9.54)

Thus R

has N unique states:

1,1

repeated once,

1,2

repeated twice,

1,N

repeated N times.

Similarly, the set R

represents the states of the sender while it is retransmitting

frames for the second time. This set is the union of several subsets

= R

2,1

∪ R

2,2

∪···∪R

1,N

(9.55)

where subset R

2,i

is the subset of R

that contains i states corresponding to retrans-

mitting i frames for the second time. With the help of (9.59), we can verify that all

states in subset R

2,i

are equal so that we can write the i states associated with R

2,i



2,i

··· r

2,i



(9.56)

318 9 Modeling Error Control Protocols

Fig. 9.6 State transition

diagram of a sending station

using the SR ARQ error

control protocol. Only

transitions in and out of R

are indicated

...

First set of

retransmit

states

Second set of

retransmit

states

Thus R

has N unique states:

2,1

repeated once,

2,2

repeated twice,

2,N

repeated N times.

The state transition diagram for the SR ARQ protocol is shown in Fig. 9.6. The

sets of states T , R

, and R

are shown. To reduce clutter, only transitions in and out

of R

are indicated. The thick lines indicate multiple transitions lumped together.

However, (9.59) shows all the transitions between states.

In the figure, all states in each column are equal due to the fact that the transition

probabilities between them is 1.

We organize the state distribution vector in the following order:

s =



T R

···



(9.57)

For the case when N = 2, the distribution vector can be written as

s =



tt | r

1,1

1,2

| r

2,1

2,2

| ···



(9.58)

The corresponding transition matrix of the sender for the case when N = 2is

given by