Module 4

Medium Access Sublayer

 Two Categories of Links
• We can have a point-to-point link or a broadcast link.
• In a point-to-point link, the link is dedicated to the two
devices; in a broadcast link, the link is shared between
several pairs of devices.
• For example, when two friends use the traditional home
phones to chat, they are using a point-to-point link; when
the same two friends use their cellular phones, they are
using a broadcast link (the air is shared among many cell
phone users).
Two Sublayers
Taxonomy of multiple-access
protocols
 Random Access

• In random access or contention methods, no station is superior to

another station and none is assigned the control over another.
• No station permits, or does not permit, another station to 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.
 Random Access

Two features give this method its name.

• First, there is no scheduled time for a station to
transmit.
• Transmission is random among the stations. That is why
these methods are called random access.
• Second, no rules specify which station should send next.
• Stations compete with one another to access the
medium. That is why these methods are also called
contention methods.
 Random Access
• If more than one station tries to send, there is an access
conflict—collision—and the frames will be either destroyed
or modified. To avoid access conflict or to resolve it when it
happens, each station follows a procedure that answers the
following questions:
❑ 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?
RANDOM ACCESS PROTOCOL

1. ALOHA
2. CSMA-Carrier Sense Multiple Access
3. CSMA/CD-Carrier Sense Multiple Access with Collision
Detection
4. CSMA/CA- Detection Carrier Sense Multiple Access with
Collision Avoidance

12.5
 ALOHA
• 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.
• Pure ALOHA
– each station sends a frame whenever it has a frame to send
(multiple access). However, since there is only one channel to share,
there is the possibility of collision between frames from different
stations
• Slotted ALOHA
– divide the time into slots
 PURE ALOHA
• It allows users to transmit whenever they have data to be sent.
• Senders wait to see if a collision occurred (after whole message has been sent).
• If collision occurs, each station involved waits a random amount of time then tries again.
• Systems in which multiple users share a common channel in a way that can lead to
conflicts are widely known as contention systems.
• Whenever two frames try to occupy the channel at the same time, there will be a collision
and both will be garbled.
• If the first bit of a new frame overlaps with just the last bit of a frame almost finished,
both frames will be totally destroyed and both will have to be retransmitted later.
Frames in a pure ALOHA
network
Procedure for pure ALOHA protocol
Vulnerable time(Time in which possibility of Collision)
for pure ALOHA protocol

12.13
Note

The throughput for pure ALOHA is

S = G × e −2G .
The maximum throughput
Smax = 0.184 when G= (1/2).
• S stand for throughput
• G stands for Number of the station that wants to transfer data
• Vulnerable Time : 2 * Transmission Time = 2 * Tfr
• Transmission Time (Tfr) = Message Size / Bandwidth 12.14
 Example 1
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
Step 1- Frame transmission time(Tfr) = 200bits/200 kbps =1 ms.
Step 2- Find Average number of frame generated(G) by the system during one frame
transmission
1 Second ---------- > 1000 Frame G = 1000 * 1 milisecond = 1
1 milisecond -------> ? 1 Second
Step 3- Calculate Maximum throughput(S)
S = G * e-2G S = 1 * e-2(1) S = 0.135 S = 13.5%
S = 0.135 * 1000 = 135 outoff 1000 frame successfully send to receiver 12.16
 Example 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
Step-1 : Transmission time Tfr = 200 bits/200 kbps = 1 ms.

Vulnerable Time of Pure ALOHA = 2 * Transmission Time

Vulnerable Time of Pure ALOHA = 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 one 1-ms period that this station is sending.

12.16
 Slotted ALOHA
• Pure ALOHA has a vulnerable time of 2 x Tfr . This is so because there is
no rule that defines when the station can send.

• A station may send soon after another station has started or soon before
another station has finished. Slotted ALOHA was invented to improve the
efficiency of pure ALOHA.

• In slotted ALOHA we divide the time into slots of Tfr s and force the
station to send only at the beginning of the time slot.
Frames in a slotted ALOHA network

12.18
Vulnerable time for slotted ALOHA protocol

12.19
Note

The throughput for slotted ALOHA

is S = G × e−G .
The maximum throughput
Smax = 0.368 when G = 1.
• S stand for throughput
• G stands for Number of the station that wants to transfer data
• Vulnerable Time : Transmission Time = Tfr
• Transmission Time (Tfr) = Message Size / Bandwidth
 Example 1
A slotted 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
Step 1- Frame transmission time(Tfr) = 200bits/200 kbps =1 ms.
Step 2- Find Average number of frame generated(G) by the system during one frame
transmission
1 Second ---------- > 1000 Frame G = 1000 * 1 milisecond = 1
1 milisecond -------> ? 1 Second
Step 3- Calculate Maximum throughput(S)
S = G * e-2G S = 1 * e-(1) S = 0.368 S = 36.8%
S = 0.368 * 1000 = 368 out off 1000 frame successfully send to receiver 12.16
 CSMA(Carrier Sense Multiple Access)
• To minimize the chance of collision and, therefore,
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 the collision in CSMA

12.23
Vulnerable time in CSMA

12.24
 Persistence Methods
• What should a station do if the channel is busy? What
should a station do if the channel is idle?
• Three methods have been devised to answer these
questions: the 1-persistent method, the nonpersistent
method, and the p-persistent method
Behavior of three persistence methods

12.26
Flow diagram for three persistence methods

12.27
 1-Persistent

• The 1-persistent method is simple and straightforward. In

this method, after the station finds the line idle, it sends its
frame immediately (with probability 1).
• This method has the highest chance of collision because
two or more stations may find the line idle and send their
frames immediately.
 Nonpersistent
• In the nonpersistent method, a station that has a frame to
send senses the line. If the line is idle, it sends immediately.
If the line is not idle, it waits a random amount of time and
then senses the line again.
• The nonpersistent approach reduces the chance of collision
because it is unlikely that two or more stations will wait
the same amount of time and retry to send
simultaneously.
• However, this method reduces the efficiency of the
network because the medium remains idle when there
may be stations with frames to send.
 p-Persistent
• The p-persistent method is used if the channel has time slots with a slot duration
equal to or greater than the maximum propagation time. The p-persistent
approach combines the advantages of the other two strategies.
• It reduces the chance of collision and improves efficiency. In this method,
after the station finds the line idle it follows these 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.
1. If the line is idle, it goes to step 1.
2. If the line is busy, it acts as though a collision has occurred and uses the
backoff procedure.
 Exercises
1. Stations in a pure Aloha network send frames of size
1000 bits at the rate of 1 Mbps. What is the vulnerable
time for this network?
2. Stations in an slotted Aloha network send frames of size
1000 bits at the rate of 1 Mbps. What is the vulnerable
time for this network?
3. In a pure Aloha network with G = 1/2, how is the
throughput affected in each of the following cases?
a. G is increased to 1. b. G is decreased to 1/4.
 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 so, the station
is finished. If, however, there is a collision, the frame is sent
again.
• To better understand CSMA/CD, let us look at the first bits transmitted
by the two stations involved in the collision. Although each station
Collision of the first bit in CSMA/CD

12.33
Collision and abortion in CSMA/CD

12.34
Figure Flow diagram for the CSMA/CD

12.35
Figure Energy level during transmission, idleness or collision

12.36
 Minimum Frame Size
• For CSMA/CD to work, we need a restriction on the
frame size. Before sending the last bit of the frame, the
sending station must detect a collision, if any, 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 for collision detection.
• Therefore, the frame transmission time Tfr must be at
least two times the maximum propagation time Tp.
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, as we see later) 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 is 10 Mbps × 51.2 μs = 512 bits or
64 bytes. This is actually the minimum size of the frame for Standard
Ethernet.
12.38
 Throughput
• The throughput of CSMA/CD is greater than that of pure
or slotted ALOHA.
• The maximum throughput occurs at a different value of G
and is based on the persistence method and the value of p in
the p-persistent approach.
• For the 1-persistent method, the maximum throughput
is around 50 percent when G = 1.
• For the nonpersistent method,the maximum throughput
can go up to 90 percent when G is between 3 and 8
 CSMA/CA
• In a wired network, the received signal has almost the same
energy as the sent signal because either the length of the cable is
short or there are repeaters that amplify the energy between the
sender and the receiver.

• This means that in a collision, the detected energy almost doubles.

• However, in a wireless network, much of the sent energy is lost in

transmission. The received signal has very little energy.
Therefore, a collision may add only 5 to 10 percent additional
energy.
• This is not useful for effective collision detection.
 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: the interframe space, the contention window,
and acknowledgments
Timing in CSMA/CA

12.42
 Interframe Space (IFS)
• First collisions are avoided by deferring transmission
• If channel ideal but it still needs to wait a time equal
to the contention time
• In CSMA/CA, the IFS can also be used to define the
priority of a station or a frame.
 Contention Window
• The contention window is an amount of time
divided into slots.
• This is very similar to the p-persistent method
• 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.
 Acknowledgment
• The data may be corrupted during the
transmission.
• The positive acknowledgment and the time-out
timer can help guarantee that the receiver has
received the frame.
 Flow
Diagram
for
CSMA/CA

12.46
 Exercises
1. Assume the propagation delay in a broadcast network is 5
μs and the frame transmission time is 10 μs.
• How long does it take for the first bit to reach
the destination?
• How long does it take for the last bit to reach the
destination after the first bit has arrived?
• How long is the network involved with this
frame (vulnerable to collision)?
 Exercises
2. Stations in a slotted Aloha network send frames of size
1000 bits at the rate of 1 Mbps. What is vulnerable time for
this network?
 Exercises
3. In a CSMAlCD network with a data rate of 10 Mbps, the
minimum frame size is found to be 512 bits for the correct
operation of the collision detection process. What should
be the minimum frame size if we increase the data rate to
100 Mbps? To 1 Gbps? To 10 Gbps?
4. In a CSMAlCD network with a data rate of 10 Mbps, the
maximum distance between any station pair is found to be
2500 m for the correct operation of the collision detection
process. What should be the maximum distance if we
increase the data rate to 100 Mbps? To 1 Gbps? To 10
Gbps?
5. In a bus CSMA/CD network with a data rate of 10 Mbps, a
collision occurs 20 μs after the first bit of the frame leaves
the sending station. What should the length of the frame be
so that the sender can detect the collision?
6. Assume that there are only two stations, A and B, in a bus
CSMA/CD network. The distance between the two stations
is 2000 m and the propagation speed is 2 × 108 m/s. If
station A starts transmitting at time t1:
a. Does the protocol allow station B to start transmitting at
time
t1 + 8 μs? If the answer is yes, what will happen?
a. Does the protocol allow station B to start transmitting at
time t1 + 11 μs? If the answer is yes, what will happen?
 Exercises
7. To understand why we need to have a minimum frame size Tfr = 2 ×
Tp in a CSMA/CD network, assume we have a bus network with only
two stations, A and B, in which Tfr = 40 μs and Tp = 25 μs. Station A
starts sending a frame at time t = 0.0 μs and station B starts sending a
frame at t = 23.0 μs. Answer the following questions:
a. Do frames collide?
b. If the answer to part a is yes, does station A detect collision?
c. If the answer to part a is yes, does station B detect collision?
CONTROLLED
ACCESS
• In controlled access, the stations consult one another to find which
station has the right to send.
• A station cannot send unless it has been authorized by other stations.
We discuss three popular controlled-access methods.

1. Reservation
2. Polling
3. Token Passing

12.53
 Reservation
• A station needs to make a reservation before sending data.
• Time is divided into intervals. In each interval, a
reservation frame precedes the data frames sent in that
interval.
• If there are N stations in the system, there are exactly N
reservation minislots in the reservation frame. Each
minislot belongs to a station.
• When a station needs to send a data frame, it makes a
reservation in its own minislot. The stations that have made
reservations can send their data frames after the
reservation frame
Reservation access method

• Figure shows a situation with five stations and a five-minislot reservation frame.
• In the first interval, only stations 1, 3, and 4 have made reservations. In the second
interval, only station 1 has made a reservation.

12.55
 Polling
• Polling works with topologies in which one device is
designated as a primary station and the other devices
are secondary stations.
• All data exchanges must be made through the primary
device even when the ultimate destination is a secondary
device.
• The primary device controls the link; the secondary
devices follow its instructions. It is up to the primary
device to determine which device is allowed to use the
channel at a given time
Select and poll functions in polling access method

• If the primary wants to receive data, it asks the secondaries if they have anything to
send; this is called poll function.
• If the primary wants to send data, it tells the secondary to get ready to receive; this is
called select function. 12.57
 Token
Passing
• In the token-passing method, the stations in a network
are organized in a logical ring.
• In other words, for each station, there is a predecessor and
a successor.
• The station having the token can access the channel and
send the data.
• When a station has some data to send, it waits until it
receives the token from its predecessor. It then holds
the token and sends its data.
Logical ring and physical topology in token-passing access method

12.59
CHANNELIZATIO
N
Channelizationis multiple-access method in which
a
bandwidth of a the
link available
is shared in time,
frequency,
between or
different through
In this code,
section, we
stations.protocols.
channelization discuss three

1. Frequency-Division Multiple Access (FDMA)

2. Time-Division Multiple Access (TDMA)
3. Code-Division Multiple Access (CDMA)

12.60
Frequency-division multiple access (FDMA)

• Channel spectrum divided into frequency bands.

• Each station assigned fixed frequency band.
• Unused transmission time in frequency bands go idle.
• Example: 6-station LAN, 1,3,4 have packet, frequency bands 2,5,6 idle

12.61
Frequency-division multiple access (FDMA)

12.62
Note

In FDMA, the available bandwidth

of the common channel is divided into bands that
are separated by guard bands.

12.63
 Time-division multiple access (TDMA)

• Suppose the channel supports N nodes and that the transmission rate of
the channel is R bps.
• TDM divides time into time frames and further divides each time frame
into N time slots.
• Each time slot is then assigned to one of the N nodes.
• Example: 6-station LAN, 1,3,4 have packet, slots 2,5,6 idle

12.64
 Time-division multiple access (TDMA)

Major drawbacks: First, A node is limited to an average rate of

R/N bps even when it is the only node with packets to send.
Second drawback is that a node must always wait for its turn in
the transmission sequence again, even when it is the only node
with a frame to send.

12.65
Time-division multiple access (TDMA)

12.66
Note

In TDMA, the bandwidth is just one channel

that is timeshared between different
stations.

12.67
 Code-division multiple access (CDMA)

• CDMA assigns a different code to each node, While TDM and FDM assign
time slots and frequencies respectively.
• Each node then uses its unique code to encode the data bits it sends.
• If the codes are chosen carefully, CDMA networks have the wonderful
property that different nodes can transmit simultaneously.
• Their respective receivers correctly receive a sender’s encoded data bits in
spite of interfering transmissions by other nodes.
• Example: Used in military and widespread civilian use, particularly in
cellular telephony.
• Because CDMA’s use is so tightly tied to wireless channels.
12.68
Note

In CDMA, one channel carries all transmissions

simultaneously.

12.69
Simple idea of communication with
code

12.70
Chip
sequences
Data representation in
CDMA
Sharing channel in CDMA
General rule and examples of creating Walsh tables
Note
The number of sequences in a Walsh table needs to be
N = 2m .
 Example

Find the chips for a network with

a. Two stations b. Four stations

Solution
We can use the rows of W2 and W4 in Figure:
a. For a two-station network, we have
[+1 +1] and [+1 −1].

b. For a four-station network we have

[+1 +1 +1 +1], [+1 −1 +1 −1],
[+1 +1 −1 −1], and [+1 −1 −1 +1].
 Example

What is the number of sequences if we have 90 stations in our network?

Solution
The number of sequences needs to be 2m. We need to choose m = 7 and
N = 27or 128. We can then use 90
of the sequences as the chips.
 Example 12.8

Prove that a receiving station can get the data sent by a specific sender if it
multiplies the entire data on the channel by the sender’s chip code and then
divides it by the number of stations.

Solution
Let us prove this for the first station, using
example.
our can
previous four-stationthe data on
We D say the channel c2 +
=
The receiver which wants tothat c1+ data sent d3
get the c3 1 multiplies
by station + these
data by(d1
c1. d2 d4 c4).
 Example
(continued)

When we divide the result by N, we get d1 .

 Ethernet

• Ethernet is a set of technologies and protocols that are used primarily in LANs. It was first
standardized in 1980s as IEEE 802.3 standard.
• Ethernet is classified into two categories:
• Classic Ethernet : which solves the multiple access problem using the techniques we have
studied previously.
• Switched Ethernet : In which devices called switches are used to connect different
computers.

• It is important to note that, while they are both referred to as Ethernet, they are quite
different.
• Classic Ethernet is the original form and ran at rates from 3 to 10 Mbps.
• Switched Ethernet is what Ethernet has become and runs at 100, 1000, and 10,000 Mbps,
in forms called fast Ethernet, gigabit Ethernet, and 10 gigabit Ethernet.
• In practice, only switched Ethernet is used nowadays. 12.80
Ethernet

12.81
 Classic Ethernet

• The historical forms of Ethernet in chronological order showing how they

developed.
• Since Ethernet and IEEE 802.3 are identical except for a minor difference,
Many people use the terms ‘‘Ethernet’’ and ‘‘IEEE 802.3’’ interchangeably.

12.82
 Switched Ethernet

• Ethernet soon began to evolve away from the single long cable
architecture of classic Ethernet.
• The problems associated with finding breaks or loose connections drove it
toward a different kind of wiring pattern, in which each station has a
dedicated cable running to a central hub.
• A hub simply connects all the attached wires electrically, as if they were
soldered together.

12.83