Medium Access Control: Methods, Protocols & Performance

TAKEAWAYS:

• Contention vs. Controlled Access: CSMA/CD (Ethernet) and CSMA/CA (Wi-Fi) resolve collisions differently, while polling and token passing enforce strict turn-taking.
• Channel Partitioning: FDMA, TDMA, and CDMA divide bandwidth by frequency, time, or code—each suited to specific scenarios (e.g., GSM vs. 5G).
• Performance Metrics: Throughput, delay, and fairness are quantified via formulas (e.g., $\text{Throughput}=\frac{P}{1+5a}$ for slotted ALOHA).
• Real-World Impact: MAC protocols directly affect app responsiveness (e.g., Pathao’s ride-matching latency or Ncell’s call setup time).
• Error Handling: CRC and acknowledgments (ACK/NACK) ensure data integrity in noisy environments like Kathmandu’s crowded 4G networks.
• Trade-offs: No single MAC method is optimal—choices depend on cost, scalability, and medium characteristics (wired vs. wireless).

1. Why Medium Access Control (MAC)?

MAC protocols regulate how devices access a shared communication channel to avoid collisions and maximize efficiency. Without MAC, devices would transmit simultaneously, leading to data loss—a problem familiar to anyone who’s experienced Wi-Fi dead zones or dropped calls on Ncell.

Key Challenges in MAC Design

mindmap
  root((MAC Challenges))
    Collision
      "Devices transmit simultaneously → Data loss"
    Fairness
      "Some devices hog bandwidth (e.g., a single Daraz server overwhelming others)"
    Efficiency
      "Minimize idle time (e.g., empty time slots in TDMA)"
    Scalability
      "Works for 2 devices (e.g., home Wi-Fi) or 10,000 (e.g., NEPSE trading floor)"

Collisions occur when two devices transmit at once in a shared medium (e.g., old 10 Mbps Ethernet). (Image: Mattias.Campe, CC BY-SA 4.0, via Wikimedia Commons)

2. Contention-Based MAC Protocols

Devices compete for the channel without a central coordinator. Used in Ethernet (CSMA/CD) and Wi-Fi (CSMA/CA).

A. Pure ALOHA and Slotted ALOHA

• Pure ALOHA: Devices transmit anytime; collisions occur if two frames overlap.
  • Throughput: $S=G{e}^{-2G}$ (max 18.4% efficiency).
  • Example: Early packet radio networks (predecessor to modern IoT).
• Slotted ALOHA: Time divided into slots; transmissions start only at slot boundaries.
  • Throughput: $S=G{e}^{-G}$ (max 36.8% efficiency).
  • Worked Example: Suppose 10 devices share a channel with $G=0.5$ (average 0.5 transmissions/slot). Throughput $S=0.5\times e^{-0.5}\approx 0.303$ (30.3% efficiency).

sequenceDiagram
    participant Device1
    participant Device2
    participant Channel
    Device1->>Channel: Transmit (Slot 1)
    Device2->>Channel: Transmit (Slot 1)  # Collision
    Channel-->>Device1: Collision detected
    Channel-->>Device2: Collision detected
    Device1->>Channel: Backoff (random delay)
    Device2->>Channel: Backoff (random delay)

B. CSMA (Carrier Sense Multiple Access)

Devices listen before transmitting to avoid collisions.

• 1-Persistent CSMA: If channel is idle, transmit immediately.
• Non-Persistent CSMA: If busy, wait a random time before retrying.
• p-Persistent CSMA: If idle, transmit with probability $p$; else wait a slot.

C. CSMA/CD (Carrier Sense with Collision Detection)

Used in Ethernet (IEEE 802.3).

1. Listen: Sense if channel is idle.
2. Transmit: If idle, send data.
3. Collision Detection: If two devices transmit simultaneously, detect collision via voltage spikes.
4. Backoff: Wait $2^k\times 512$ bit times (exponential backoff), then retry.

Worked Example: Ethernet Collision

• Two devices (A and B) transmit at the same time.
• Collision detected after 64 bytes (minimum frame size).
• Both stop transmitting, send a JAM signal, and wait $2^k\times 512$ bit times before retrying.

sequenceDiagram
    participant A
    participant B
    participant Channel
    A->>Channel: Transmit Frame
    B->>Channel: Transmit Frame  # Collision
    Channel-->>A: Collision detected
    Channel-->>B: Collision detected
    A->>Channel: JAM signal
    B->>Channel: JAM signal
    A->>Channel: Backoff (e.g., 1024 bit times)
    B->>Channel: Backoff (e.g., 1024 bit times)

Why 64-byte minimum frame?

• Ensures collision detection before transmission completes.
• Formula: $\text{Propagation delay}\times 2\times \text{Bandwidth}=64$ bytes (for 10 Mbps Ethernet).

3. Controlled Access MAC Protocols

A central authority or token controls access to prevent collisions.

A. Polling

• A central controller (e.g., hub, switch) polls each device in turn.
• Pros: Simple, no collisions.
• Cons: Inefficient if many devices have little data (e.g., NTC’s old telephone switching systems).

sequenceDiagram
    participant Controller
    participant Device1
    participant Device2
    Controller->>Device1: Poll (Request to send)
    Device1->>Controller: Data (if any)
    Controller->>Device2: Poll
    Device2->>Controller: Data

B. Token Passing

• A token circulates among devices.
• Only the device holding the token can transmit.
• Used in Token Ring (IEEE 802.5) and FDDI.

Example: Token Ring Network

• Devices connected in a ring; token passes sequentially.
• If a device has data, it holds the token until transmission completes.
• Failure Handling: If token is lost, a monitor station regenerates it.

stateDiagram-v2
    [*] --> Idle
    Idle --> TokenSent: Token passed to next device
    TokenSent --> DataTransmit: Device has data
    DataTransmit --> TokenSent: Transmission complete
    TokenSent --> [*]: Token circulates

4. Channel Partitioning MAC Protocols

The channel is divided among users to avoid contention.

A. Frequency Division Multiple Access (FDMA)

• Channel divided by frequency (e.g., FM radio, GSM).
• Each user gets a fixed frequency band.
• Example: GSM cellular networks assign a unique frequency to each call.

B. Time Division Multiple Access (TDMA)

• Channel divided by time slots (e.g., GSM, digital TV).
• Each user gets a time slot in a repeating frame.
• Example: Ncell’s 4G network uses TDMA to assign slots to multiple users.

Worked Example: TDMA in GSM

• A 200 kHz channel is divided into 8 time slots.
• Each slot carries 22.8 kbps → Total bandwidth = 183.2 kbps.
• If 4 users share the channel, each gets 45.6 kbps.

C. Code Division Multiple Access (CDMA)

• Users share the same frequency and time but use unique codes (e.g., 5G, GPS).
• Spread Spectrum: Signal is spread over a wide bandwidth using a pseudo-noise (PN) code.
• Example: Ncell’s 5G uses CDMA to allow multiple users simultaneously.

Comparison Table: FDMA vs. TDMA vs. CDMA

5. Random Access vs. Controlled Access vs. Channel Partitioning

classDiagram
    class MACProtocol {
        <<abstract>>
        +accessMethod()
    }
    class ContentionBased {
        +collisionHandling()
    }
    class ControlledAccess {
        +centralCoordination()
    }
    class ChannelPartitioning {
        +resourceDivision()
    }
    MACProtocol <|-- ContentionBased
    MACProtocol <|-- ControlledAccess
    MACProtocol <|-- ChannelPartitioning
    ContentionBased : +ALOHA, CSMA/CD, CSMA/CA
    ControlledAccess : +Polling, Token Passing
    ChannelPartitioning : +FDMA, TDMA, CDMA

In the Real World

1. Pathao’s Ride-Matching Latency

   • Uses CSMA/CA-like contention in its backend servers to assign drivers to requests.
   • If two servers try to assign the same driver simultaneously, a collision avoidance mechanism (similar to RTS/CTS in Wi-Fi) resolves it.
   • Impact: Faster matching = happier users.

2. Ncell’s 4G/5G Networks

   • TDMA in 4G: Time slots are dynamically allocated to users based on demand (e.g., during peak hours in Kathmandu).
   • CDMA in 5G: Allows multiple users to share the same spectrum without interference, improving capacity in crowded areas like Thamel.
   • Example: During a concert, Ncell’s 5G CDMA ensures smooth streaming for thousands simultaneously.

3. Daraz’s Order Fulfillment Queue

   • Token Passing Analogy: Orders are processed in a "tokenized" sequence (like a token ring) to ensure fairness.
   • FDMA-like Partitioning: High-priority orders (e.g., same-day delivery) get dedicated "frequency bands" (server resources).

4. Khalti’s Payment Processing

   • Uses CSMA/CD-like contention in its microservices to handle simultaneous transactions.
   • If two users pay at the exact same millisecond, Khalti’s backend detects the "collision" and retries with backoff.

5. NTC’s Fiber-Optic Backbone

   • WDM (Wavelength Division Multiplexing): A type of FDMA where multiple signals are sent over different wavelengths in a single fiber.
   • Example: NTC’s fiber links between Kathmandu and Pokhara use WDM to carry voice, internet, and TV signals simultaneously.

Exam Tip

What Examiners Look For

1. Definitions with Examples

   • Always pair definitions with real-world systems (e.g., "CSMA/CD is used in Ethernet; CSMA/CA in Wi-Fi").
   • Example Answer:

     "CSMA/CD is a contention-based protocol where devices listen before transmitting. If a collision occurs (e.g., two laptops on a shared Ethernet hub), a JAM signal is sent, and devices wait $2^k\times 512$ bit times before retrying."

2. Performance Metrics

   • Memorize formulas for throughput (ALOHA, CSMA) and delay.
   • Example:

     "For slotted ALOHA with $G=0.6$, throughput $S=0.6\times e^{-0.6}\approx 0.276$ or 27.6%."

3. Diagrams and Traces

   • Draw sequence diagrams for handshakes (e.g., RTS/CTS in CSMA/CA).
   • Show timeline diagrams for TDMA/FDMA.
   • Example Question: "Explain the RTS/CTS handshake in CSMA/CA with a diagram."

     sequenceDiagram
         participant Sender
         participant Receiver
         participant Channel
         Sender->>Channel: RTS (Request to Send)
         Receiver->>Channel: CTS (Clear to Send)
         Sender->>Channel: Data
         Receiver->>Channel: ACK

4. Comparison Tables

   • Compare CSMA/CD vs. CSMA/CA, FDMA vs. TDMA vs. CDMA, or polling vs. token passing.
   • Example Table:

     Protocol	Collision Handling	Medium	Example
     CSMA/CD	JAM signal	Wired	Ethernet
     CSMA/CA	RTS/CTS	Wireless	Wi-Fi
     Token Passing	Token rotation	Ring	Token Ring

5. Worked Numerical Problems

   • Solve for throughput, delay, or backoff time.
   • Example:

     "In a CSMA/CD network with 10 Mbps bandwidth and 200 m cable, what is the minimum frame size to detect collisions within 51.2 µs?" Solution: $\text{Propagation delay}=\frac{200\text{ m}}{2\times 10^8\text{ m/s}}=1\text{ µs}$ $\text{Minimum frame size}=1\text{ µs}\times 10\text{ Mbps}\times 2=20\text{ bytes}$ (Note: Real Ethernet uses 64 bytes for safety margin.)

6. Real-World Applications

   • Link concepts to Nepali tech (e.g., "Ncell’s 5G uses CDMA to handle 10,000 users in a stadium").
   • Avoid vague answers like "used in networks"; specify the exact protocol/system.

Common Mistakes to Avoid

• Ignoring the Medium: CSMA/CD is for wired networks; CSMA/CA is for wireless. Always state which applies.
• Forgetting Backoff: In CSMA/CD, backoff is exponential ($2^k\times 512$ bit times).
• Mixing FDMA/TDMA/CDMA: FDMA divides by frequency, TDMA by time, CDMA by code.
• Skipping Units: Always include units in calculations (e.g., "throughput in frames/sec").

Quick Revision Checklist

• Can you draw a CSMA/CD collision scenario?
• Do you know the throughput formula for ALOHA?
• Can you compare polling vs. token passing in a table?
• Can you explain how TDMA works in GSM?
• Can you relate CDMA to 5G in Nepal?
• Can you calculate minimum frame size for Ethernet?