Chapter 12
Multiple Access
McGraw-Hill Copyright © The McGraw-Hill Companies, Inc. Permission required
©Thefor reproduction or display.
McGraw-Hill Companies, Inc., 2004
Multiple Access
Broadcast link used in LAN consists of multiple sending and
receiving nodes connected to or use a single shared link
Broadcast links Examples
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Figure 12.1 Data link layer divided into two functionality-oriented sublayers
Responsible for error
and flow control
Link Layer Control (LLC)
Control
MAC
Responsible framing
and MAC address and
Multiple Access Control
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Multiple Access
Problem: When two or more nodes transmit at the same time, their
frames will collide and the link bandwidth is wasted during collision
How to coordinate the access of multiple sending/receiving nodes
to the shared link???
Solution: We need a protocol to coordinate the transmission of the
active nodes
These protocols are called Medium or Multiple Access Control
(MAC) Protocols belong to a sublayer of the data link layer called
MAC (Medium Access Control)
What is expected from Multiple Access Protocols:
Main task is to minimize collisions in order to utilize the bandwidth by:
Determining when a station can use the link (medium)
what a station should do when the link is busy
what the station should do when it is involved in collision
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Figure 12.2 Taxonomy of multiple-access protocols discussed in this chapter
For wireless not
included with us
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Random Access
Random Access (or contention) Protocols:
No station is superior to another station and none is assigned the control over another.
A station with a frame to be transmitted can use the link directly based on a procedure defined by the
protocol to make a decision on whether or not to send.
ALOHA Protocols (Additive Links On-line Hawaii Area)
Was designed for wireless LAN and can be used for any shared medium
Pure ALOHA Protocol Description
All frames from any station are of fixed length (L bits)
Stations transmit at equal transmission time (all stations produce frames with equal frame lengths).
A station that has data can transmit at any time
After transmitting a frame, the sender waits for an acknowledgment for an amount of time (time out)
If no ACK was received, sender assumes that the frame or ACK has been destroyed and resends that
frame after it waits for a random amount of time
If station fails to receive an ACK after repeated transmissions, it gives up
Channel utilization or efficiency or Throughput is the percentage of the transmitted frames that arrive
successfully (without collisions) or the percentage of the channel bandwidth that will be used for
transmitting frames without collisions
ALOHA Maximum channel utilization is 18% (i.e, if the system produces F frames/s, then 0.18 * F frames
will arrive successfully on average without the need of retransmission).
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Maximum Propagation Delay
Maximum propagation delay(tprop): time it takes for a bit of a frame
to travel between the two most widely separated stations.
The farthest
station
Station B
receives the
first bit of
the frame at
time t= tprop
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Figure 13.4 Procedure for ALOHA protocol
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Critical time for pure ALOHA protocol
Tfr= Frame
Transmission time
If the frame transmission time is T sec, then the
vulnerable time is = 2 T sec.
This means no station should send during the T-sec
before this station starts transmission and no station
should start sending during the T-sec period that the
current station is sending.
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Pure ALOHA
In pure ALOHA, frames are transmitted at completely arbitrary times.
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Random Access – Slotted ALOHA
Time is divided into slots equal to a frame transmission
time (Tfr)
A station can transmit at the beginning of a slot only
If a station misses the beginning of a slot, it has to wait
until the beginning of the next time slot.
A central clock or station informs all stations about the
start of a each slot
Maximum channel utilization is 37%
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
In danger time for slotted ALOHA protocol
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Random Access – Slotted ALOHA
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Efficiency of Aloha
S = throughput =(success rate)
0.4
0.3
Slotted Aloha
0.2
0.1
Pure Aloha
0.5 1.0 1.5 2.0
G = offered load rate= new frames+ retransmitted
= Total frames presented to the link per
the transmission time of a single frame
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
Advantage of ALOHA protocols
A node that has frames to be transmitted can transmit continuously at the
full rate of channel (R bps) if it is the only node with frames
Simple to be implemented
No master station is needed to control the medium
Disadvantage
If (M) nodes want to transmit, many collisions can occur and the rate
allocated for each node will not be on average R/M bps
This causes low channel utilization
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
