Multiple Access Protocols

When a single, shared physical medium is utilized by multiple independent nodes for transmission, coordinating access to the channel becomes a fundamental challenge. Multiple access protocols reside within the Medium Access Control (MAC) sublayer of the data link layer to manage channel allocation, minimize collisions, and maximize channel utilization.

text

               +-----------------------------------------+
               |             Data Link Layer             |
               +-----------------------------------------+
                                    |
                 +------------------+------------------+
                 |                                     |
+---------------------------------+   +---------------------------------+
|  Logical Link Control (LLC)     |   |   Medium Access Control (MAC)   |
|  - Framing, flow/error control  |   |  - Addressing, Multiple Access  |
+---------------------------------+   +---------------------------------+

1. Taxonomy of Multiple Access Protocols

Multiple access strategies are broadly categorized into three distinct paradigms, each offering different tradeoffs between overhead, delay, and determinism.

text

                              Multiple Access
                                 Protocols
                                     |
         +---------------------------+---------------------------+
         |                           |                           |
  Random Access              Controlled Access            Channelization
 (Contention-Based)           (Collision-Free)          (Static Partition)
     |                           |                           |
     +-- Pure ALOHA              +-- Reservation             +-- FDMA
     +-- Slotted ALOHA           +-- Polling                 +-- TDMA
     +-- CSMA                    +-- Token Passing           +-- CDMA
     +-- CSMA/CD
     +-- CSMA/CA

Random Access Protocols (Contention-Based): Stations compete dynamically for the medium. No station has absolute priority, and transmissions are uncoordinated, leading to potential collisions.
Controlled Access Protocols: Stations negotiate or coordinate through scheduling algorithms to determine who gets to transmit, entirely avoiding collisions.
Channelization Protocols: The available channel bandwidth is split statically or dynamically in frequency, time, or code spaces to allow simultaneous, non-interfering communication.

2. Random Access Protocols

In random access methods, any station with data to send can attempt to transmit at will. If multiple stations transmit concurrently, their signals overlap, resulting in a collision that corrupts the frames.

2.1 Pure ALOHA

Developed at the University of Hawaii, Pure ALOHA is the simplest random access protocol. Stations transmit frames immediately when they are generated.

text

Station 1:       +---------+
                 | Frame 1 |
                 +---------+
Station 2:            +---------+
                      | Frame 2 |  <--- Collision Region
                      +---------+
Station 3:                 +---------+
                           | Frame 3 |
                           +---------+
Time: ------------[====================]------------------------->

If a frame is corrupted (due to lack of acknowledgment), the station waits a random amount of time $T_B$ (backoff time) and retransmits. The backoff time is typically calculated using binary exponential backoff:

$T_B = K \cdot T_{fr}$

Where $K$ is a random integer drawn from $[0, 2^n - 1]$ (where $n$ is the collision count) and $T_{fr}$ is the frame transmission time.

Vulnerable Time ( $T_v$ ) in Pure ALOHA

The vulnerable time is the window of time during which an arriving frame can collide with another frame. Let $T_{fr}$ be the frame transmission time. If our frame starts transmission at time $t$ , any other transmission starting between $t - T_{fr}$ and will cause a collision.

text

             t - T_fr            t            t + T_fr
                 |---------------|---------------|
                 <------------------------------->
                      Vulnerable Time = 2 * T_fr

$T_v = 2 \cdot T_{fr}$

Throughput of Pure ALOHA

Assuming the frame arrival process is a Poisson process with parameter $G$ (where $G$ is the average number of frames requested per frame transmission time $T_{fr}$ ), the throughput $S$ (the average number of successful transmissions per interval $T_{fr}$ ) is:

$S = G \cdot e^{-2G}$

The maximum throughput $S_{max}$ occurs when $G = \frac{1}{2}$ : $S_{m a x} = \frac{1}{2} \cdot e^{-}$

2.2 Slotted ALOHA

Slotted ALOHA was designed to double the throughput of Pure ALOHA. It divides the shared channel's time into discrete slots of duration equal to $T_{fr}$ . Stations are only allowed to transmit at the beginning of a time slot.

text

Slot Boundaries:   |       Slot 1       |       Slot 2       |
Station 1:         +--------------------+
                   |      Frame 1       |
                   +--------------------+
Station 2:         +--------------------+
                   |      Frame 2       | <--- Collision occurs 
                   +--------------------+      strictly in Slot 1
Time: -------------[--------------------[--------------------[---->

If a frame generator becomes active mid-slot, it must buffer the frame and wait until the next slot boundary.

Vulnerable Time ( $T_v$ ) in Slotted ALOHA

Since frames can only be initiated at slot boundaries, a collision can only occur if two or more stations attempt to transmit at the exact same slot boundary. Thus, the vulnerable time is reduced to:

$T_v = T_{fr}$

Throughput of Slotted ALOHA

The probability of a successful transmission in a slot is the probability that exactly one frame is generated during the preceding slot interval:

$S = G \cdot e^{-G}$

The maximum throughput $S_{max}$ occurs when $G = 1$ : $S_{max} = 1 \cdot e^{-1} \approx 0.368 \quad (36.8\%)$

2.3 Carrier Sense Multiple Access (CSMA)

To minimize collisions, CSMA implements a "Listen Before Talk" (LBT) rule. A station senses the energy level on the physical medium before attempting transmission.

text

                  +-----------------------+
                  |   Station wants to    |
                  |       transmit        |
                  +-----------------------+
                              |
                              v
                  +-----------------------+
                  |   Sense the channel   | <--------+
                  +-----------------------+          |
                              |                      |
               +--------------+--------------+       |
               |                             |       |
         [ Channel Idle ]             [ Channel Busy ]
               |                             |
               v                             v
       Transmit Frame               Apply Persistence
                                        Strategy

Persistence Strategies

When a station senses a busy channel, it behaves according to one of three persistence strategies:

1-Persistent CSMA:
- The station continuously senses the channel.
- As soon as the channel becomes idle, it transmits with a probability of $1$ .
- Tradeoff: High collision probability when multiple stations are waiting for a transmission to finish.
Non-Persistent CSMA:
- If the channel is busy, the station immediately stops sensing.
- It waits a random period of time and then senses the channel again.
- Tradeoff: Reduces collisions but increases channel idle time (higher latency).
p-Persistent CSMA:
- Used in slotted channels. The station continuously senses the channel.
- When the channel becomes idle, it transmits with probability $p$ . With probability $q = 1 - p$ , it waits for the next slot.
- Tradeoff: Balances the risk of collisions against wasted idle slots.

Vulnerable Time in CSMA

The vulnerable time in CSMA is the time $\tau$ (propagation delay) required for a signal to travel from one end of the medium to the other. If a station transmits at $t_0$ , other stations will not detect the carrier until $t_0 + \tau$ . If another station senses the channel and transmits during this window, a collision occurs.

2.4 Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

Used in wired Ethernet (IEEE 802.3), CSMA/CD augments CSMA by adding a "Listen While Talk" capability. If two stations transmit simultaneously, they detect the resulting signal distortion, immediately abort their transmission, and send a high-frequency jam signal to notify all other nodes.

text

Station A                      Station B
   |                              |
   |--- Frame Transmit ---------->|  (Collision occurs at mid-point)
   |                              |
   |<-- Collision Signal Detected |
   |=== Jam Signal Transmitted ===|
   |                              |

Minimum Frame Size Constraint

For a station to reliably detect a collision, it must not finish transmitting its frame before the collision signal returns. In the worst-case scenario, the two farthest nodes are separated by a propagation delay $T_p$ .

Station A begins transmitting at $t = 0$ .
The signal reaches Station B at $t = T_p - \epsilon$ (just before B senses the carrier).
Station B transmits, causing a collision.
The collision effect travels back and reaches Station A at $t = 2 \cdot T_p - \epsilon$ .

To guarantee A is still transmitting when the collision indicator arrives:

$T_{fr} \ge 2 \cdot T_p$

If the data rate is $R$ bits/sec, the minimum frame size $L_{min}$ (in bits) is:

$L_{min} \ge 2 \cdot T_p \cdot R$

2.5 Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

In wireless networks, CSMA/CD is impractical because the transmitter's own high-power output overwhelms its receiver circuits (the self-interference problem), making collision detection impossible. Wireless networks (IEEE 802.11) instead use CSMA/CA to actively avoid collisions.

CSMA/CA employs three primary mechanisms:

Interframe Space (IFS): When the channel is sensed idle, stations must wait for a brief period called the IFS before transmitting. IFS can vary to prioritize different traffic classes (e.g., SIFS, DIFS).
Contention Window: A backoff timer is chosen randomly from a range. The timer decrements only when the channel is sensed idle.
RTS/CTS Handshaking: To resolve the Hidden Station Problem, the sender transmits a short Request to Send (RTS) frame. The receiver replies with a Clear to Send (CTS) frame. All other stations hearing the CTS remain silent for the duration indicated.

text

Source                         Destination                  Other Stations
  |                                 |                             |
  |--- RTS (Request to Send) ------>|                             |
  |                                 |--- CTS (Clear to Send) ---->| (Deferred state)
  |                                 |                             |
  |========= Data Frame ===========>|                             |
  |                                 |                             |
  |<-------- ACK Frame -------------|                             |

3. Controlled Access Protocols

In controlled access, stations coordinate with one another so that only one station has the right to transmit at any given instant. This design completely eliminates collisions.

3.1 Reservation

Stations must reserve the channel before transmitting. Time is structured into intervals containing a reservation frame followed by data frames.

text

+---------------------------------------+---------------------+
|         Reservation Interval          |   Data Intervals    |
|  [Slot 1] [Slot 2] [Slot 3] [Slot 4]  |  [Frame 1] [Frame 3]|
+---------------------------------------+---------------------+
  (Station 1 & 3 set their mini-slots)    (Only 1 & 3 transmit)

If there are $N$ stations, the reservation interval has $N$ mini-slots. Each station owns one mini-slot. A station sets its mini-slot bit to $1$ to reserve a data slot.

3.2 Polling

Polling operates in topologies with a primary (master) controller and multiple secondary (slave) nodes.

Poll: The primary station asks a secondary station if it has data to send. If yes, the secondary transmits its data.
Select: The primary station wants to send data to a secondary. It sends a select frame to verify if the secondary is ready to receive.

text

Poll Cycle:
Primary Station                 Secondary Node 1             Secondary Node 2
     |                                 |                            |
     |--- Poll Node 1 ---------------->|                            |
     |<-- No Data (NAK) ---------------|                            |
     |                                                              |
     |--- Poll Node 2 --------------------------------------------->|
     |<-- Data Frame -----------------------------------------------|
     |--- ACK ----------------------------------------------------->|

3.3 Token Passing

Stations are organized in a logical ring. A special small frame called the token is circulated around the ring.

text

        +-------> [ Station 1 ] ------->+
        |                               |
        |                               v
  [ Station 4 ]                   [ Station 2 ]
        ^                               |
        |                               v
        +-------< [ Station 3 ] <-------+

A station must capture the token to transmit data.
The token-holding station can transmit frames up to a maximum holding time ( $T_{HT}$ ).
After transmitting, the station releases the token back into the ring.

4. Channelization Protocols

Channelization partitions the available bandwidth of the link in frequency, time, or code spaces, allowing multiple stations to communicate simultaneously without collisions.

text

     Frequency Division (FDMA)                  Time Division (TDMA)
     +-----------------------+              +-----------------------+
Ch3  |      Station 3        |              | Slot 1 | Slot 2 | Slot 3|
     +-----------------------+              +-----------------------+
Ch2  |      Station 2        |              |   S1   |   S2   |   S3  |
     +-----------------------+              +-----------------------+
Ch1  |      Station 1        |              |   S1   |   S2   |   S3  |
     +-----------------------+              +-----------------------+
     0------------------- Time              0------------------- Time

Frequency-Division Multiple Access (FDMA): The total bandwidth is divided into narrow frequency bands. Each station is assigned a dedicated band for continuous transmission.
Time-Division Multiple Access (TDMA): Stations share the entire frequency spectrum but transmit in non-overlapping, periodic time slots.
Code-Division Multiple Access (CDMA): Stations transmit simultaneously over the entire frequency band. Signals are separated using unique, orthogonal mathematical codes.

4.1 Mathematical Analysis of CDMA

In CDMA, each station $i$ is assigned a unique $N$ -bit chip sequence (or vector) $C_i$ . These sequences are chosen to be orthogonal, meaning their inner product is zero:

$C_i \cdot C_j = 0 \quad (\text{for } i \neq j)$

$C_i \cdot C_i = N$

To achieve this, bit values are represented as:

Binary $0 \rightarrow -1$
Binary $1 \rightarrow +1$
Idle state $\rightarrow 0$

Self-Study: Walsh Table Generation

Walsh matrices, which provide orthogonal chip codes, are defined recursively using the following rules:

$W_1 = [ +1 ]$

$W_{2N} = \begin{bmatrix} W_N & W_N \\ W_N & -W_N \end{bmatrix}$

For $N=2$ :

$W_2 = \begin{bmatrix} +1 & +1 \\ +1 & -1 \end{bmatrix}$

For $N=4$ :

$W_4 = \begin{bmatrix} +1 & +1 & +1 & +1 \\ +1 & -1 & +1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & -1 & +1 \end{bmatrix}$

Each row in $W_4$ represents an orthogonal chip sequence $C_i$ of length 4.

Step-by-Step Execution Example

Let us trace a scenario with 2 active stations using Walsh codes of length $N = 4$ derived from $W_4$ :

Station 1 Vector ( $C_1$ ): $[+1, +1, -1, -1]$ (Row 3 of $W_4$ )

text

Let's verify orthogonality:
C1 . C2 = (+1)(+1) + (+1)(-1) + (-1)(-1) + (-1)(+1)
        = 1 - 1 + 1 - 1 = 0 (Orthogonal!)

1. Encoding Phase

Suppose:

Station 1 wants to send a data bit $d_1 = 1 \rightarrow$ represented as $+1$ .
Station 2 wants to send a data bit $d_2 = 0 \rightarrow$ represented as .

Each station multiplies its data bit by its chip sequence:

$S_1 = d_1 \cdot C_1 = +1 \cdot [+1, +1, -1, -1] = [+1, +1, -1, -1]$

$S_2 = d_2 \cdot C_2 = -1 \cdot [+1, -1, -1, +1] = [-1, +1, +1, -1]$

The signals combine on the shared medium as vector addition:

$S_{total} = S_1 + S_2 = [+1-1, \,\, +1+1, \,\, -1+1, \,\, -1-1]$

$S_{total} = [0, +2, 0, -2]$

2. Decoding Phase

To recover the data bit of Station 1, the receiver takes the dot product of the combined signal $S_{total}$ and Station 1's unique chip sequence $C_1$ , then divides by $N = 4$ :

$\text{Recovered}_1 = \frac{S_{total} \cdot C_1}{4}$

$S_{total} \cdot C_1 = (0 \cdot +1) + (+2 \cdot +1) + (0 \cdot -1) + (-2 \cdot -1)$

$S_{total} \cdot C_1 = 0 + 2 + 0 + 2 = 4$

$\text{Recovered}_1 = \frac{4}{4} = +1 \quad (\text{Binary } 1)$

To recover the data bit of Station 2:

$\text{Recovered}_2 = \frac{S_{total} \cdot C_2}{4}$

$S_{total} \cdot C_2 = (0 \cdot +1) + (+2 \cdot -1) + (0 \cdot -1) + (-2 \cdot +1)$

$S_{total} \cdot C_2 = 0 - 2 + 0 - 2 = -4$

$\text{Recovered}_2 = \frac{-4}{4} = -1 \quad (\text{Binary } 0)$

The signals are successfully separated and recovered with zero inter-channel interference.

Summary

Random Access Protocols introduce collisions but do not require setup overhead.
- Pure ALOHA: Transmit immediately; vulnerable time $T_v = 2 \cdot T_{fr}$ ; maximum throughput is $18.4\%$ .
- Slotted ALOHA: Transmit only on slot boundaries; vulnerable time ; maximum throughput is .

Assessed progress

Multiple Access Protocols

Multiple Access Protocols

1. Taxonomy of Multiple Access Protocols

2. Random Access Protocols

2.1 Pure ALOHA

Vulnerable Time ( $T_v$ ) in Pure ALOHA

Throughput of Pure ALOHA

2.2 Slotted ALOHA

Vulnerable Time ( $T_v$ ) in Slotted ALOHA

Throughput of Slotted ALOHA

2.3 Carrier Sense Multiple Access (CSMA)

Persistence Strategies

Vulnerable Time in CSMA

2.4 Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

Minimum Frame Size Constraint

2.5 Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

3. Controlled Access Protocols

3.1 Reservation

3.2 Polling

3.3 Token Passing

4. Channelization Protocols

4.1 Mathematical Analysis of CDMA

Self-Study: Walsh Table Generation

Step-by-Step Execution Example

1. Encoding Phase

2. Decoding Phase

Summary

Key Concepts

Random Access Protocols

Vulnerable Time

CSMA/CD Collision Detection Window

Controlled Access

CDMA Orthogonal Coding

Quick Check

Computer Networks

Computer Networks