Channel Allocation Protocols

Dynamic Channel Allocation Parameters

• Station Model.
– N independent stations, each acting as a Poisson Process for
the purpose protocol analysis
• Single Channel Assumption.
– A single channel is available for all communication.
• Collision Assumption.
– If transmitted frames overlap in time, the resulting signal is
garbled.
• Transmission Discipline:
– Continuous time
• Frames can be transmitted at any time
– Slotted time
• Frames can be transmitted at particular time points
• Sensing capability:
– Station cannot sense the channel before trying to use it.
– Stations can tell if the channel is in use before trying to use it
Poisson Process
• The Poisson Process is a celebrated model
used in Queuing Theory for “random arrivals”.
Assumptions leading to this model include:
– The probability of an arrival during a short time
interval Δt is proportional to the length of the interval,
and does not depend on the origin of the time interval
(memory-less property)
– The probability of having multiple arrivals during a
short time interval Δt approaches zero.
Poisson Distribution
The probability of having k arrivals during a time
interval of length t is given by:

 t
( t ) e k
Pk (t ) 
k!

where λ is the arrival rate. Note that this is a single-

parameter model; all we have to know is λ.
Pure ALOHA Protocol

While there is a new frame A to send DO

1. Send frame A and wait for ACK
2. If after “some” time ACK is not
received (timer times out), wait a
random amount of time and go to 1.
End
Pure ALOHA
In pure ALOHA, frames are transmitted at
completely arbitrary times.
Analysis of Pure ALOHA
• Notation:
– Tf = frame time (processing, transmission, propagation)
– S: Average number of successful transmissions per Tf ; that is,
the throughput or efficiency.
– G: Average number of total frames transmitted per Tf
– D: Average delay between the time a packet is ready for
transmission and the completion of successful transmission.
• We will make the following assumptions
– All frames are of constant length
– The channel is noise-free; the errors are only due to collisions.
– Frames do not queue at individual stations
– The channel acts as a Poisson process.
Analysis of Pure ALOHA…
• Since S represents the number of “good”
transmissions per frame time, and G represents
the total number of attempted transmissions per
frame time, then we have:
S = G  (Probability of good transmission)
• The vulnerable time for a successful
transmission is 2Tf
• So, the probability of good transmission is not to
have an “arrival” during the vulnerable time .
Analysis of Pure ALOHA (4)

Collides with Collides with

the start of the end of
the shaded t the shaded
frame frame

t0 t0 + t t0 + 2t t0 + 3t

Vulnerable Time

Vulnerable period for the shaded frame

9
Analysis of Pure ALOHA…
Using: (  t ) k e  t
Pk (t ) 
k!

And setting t = 2Tf and k = 0, we get

  2T f
(  2T f ) 0 e
P0 (2T f )   e 2 G
0!
G
becasue   . Thus, S  G  e 2 G
Tf
Analysis of Pure ALOHA…
• If we differentiate S = Ge-2G with respect to G
and set the result to 0 and solve for G, we
find that the maximum occurs when
G = 0.5,
and for that S = 1/2e = 0.18. So, the
maximum throughput is only 18% of capacity.

• ALOHANET uses a data rate of 9600bps.

This means the maximum total throughput
(sum of data arriving from all user nodes) is
only 0.18 9600 = 1728bps.

11
Pure ALOHA …
Throughput versus offered traffic for ALOHA
systems.
Analysis of Pure ALOHA; another approach

• There are N stations

• Each station transmits with probability p
• For a typical node i to have a successful transmission
means that there was no prior overlapping transmissions
before or after, each with probability (1-p)N-1
• Thus the probability of node i having a successful
transmission is p (1-p)2(N-1)
• Therefore, the probability of a successful transmission is
Np (1 ₋ p)2(N-1)
• The maximum value for the above term when N is large
is 1/2e
Analysis of Pure ALOHA; another
approach…
f  Np(1  p )2( N 1)
df
 N (1  p ) 2( N 1) 2( N  1)(1  p )2( N 1)1 ( 1) Np
dp
df
 N (1  p ) 2( N 1)1  (1  p )  2( N  1) p   N (1  p )2( N 1)1 [1  p  2 Np ]
dp
df 1
 0  p* 
dp 2N  1
2( N 1)
1  1 
f N
*
1  
2N  1  2N  1 
Expected number of
transmissions
• In Pure ALOHA, what is the expected
number of transmissions per frame?
– Let x be the random variable representing the
number of transmissions. Thus, x will take on
values 1, 2, 3, …, etc
– The probability Pk that x takes value k is when
we have (k-1) unsuccessful transmissions
followed by a successful transmission.
– For PURE ALOHA, the probability of a
successful transmission is e-2G
Expected number of
transmissions
2 G 2 G k 1
Thus Pk  e (1  e ) . So, we have
 
E[ x ]   kPk   ke 2 G
(1  e 2 G k 1
) e 2G

k 1 k 1

Thus E[x] grows exponentially with G, which means that

a small increase in the channel load, that is G, can
drastically reduce its performance. The ALOHA
protocol is an example of an unstable protocol.
Slotted ALOHA
• Channel is organized into uniform slots whose
size equals the frame transmission time.
Transmission is permitted only to begin at a slot
boundary. Here is the procedure:
While there is a new frame A to send do
1. Send frame A at a slot boundary and wait for
ACK
2. If after “some” time ACK is not received, wait a
random amount of time and go to 1.
End

17
Analysis of Slotted ALOHA
• Note that the vulnerable period is now reduced in half.
Using: (  t ) k e  t
Pk (t ) 
k!
And setting t = Tf and k = 0, we get

 T f
(  T f )0 e
P0 (T f )   eG
0!
G
because   . Thus, S  G  e  G
Tf
Slotted ALOHA
Throughput versus offered traffic for ALOHA
systems.
Alternate Analysis for Slotted Aloha
• Use of alternate approach for throughput
of slotted aloha is left as exercise
Carrier Sense Multiple Access (CSMA)

• Additional assumption:
– Each station is capable of sensing the
medium to determine if another transmission
is underway
Non-persistent CSMA
While there is a new frame A to send DO
1. Check the medium
2. If the medium is busy, wait some time, and
go to 1.
3. (medium idle) Send frame A and wait for
ACK
4. If after some time ACK is not received (timer
times out), wait a random amount of time
and go to 1.
End
1-persistent CSMA
While there is a new frame A to send do
1. Check the medium
2. If the medium is busy, go to 1.
3. (medium idle) Send frame A and wait
for ACK
4. If after some time ACK is not received
(timer times out), wait a random
amount of time and go to 1.
End.
p-persistent CSMA
While there is a new frame A to send do
1. Check the medium
2. If the medium is busy, go to 1.
3. (medium idle) With probability p send frame
A and the go to 4, and probability (1- p)
delay one time slot and go to 1.
4. If after some time ACK is not received (timer
times out), wait a random amount of time
and go to 1.
End.
CSMA Summary
 Nonpersistent
 1-persistent CSMA persistence and backoff
 p-persistent Non-persistent:
Transmit if idle
Constant or variable Otherwise, delay, try again
Delay
Channel busy Time

Ready

1-persistent: p-persistent:
Transmit as soon as Transmit as soon as channel goes
channel goes idle idle with probability p
If collision, back off and try again Otherwise, delay one slot, repeat process

25
Persistent and Non-persistent
CSMA
Comparison of throughput versus load
for various random access
protocols.
CSMA with Collision Detection
• Stations can sense the medium while
transmitting
• A station aborts its transmission if it senses
another transmission is also happening (that is,
it detects collision)
• Question: When can a station be sure that it has
seized the channel?
– Minimum time to detect collision is the time it takes for
a signal to traverse between two farthest apart
stations.
CSMA with Collision Detection

CSMA/CD can be in one of three states:

contention, transmission, or idle.
CSMA/CD
• A station is said to seize the channel if all
the other stations become aware of its
transmission.
• There has to be a lower bound on the
length of each frame for the collision
detection feature to work out.
• Ethernet uses CSMA/CD
CSMA/CA
• Identical to CSMA/CD but used when
listening is not possible while transmitting
• Idle channel reservation is done by
sending a short request message asking
other nodes to defer transmission
• If collison is detected then, then random
wait is used
• Wireless IEEE 802.11 uses CSMA/CA
with an RTS/CTS mechanism