Gebali F. Analysis Of Computer And Communication Networks

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

10.4 Slotted ALOHA 339

Thus, the maximum throughput is theoretically equal to

Th(max) =



1 −



N−1

(10.59)

The above equation gives the maximum throughput for any number of users N.

A simple expression is obtained when the user population is very large, N →∞:

Th(max) =

= 36.788% (10.60)

In summary, maximum throughput occurs when N →∞and we have

Th = 36.788% frames/time step (10.61)

(in) = 1 frames/time step (10.62)

= 1/N (10.63)

= Th/N

(in) = 0.367 (10.64)

This compares very well with the throughput estimate obtained using fluid flow

analysis [1] for a continuous-time system with Poisson traffic. Thus when the num-

ber of users increases, the transmission request probability must decrease in propor-

tion. For example, when the system has N = 100 users, the maximum throughput is

approximately 36.788% and the transmission request probability must be a ≈ 0.01.

Comparing these predictions with pure ALOHA, we find that slotted ALOHA

could support double the number of users and achieve double the throughput.

We note that at maximum throughput, pure ALOHA and slotted ALOHA have

the same efficiency. This is a bit surprising since it was not previously reported in

the literature. In fact, the efficiency for pure ALOHA is given by the expressions

= (1 −a

)

2N −1

= 1/2N

And the efficiency for slotted ALOHA is given by the expressions

= (1 −a

)

N−1

= 1/N

Both of these expressions evaluate to e

−1

as N →∞and the arrival probability

at maximum throughput is taken as a

= 1/2N (for pure ALOHA) and a

= 1/N

(for slotted ALOHA).

340 10 Modeling Medium Access Control Protocols

Both systems show maximum efficiency at very low traffic. As traffic increases,

the efficiencies of both systems start to decrease. However, the efficiency of slotted

ALOHA decreases at a slower rate compared to pure ALOHA.

Example 10.3 Repeat Example 10.2 assuming a slotted ALOHA network.

The performance figures are as follows:

Th = 0.1652 frames/time step

= 0.2104 attempts

Th (max) = 0.3679 frames/time step

= 0.05 for maximum throughput

We note that the throughput of slotted ALOHA is slightly higher than pure

ALOHA but it is not its double since we are far from the optimum traffic arrival

probability for either systems.

Similarly, the average number of tries is less for slotted ALOHA.

10.5 IEEE Standard 802.3 (CSMA/CD)

The IEEE 802.3 standard is used for wired LANs where the time required for one

bit to travel between the two farthest stations (propagation time) is much smaller

than the time required for one frame to be sent by the sender (transmission delay).

The IEEE Standard 802.3 specifies a carrier sense multiple access with collision

detection (CSMA/CD).

Signals on the channel travel very close to the speed of light and it takes a finite

amount of time before all stations become aware that a channel is starting to ac-

cess the medium. Therefore, a collision is said to take place when two or more

stations start transmitting within the frame propagation delay. Because during this

time, transmitting stations think that the medium is idle. When that happens, the two

colliding stations stop transmitting and wait for a random amount of time before at-

tempting to transmit again. This reduces the chance that the stations will once again

transmit simultaneously. The maximum distance limitation for CSMA/CD is about

2500 m (1.5 miles). At this value, the ratio of propagation delay to transmission

delay is less than 0.1 [3].

To summarize, in CSMA/CD protocol, all stations monitor the channel to de-

termine when it is free. This is done by special carrier sensing circuits in each

station. If the channel is busy, a station backs off and starts sensing the channel

with probability p. This is called p-persistent CSMA/CD. The station refrains from

transmitting on an idle channel with probability 1 − p. This reduces the probability

of collisions. If the channel is sensed free, the station starts to transmit. Transmitting

stations monitor the signal on the channel and compare it to the transmitted signal to

decide if a collision is taking place or not. This is done by special collision detection

circuits. When the LAN contains N stations, p is chosen such that Np < 1[3].

The IEEE 802.3 standard describes a 1-persistent CSMA/CD with exponential

backoff strategy which is more commonly known as Ethernet.

10.5 IEEE Standard 802.3 (CSMA/CD) 341

At this point, it is worthwhile mentioning three different CSMA access strategies:

• 1-persistent CSMA

• Nonpersistent CSMA

• p-persistent CSMA

In a 1-persistent CSMA, a station with frame to send senses the channel. If the

channel is sensed free, the frame is sent. If the channel is busy, the station continu-

ously monitors the channel and sends the frame when the channel is sensed idle.

In a nonpersistent CSMA, a station with frame to send senses the channel. If the

channel is sensed free, the frame is sent. If the channel is busy, the station waits

for a random amount of time before monitoring the channel and sends the frame

when the channel is sensed idle. If the channel is sensed busy, the station repeats the

random wait.

In a p-persistent CSMA, a station with frame to send senses the channel. If the

channel is sensed free, the frame is sent with probability p. The transmission is

deferred for the next time slot with probability 1 − p. This process is repeated until

the frame is sent.

10.5.1 IEEE 802.3 (CSMA/CD) Model Assumptions

A simple analysis of IEEE 802.3 was given in [4] and [5]. A more complicated

analysis of IEEE 802.3 can be found [6] which is by no means more accurate since

it makes drastic assumptions about the channel states and the probability of a suc-

cessful transmission. We follow here the middle ground and provide a tractable

analysis making reasonable approximations.

Let us define τ

to be the delay time required for a user to detect that a collision

has taken place and τ

to be the transmission delay for one frame. Typically, τ

 τ

since collision detection is done using fast electronic circuits. Therefore, periods

of transmission are separated by one or more contention minislots [7]. Similar to

ALOHA, a user could determine if there is contention or not during a time period

equal to the propagation delay, i.e., τ

To start our analysis, we employ a set of assumptions for IEEE 802.3 model as

follows:

1. Since the current state of the channel depends only on its immediate past his-

tory, we can model the channel using Markov chain analysis.

2. The states of the Markov chain represent the states of the channel: idle, trans-

mitting, and collided.

3. The channel is shared among N stations.

4. There is a single station class (equal priority).

5. The frame arrival probability per time step is a.

6. All transmitted frames have equal lengths.

7. A frame duration is equal to the transmission delay of a frame τ

8. The time step of the Markov chain is chosen equal to the collision detection

delay, i.e., T = τ

342 10 Modeling Medium Access Control Protocols

9. We define n as the ratio of transmission delay to propagation delay, i.e., n =

/τ

. We assume that n > 1, which is true for small LANs carrying long frames

or operating at low transmission speeds.

10. The time required to detect a collision is less than or equal to the time step

value T .

11. Probability that an idle station receives a frame for transmission during a frame

transmission time (or frame duration) is a.

12. A p-persistent CSMA/CD is assumed. This is equivalent to a 1-persistent

CSMA/CD with a backoff strategy.

13. An adaptive backoff strategy is assumed where a collided user starts to sense the

channel with probability α, which is taken equal to the frame arrival probability

(i.e., α = a). In that sense, each collided user adapts its request probability α

to be proportional to its incoming traffic probability a.

14. A station can have at most one message waiting for transmission.

The alert reader will note that the above assumptions lead to significant simpli-

fication. We were able to justify that collided users behave the same as uncollided

users through the adoption of 1-persistence and the adaptive backoff strategy.

10.5.2 IEEE 802.3 (CSMA/CD) State Transition Diagram

Based on the above assumptions, the wireless channel can be in one of three states:

idle, collided,ortransmitting. Figure 10.6 shows the state diagram of CSMA/CD

protocol. The channel has several transmitting states because the time required for

transmitting one frame (τ

) is bigger than the propagation delay τ

The probability that i users are active at a given time step is given by





(1 −a)

N−i

(10.65)

where a is the probability that a station requests a transmission during a time step.

We organize the distribution vector at equilibrium as follows:

s =



··· s



(10.66)

The corresponding transition matrix of the channel is given by

P =

⎡

⎢

⎣

000··· 011

000··· 000

0 100··· 000

0 010··· 000

0 000··· 000

0 000··· 100

1 −u

−u

000··· 000

⎤

⎥

⎦

(10.67)

10.5 IEEE Standard 802.3 (CSMA/CD) 343

Fig. 10.6 State transition

diagram for the IEEE 802.3

CSMA/CD channel

Idle

Collided

Transmitting

1-u

-u

...

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

Ps= s (10.68)



s = 1 (10.69)

The solution to the above two equations is simple:

s =

2 +u

(n − 1) −u

⎡

⎢

⎣

1 −u

−u

⎤

⎥

⎦

(10.70)

10.5.3 IEEE 802.3 (CSMA/CD) Protocol Performance

The throughput is given by the equation

Th =



i=1

2 +u

(n − 1) −u

(10.71)

For large values of n, the throughput approaches 100% which is expected since

little time is wasted during the collision.

Figure 10.7 shows the throughput of the IEEE 802.3 protocol when n = 10,

N = 10, and p = 1. The solid line is the throughput of CSMA/CD, the dashed

344 10 Modeling Medium Access Control Protocols

Fig. 10.7 The throughput for

CSMA/CD versus the

average input traffic when

n = 10, N = 10, and p = 1.

The solid line is the

throughput of CSMA/CD, the

dashed line represents the

throughput of slotted

ALOHA, and the dotted line

represents the throughput of

pure ALOHA

0 2.5 5 7.5 10

0.2

0.4

0.6

0.8

Input traffic

Throughput

line represents the throughput of slotted ALOHA, and the dotted line represents the

throughput of pure ALOHA.

The access probability for the user in the CSMA/CD protocol is given by

(10.72)

Figure 10.8 shows the access probability of CSMA/CD protocol. The solid line

is the access probability of CSMA/CD, the dashed line represents the access prob-

ability of slotted ALOHA, and the dotted line represents the access probability of

pure ALOHA.

Fig. 10.8 Access probability

of the IEEE 802.3 CSMA/CD

protocol versus the average

input traffic per time step for

the case n = 10, N = 10, and

p = 1. The solid line is the

access probability of

CSMA/CD, the dashed line

represents the access

probability of slotted

ALOHA, and the dotted line

represents the access

probability of pure ALOHA

0 2.5 5 7.5 10

0.2

0.4

0.6

0.8

Input traffic

Access probability

10.6 Carrier Sense Multiple Access-Collision Avoidance (CSMA/CA) 345

Fig. 10.9 Frame delay for the

IEEE 802.3 CSMA/CD

protocol versus the average

input traffic frame for the

case n = 10, N = 10, and

p = 1. The solid line is the

delay of CSMA/CD, the

dashed line represents the

delay of slotted ALOHA, and

the dotted line represents the

delay of pure ALOHA

0 2.5 5 7.5 10

−5

Input traffic

Delay

The average number of attempts for a successful transmission is

∞



i=0

i (1 − p

)

1 − p

(10.73)

Figure 10.9 shows the delay of the IEEE 802.3 CSMA/CD protocol when

n = 10, N = 10, and p = 1. The solid line is the delay of CSMA/CD, the dashed

line represents the delay of slotted ALOHA, and the dotted line represents the delay

of pure ALOHA.

10.6 Carrier Sense Multiple Access-Collision Avoidance

(CSMA/CA)

Carrier sense multiple access with collision avoidance (CSMA/CA) is used in wire-

less LANs where a transmitting station is unable to determine if a collision occurred

while transmitting or not. Collision detection, as is employed in Ethernet, cannot

be used for the radio frequency transmissions. The reason is that when a node is

transmitting it cannot hear any other node in the system which may be transmitting,

since its own signal will drown out other signals arriving at the node. A station will

ultimately know when a collision has taken place by reception of negative acknowl-

edgment or by timeout mechanisms.

An ad hoc network is a collection of communicating nodes that do not have

established infrastructure or centralized administration [8]. CSMA/CA protocol is

useful in ad hoc networks where access to the network is decentralized since each

station coordinates its own decisions for accessing the medium. There is no central

346 10 Modeling Medium Access Control Protocols

access point to coordinate activities of all station. Thus ad hoc networks are simpler

to implement and to modify. The price for this simplicity is that ad hoc networks are

prone to collisions.

10.6.1 CSMA/CA Model Assumptions

Let us define τ

to be the propagation delay between users and τ

to be the transmis-

sion delay for one frame. To start our analysis, we employ a set of assumptions for

CSMA/CA model as follows:

1. Since the current state of the channel depends only on its immediate past his-

tory, we can model the channel using Markov chain analysis.

2. The states of the Markov chain represent the states of the channel: idle, trans-

mitting, and collided.

3. The channel is shared among N stations.

4. There is a single station class (equal priority).

5. The frame arrival probability per time step is a.

6. All transmitted frames have equal lengths.

7. A frame duration is equal to the transmission delay of a frame τ

8. The time step of the Markov chain is chosen equal to the propagation delay, i.e.,

T = τ

9. We define n as the ratio of transmission delay to propagation delay, i.e.,

n = τ

/τ

. We assume that n > 1, which is true for small LANs carrying

long frames or operating at low transmission speeds.

10. A 1-persistent CSMA/CA is assumed.

11. A station can have at most one message waiting for transmission.

Based on the above assumptions, the wireless channel can be in one of three

states: idle, collided,ortransmitting. Figure 10.10 shows the state diagram of

CSMA/CA protocol. The channel has several transmitting states because the time

required for transmitting one frame (τ

) is bigger than the propagation delay τ

The probability that i users are active at a given time step is given by





(1 −a)

N−i

(10.74)

We organize the distribution vector at equilibrium as follows.

s =



··· s



(10.75)

The corresponding transition matrix of the channel for the case when n = 3is

given by

10.6 Carrier Sense Multiple Access-Collision Avoidance (CSMA/CA) 347

P =

⎡

⎢

⎣

001001

000000

0 100000

0 010000

1 −u

−u

000000

0 000100

0 000010

⎤

⎥

⎦

(10.76)

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

Ps = s (10.77)



s = 1 (10.78)

The solution to the above two equations is simple:

s =

n(1 −u

) +1

⎡

⎢

⎣

1 −u

−u

1 −u

−u

1 −u

−u

⎤

⎥

⎦

(10.79)

Fig. 10.10 State transition

diagram for the CSMA/CA

channel

Idle

Transmitting

Collided

1 1

...

1-u

-u

348 10 Modeling Medium Access Control Protocols

10.6.2 CSMA/CA Protocol Performance

The throughput is given by the equation

Th =



i=1

n(1 −u

) +1

(10.80)

For large values of N, we can write the throughput as

Th =

−λ



1 −e

−λ



(10.81)

For large values of n, the throughput approaches the expression

Th → u

/(1 −u

) < 100% (10.82)

≈

λe

−λ

1 −e

−λ

−1

< 100% (10.83)

which is expected since little time is wasted during collisions.

Figure 10.11 shows the throughput of CSMA/CA when n = 50 and N = 10. The

solid line is the throughput of CSMA/CA, the dashed line represents the throughput

of slotted ALOHA, and the dotted line represents the throughput of pure ALOHA.

It is interesting to compare Fig. 10.7 for CSMA/CD and Fig. 10.11 for CSMA/CA.

The latter protocol shows lower throughput for the same set of parameters as the

Fig. 10.11 The throughput

for CSMA/CA versus the

average input traffic when

n = 50 and N = 10. The

solid line is the throughput of

CSMA/CA, the dashed line

represents the throughput of

slotted ALOHA, and the

dotted line represents the

throughput of pure ALOHA

0 2.5 5 7.5 10

0.2

0.4

0.6

0.8

Input traffic

Throughput