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 ( tprop + tproc ) * 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
tpropbetween the two stations is fixed, and known between those two stations.
Station A - - - - - tprop - - - - - Station BCase 1: A started transmission at t = 0, B does not transmit anything before t = tprop. So A captures the channel.
Case 2: A started transmission at t = 0, B started transmission just before t = tprop, 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 tprop (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 tprop, 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 tprop is required to coordinate the access for each frame transmitted. So efficiency and max throughput are therefore derived:
a = tprop / (L / R)
Efficiency = L / (L + 2 tprop R) = 1 / (1 + 2 tprop R / L) = 1 / (1 + 2 a) (%)
Throughput = L / ((L + 2 tprop R) / R) = L / (L / R + 2 tprop ) = R / (1 + 2 a) (bits/sec)
where
tprop : 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 tprop 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.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
βt0-X βt0 βt0+X βt0+X+2tprop (backoff B starts) βt0+X+2tprop+B (retransmits)We assume all frames have same lengths and the same transmission time X. The first frame transmission at t0 is done without any scheduling, the transmission is done at t0+X, while the outcome of the transmission is only obtained at t0+X+2tprop.
Any other frame that begins its transmission between t0-X and t0 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 t0-X to t0+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 Psuccess
where
S : throughput, the average number of successful frame transmission per X seconds
G : workload, the average number of transmission attempts per X seconds
Psuccess : 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.
Psuccess β e-2G as n β β
S = G e-2G
where
n : X is divided into n intervals of duration Ξ = X / nThe 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 βt0+X+2tprop (backoff B starts) βt0+X+2tprop+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.
Psuccess β e-G as n β β
S = G e-G
where
n : X is divided into n intervals of duration Ξ = X / nWe can compare the throughput S of ALOHA and that of Slotted ALOHA:
| Psuccess | S = G Psuccess | 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 tprop. 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 = tprop / X
where
a : normalized propagation delay
tprop : propagation delay
X : frame transmission timeThere 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 tprop 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 tprop. However, collisions still involve entire frame transmission time.
Generally frame transmission time X is far greater than propagation delay tprop, 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 = tprop – Ξ΄
- B detects collision at t = tprop
- A detects collision at t = 2 (tprop – Ξ΄)
A - - - - - - - - - - tprop - - - - - - | - Ξ΄ - B
β t=0
β t=tprop-Ξ΄
β t=tprop
β t=2(tprop-Ξ΄)It takes 2 tprop 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 tprop).
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:
Psuccess = n p (1-p)n-1That 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 Psuccess, we find its max value occurs at p = 1/n.
Pmaxsuccess β 1 / e
βΉ 1 / Pmaxsuccess β eTherefore on average, it takes e attempts (contention slots) to resolve contention. So average contention period is 2 tprop e seconds.
Throughput
At maximum throughput, the systems alternate between contention periods and frame transmission times:
2 tprop e β X β 2 tprop e β X β 2 tprop e β X ...So, the maximum throughput is:
Throughput = X / (2 tprop e + X + tprop)
= 1 / (2 e a + 1 + a) = 1 / (1 + (2e + 1) a)
= 1 / (1 + (2e + 1) (R d / v L) )
where
a = tprop / X (normalized propagation delay)
X = L / R (frame transmission time, seconds per frame)
L : frame lengths (bits per frame)
R : bandwidth (bits per second)
tprop = d / v (transmission delay, seconds)
v : speed (meters per second)
d : diameter of system (meters)
2e + 1 β 6.44When 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 stationsMultiple 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 stationsRandom 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 XOne 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
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
