Medium Access Control

Introduction

Core Questions

• What purpose does the data link layer serve in OSI network model?
• How does collision occur in wireless communication?
  • What are hidden and exposed terminal problem?
• What are the major categories for medium access control protocols?
• How to save energy in the MAC protocol?

Learning Objectives

• Definition of the data link layer in the OSI network model
  • Medium Access Control
  • Logical Link Control
• Characteristics of collision problem in wireless communication
  • Hidden terminal problem
  • Exposed terminal problem
• MAC layer protocols
  • Deterministic access
  • Ordered access
  • Random access

Table of Contents

Overview

OSI 7-Layer Network Model

Data-Link Layer

• Physical Layer: handles transmission of raw bits
• What is not taken care of…
  • Handling collision
  • Multiplexing
  • Error checking
  • Framing

Data-Link Layer

• Logical Link Control (LLC)
  • IEEE 802.2 standard
  • recognizing where frames begin and end in the bit-stream
  • (de)multiplexing different protocols to be transmitted over the MAC layer
  • optionally providing flow control, and detection and retransmission of dropped frames
    • Usually provided by transport layer protocols (TCP) in an end-to-end fashion
• Medium/Media Access Control (MAC)

What is MAC?

• Defines how a node obtains a channel when it needs to
  • Determines who gets to send data at any given time
  • Avoid Collision

Design Considerations

• What kind of a resource do we have?
  • Frequency: bandwidth
  • Time: Latency
  • Energy
• How much does a node need?
  • How often?
  • How regular? Is the communication bursty or not?
• What kind of a “guarantee” should be provided?
• Do we need central control or “let things happen as they may”?
• Complexity/Fairness/…

The Collision Problem in Wireless Communications

• Two nodes send to the same node at the same time
• Interference of data: data loss

Ethernet vs. Wireless

• Ethernet
  • Medium is clear
    • if you sense no carrier, there is no one sending data on the wire
  • Node can send and receive at the same time
• Wireless LAN
  • Medium is not clear
    • possible that some node is sending data but is out of your range
  • Cannot send and receive at the same time
    • (assuming a single frequency)

The “Hidden Terminal” Problem

• Station C is sending data to station B.
• Station A wants to do the same and listens for other frames being sent.
• Since A is out of the range of station C, it does NOT notice its frames and thinks the media is free.

• A and C transmit simultaneously to B, and B loses both frames.

  Hidden Terminal Problem

  by Andrei Stroe under GNU Free Document License; from Wikipedia

The “Exposed Terminal” Problem

• The two transmitters (S1, S2) in the middle are in range of each other.
• The two receivers (R1, R2) are out of range of each other
• If a transmission between S1 and R1 is taking place:
  • However, S2 can “hear” S1’s transmission
  • S2 concludes that it will interfere with S1
  • So S2 chooses NOT to transmit

• However R1 cannot hear S2 and R2 cannot hear S1.

  Exposed Terminal Problem

  by Fibonacci under Public Domain; from Wikipedia

Wasted Energy in Communication

• Collisions
  • Data become corrupted
  • Expend more energy for re-transmission
• Overhearing
  • Receiving a frame intended for another node
  • Expend energy receiving a frame that is useless
• Control Packet Overhead
  • Large overhead translates into sending larger packets or more packets, and therefore more energy expended
• Idle Listening
  • Waiting to receive a frame
  • Receiver expends energy and receives no data
  • #1 source of wasted energy

Collision Problem (Wireless Version)

• Collision cannot be sensed when transmitting
• Hidden Terminal problem
• Exposed Terminal problem
• Energy concern

Types of MAC

• Ordered Access
• Deterministic Access
  • Some of the protocols are in the physical layer
• Random Access/Contention-Based Access
• Hybrid

Ordered Access

Ordered Access

• Not random
• Not controlled by a central control point that allocates channels
• Token Ring
  • Introduced by IBM in 1984
  • Standardized in 1989 as IEEE 802.5
  • Was successful in corporate environments
  • Taken over by Ethernet (Random Access)

Token Passing

• Only the system which has some “token” can communicate

  “IBM Multistation Access Unit” by Raymangold22 under CC0 1.0; from Wikipedia

• Token is passed to the next candidate in a sequential manner

  Example of a Token Ring Network

  by Andrew28913 under CC BY-SA 3.0; from Wikipedia

Problems with Ordered Access

• How about in a wireless network?
  • Nodes might leave?
  • Break the Order
  • Take away the token

Deterministic Access

Deterministic Access

• Controlled by a central control point that allocates channels
  • Time Division Multiple Access (TDMA)
  • Frequency Division Multiple Access (FDMA)
  • Space Division Multiple Access (SDMA)
  • Code Division Multiple Access (CDMA)
• Requires access points for coordination

Frequency Division & Time Division

• Frequency Division Duplexing (FDD)
  • Two distinct frequencies at the same time for the two directions
  • Capacity is determined by frequency band allocation, making it difficult to make a dynamic change.
• Time Division Duplexing (TDD)
  • Two distinct sets of time slots on the same frequency for the two directions
  • Cheaper since without the need of a diplexer to isolate transmission and receptions.
  • Possible to change the uplink and downlink capacity ratio dynamically according to the needs.
  • Time latency because only half-duplex
  • Guard period is necessary
• Both are used in 4G (not compatible)
  • China Unicom, Telecom: FDD
  • China Mobile: TDD -> FDD

Time & Frequency Division Multiple Access (TDMA & FDMA)

• TDMA: Multiple users share the same frequency band via repeating “time slots”
  • Transmission for any user is non-continuous: buffer-and-burst digital data & modulation needed, lower battery consumption
  • Larger overhead: synchronization bits for each data burst, guard bits for variations in propagation delay and delay spread
• FDMA: Assign different frequency bands to individual users
  • Available spectrum is divided into a number of “narrowband” channels

LTE Resource Block [Lea2018]

LTE Resource Block

• Each LTE frame is 10ms and 20MHz, 2MHz of which are used as guard band.
• A resource block of 180kHz and 0.5ms can be allocated to each user.
• \( (20-2)/0.18 \times 10/0.5 = 2000 \) resource blocks in 1 frame.
• Each resource block is further divided into \(12\times 15Khz \) subcarriers.
• 7 symbols can be transmitted by 1 subcarrier (\(0.5 ms \times 15kHz\))
• 1 resource block can transmit 84 OFDM symbols
• \(84\times 2000 = 168k\) OFDM symbols can be transmitted in 1 frame
• The symbol rate is 16.8M/s
• Assuming 64-QAM, the raw bit rate is \(16.8\times \log_264 = 100.8Mbps\).
• With \(2\times 2\) MIMO, the throughput can be further increased to 201.6Mbps.

Code Division Multiple Access (CDMA)

• Exploits mathematical properties of orthogonality
• The code from different users are orthogonal to each other
  • or “statistically” orthogonal if PN sequence is used
• To decode the signal, one need to compute the inner product of the received signal with the corresponding PN sequence.

Space Division Multiple Access (SDMA)

• Traditional mobile network has no information on the position of the mobile units
  • Hence, the signal is transmitted in all directions
  • Likewise, in reception, the antenna receives signals coming from all directions
    • including interference signals.
• For SDMA, the antenna, both in transmission and reception, is adapted to each user to obtain highest gain in the direction of that user.
  • This is often done using phased array techniques.

Random Access

Random Access

• Randomly access media, usually detect collision after it happens
  • ALOHA
  • Carrier Sense Multiple Access (CSMA)
  • Carrier Sense Multiple Access w/ Collision Detection (CSMA/CD)
  • Carrier Sense Multiple Access w/ Collision Avoidance (CSMA/CA)

ALOHA

• ALOHAnet was a pioneering computer networking system developed at the University of Hawaii.
  • Became operational in June, 1971,
  • the first public demonstration of a wireless packet data network.
• ALOHA originally stood for Additive Links On-line Hawaii Area.
• The ALOHAnet employed
  • a new medium access control: ALOHA protocol
  • and UHF: 300Mhz - 3GHz
• ARPANET: each node could only talk directly to a node at the other end of a wire or satellite circuit

Slotted ALOHA

• Time is divided into “slots” of one frame duration
  • E.g., fixed size frames
• When a node has a frame to send, it waits until the start of the next slot to send it
  • Requires synchronization
• If no other nodes attempt transmission during that slot, the transmission is successful
  • Otherwise “collision”
  • Collided frames are re-transmitted after a random delay
• Simple and has low latency under low traffic
• But not efficient under high traffic

Slotted ALOHA

Throughput of Slotted ALOHA

• Assuming that the packet transmission attempts in a time slot follows a Poission distribution of rate \(\lambda\)
  • Valid when there are many nodes, each transmit independently with a small probability

\(P(\#attempts) = \frac{\lambda^k}{k!}\exp(-\lambda).\)

• The probability of idle: \(\exp(-\lambda)\).
• The probability of successful transmission: \(\lambda\exp(-\lambda)\).
• The probability of collision: \(1-\exp(\lambda)-\lambda\exp(-\lambda)\).
• Maximum throughput is \(1/e\approx 0.368\), when \(\lambda = 1\).

Throughput of Slotted ALOHA

Pure ALOHA

• A node can transmit as soon as it has a frame to send
• Each node acts independently
• No need for synchronization
• Smaller delay than slotted version when traffic is low
• More chance for interference

Pure v.s. Slotted ALOHA

• Slotted: Collision can only occur if someone else transmitted at time \(k\)
• Pure: Collision can occur if someone else transmitted between time \(k-1,k+1\)
  • The expected throughput is \(\lambda \exp(-2\lambda)\)
  • Maximum throughput is \(1/2e\approx 0.184\), when \(\lambda = 0.5\).

Throughput of Pure v.s. Slotted ALOHA

Carrier Sense Multiple Access (CSMA)

• Verifies the absence of other traffic before transmitting
• If a carrier is sensed, the node waits for the transmission in progress to finish before initiating its own transmission.
• However, if two nodes try to send a frame at nearly the same time, neither detects a carrier so both begin transmitting.

Carrier Sense Multiple Access w/ Collision Detection (CSMA/CD)

• Sending nodes are able to detect when a collision occurs and stop transmitting immediately, backing off for a random amount of time before trying again
• Used in Ethernet
• Does not work in Wireless
  • hidden node problem
  • cannot send and receive at the same time
  • continuous carrier sensing is energy inefficient

Carrier Sense Multiple Access w/ Collision Avoidance (CSMA/CA)

• IEEE 802.11 Standard
• First, listen to the channel for a pre-determined amount of time so as to check for any activity on the channel
• If the channel is sensed “idle”, then the station is permitted to transmit
• If the channel is sensed as “busy” the station has to delay its next carrier sense for a random amount of time
  • Ethernet will continuously listen to the channel and transmit immediately after the channel is clear for 96bit time
• Additional RTS(Request To Send) / CTS(Clear To Send) mechanism can also be used
  • RTS/CTS are smaller comparing to data packet (low cost of collision)

CSMA/CA

Hidden Terminal Problem

• Partially solves the hidden node problem
  • A sends RTS to B, and B sends CTS back
  • C, although CANNOT hear RTS from A, can hear CTS from B
  • C knows that there is a hidden terminal (B) and back-off for a random amount of time

Exposed Terminal Problem

• Partially solves the exposed terminal problem
• If C receives the RTS from B but not the CTS from A
  • C knows that it can transmit to D and A CANNOT hear it
• However, CTS from A maybe lost due to other reasons

Design Considerations

Random Access

• Carrier sense or not?
  • What is the probability of “hearing someone is talking”?
• Slotted or Unslotted?
• Cost of collision v.s. cost of overhead?

Deterministic v.s. Random

How to Choose?

MAC Layer for Various Wireless Protocols

Hybrid MAC: IEEE 802.15.4

IEEE 802.15.4 Protocol Revisit

• Low-rate Wireless Personal Area Network (WPAN)
• For wireless sensor networks, home automation, home networking, connecting devices to a PC, home security, etc.
• Combines schedule-based and contention-based schemes
• Different roles as different types of nodes

Node Type and Topology

• There are two types of nodes in 802.15.4:

• Device must be connected to a coordinator/PAN coordinator and form a star topology
• Coordinator:
  • can communicate with the devices connected to it
  • or other coordinators (in a peer-to-peer) fashion
  • It can also relay messages from/to its devices
• In addition, one of the coordinators is designated as a PAN coordinator:
  • has the duty of transmitting network beacons and storing node information
  • the PAN coordinator is constantly receiving transmissions and is usually on a dedicated power line
  • also serves as the gateway to LAN/WAN

IEEE 802.15.4 Topology for Star and P2P Network

• Routing protocols can be added to create a mesh network

Medium Access Control for IEEE 802.15.4

Beacon Mode

• PAN coordinator communication
  • Super-frame structure
    • 16 time slots
    • up to 7 time slots in the end of the super-frame can be guaranteed time slots
  • Inactive nodes including coordinator switch off their transceivers
• Data transfer with guaranteed time-slot
  • Device gets guaranteed time slots only if it sends request frames during contention access period
  • Device transmits immediately in time slot without carrier sense or collision avoiding
• Data transfer without guaranteed time-slot
  • Slotted CSMA-CA

Beaconless mode

• PAN coordinator does not send beacon frames
• No guaranteed time-slot
• Un-slotted (not time-synchronized) CSMA-CA
• PAN coordinator must be “on” constantly, although devices can follow their own sleep schedule

Bibliography

• [Lea2018] Parry Lea, Internet of Things for Architects, Packt Publishing, 2018.