Medium Access Control - KZHU.ai 🚀

Table of Contents

Broadcast networks are of high bandwidth and low cost. All information will be sent to all users, no routing is really necessary in a broadcast network. Share media is the basis of broadcast networks, like radio over air, copper or coaxial cable.

The key issue is: how to share the medium when there is a competition? The answer is Medium Access Control, its primary function is to minimize or eliminate the instance of the collisions to achieve a reasonable utilization of the medium.

There are two broader categories of schemes for sharing a broadcast transmission medium:

Static channelization	Involve the partitioning of the medium into separate channels that are then dedicated to particular users. For example: satellite transmission, cellular telephone, Frequency division multiple access (FDMA), Time division multiple access (TDMA) Coded division multiple access (CDMA).
Dynamic medium access control	Involves a dynamic access sharing of the medium on a peripheral basis that is better matched to situations in which user’s traffic is bursty. Two basic approaches are: 1. Scheduling. taking turns (polling), or request for slot in transmission schedule. For example: token ring, wireless LANs. 2. Random access. Loose coordination. Send, wait, retry if necessary. For example: Aloha, Ethernet.

Channelization techniques are suitable when stations generate a steady stream of information that makes efficient use of the dedicated channel. But, channelization is inflexible in allocation of bandwidth to users with different requirements and inefficient for bursty traffic. However Dynamic Media Access Control schemes are much better at handling bursty traffic.

Ring networks often use scheduling approaches. It involves the use of a token for Media Access Control. A station holds a token transmits into the ring and token is passed to the next station. Scheduling techniques are also used in multi job lines that were used in early data networks to connect a number of terminals to a central computer.

In a random access approach, a station can transmit whenever ready. The problem is, simultaneous transmissions can occur and therefore collision may occur, then a re-transmission strategy is required.

The Impact of Delay-Bandwidth Product

Some transmission resources will be utilized implicitly or explicitly to transfer coordination information. Recall that the delay-bandwidth product, i.e. 2 ( t_prop + t_proc ) * R, where R is bandwidth, plays a key role in the performance of Automatic Repeat Request protocols. It is also a key parameter in the performance of media access control protocols.

In a configuration that there are 2 stations trying to share a common channel:

A station (with the frame to send) listens to the communication channel and transmits if channel found idle.
Stations monitor the channel to detect collisions.
- If collision occurs, stations that begin transmitting earlier re-transmits.
The propagation delay t_prop between the two stations is fixed, and known between those two stations.

Station A - - - - - t_prop - - - - - Station B

Case 1: A started transmission at t = 0, B does not transmit anything before t = t_prop. So A captures the channel.

Case 2: A started transmission at t = 0, B started transmission just before t = t_prop, at that time, A’s signal has not reached B yet. There is a collision. B can detect the collision soon thereafter, however, A only detects that collision at about two propagation time t = 2 t_prop (the round trip delay).

At this point, both stations are aware that they are competing for the channel, they need to figure out a way to resolve their contention. As they know the value of propagation delay t_prop, they can measure the time duration since the time when they began transmitting to the time when the collision occurred. The stations that have began transmitting earlier will re-transmit as soon as the channel becomes quiet.

Two propagation delay 2 t_prop is required to coordinate the access for each frame transmitted. So efficiency and max throughput are therefore derived:

a = t_prop / (L / R)

Efficiency = L / (L + 2 t_prop R) = 1 / (1 + 2 t_prop R / L) = 1 / (1 + 2 a) (%)

Throughput = L / ((L + 2 t_prop R) / R) = L / (L / R + 2 t_prop ) = R / (1 + 2 a) (bits/sec)

where
t_prop : propagation delay
L / R : time to transmit a frame
a : normalized delay-bandwidth
R : transmission rate or bandwidth (bits / second)
L : length of frame (bits)

Normalized delay-bandwidth product, i.e. the ratio of propagation delay t_prop over the frame transmission time L / R, plays a key role in performance measurement of Media Access Control protocol.

Random Access: ALOHA

ALOHA is one of random access MAC protocols. It was originated as University of Hawaii needed a means to interconnect terminals at campuses located in different islands to the host computer at the main campus. It is a simple scheme: a station transmits whenever data that it has to transmit.

If more than one frames are transmitted at the same time, they collide with each other and therefore, all are lost.
If the acknowledgement was not received within the timeout, station picks a random backoff, and retransmits frame after backoff time. The randomization is intended to reduce the likelihood of additional collisions between the station retransmissions.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   ↑t₀-X    ↑t₀    ↑t₀+X      ↑t₀+X+2t_prop (backoff B starts)        ↑t₀+X+2t_prop+B (retransmits)

We assume all frames have same lengths and the same transmission time X. The first frame transmission at t₀ is done without any scheduling, the transmission is done at t₀+X, while the outcome of the transmission is only obtained at t₀+X+2t_prop.

Any other frame that begins its transmission between t₀-X and t₀ will also collide with the reference frame. Therefore, the probability of a successful transmission is a probability that there are no additional frame transmissions in the vulnerable period which is from t₀-X to t₀+X, i.e. two X seconds.

The system’s throughput is a system workload (in terms of number of transmission attempts per unit of time), multiply the probability of frame transmission is successful.

S = G P_success

where
S : throughput, the average number of successful frame transmission per X seconds
G : workload, the average number of transmission attempts per X seconds
P_success : probability that a frame transmission is successful
X : frame transmission time (assume constant)

Abramson used an approach to find the probability that there is no collision with the reference frame. He assumes that frame arrivals are equally likely to occur at any time, since using the backoff algorithm.

P_success → e^-2G as n → ∞

S = G e^-2G

where
n : X is divided into n intervals of duration Δ = X / n

The performance of ALOHA scheme can be improved by reducing the probability of collisions. If we reduce the vulnerable period, we can reduce the collision probability.

Slotted ALOHA

Slotted ALOHA reduce the collision probability by constraining the stations to transmit in a synchronized manner. Time is slotted for frame transmission. All stations keep track of transmission time slots and only initiate transmissions at the beginning of a time slot. By doing so, it will reduce the vulnerable period from two frame transmission time 2X to just X, i.e. from kX to (k+1)X.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   ↑kX    ↑(k+1)X      ↑t₀+X+2t_prop (backoff B starts)        ↑t₀+X+2t_prop+B (retransmits)

The cost of slotted ALOHA is awaiting delay because stations can only initiate the transmissions at a beginning of a time slot. The probability of a successful frame transmission is approximately e^-G.

P_success → e^-G as n → ∞

S = G e^-G

where
n : X is divided into n intervals of duration Δ = X / n

We can compare the throughput S of ALOHA and that of Slotted ALOHA:

	P_success	S = G P_success	Max S ocurr when
ALOHA	e^-2G	< 1/2e (≈ 0.184)	G = 0.5 (frames / frame arrival time X)
Slotted ALOHA	e^-G	< 1/e (≈ 0.368)	G = 1 (frame / frame arrival time X)

ALOHA schemes are simple but not very effective because of high frame collisions.

Random Access: CSMA and CSMA-CD

The low maximum throughput of Aloha protocol is due to the wastage of transmission bandwidth because of frequent collisions. When collision occur, they involve entire frame transmission time.

By sensing the communication medium for the presence of a carrier signal from other stations, these collisions can be reduced by avoiding transmissions that are certain to cause collisions. A station can determine whether there is an ongoing transmission, this capability is called carrier sense.

In Carrier Sensing Multiple Access (CSMA) schemes, a station senses the channel before it starts transmission:

if busy, either wait or schedule backoff.
if idle, start transmission.

From the two station example above, we learn that a station would capture the channel after one propagation delay t_prop. Therefore, vulnerable period is reduced to one propagation delay. The normalized propagation delay has a significant impact on the maximum achievable throughput of a CSMA scheme.

a = t_prop / X

where
a : normalized propagation delay
t_prop : propagation delay
X : frame transmission time

There are different CSMA options, mainly due to the backoff strategies:

1-persistent CSMA (the most greedy)	Start transmission as soon as the channel becomes idle. Low delay. Low efficiency due to relatively high collision rate. For small a, the throughput is better than Slotted ALOHA. For a > 1, the throughput is worse than ALOHA.
p-persistent CSMA (adjustable greedy)	If busy, wait till channel become idle. If idle, transmit with probability p; or wait `t_prop` time and re-sense with probability 1-p.
Non-persistent CSMA (the least greedy)	If busy, wait a backoff period, and then sense carrier again. If idle, start transmission. High delay. High efficiency. For small a, the throughput is higher than 1-persistent CSMA. For a > 1, the throughput is worse than ALOHA.

CSMA with Collision Detection

CSMA schemes improve over Aloha scheme by reducing the vulnerable period from one or two frame transmission times (X ~ 2X) to just a single propagation delay t_prop. However, collisions still involve entire frame transmission time.

Generally frame transmission time X is far greater than propagation delay t_prop, if a station can detect that a collision is taking place, and abort the transmission right away, the waste would be reduced to time of detecting collision and aborting a transmission. Quickly terminating a damaged frame saves both time and bandwidth. This is called CSMA with Collision Detection. If collisions are detected, all of stations involved:

abort their transmissions
reschedule a random backoff time
try again at a scheduled time

Reaction Time

Again, in a 2-system example, propagation delay is fixed.

A begins to transmit at t = 0.
B begins to transmit at t = t_prop – δ
B detects collision at t = t_prop
A detects collision at t = 2 (t_prop – δ)

A - - - - - - - - - - t_prop - - - - - - | - δ - B
⇒ t=0
                                                       ← t=t_prop-δ
                                                             → t=t_prop
⇐ t=2(t_prop-δ)

It takes 2 t_prop to find out if channel has been captured. This is the action time of CSMA with Collision Detection.

Contention Resolution

So, in CSMA-CD, collisions can be detected and resolved in 2 propagation delays. Each contention slot is also designed as 2 propagation delays. Once a contention period is over, a station will successfully occupy the channel, the station will take frame transmission time (X seconds) to transmit a frame. It takes one propagation delay for a station to find out that a transmission is just over, and then to start a contention again.

To know the efficiency of the CSMA-CD model, we needed to know how long does it take to resolve contention on a successfully captured channel. We know that contention is resolved if exactly only one station transmits in a contention slot (2 t_prop).

Let’s assume there are n active stations in a network and each station may transmit with probability p in each contention time slot. We have the probability of successful capture:

P_success = n p (1-p)^n-1

That is 1 station transmits in probability p and the other n – 1 stations each is not transmitting with probability 1 – p. By taking derivative of P_success, we find its max value occurs at p = 1/n.

P^max_success → 1 / e
⟹ 1 / P^max_success → e

Therefore on average, it takes e attempts (contention slots) to resolve contention. So average contention period is 2 t_prop e seconds.

Throughput

At maximum throughput, the systems alternate between contention periods and frame transmission times:

2 t_prop e → X → 2 t_prop e → X → 2 t_prop e → X ...

So, the maximum throughput is:

Throughput = X / (2 t_prop e + X + t_prop)
= 1 / (2 e a + 1 + a) = 1 / (1 + (2e + 1) a)
= 1 / (1 + (2e + 1) (R d / v L) )

where
a = t_prop / X (normalized propagation delay)
X = L / R (frame transmission time, seconds per frame)
L : frame lengths (bits per frame)
R : bandwidth (bits per second)
t_prop = d / v (transmission delay, seconds)
v : speed (meters per second)
d : diameter of system (meters)
2e + 1 ≈ 6.44

When the normalized propagation delay factor a is small, CSMA with collision detection has the best maximum throughput, but when a is large, Aloha schemes have better maximum throughput since doesn’t depend on the factor a.

Scheduling Approaches

Randomness access can achieve a limited maximum throughput and result in large variation in frame delays when the traffic loads are heavy. Scheduling approaches attempt to produce an orderly access to the transmission medium but they often increase computational or procedural complexity. There are two main scheduling approaches: reservation and polling.

Reservation

Collision-free. Transmissions are organized into cycles. Each cycle begins with a reservation interval and is followed by frame transmissions. In the simplest case, the reservation interval consists of m mini-slots. In a basic reservation system, 1 mini-slot for each station to request reservation for frame transmission.

By listening to the reservation interval, stations determine the order of frame transmissions in the corresponding cycle. Mini-slot should cover the round-trip propagation delay. The length of the cycle is determined by the number of stations that have frames to transmit.

For example: initially station 3 and 5 have reservations to transmit frames. In cycle 3, station 8 become active and makes reservation.

If the propagation delay is negligible, then cycle 3 will include frame transmission from station 8.

Cycle 1	Cycle 2	Cycle 3	Cycle 4	…
		↓ Station 8 reserves
R 3 5	R 3 5	R 3 5 8	R 3 5 8

If the propagation delay is non-negligible, the reservation could not take effect until some fixed number of cycles later. The reason is that one station reservation must be heard by all other stations which takes at least one propagation delay.

Reservation system can be centralized or distributed:

Centralized	A central controller listens to reservation information, decides order of transmission, issues grants to stations.
Distributed	Via an election process, each station determines its slot for transmission from the reservation information.

The basic reservation system can be modified so that stations can reserve more than one mini-slots.

Single Frame Reservation

In single frame reservation scheme, only one frame transmission can be reserved within a reservation cycle. Let us assume mini-slot duration is v X, where v < 1 and almost negligible, then a single frame transmission needs v X + X seconds. The communication link is fully loaded when all stations transmit. Therefore the maximum efficiency is

ρ_max = M X / (M X + M v X) = 1 / (1 + v) (%)

where
X : frame transmission time
v : mini-slot duration ratio to X
M : number of stations

Multiple Frame Reservation

In multiple frame reservation scheme, more than one frame transmission can be reserved within a mini-slot. Suppose k frame transmissions can be reserved with a reservation message, and if there are M stations, as many as k M frames can be transmitted in (v X M + k X M) seconds. Therefore the maximum efficiency is

ρ_max = k M X / (k M X + M v X) = 1 / (1 + v / k) (%)

where
k : number of frame reserved in a mini-slot
X : frame transmission time
v : mini-slot duration ratio to X
M : number of stations

Random Access Reservation

Random access reservation means each station transmits its reservation message randomly until the message goes through. When there are a large number of light-traffic stations, dedicating a mini-slot to each station is inefficient particularly when the propagation delay is non-negligible.

Slotted ALOHA can be combined with a reservation scheme, in other words, stations use Slotted ALOHA when reserving mini-slots. On average, each reservation takes at least e attempts, so the effective time required to make a reservation is e v X. The maximum efficiency is

ρ_max = X / (X + e v X) = 1 / (1 + 2.71 v) (%)

where
e: Euler's number
X : frame transmission time
v : mini-slot duration ratio to X

One such combination of Slotted ALOHA and reservation system is a General Packet Radio Service (GPRS).

Besides the random access reservation, reservation could also be channelized, where the reservation messages from different stations are multiplexed without any risk of collision. Typically used in TDMA.

Polling

Polling is the generalization of time-division multiplexing. It provides fairness through regular access opportunities. I can provide bounds on access delay. However the performance of polling will deteriorate with large delay-bandwidth product.

Polling systems can be either centralized or distributed:

Centralized	a central controller accepts requests from stations and issues grants to transmit.
Distributed	stations implemented a decentralized algorithm to determine transmission order.

My Certificate

For more on Medium Access Control, please refer to the wonderful course here https://www.coursera.org/learn/peer-to-peer-protocols-local-area-networks

My #119 certificate from Coursera

Related Quick Recap

Reliable Services and Data Link Controls

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!