Multiple Access Methods

Nov 15, 2023

Queueing Theory Pillars

Multiple access methods techniques belong to Data-Link layer. They are a field of study under Queueing Theory.

Within a queue system:

born rate $\lambda_k$ is equivalent to packets arrival rate
dead rate $\mu_k$ is equivalent to packets departure rate
mean service time $E\big\{T_x\big\}=1/\mu$
utilization factor $\rho=E\big\{\lambda\big\}E\big\{T_x\big\}$

A given number of hosts (users) have to utilize the same shared resource. Hosts access the shared resource can be in the following ways:

Deterministic: the resource usage is determined beforehand,
Controlled: a host asks for its turn and exclusively use the resource until the drop,
Random: the access of each host is independent from each other host’s access

Characterization parameters are:

S: throughput,
G: offered load,
$t_{\rm ACC}$ : access time.

Throughput is the radio of correctly transmitted bits per second to the average speed of a section of the network. It is a pure number (no measure unit). Offered load is the ratio of the average bits per second a host tries to transmit to the average speed of a section of the network. $t_{\rm ACC}$ is the average time between packet arrival at the transmitting station and successful delivery at the receiving station. It is measured in seconds (sec).

Furthermore, it is possible to demonstrate that:

0 \leq S \leq 1 \quad ; \quad S = \rho \quad ; \quad G \geq 0

Given the following definitions:

N: number of hosts that want to communicate through the shared resource,
C: mean transmission speed of the link (bit/sec),
F: length of the packet to transmit (bit),
$t_F$ : transmission time of F (random variable)
$\tau_P$ : propagation delay

For simplicity’s sake, the article below is based on these assumptions:

failure probability $p$ is irrelevant,
the distribution of inter-arrival times is poissonian

There is no optimal multiple access technique. As any good engineer would say: “It depends”. The transmission medium (physical layer) is crucial for all layers above.

Deterministic Multiple Access Methods

Channels are orthogonal to each other so that the flow of information can be distinguished.

Orthogonality means having high spectral efficiency (at the same bit-rate), using all the available bandwidth. Orthogonality requires extremely high synchronization between the local frequencies of the receiver and transmitter. Frequency deviation would cause inter-carrier interference: crosstalk.

Time Division Multiple Access

TDMA subdivides the time into different slots called waves (or plots). Each wave is then divided into N different time slot, one for each transmitting host. The hosts transmit with C bit/sec of speed every N time slot periods.

Neglecting the so-called “guard times” that are supposed to avoid overlapping signals on the slots, each station transmits at a rate of $C/N$ bit/sec.

Packets departure rate is:

\mu = \frac{C}{NF} \bigg[ \rm \frac{pkt.}{sec} \bigg]

Frequency Division Multiple Access

FDMA requires all stations to transmit simultaneously, but at different frequencies. Neglecting the so-called “guard band”, that should avoid overlapping signals on the frequencies, each station transmits at a rate of $C/N$ bit/sec.

Given the overall band B, the $i$ -th band is $B_i = B/N$ . Packets departure rate remains the same of TDMA.

Characterization parameters

For both TDMA ad FDMA, the throughput S is:

S = \rho = \frac{\lambda}{\mu} = \lambda \frac{NF}{C}

$W_q$ is the average queuing time for a M/D/1 system:

W_q = \frac{\lambda E\big\{t_x^2\big\}}{2(1-\rho)}= \frac{S}{1-S}\frac{NF}{2C}

$W_{\rm slot}$ is the average time slot waiting time:

W_{\rm slot} =\frac{NF}{2C}

$t_x\big|_C$ is the average service time affected by speed C:

t_x\big|_C = \frac{F}{C}\; [\text{sec}]

Transmission time of F is:

t_F = \frac{F}{C}

$\alpha$ is the propagation delay normalized against $t_F$ :

\alpha = \frac{\tau_P}{t_F}

Due to several random factors that insist on the shared resource access, in a TDMA system the access time is:

\eq{ t_{\small \text{ACC}}^{\small (\rm TDMA)} &= W_q + W_{\rm slot} + t_x\big|_C + \tau_P =\\ &= \frac{F}{C}\bigg[\frac{S}{1-S}\frac{N}{2}+\frac{N}{2}+1+\alpha\bigg] =\\ &= t_F\bigg[\frac{S}{1-S}\frac{N}{2}+\frac{N}{2}+1+\alpha\bigg] }

Within FDMA systems, average service time is not affected by speed C:

t_x = \frac{1}{\mu}= \frac{NF}{C}

The access time is:

t_{\small \text{ACC}}^{\small (\rm FDMA)} = \frac{F}{C}\bigg[\frac{S}{1-S}\frac{N}{2}+N+\alpha\bigg]

Random Multiple Access Methods

The hosts independently decide when to use the shared resource. This behavior cause collisions, that implies retransmission of the packets. Those methods are used in scenarios where stations need to communicate rarely, or small packets.

Pure Aloha System

When a host wants to use the resource, it just does. This leas to partial or total packets overlaps. It becomes then necessary to retransmit the packets. Retransmissions are performed after a random back-off time called $t_B$ .

time analysis

Characterization of a Pure Aloha system can be performed under the following hypotheses:

packets have all the same length F
$\implies E\{F\}=F,\;E\{t_F\}=t_F$
$A \ll F$ : ACK/NACK packets are negligible compared to F, ACK/NACK overlaps are not taken into account

First hypothesis tells that the mean value of F is actually F: no randomness. Same as for its transmission time $t_F$ . The second one tells that A is small enough compared to F.

G has an arrival rate of $\widetilde{\lambda} = \lambda + \lambda_R$ , given $\lambda_R$ the arrival rate of the retransmissions.

\eq{ S &= \lambda \frac{N F}{C} = \lambda N t_F \\ \\ G &= \widetilde{\lambda} \frac{N F}{C} = N \widetilde{\lambda} t_F }

The distribution of arrival times is not no more poissonian. The system is being studied at steady state, so $\lambda_R \neq 0 \implies \widetilde{\lambda} > \lambda$ .

The vulnerability time $t_v = 2 t_F$ is the time in which an overlap can happen.

vulnerability time

Given $\lambda_{\rm TOT} = N \widetilde{\lambda}$ , the probability of $k$ packets’ arrival in a time $t$ is:

P_k (t) = \frac{(\lambda_{\rm TOT} \cdot t)^k}{k!} e^{-\lambda_{\rm TOT} \cdot t}

Then the probability to have no collisions is:

\mathbb{P}\{\text{no collisions}\}= \frac{S}{G}= \mathbb{P}\{0 \text{ collisions in } t_v\}= e^{-N \widetilde{\lambda} 2 t_F} = e^{-2G}

This leas to the throughput formula for Pure Aloha systems: $S = G e^{-2G}$

pure aloha

The maximum point of a graph is found by performing the derivative operation: $\frac{d}{dG} S(G)$ .

G = 0.5 \implies \text{max } \{S(G)\}= \frac{1}{2e}\approx 0.18

Supposing a poissonian traffic despite retransmissions: $W_q \longrightarrow 0$

Given the random variable $k$ , the back-off time is evenly distributed between $0$ and $k \cdot t_F$ . Its mean value is:

E\{t_B\} = \frac{k}{2}t_F

Time for a retransmission is:

\eq{ t_{\rm rtx} &= t_F + t_A + 2 \tau_P + E\{t_B\} = \\ &= t_F + t_A + 2 \tau_P + \frac{k}{2}t_F }

$G/S$ is the mean number of transmissions, so $\frac{G}{S}-1$ is the mean number of retransmissions. Access time is given by:

\eq{ t_{\text{ACC}} &= \bigg(\frac{G}{S}-1 \bigg) \bigg( t_F + t_A + 2 \tau_P + E\{t_B\} \bigg) + t_F + \tau_P \approx \\ & \approx \bigg(\frac{G}{S}-1 \bigg) t_F \bigg(1 + 2 \alpha + \frac{k}{2} \bigg) + t_F + \alpha t_F \approx \\ & \approx t_F \bigg[ \bigg(\frac{G}{S}-1 \bigg) \bigg(1 + 2 \alpha + \frac{k}{2} \bigg) +1 +\alpha \bigg] \approx \\ & \approx \frac{F}{C}\bigg[ \bigg(e^{2G}-1 \bigg)\bigg(1 + 2 \alpha + \frac{k}{2} \bigg)+1 +\alpha \bigg] }

Slotted Aloha

Time is subdivided into $t_F$ -long time slots. Hosts access the shared resource randomly, but they wait for the start of the next time slot to communicate. Partially overlapped transmissions can no longer occur. The down arrows in the diagram below denote the time instant where the host would start to transmit.

Slotted Aloha Time

Time slotting implies vulnerability time to be equal to the transmission time of F: $t_v = t_F$ . The ratio of S to G is the probability of no packets’ arrival in $t_v$ time:

\eq{ \frac{S}{G} &= P_0 (t_v) =\\ &= e^{-N \widetilde{\lambda} t_v} =\\ &= e^{-N \widetilde{\lambda} t_F} =\\ &= e^{-G} \\ \implies S &= G e^{-G} }

Pure VS Slotted Aloha

By performing the derivatives again, given $G=1$ it gets $\max\{S(G)\} \approx 0.37$ as maximum throughput.

Slotted time subdivision implies synchronization between hosts, which leads to increasing realization costs.

The access time to the shared resource is given by the average number of retransmissions multiplied by the average retransmission time, to which the transmission time is added.

\eq{ t_{\text{ACC}} &= \bigg( \frac{G}{S} -1 \bigg) \cdot \bigg( t_F + 2 \tau_P + t_A + E\{t_B\} \bigg) + t_F + \frac{t_F}{2} + \tau_P \approx \\ & \approx t_F \bigg[ (e^G -1)(1+2\alpha + \frac{k}{2}) + \frac{3}{2} + \alpha \bigg] }

Remind that $t_A \ll t_F$

Carrier Sensing Multiple Access

Within CSMA, the host that wants to communicate, before starting the transmission, tries to understand if the shared resource is already in use. It is said that the host performs carrier sensing. If the resource is busy, the host does not even start to communicate: it avoids collisions and the subsequent retransmissions.

CSMA can be distinguished into three categories:

Non-persistent CSMA
$1$ -persistent CSMA
$p$ -persistent CSMA

Non-persistent CSMA

Let’s analyze the collision between packets on the time axis.

Non-persistent CSMA caratterization

Transmission lasts $t_F$ , plus the propagation delay $\tau_P$ . The resource remains busy for an additional collision time $t_{cal}$ . It is the time from the transmission start of the first packet to the transmission start of the last packet that cause the collision (in the case of $n\geq 2$ packets collision).

t_{\rm BUSY} = t_{cal}+t_F+\tau_P

Before using the shared resource again, it must be left free for an additional idle time $t_I$ . Its mean value is:

E\{t_I\} = \frac{1}{N\widetilde{\lambda}} = \frac{t_F}{G}

Note that $t_{cal}$ and $t_{\rm BUSY}$ are random variables, unlike $t_F$ and $\tau_P$ .

Collision time mean value is:

E\{t_{cal}\} = t_F \bigg( \alpha - \frac{1-e^{-G \alpha}}{G} \bigg)

Busy time mean value is:

\eq{ E\{t_{\rm BUSY}\} &= t_F + \tau_P + E\{t_{cal}\} =\\ &= t_F \bigg(1+ 2\alpha - \frac{1-e^{-G \alpha}}{G} \bigg) }

Vulnerability time is equal to the propagation delay: $t_v = \tau_P$ , $t_{cal} \leq t_v$ .

The probability to find the resource busy is:

\eq{ P_0 &= \mathbb{P}\{\text{resource busy}\} =\\ &= \frac{E\{t_{\rm BUSY}\}-\tau_P}{E\{t_{\rm BUSY}\}+E\{t_I\}} =\\ &= \frac{G(1+\alpha ) -1 +e^{-G \alpha}}{G(1+2\alpha )+e^{-G \alpha}} }

The usable time $t_U$ is the time in which the resource is being used without suffering conflicts. It applies to every transmission:

\eq{ t_U &= t_F \cdot \mathbb{P}\{\text{no collisions}\} =\\ &= t_F \cdot \mathbb{P}\{0 \text{ arrival in } t_v\} =\\ &= t_F \cdot P_0 (\tau_P) =\\ &= t_F \cdot e^{-N\widetilde{\lambda}\tau_P} }

Its mean value is:

E\{t_U\} = t_F \cdot e^{-G \alpha}

It is now possible to define the cycle time $t_{\rm CYCLE} = t_{\rm BUSY} + t_I$ to rewrite the throughput formula:

\eq{ S &= \frac{E\{t_U\}}{E\{t_{\rm CYCLE}\}} =\\ &= \frac{t_F \cdot e^{-G \alpha}}{t_F \bigg(1+ 2\alpha - \frac{1-e^{-G \alpha}}{G} \bigg) + \frac{t_F}{G}} =\\ &= \frac{G e^{-G \alpha}}{G(1+2\alpha)+e^{-G \alpha}} }

S 1st graph

For $\alpha \longrightarrow 0$ , it gets $S \longrightarrow 1$

S 2nd graph

The access time to the shared resource is given by the average time of retransmissions, multiplied by the average time of the single retransmission, to which the average time of the last transmission is finally added.

t_{\text{ACC}} = t_F \bigg[\bigg(\frac{G}{S}-1\bigg)\bigg(1+2\alpha+\frac{k}{2}+\frac{k}{2}\frac{P_0}{1-P_0}\bigg) +\frac{k}{2}\frac{P_0}{1-P_0}+1+\alpha \bigg]

Before communicating, the waiting time that hosts are subject to, is:

t_{\rm LIB} = t_F \frac{k}{2} \frac{P_0}{1-P_0}

1-persistent CSMA

p-persistent CSMA

$\mathbb{P}\{\cdot\}=p$ is the probability to decide to communicate, by having the resource free. $\mathbb{P}\{\cdot\}=1-p$ is the probability to decide not to communicate, despite having the resource free.

In other words, when the resource is free, the host decide to communicate or not with probability $p$ .

Back-off time must be (at least) equal to the maximum network delay: $t_B \geq \tau_{P_{\rm MAX}}$

Note that non-persistent CSMA is different from 0-persistent CSMA.