Medium Access Control

Multiple Access Protocol

Point-to-Point vs Broadcast Links

Networks can have two types of links:

• Point-to-Point Links: Direct connection between transmitter and receiver where the link is not shared (e.g., fiber optic, twisted pair)
• Broadcast Channels: Multiple transmitters and receivers connected via a shared channel (e.g., Ethernet, WiFi)

Important

Collision: Occurs when a node receives two or more signals simultaneously, causing interference and data corruption.

Motivation

A multiple access protocol is a distributed algorithm that determines how nodes share a communication channel - specifically deciding when a node should transmit.

Ideal Protocol Requirements

1. Efficiency: When one node wants to transmit, it should send at full link rate bits/second
2. Fairness: When nodes want to transmit, each should get bits/second on average
3. Decentralization: No special coordinator node (preferred when possible)
4. No Synchronization: No requirement for synchronized clocks or time slots (when possible)
5. Simplicity: Easy to implement in networks

Taxonomy of MAC Protocols

MAC protocols can be categorized into three main types:

• channel partitioning: divide channel into pieces for exclusive use (fair, not efficient)
• random access: nodes transmit randomly, collisions possible (efficient, not fair)
• taking turns: nodes take turns transmitting (balances efficiency and fairness)

Channel Partitioning

Time Division Multiple Access (TDMA)

• Idea: divide time into equal-size slots, assign each station a fixed slot in rotating frames
• Pros: achieves fairness, simple implementation
• Cons: Bandwidth waste when nodes have nothing to transmit (static allocation)

Frequency Division Multiple Access (FDMA)

• Idea: divide frequency spectrum into bands, assign each station exclusive frequency band
• Pros: achieves fairness, simple implementation
• Cons: Bandwidth waste when nodes have nothing to transmit (static allocation)

Random Access Protocols

Nodes access channel randomly without a priori coordination:

• Transmit at full channel rate when in turn
• No coordination between nodes
• Collisions can occur and must be handled

Hence, the protocol should define:

• How to detect collisions
• How to recover from collisions

Slotted Aloha

• All frames same size
• Time divided into equal slots (one frame transmission time)
• Nodes synchronized - transmit only at slot beginning
• Collision detection through satellite rebroadcast

How slotted Aloha works:

• Fresh frame → transmit in next slot
• Collision → retransmit in subsequent slots with probability
• Success → move to next frame

Efficiency Analysis

Assuming we have nodes in a saturated network (always have data to send), the probability of a given node transmit successfully in a time slot is:

Therefore, the probability of any node transmitting successfully in a time slot is:

To maximize efficiency, we want to:

which is reached at , and thus the maximum efficiency is

Pure (Unslotted) Aloha

Unlike Slotted Aloha, pure aloha use simpler primitives:

• No synchronization required
• Transmit immediately when frame arrives

• Vulnerability period: 2 packet times (vs. 1 packet time in slotted)

Efficiency: Approximately 18% (half of Slotted Aloha)

Carrier Sense Multiple Access (CSMA)

Principle: “Listen before you speakA”

Basic CSMA Operation

• Sense channel before transmitting
• If idle → transmit entire frame
• If busy → defer transmission

Problem: Collisions still possible due to propagation delay

CSMA/CD (Collision Detection)

CSMA/CD is widely used in ethernet, it act like a polite conversationalist, who listens while speaking, and stops talking when hearing others:

1. Sense channel
2. If idle → start transmission
3. While transmitting → continue listening
4. If collision detected → abort transmission and send jam signal
5. Use Binary Exponential Backoff for retransmission

Binary Exponential Backoff (BEB)

After -th collision:

• Choose random from
• Wait bit times
• Retry transmission

Efficiency of CSMA/CD

As shown below, the CSMA/CD efficiency goes to 1 as the ratio of propagation delay to transmission time goes to 0:

where:

• : maximum propagation delay between two nodes
• : time to transmit the frame

Taking Turns Protocols

Combine benefits of channel partitioning and random access.

Polling Protocol

Operation:

• Master node invites other nodes to transmit in turns
• Master sends polling frame → node responds with data
• Used in Bluetooth

sequenceDiagram
    participant M as Master
    participant N1 as Node 1
    participant N2 as Node 2
    participant N3 as Node 3

    M->>N1: Poll
    N1->>M: Data
    M->>N2: Poll
    N2->>M: Data
    M->>N3: Poll
    N3->>M: No data

Concerns:

• Polling overhead
• Latency with many nodes
• Single point of failure (master)

Token Passing Protocol

Operation:

• Token (control message) passes sequentially between nodes
• Only token holder can transmit
• Used in ring networks
• Token released after transmission complete

Concerns:

• Token overhead
• Latency in large rings
• Single point of failure (token loss)

Key Takeaways

• No perfect MAC protocol - each has trade-offs between efficiency, fairness, and complexity

• Protocol choice depends on application:

  • TDMA/FDMA: Predictable traffic patterns
  • Random access: Bursty, unpredictable traffic
  • Taking turns: Mix of both scenarios

• Efficiency vs. Fairness trade-off is fundamental in MAC protocol design

• Propagation delay is critical factor in collision-based protocols