Chapter 12: Outline
12.1 RANDOM ACCESS
12.2 CONTROLLED ACCESS
12.3 CHANNELIZATION
Chapter 12: Objective
The first section discusses random-access protocols. Four
protocols, ALOHA, CSMA, CSMA/CD, and CSMA/CA, are
described. These protocols are mostly used in LANs and WANs.
The second section discusses controlled-access protocols. Three
protocols, reservation, polling, and token-passing.
The third section discusses channelization protocols. Three
protocols, FDMA, TDMA, and CDMA are described.
Media Access Control(MAC)
• When stations are connected to a common link(multi
point/broadcast link), multiple access protocol is
required to coordinate access to the link.
• The problem of controlling the access to the medium
should ensure that at the same time no two devices can
interrupt or monopolize the link.
• Many protocols have been devised to handle access to
a shared link.
• These protocols belong to a sub layer in DLL called
media access control(MAC).
Taxonomy of multiple-access protocols
12-1 RANDOM ACCESS
In random-access or contention no station is superior to
another station and none is assigned control over another.
At each instance, a station that has data to send uses a
procedure defined by the protocol to make a decision on
whether or not to send.
This decision depends on the state of the medium (idle
or busy).
Each station can transmit when it desires on the
condition that it follows the predefined procedure, testing
the state of the medium.
Random access(Contention Method)
• Two features that gave this name
1) There is no scheduled time for the station to transmit.
Transmission is random among the stations.
So, the name Random access method.
2)No rules specify which station should send next.
Stations compete with one another to access the medium.
So, the method is called Contention methods.
Random access
• As each station has right to access the medium, if more
than one station tries to send, there is an access conflict
and frames will be either modified or destroyed.
• To avoid this access conflict, each station follows the
procedures which answers questions
1)When can the station access the medium?
2)What can station do if medium is busy.
3)How can the station determine the success or failure of
the transmission
4) What can station do if there is access conflict.
Methods
1)ALOHA
2)CSMA/CD
3)CSMA/CA
ALOHA:- The earliest random access method, was
developed at the University of Hawaii in early 1970.
It was designed for a radio (wireless) LAN, but it can
be used on any shared medium.
The medium is shared between the stations, there are
potential collisions in this arrangement. When a station
sends data, another station may attempt to do so at the
same time.
The data from the two stations collide and become
garbled.
Pure ALOHA
• Original ALOHA protocol is called Pure
ALOHA.
Idea is
1)Each station sends a frame whenever it has data
to send.
2)Since there is only one channel to share, there is
possibility of collision between frames from
different stations.
Frames in a pure ALOHA network
Pure ALOHA
Eg: There are 4 stations that content with one another for
access to the shared channel.
Each station sends two frames, there are totally 8 frames
on this medium.
Some of these frames collide because multiple access
frames are in the contention for the shared channel.
• Only two frames, frame 1.1 from station 1 and frame 3.2
from station 3survived.
• Even if 1 bit of a frame coexists on the channel with one
bit from another frame, there is a collision and both will
be destroyed.
• Need to resend the frames that have been destroyed during
transmission.
Pure ALOHA
• Pure ALOHA protocol relies on ack. from the receiver.
• If station does not receive ack. with in time-out period,
station assumes that frames have been destroyed and
resends it.
• A Collision involves two or more stations. If all these
stations resend frames again, frames collide.
• PURE ALOHA dictates that when the time out period
passes, each station waits for random amount of time
before resending the frames.
• Randomness avoid more collisions .
• This is called Back-off time TB .
Pure ALOHA
• Second method to prevent congesting the channel with
retransmitted frames is after maximum number of
retransmission attempts KMax the stations must give up and
try later.
• Time out period is equal to maximum possible round trip
propagation delay, which is twice the amount of time
required to send the frame between most widely separated
stations(2*Tp).
• (Propagation time is time taken by a bit to travel from
source to destination)
• Back-off time TB is a random value which depends on
value of K.
Procedure for pure ALOHA protocol
Example 12. 1
The stations on a wireless ALOHA network are a maximum
of 600 km apart.
If we assume that signals propagate at
3 × 108 m/s, find Tp and TB .
Solution:
Tp =Distance/Propagation speed of the medium
=(600 × 103) / (3 × 108) = 2 ms.
for K = 2, the range of R is {0, 1, 2, 3}.
This means that TB can be 0, 2, 4, or 6 ms, based on the
outcome of the random variable R.
Continued…
• Common formula is binary exponential back-off.
In this method, for each retransmission, a multiplier in
the range 0 to 2K-1 is randomly chosen and multiplied by
Tp (Max. propagation time) or Tfr(Average time required
to send out a frame) to find TB
The range of random numbers increases after each
collision.
The value of KMax chosen is 15.
Vulnerable time
• Vulnerable time is length of a time, in which there is a
possibility of collision.
• Assume that stations send fixed frames with each frame
taking Tfr seconds to reach .
• From the fig. the vulnerable time ,during which a
collision may occur in PURE ALOHA, is 2 times the
frame transmission time.
Pure Aloha Vulnerable time=2* Tfr
Vulnerable time for pure ALOHA protocol
Example 12.2
A pure ALOHA network transmits 200-bit frames on a
shared channel of 200 kbps. What is the requirement to
make this frame collision-free?
Solution
Average frame transmission time Tfr = 200 bits/200 kbps or
1 ms.
The vulnerable time is 2 × 1 ms = 2 ms.
This means no station should send later than 1 ms
before this station starts transmission and no station should
start sending during the period (1 ms) that this station is
sending.
Throughput
• Let G be the average number of frames generated by the system
during one frame transmission time.
• It can be proved that, average number of successful transmission
for pure ALOHA is
• The Maximum through put Smax =0.184 for G=1/2.
• In other words, if one-half frame is generated during one frame
transmission time, then 18.4% of these frames reach their
destination successfully.
• The throughput for pure ALOHA is
S = G × e −2G .
• The maximum throughput
Smax = 0.184 when G= (1/2).
Example
A pure ALOHA network transmits 200-bit frames on a
shared channel of 200 kbps. What is the throughput if the
system (all stations together) produces
a. 1000 frames per second?
b. 500 frames per second?
c. 250 frames per second?
Solution
The frame transmission time is 200/200 kbps or 1 ms.
a. If the system creates 1000 frames per second, then 1 frame per
millisecond.
Therefore G = 1.
Throughput S = G × e−2G = 0.135 (13.5 percent).
This means that the throughput is
1000 × 0.135 = 135 frames. Only 135 frames out of 1000
will probably survive.
Example (continued)
b. If the system creates 500 frames per second, or 1/2 frames
per millisecond.
Therefore G = 1/2.
Throughput S=G×e−2G =0.184 (18.4 percent).
This means that the throughput is
500 × 0.184 = 92 and that only 92 frames out of 500 will
probably survive.
c. If the system creates 250 frames per second, or 1/4
frames per millisecond.
Therefore G = 1/4.
Throughput S = G × e−2G = 0.152 (15.2 percent).
This means that the throughput is 250 × 0.152 = 38.
Only 38 frames out of 250 will probably survive
Slotted ALOHA
• Pure Aloha vulnerable time is 2*Tfr, because no rule that defines
when the station is allowed to transmit.
• Station may send before other station has finished/another station
has started.
• To improve the efficiency of PURE ALOHA, Slotted ALOHA was
invented.
• In Slotted ALOHA, divide the time into slots of Tfr Sec and force the
station to send only in the beginning of the time slot.
• Because station is allowed to send only at the beginning of the
synchronized time slot,if a station misses this moment, it must wait
until the beginning of the next time slot.
• There is possibility of collision if two stations try to send at the
beginning of the same time slot.
• Vulnerable time is one-half that of PURE ALOHA= Tfr.
Frames in a slotted ALOHA network
Vulnerable time for slotted ALOHA protocol
Throughput
• The throughput for slotted ALOHA is
S = G × e−G .
• The maximum throughput
Smax = 0.368 when G = 1.
• If one frame is generated during one frame transmission
time, then 36.8% of these frames reach the destination
successfully.
• Because vulnerable time is equal to frame transmission
time, station generates only one frame in this time .
Example 12. 4
A slotted ALOHA network transmits 200-bit frames using a
shared channel with a 200-kbps bandwidth. Find the
throughput if the system (all stations together) produces
a. 1000 frames per second.
b. 500 frames per second.
c. 250 frames per second.
Solution
The frame transmission time is 200/200 kbps or 1 ms.
a.G =1. So throughput S = G × e−G = 0.368 (36.8
percent).
This means that the throughput is 1000 × 0.368 = 368
frames. Only 368 out of 1000 frames will probably survive.
Example 12. 4 (continued)
b) G = 1/2.
In this case S = G × e−G = 0.303 (30.3 percent).
This means that the throughput 500 × 0.303 = 151.5.
Only 151 frames out of 500 will probably survive.
c) G = 1/4.
In this case S = G × e−G = 0.195 (19.5 percent).
This means that the throughput is 250 × 0.195 = 49.
Only 49 frames out of 250 will probably survive.
CSMA
To minimize the chance of collision and increase
the performance, the CSMA method was developed.
The chance of collision can be reduced if a station
senses the medium before trying to use it.
Carrier sense multiple access (CSMA) requires that
each station first listen to the medium (or check the
state of the medium) before sending.
In other words, CSMA is based on the principle
“sense before transmit” or “listen before talk.”
Space/time model of a collision in CSMA
Vulnerable time
• Vulnerable time for CSMA is the Propagation
time Tp.
• Tp is the time needed for the signal to propagate
from one end of the medium to other.
• When any station sends a frame during this time
collision will occur.
• If the first bit of the frame reaches the end of the
medium, every station will already have heard the bit
and will refrain from sending.
Vulnerable time in CSMA
Persistence Methods
What should station do if channel is busy/idle?
• Three methods to answer this
1) 1-Persistent method
2) Non persistent method.
3) p-Persistent method
• When a station finds channel is busy, behavior
of three persistence methods are shown below
Behavior of three persistence methods
Behavior of three persistence methods
1-Persistent : After station finds the line idle, it sends the frame
immediately.(Probability 1)
This methods has highest chance of collision because two or more
stations may find the line idle and send their frames immediately.
Non-Persistent: Station that has frame senses the line. If line is idle, it
sends immediately.
If not, it waits for random amount of time and then senses the
line again.
The Non-Persistent approach reduces the chance of collision
because it is unlikely that two or more stations will wait for same
amount of time.
This method reduces efficiency of the n/w because the medium
remains idle when there may be stations with frames to send.
Continued..
P-persistent: This method is used if the channel has time
slot with the slot duration equal to or greater than
maximum propagation time.
It reduces the chance of collision & improves efficiency.
After station finds channel is idle, it follows the
following steps
1) With probability p, the station sends its frame.
2) With probability q=1-p, the station waits for the beginning of the
next time slot and checks the line again.
a) If line is idle , it goes to step 1.
b) If the line is busy, it acts as though a collision has occurred and
uses the back off procedure.
Flow diagram for three persistence methods
CSMA/CD
•The CSMA method does not specify the procedure
following a collision.
•Carrier sense multiple access with collision detection
(CSMA/CD) augments the algorithm to handle the
collision.
In this method, a station monitors the medium after it
sends a frame to see if the transmission was successful.
If yes, the station is finished transmitting the frame.
If there is a collision, the frame is sent again.
Collision of the first bits in CSMA/CD
Collision and abortion in CSMA/CD
Minimum Frame size
• CSMA/CD to work, need a restriction on the frame size.
• Before sending the last bit of the frame, if sending station
detects a collision, if any, abort the transmission.
• Once station sends entire frame, does not keep a copy of
the frame and monitor the line for collision detection.
• Frame transmission time Tfr must be at least two times the
maximum propagation time Tp(2Tp).
Example
A network using CSMA/CD has a bandwidth of 10 Mbps. If
the maximum propagation time (including the delays in the
devices and ignoring the time needed to send a jamming
signal ) is 25.6 μs, what is the minimum size of the frame?
Solution
The minimum frame transmission time is
Tfr = 2 × Tp = 51.2 μs.
This means, in the worst case, a station needs to transmit for
a period of 51.2 μs to detect the collision.
The minimum size of the frame is
10 Mbps × 51.2 μs = 512 bits or 64 bytes
Which is actually the minimum size of the frame for
Standard Ethernet.
Flow diagram for the CSMA/CD
12.44
Energy level during transmission, idleness, or
collision
Energy level
• Level of energy in a channel can have three values
zero, normal and abnormal.
At Zero level, channel is idle.
At Normal Level, station has successfully captured the
channel and is sending its frame.
At Abnormal level, there is a collision and level of
energy is twice the normal level.
The station that has frame to send, needs to monitor the
energy level of the channel.
Throughput
• Is greater than PURE ALOHA.
• Maximum throughput occurs at a different values
of G and is based on Persistence method and
value p in p-persistent approach.
• For 1-persistent method the maximum through
put is around 50% when G=1.
• For non persistent method, the maximum through
put can go up to 90% when G is between 3 and 8.
CSMA/CA
Carrier sense multiple access with collision
avoidance (CSMA/CA) was invented for wireless
networks.
Collisions are avoided through the use of
CSMA/CA’s three strategies:
1)Inter frame space,
2)Contention window
3) Acknowledgments
Contention window
Inter frame Space(IFS)
• Collisions are avoided by deferring the transmission
even if channel is idle.
• Station does not send immediately, it waits for a period
called IFS.
• Even though channel is found idle when it is sensed, a
distant station may have already started transmitting and
the signal has not yet reached this station.
• IFS time allows signal from the distant station to reach
this station. After IFS time, if channel is found idle, the
station can send, but still need to wait a time equal to
contention time.
• In CSMA/CA, the IFS can also be used to define the
priority of a station or a frame.
Contention window
• Is an amount of time divided into slots.
• A station that is ready to send chooses a random number
of slots as its wait time.
• The number of time slots in the window changes
according to binary exponential back off strategy.
• Means it is set to one slot first time and then doubles
each time the station can not detect an idle channel after
IFS time.
• Station needs to sense the channel after each time slot.
In CSMA/CA, if the station finds the channel busy, it does not
restart the timer of the contention window;
it stops the timer and restarts it when the channel becomes idle.
• This gives priority to the station with longest waiting time.
Acknowledgment
• With all these precautions, data may get corrupted
during transmission resulting in destroyed data.
• Positive ack. and the time-out timer guarantee that
receiver has received the frame.
Frame exchange Time Line
1. Before sending the frame, the source station senses the
medium by checking the energy level at the carrier
frequency.
a) Station uses persistent strategy with back off until
channel is idle.
b) After channel is found idle, the station waits for a period
of time called Distributed coordination Function(DCF)
inter frame space(DIFS), then sends a control frame
called request to send(RTS).
[Link] receiving the RTS & waiting for a period time called
short inter frame space(SIFS), the destination station sends
the a control frame, called clear to send(CTS) to the source
station. The control frame indicates that the destination is
ready to receive data.
Frame exchange Time Line
3. Source station sends data after waiting for an amount of
time equal to SIFS.
4. Destination station after waiting for SIFS time, sends an
acknowledgment to show that frame has been received.
Acknowledgment is needed in this protocol to
check for the successful transmission of its data at the
destination.
Flow diagram for CSMA/CA
Network Allocation vector
• How do other stations defer sending data when one of the station
acquire access i.e How collision avoidance aspect is
accomplished??
• Feature is NAV
I. When station sends RTS frame, it includes the duration of the
time that it needs to occupy the channel.
The stations that are affected by this transmission creates a
timer called Network Allocation Vector(NAV), that shows how
much time is passed and when these stations are allowed to check
the idleness of the medium.
Each time a station access the system and sends an RTS frame,
other stations starts their NAV.
i.e Each station before sensing the medium to see if it is idle, it
first checks NAV if it has expired.
Collision during the Handshaking
[Link] happens if there is a collision during the time
when RTS or CTS control frames are in
transition(Handshaking period)
Two or more stations try to sends RTS frame at the
same time, the control frames may collide.
There is no mechanism for collision detection, the
sender assumes there has been a collision if CTS frame
is not received from the receiver.
The back off strategy is applied and sender tries again.
Hidden station Problem
• Solution is to use hand shake frames.
• When RTS message is sent from B to A, not C.
• Because both B & C are with in transmission range of
A, the CTS message, which contains the duration of
data transmission from B to A, reaches C.
• Station C knows that there is some hidden station is
using the channel and refrains from transmitting until
the duration is over.