Gebali F. Analysis Of Computer And Communication Networks

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

9.4 Selective-Repeat (SR ARQ) Protocol 319

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 000 000···

00p

1,1

0 p

2,1

000···

00 00p

2,2

000···

00 000 010···

⎤

⎥

⎦

(9.59)

In the above matrix, the transition probability p

i, j

is the probability that j frames

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

5,2

indicates the probability that two frames have to be retransmitted, given that five

frames were sent. p

i, j

is given by the expression

i, j





(

1 −e

)

i−j

(9.60)

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

e = 1 −(1 −)

(9.61)

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

Ps = s (9.62)



s = 1 (9.63)

When k

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

be given by

dim (s) = N +

N(N +1)

(9.64)

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.

320 9 Modeling Error Control Protocols

9.4.2 SR 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.65)

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

given by



k=1

k α

(9.66)

Estimating average delay T

The average number of frames sent at the kth retransmissions is given by



j=1

k, j

(9.67)

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.68)

The average delay for transmitting a given frame is given by



k=1

(9.69)

Estimating the average number of frames sent N

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



k=1

(9.70)

9.4 Selective-Repeat (SR ARQ) Protocol 321

SR ARQ efficiency η and throughput (Th)

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

of frames transmitted:

η =

N + N

(9.71)

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.72)

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.3 Assume an SR ARQ protocol with the following parameters.

n = 500 bits

N = 8 frames

e = 10

−4

= 16

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

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

a given frame is

= 0.37

the average delay for a given frame is

= 0.14

the average number of retransmitted frames for a given frame is

= 0.13

and the efficiency is

η = 98.41%

Comparing these results with those of GBN ARQ, we note that SR ARQ per-

forms better for the same parameters.

322 9 Modeling Error Control Protocols

Problems

Stop-and-Wait Automatic-Repeat-Request (SW ARQ) Protocol

9.1 Prove that the probability e that a frame in the SW ARQ protocol is in error is

e ≈  n when   1.

9.2 One of the assumptions in Section 9.2.1 of the SW ARQ protocol was that the

sender will keep retransmitting the frame until it is correctly received. Assume

the maximum number of retransmissions is limited to k

. How will this impact

the state transition diagram, state transition matrix, the distribution vector, and

the system performance?

9.3 Assume a SW ARQ protocol in which the frame size is 100 bits and the prob-

ability that a received frame is in error is  = 10

−5

. Find the performance of

the protocol.

9.4 Assume a forward error control (FEC) coding is used such that the receiving

station can correctly decode a received frame if the number of errors does not

exceed k errors. Obtain an expression for the frame error probability e under

this scheme and compare the expression you get to Equation (9.2).

9.5 Assume a SW ARQ protocol in which the frame size is n bits but forward

error correction (FEC) is used to improve the performance. The FEC code

employed can correct only up to k = 3 bits in error.

1. Draw the transition diagram for such a protocol and compare with the stan-

dard SW ARQ protocol discussed in the text.

2. Derive the transition matrix and compare with the standard SW ARQ

protocol.

3. Estimate the performance of this protocol and compare with the standard

SW ARQ protocol.

9.6 Equations (9.11) and (9.13) indicate that SW ARQ performance will not

change if we scale n to αn, where α>1, and decrease  by the same scale

factor /α when   1. Verify these assertions using SW ARQ parameters of

n = 100,  = 10

−4

9.7 Assume SW ARQ where the sender has a transmit buffer of size B. Study the

sender transmit buffer.

GBN ARQ Protocol

9.8 Obtain the transition matrix for the GBN ARQ protocol having the following

parameters (chosen to make the problem manageable):

N = 3 k

= 1

Problems 323

Assume two cases of the channel: a very noisy channel ( = 0.01) and for

a less noisy channel ( = 10

−5

). Compare the two matrices and state your

conclusions.

9.9 Given a GBN ARQ protocol in which the window size is N = 20 frames

and the probability that a received frame is in error is e = 10

−4

,findthe

performance of such a protocol for this channel assuming k

= 8.

9.10 Given a GBN ARQ protocol in which the window size is N = 20 frames

and the probability that a received frame is in error is e = 5 ×10

−4

,findthe

performance of such a protocol for this channel.

9.11 Assume the GBN ARQ protocol is now modified such that if the received

window contained one or more frames in error, then the whole window is

discarded and a request is issued to retransmit the entire window again.

This is repeated for a maximum of k

times until an error-free window is

received.

1. Identify the states of this system.

2. Write down the transition matrix.

3. The transition matrix that results will be reducible. Derive the steady-state

distribution vector.

Selective-Repeat (SR ARQ) Protocol

9.12 Obtain the transition matrices for the SR ARQ protocol having the following

parameters (chosen to make the problem manageable):

N = 3 k

= 1

Assume two cases of the channel: a very noisy channel (e = 0.01) and for

a less noisy channel (e = 10

−5

). Compare the two matrices and state your

conclusions.

9.13 Given a SR ARQ protocol in which the window size is N = 20 frames and the

probability that a received frame is in error is e = 10

−4

, find the performance

of such a protocol for this channel assuming k

= 8.

9.14 Given a SR ARQ protocol in which the window size is N = 20 frames and

the probability that a received frame is in error is e = 5 × 10

−4

,findthe

performance of such a protocol for this channel.

9.15 Consider a SR ARQ protocol where forward error correction (FEC) coding is

employed. In that scheme, the sender adds extra correction bits to each frame

or frame. The receiver is thus able to correct frames that have up to two errors

per window. Draw the transition diagram for this system and compare with the

SR ARQ protocol discussed in this chapter. Derive the relevant performance

for this modified protocol.

9.16 In the SR ARQ protocol discussed in the test, when a window is received with

i errors, the i frames are retransmitted until all of them are received without

324 9 Modeling Error Control Protocols

any errors. Now consider the case when the receiver only requests to retransmit

j frames out of the i frames that contained i errors originally. Do you expect

this protocol to perform better than the SR ARQ protocol discussed in text?

References

1. S. Lin, D.J. Costello, Jr., and M.J. Miller, “Automatic-repeat-request error-control schemes”,

IEEE Communications Magazine, vol. 22, no. 12, pp. 5–17, 1984.

Chapter 10

Modeling Medium Access Control Protocols

10.1 Introduction

In this chapter, we illustrate how to develop models for several medium access

control (MAC) protocols that are commonly used in computer communications. We

will model the following medium access protocols:

1. IEEE Standard 802.1p: The static priority scheduling algorithm

2. Pure ALOHA

3. Slotted ALOHA

4. IEEE Standard 802.3: carrier sense multiple access with collision detection

(CSMA/CD)

5. Carrier sense multiple access with collision avoidance (CSMA/CA)

6. IEEE Standard 802.11: for ad hoc wireless LANs using the distributed coordina-

tion function (DCF)

7. IEEE Standard 802.11: for infrastructure wireless LANs using the point coordi-

nation function (PCF) and a p-persistent backoff strategy

8. IEEE Standard 802.11: for infrastructure wireless LANs using the point coordi-

nation function (PCF) and a 1-persistent backoff strategy

The static, or fixed, priority scheduling algorithm is lumped with media access

algorithms since static priority is also used as a medium access protocol. Because

MAC belongs to the data link layer, our unit of data transfer is the frame since

packets are the business of the higher layer like the network layer and above.

Modeling a protocol is just like designing a digital system, or any system for that

mater—There are many ways to model a protocol based on the assumptions that

one makes. Our motivation here is simplicity and not taking a guided tour through

the maze of protocol modeling. Our recommendation to the reader is to read the

discussion on each protocol and then lay down the outline of a model that describes

the protocol. The model or models developed here should then be compared with

the one attempted by the reader.

F. Gebali, Analysis of Computer and Communication Networks,

DOI: 10.1007/978-0-387-74437-7

10,



Springer Science+Business Media, LLC 2008

325

326 10 Modeling Medium Access Control Protocols

10.2 IEEE Standard 802.1p: Static Priority Protocol

The IEEE 802.1p is based on the static priority scheduling algorithm. IEEE 802.1p

standard has a priority scheme such that frames queued in a lower priority queue are

not sent if there are frames queued in higher priority queues. The frames are sent

only when all higher priority queues are empty. In that sense, the static priority pro-

tocol is a scheduling protocol to provide access to an outgoing link among several

competing queues.

The IEEE 802.1p enables creating priority classes for network traffic. This en-

ables quality of service (QoS) support. The analysis given here provides insight into

how to use Markov chains to derive important performance figures.

10.2.1 Modeling the IEEE 802.1p: Static Priority Protocol

In this section, we assume there are N priority classes and each class has its own

queue to store incoming traffic for that class. The state of each queue depends only

on its immediate past history and we can model the queues using Markov chain

analysis. To start our analysis, we employ the following assumptions:

1. The states of the Markov chain represent the occupancy of the priority queues.

2. The time step is taken equal to the transmission delay of a frame.

3. There are N priority classes, with class 1 having the highest priority and so on

till class N which has the lowest priority.

4. The size of the queue in priority class i is equal to B

5. a

is the frame arrival probability for queue i.

6. c

is the frame departure probability for queue i.

7. Arrivals are processed at the same time step.

8. All frames have equal lengths.

Figure 10.1 illustrates the flows into and out of each queue. The downward ar-

rows represent lost flows. Notice that some data are lost by each queue when the

arrival rate exceeds the departure rate. The highest priority queue does not suffer

any data loss since its data are guaranteed service. The highest priority queue does

not need a buffer to store incoming data when preemptive static priority is em-

ployed. If a nonpreemptive scheme is employed, then the highest priority queue

will require a buffer of size one to store incoming data until the frame being sent is

finished.

From the above assumptions, we can write for queue 1 the following frame arrival

and departure probabilities:

(arrival) = a

(10.1)

(departure) = c

= 1 (10.2)

10.2 IEEE Standard 802.1p: Static Priority Protocol 327

Fig. 10.1 The flows into and

out of each priority queue in

the static priority scheduling

protocol. The downward

arrows represent lost flows

Session 1

Scheduler

Session 2

Session N

...

Highest priority

traffic flow

Lowest priority

traffic flow

Lost flow

For queue 2, we can write the following frame arrival and departure probabilities:

(arrival) = a

(10.3)

(departure) = c

= e

(10.4)

where e

= b

= 1 − a

is the probability that queue 1 is empty since no frames

arrive. Thus queue 2 can access the output channel. The probability that queue 2 is

empty is given by the expression for state s

of the M/M/1/B queue:

1 −ρ

(10.5)

where B

is the size of the queue 2 buffer and ρ

is the distribution index for queue 2:

(10.6)

with b

= 1 −a

and d

= 1 −c

For queue 3, we can write the following frame arrival and departure probabilities:

(arrival) = a

(10.7)

(departure) = c

= e

×e

(10.8)

1 −ρ

(10.9)

In general, we can write the following iterative expression for queue i, where

1 < i ≤ N:

328 10 Modeling Medium Access Control Protocols

(arrival) = a

(10.10)

(departure) = c

= e

i−1

i−2

···e

(10.11)

1 −ρ

(10.12)

where ρ

is the distribution index for queue i and is given by

(10.13)

with b

= 1 −a

and d

= 1 −c

After the arrival and departure probabilities of each queue are found, we can

estimate the queue parameters according to the M/M/1/B analysis in Section 7.6.

The performance parameters for queue 1 are a bit unique due to its high priority:

= 1 frames/time step

a,1

(lost) = 0 frames/time step

a,1

= 0 frames

= 0 time steps

For queue i with 1 < i ≤ N, we can write

= c

(

1 −b

)

frames/time step

a,i

(

1 −b

)

a,i

(lost) = e

frames/time step

= e

a,i

−(B

+1)ρ

+ B

(

1 −ρ

)



1 −ρ



frames

a,i

time steps

Example 10.1 Consider a static priority protocol serving four users where the frame

arrival probabilities for all users are equal (i.e., a

= a for all 1 ≤ i ≤ 4) and all

users have the same buffer size (i.e., B

= B for all 1 ≤ i ≤ 4). Estimate the

performance of each user.

The following table shows the performance parameters for each user starting with

the highest priority user: