Chapter 12
Multiple Access
Multiple-access protocols
When more than two nodes send at the same time , the
transmitted frames collide.
All collide frames are lost and the bandwidth of the broadcast
channel will be wasted.
We need multiple –access protocol to coordinate access to
multipoint or broadcast link (Nodes or stations are connected to or
use a common link)
Multiple access protocols are needed in wire and wireless LANs
and satellite networks
1
Multiple-access protocols
Problem of controlling the access to the medium is similar to
the rules of speaking in an assembly :
• Given everyone a chance to speak
• Don’t speak until you are spoken to
• Don’t monopolize the conversation
• Raise your hand if you have a question
• Don’t interrupt when someone speaking
Multiple-access protocols
2
1- RANDOM ACCESS
In random access or contention methods, no station is
superior to another station and none is assigned the
control over another
another.. No station permits, or does not
permit, another station to send
send.. 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(
send
idle or busy)
Random Access Methods:
ALOHA
Carrier Sense Multiple Access ; CSMA
Carrier Sense Multiple Access with Collision Detection (CSMA/CD)
Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)
1-RANDOM ACCESS
Each station has the right to the medium without being
controlled by any other station.
Two features gives the method its name:
There is no schedule time for a station to transmit:
transmission is random among stations
Stations compete with one another to access the medium
Contention method.
Collision: an access conflict occurs when more than one
station tries to send, as a result the frame will be either
destroyed or modified.
3
RANDOM ACCESS
Each station follows a procedure that answer the
following questions to avoid collision:
When can the station access the medium?
What can the station do if the medium is busy?
How can the station determine the success or failure of
the transmission?
What can the station do if there is an access conflict (
collision)?
Evolution of random-access methods
ALOHA : uses MA ( Multiple Access) No carrier sense
CSMA : Carrier Sense Multiple Access
CSMA/CD : Collision Detection
CSMA/CA Collision Avoidance
4
Pure ALOHA
The earliest random access method developed at the Univ. of Hawaii
in the early 1970s
Designed for a radio (wireless) LAN
Simple method. Each station sends a frame whenever it has a frame
to send.
Since there is only one channel to share, there is the possibility of
collision between frames from different stations.
ACK ACK
ACK ACK
Frames in a pure ALOHA network
1
0
5
Pure ALOHA
Each station sends a frame whenever it has a frame to send.
It relies on acknowledgments from the receiver.
If the ACK dose not arrive after a time-out period, the station resend the frame.
time-out is equal the max possible round trip time = 2 x Tp
Tp(max propagation time) time required to send a frame between the most
widely separated station
To minimize collisions, each station waits a random amount of time (back-off
time TB ) before resending its frame.
TB is a random value that depend on K ( the number of attempted unsuccessful
transmission) .
The formula of TB is the binary exponential back-off.
After a max number of retransmission attempts Kmax, a station must give up and
try later to prevent congestion.
11
Procedure for pure ALOHA protocol
Note: R range from 0 to 2k -1
12
6
Figure 12.5 Vulnerable time for pure ALOHA protocol
Note
The throughput for pure ALOHA is
S = G × e −2G
2G .
The maximum throughput
Smax = 0.184 when G= (1/2).
Example 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, we find
Tp = (600 × 103 ) / (3 × 108 ) = 2 ms.
Now we can find the value of TB for different values of
K.
a. For K = 1, the range R is {0, 1}. The station needs to|
generate a random number with a value of 0 or 1.
This
means that TB is either 0 ms (0 × 2) or 2 ms (1 × 2),
based on the outcome of the random variable.
13
Example 1 (continued)
b. For K = 2, the range 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.
c. For K = 3, the range is {0, 1, 2, 3, 4, 5, 6, 7}. This
means that TB can be 0, 2, 4, . . . , 14 ms, based on the
outcome of the random variable.
d. We need to mention that if K > 10, it is normally set
to 10.
14
7
Figure 12.6 Frames in a slotted ALOHA network
Note
The throughput for slotted ALOHA is
S = G × e−G
G .
The maximum throughput
Smax = 0.368 when G = 1.
Figure 12.7 Vulnerable time for slotted ALOHA protocol
Example 12.4
A slotted ALOHA network transmits 200-bit frames on a
shared channel off 200 kbps.
p What is the throughput
g p iff the
system (all stations together) produces
a. 1000 fframes pper second b. 500 fframes pper 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,
a. second this is 1
frame per millisecond. The load is 1. In this case
S = G× e−GG or S = 0.368
0 368 (36.8
(36 8 percent).
percent) This means
that the throughput is 1000 × 0.368 = 368 frames.
Only 386 frames out of 1000 will probably survive.
survive
Example 12.4 (continued)
b. If the system creates 500 frames per second, this is
((1/2)) fframe p
per millisecond. The load is ((1/2).
) In this
case S = G × e−G or S = 0.303 (30.3 percent). This
means that the throughput g p is 500 × 0.303 = 151 .
Only 151 frames out of 500 will probably survive.
c. If the system creates 250 frames per second, this is (1/4)
fframe pper millisecond. The load is (1/4). In this case
S = G × e −G or S = 0.195 (19.5 percent). This means
that the throughput
g p is 250 × 0.195 = 49. Onlyy 49
frames out of 250 will probably survive.
Carrier Sense Multiple Access (CSMA)
Sense the carrier before transmit : “listen before you talk”
CSMA can reduce the possibility of collision, but it can not
eliminate it because of the propagation delay (a station may sense the
medium and find it idle, only because the first bit of a frame sent by another
station has not been received)
15
Vulnerable time in CSMA
Vulnerable time : time in which there is a possibility of collision
Vulnerable time for CSMA is the max propagation time Tp
needed for a signal to propagate from one end of the medium to the
other
16
8
persistence methods
What should a station do if the channel is
busy?
What should a station do if the channel is
idle?
17
1-persistence methods
When the sender (station) is ready to transmit
data, it checks if the medium is busy. If so, it
senses the medium continually until it becomes
idle
If line is idle, sends the frame immediately (with
probability of 1).
Chances of collision is high.
18
9
non-persistence methods
If a station has a frame to send, it senses the line.
If line is idle, the station sends the frame immediately.
If line is not idle, the station waits a random period of time
and then senses the line again.
Chances of collision is reduced
Reduces efficiency of the network ( because the medium
remain idle when there may be stations with frames to
send
19
P- Persistence
It used if the channel has time slots
with a slot duration equal to or grater
than the maximum propagation time.
When the sender (station) is ready
to transmit data, it checks if the
medium is busy. If so, it senses the
medium continually until it becomes
idle.
If line is idle it may or may not
send. It sends with probability p.
Reduces the chance of
collision and improves the
efficiency by combining the
other two strategies
20
10
Carrier Sense Multiple Access collision detection
CSMA/CD
“Listen-while-talk” protocol. A host listens even while it is
transmitting, and if a collision is detected, stops
transmitting
21
Flow diagram for the CSMA/CD
22
11
Collision Detection
How the station detects a collision?
Detecting voltage level on the line
Detecting energy level .
Energy in channel can have three values: zero, normal, and abnormal.
at zero level, the channel is idle
At the normal level, a station has successfully captured the channel and is
sending its frame.
At the abnormal level, there is a collision and the level of the energy twice
the normal level.
23
Minimum frame size
For CSMA/CD to work correctly we need to restrict the
minimum frame size.
Before sending the last bit of a frame , the sending station
must detect a collision and abort the transmission.
This is so because the station, once the entire frame is sent
does not keep a copy of the frame and does not monitor the line
of collision detection.
For the worst case scenario; if the two stations involved in a
collision are the max distance apart
transmission time > = 2 x max. propagation time
Tfr > = 2 X Tp
(MinFrame size)/B-W = 2 X Tp
24
12
Example 2:
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 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 = 10 Mbps × 51.2 μs
= 512 bits or 64 bytes.
This is actually the minimum size of the frame for Standard
Ethernet.
25
13
Figure 12.16 Timing in CSMA/CA
12.28
Note
In CSMA/CA, the IFS can also be used to
d fi the
define th priority
i it off a station
t ti or a frame.
f
12.29
Note
In CSMA/CA, if the station finds the
channel
h l busy,
b it does
d nott restart
t t the
th
timer of the contention window;
it stops the timer and restarts it when
the channel becomes idle.
12.30
Figure 12.17 Flow diagram for CSMA/CA
12.31
12--2 CONTROLLED ACCESS
12
I controlled
In t ll d access
access,, the
th stations
t ti consult
lt one another
th
to find which station has the right to send.
send. A station
cannott sendd unless
l it has
h been
b authorized
th i d by b other
th
stations.. We discuss three popular controlled
stations controlled--access
methods
methods.
th d .
Topics discussed in this section:
Reservation
Polling
Token Passing
12.32
Reservation access method
A station needs to make a reservation before sending data.
Time is divided into intervals
A reservation frame proceeds each time interval
Number of stations and number of mini-slots in the reservation
frame are equal
Each time slot belongs to a particular station
If there are N stations in the system, there are exactly N
reservation mini-slots in the reservation frame
27
Polling access method
Devices are designated as a Primary station and
secondary station.
All data exchange must go through the primary station
Primary station controls the link and initiates the
session; the secondary station follow its instructions.
Two functions: polls and select
Poll : If the primary wants to receive data, it asks
the secondary if they have anything to send.
Select: if the primary wants to send data, it tells
the secondary to get ready to receive data
28
14
Select function
The select function is used when
the primary has frames to send.
The primary creates and
transmits a select (SEL) frame.
SEL alerts the secondary to the
upcoming transmission
The primary waits for ACK to
send the data
29
Poll function
When the primary is ready to receive
data, it must ask (Poll) each device in turn
if it has anything to send.
When the first secondary is approached,
it responds either with a NAK frame if it
has nothing to send or with data if it does.
If the response is NAK, the primary
polls the next secondary.
If it receives data, it sends ACK frame.
30
15
Token Passing
In the token-passing, the stations are organized in a
logical ring.
For each station there is a predecessor and a successor
predecessor is the station which is logically before the
station in the ring
The successor is the station which is logically after the
station in the ring
The current station is the one that accessing the channel
now.
How is The right to access channel passed from one station
to another?
31
Token Passing
Station is authorized to send data when it receives a special
frame called a token
Stations are arranged around a ring.
When no data are being sent, a token circulates the ring.
If a station needs to send data, it waits for the token.
The station captures the token and sends one or more frames
(as long as it has frames to send or the allocated time has not
expired), and finally it releases the token to be used by next
station ( successor).
The maximum time any station can hold the token is limited.
Since there is only one token, only one station transmits at a
time, and collisions never occur.
32
16
Token Passing
Token management is needed for this access
method:
Stations must be limited in the time they can have
possession of the token
the token must be monitored to ensure it has not
been lost or destroyed( if the station that is holding
the token fails, the token will disappear from the
network)
Assign priorities to the stations , to make low-
priority stations release the token to high priority
stations.
Stations do not have to be physically connected in a ring ;
the ring can be logical one
33
Logical ring and physical topology in token-passing access method
Token bus
34
17