Computer Networks

Data Link Layer - Medium Access Control

Prof. Dr. Oliver Hahm

2023-12-01

Coordinated Medium Access

  • If multiple Network Interface Cards (NICs) are connected to a medium the access needs to be coordinated
  • Otherwise collisions (simultaneous transmissions) may occur
  • We distinguish between
    • Contention-based Protocols
      • Participants compete for medium access
      • Multiple NICs may transmit simultaneously \(\Rightarrow\) collisions must be handled
      • Perform well for low to medium utilization and bursty traffic
    • Contention-free Protocols
      • Access to the medium is allocated in advance
      • Collisions can be completely avoided
      • Perform well for high utilization and can guarantee fair use of the capacity

Contention-based

ALOHA

ALOHA 1

  • No central control, no coordination between stations
  • Stations start sending whenever they want to

Source: Wikipedia, CC 3.0

  • Collision may occur
  • No fairness
  • Very simple solution without any requirements

Slotted ALOHA

  • Send packets of fixed length within fixed time-slots

    \(\Rightarrow\) Requires common time-base for synchronization

  • Stations start sending whenever they want to

Source: Wikipedia, CC 3.0

  • Only complete collision may occur
  • No fairness
  • Improved throughput
  • Increased delay
  • Used for first GSM networks

Performance of ALOHA

  • According to an analysis from the queuing theory the throughput \(S\) of a network using ALOHA MAC looks as follows:

© by Pearson Education-Prentice Hall and D. Wetherall, 2011

  • For 1 attempted transmission per packet time the achieved throughput peaks at \(\approx\) 18 % resp. 37 % of the channel’s capacity

  • Performance is rather low

CSMA

CSMA

  • Carrier Sense \(\rightarrow\) Listen before talk
  • Multiple Access \(\rightarrow\) Multiple stations compete for the medium
  • p-persistent CSMA:
    • Medium is busy: keep listening until it becomes idle
    • Medium is idle: With probability p, transmit the frame
      \(\Rightarrow\) with probability 1-p, wait until next time slot and then sense the medium again
  • non-persistent CSMA:
    • Medium is busy: wait a random amount of time, before sensing the medium again
    • Medium is idle: transmit the frame immediately

Performance of CSMA

  • Comparing the performance for the different variants of CSMA to ALOHA:

© by Pearson Education-Prentice Hall and D. Wetherall, 2011

  • The lower the probability \(p\) the better the performance (particular for higher load)
  • Latency may suffer for lower values of \(p\)

CSMA/CD

CSMA/CD

  • Collision Detection
  • During transmission, keep sensing the medium to detect collisions
  • If collision detected, stop frame transmission and send a JAM signal to guarantee that everyone detects the collision
    \(\Rightarrow\) Time wasted on collisions is reduced
  • Wait a random amount of time before transmitting again
  • Waiting time is determined by how many collisions have occurred before (exponential backoff algorithm)

Example: Ethernet

  • For Ethernet networks with Hubs or using a Bus (e.g., 10Base5)
  • When using switches, there is no need to use CSMA/CD
  • Only applicable if nodes are able to detect collisions

Functioning of CSMA/CD

If a network device wants to transmit frames via Ethernet, it …

  1. Monitors the transmission medium
    • Transmission medium is idle \(\Longrightarrow\) step 2
    • Transmission medium is busy \(\Longrightarrow\) step 3
  1. Start transmission and continue to monitor the transmission medium
    • Successful transmission
      • Signal success to upper network layers \(\Longrightarrow\) step 5
    • Collision is detected
      • Stop frame transmission and send the 48 bits long (jam signal) to announce the collision \(\Longrightarrow\) step 3
  1. Transmission medium is busy. Check the number of transmission attempts:
    • Maximum number not yet reached
      • Wait a random time \(\Longrightarrow\) step 1
      • The random time is calculated using the backoff method
    • Maximum number is reached \(\Longrightarrow\) step 4
  1. Error
    • Maximum number of transmission attempts reached
    • Signal error to upper network layers \(\Longrightarrow\) step 5

CSMA/CA and MACA

CSMA/CA

  • In wireless networks collisions cannot be detected reliably
    • Sending and receiving (i.e., sensing collisions) at the same time is difficult
    • Hidden terminal problem
  • \(\Rightarrow\) Goal: Collision Avoidance
  • Sender:
    • If medium is idle for a certain amount of time slots (DIFS), transmit frame
    • If no ACK received, retransmit frame
  • Receiver
    • Check if received frame OK (using CRC), send ACK with a short time delay (SIFS)

Functioning of CSMA/CA

Source: Grundkurs Computernetzwerke, Jürgen Scherff, Vieweg + Teubner (2010)

  • First, the sender listens to the transmission medium
    (\(\Longrightarrow\) carrier sense)
  • The transmission medium needs to be idle for a short period
    • This period is called Distributed Interframe Spacing (DIFS) \(\approx 50\mu s\)
  • If the transmission medium is idle for the duration of 1 DIFS, the station can start sending a frame
  • If a station receives a frame, which passes the CRC check, it waits for a short period
    • This period is called Short Interframe Spacing (SIFS) \(\approx 10\mu s\)
    • Next, the receiver sends an acknowledgement frame (ACK)
  • DIFS and SIFS guarantee for CSMA/CA a minimum spacing, when a sequence of frames shall be transmitted
  • If another DIFS with an idle transmission medium has expired, a backoff time is calculated
    • The backoff time is calculated by using a random value between the minimum and maximum contention window and multiplying this random value with the slot time
      • After the backoff time has expired, the frame is transmitted
  • If during the backoff time period, another station occupies the transmission medium, the counter variable is stopped until the transmission medium is idle again for the duration of at least one DIFS.

MACA
(Multiple Access with Collision Avoidance)

  • CSMA/CA reduces the number of collisions, but cannot fully avoid them
  • A better collision avoidance implements MACA/MACAW
    • Concept: Sender and receiver exchange control frames first
      • This way, all stations in the network learn that a transmission will start soon
    • Control frames: Request To Send (RTS) and Clear To Send (CTS)
      • They contain information about the occupation time of the channel

Station Y cannot receive the RTS frame from X, but the CTS frame from the Access Point

  • Collisions can only occur during the transmission of RTS and CTS frames
    • Because of the hidden terminal problem

Functioning of MACA

Source: Grundkurs Computernetzwerke, Jürgen Scherff, Vieweg + Teubner (2010)

  • After the DIFS, the sender transmits a RTS frame to the receiver
  • The receiver acknowledges the reservation request by waiting the SIFS and then transmitting a CTS frame, which also contains the period of time, the sender wants to reserve the transmission medium
  • After the receiver successfully received the data frame, it waits for the period of a SIFS and transmits an ACK frame to the sender
  • If the transmission medium is occupied, no further station tries to transmit a frame, until the end of the Network Allocation Vector (NAV)
    • The NAV is a counter variable that each station manages by itself
      • Reduces the number of collisions
      • Contains the expected occupation time of the transmission medium
      • Is decremented over time, until it reaches value \(0\)
  • Advantages:
    • Fewer collisions, because it solves the problem of hidden terminals
    • Less energy consumption, because no transmission attempts during NAV
  • Drawbacks:
    • The reservation of the transmission medium causes delays
    • The RTS and CTS frames are overhead

Contention-free

Token Passing

  • A Token frame is sent around the ring \(\rightarrow\) defining the sending order
  • Only the station that currently has the token may send
  • Idea can be used without ring too, e.g., token bus

TDMA

Time Division Multiple Access (TDMA)

  • Time is divided into time slots
  • Each time slot is assigned to one particular host \(\rightarrow\) scheduling
  • During the time slot this host can use the full channel capacity
  • The schedule can be static or dynamic
  • Some time slots may be assigned for broadcast traffic
  • Combination with contention-based MAC is possible

FDMA

Frequency Division Multiple Access (FDMA)

  • Subdivide spectrum into sub-channels
  • Assign sub-channel to host or link
  • Control traffic and beacons are typically sent on fixed channels
  • Static vs. dynamic assignment
  • \(\rightarrow\) Graph coloring problem

Example: IEEE 802.15.4e

  • IEEE 802.15.4 is a specification for PANs, cf. Zigbee
  • IEEE 802.15.4e is an amendment to the MAC layer for Time-Slotted Channel-Hopping (TiSCH)
  • Combining TDMA and FDMA

CDMA

Code Division Multiple Access (CDMA)

  • Hosts can access the medium at the same time on the same frequency using different coding schemes
  • These codes have to be orthogonal
  • Forward Error Correction (FEC) can be used to restore erroneous frames

Summary

You should now be able to answer the following questions:

  • Why a media access control mechanism is important?
  • What is the difference between contention-based and contention-free media access?
  • Which performance can ALOHA, different CSMA variants, and contention-free MAC protocols achieve?
  • How can collisions be detected or avoided?

Computer Networks - Data Link Layer - Medium Access Control - WS 23/24