PURPLE: Dynamic Control of CAKE

PURPLE is an algorithm designed to estimate "useful capacity" and control bufferbloat in wireless networks through dynamic adjustment of CAKE's bandwidth parameter. The algorithm draws inspiration from the BLUE active queue management scheme, itself being an evolution of RED, adapting its congestion detection mechanisms for wireless capacity estimation.

Disclaimer

This repository hosts an application-specific proof of concept implementation of PURPLE that is intended for use with Ubiquiti airMAX radios running airOS. It has been tested on a pair of NanoStation Loco 5ACs, although the Ubiquiti web API might differ between models.

Note: See cake-autorate for a general purpose, production ready alternative for dynamic control of CAKE.

Background

Bufferbloat, or excessive queuing delay under load, is a noticeable quality of service degradation that occurs when latency-sensitive traffic experiences the effects of increased packet buffering delays in network devices. This phenomenon leads to increased latency and reduced network performance, particularly affecting real-time applications.

While FQ-CoDel and CAKE are existing AQM solutions that help mitigate bufferbloat, they require properly configured bandwidth settings. In wireless networks where capacity can be highly variable, static bandwidth settings are insufficient. PURPLE addresses this by dynamically adjusting CAKE's bandwidth parameter based on real-time network conditions.

Quick Start

See the Quick Start Guide for step-by-step instructions on setting up and running PURPLE experiments in a testbed environment.

How PURPLE Works

PURPLE consists of two main components:

1. Queue state monitoring
2. Capacity adjustment based on congestion signals

Queue State Monitoring

PURPLE maintains a marking probability that reflects the congestion state:

p_m(t + \Delta t) = 
\begin{cases}
\min(1, p_m(t) + \delta_i) & \text{if } q_b > 0 \text{ or } \Delta q_d \geq \theta_d \text{ and } t - t_{last} \geq t_f \\
\max(0, p_m(t) - \delta_d) & \text{if } q_b = 0 \text{ and } \Delta q_d < \theta_d \text{ and } t - t_{last} \geq t_{df} \\
p_m(t) & \text{otherwise}
\end{cases}

where:

• $q_b$ is the current queue backlog
• $\Delta q_d$ is the change in packet drops since last measurement
• $\theta_d$ is the drop threshold
• $\delta_i$ is the increment step
• $\delta_d$ is the decrement step
• $t_f$ is the freeze time for increments
• $t_{df}$ is the freeze time for decrements
• $t_{last}$ is the time of last probability update

Adaptive Capacity Management

PURPLE uses the marking probability to estimate the useful capacity:

if in_congestion:
    reduction = p_m × 0.5
    C_target = r_p50 × (1 - reduction)
    C_target = max(C_target, r_tx × α_min)  # Handle rate divergence
else:
    if C_useful is empty:  # Initial state
        C_target = C_p50 × β_safety
    else:
        headroom = max(0, (C_p50 × β_safety) - C_useful)
        if headroom = 0:  # Capacity dropping
            C_target = C_p50 × β_safety
        else:
            C_target = C_useful + (headroom × α_recovery)

# Apply smoothing
if in_congestion or C_target > C_useful:
    C_target = α × C_target + (1-α) × C_useful

C_useful = C_target

where:

• $C_{useful}$ is the estimated useful capacity
• $C_{p50}$ is the median of radio's reported capacity
• $r_{p50}$ is the median of transmission rate
• $p_{enter}$ and $p_{exit}$ are congestion entry/exit thresholds
• $\alpha_{min}$ is the minimum decrease factor
• $\alpha_{recovery}$ is the recovery rate factor
• $\alpha$ is the smoothing factor
• $\beta_{safety}$ is the safety margin factor

Network State Classification

PURPLE classifies the network state based on the marking probability:

\text{State} = 
\begin{cases}
\text{SEVERE\_CONGESTION} & \text{if } p_m > 0.8 \\
\text{MILD\_CONGESTION} & \text{if } p_m > 0.3 \\
\text{STABLE} & \text{otherwise}
\end{cases}

PURPLE-AIMD: Latency-Based Dynamic Bandwidth Control

PURPLE-AIMD is a simplified approach to the regular PURPLE algorithm. The responsiveness of regular PURPLE depends on the polling frequency of target radio queue metrics, which might not always be available for all vendors. Furthermore, these metrics are difficult to obtain in real-time. Utilities such as traffic control (tc) on Linux suffice, but poll-mode operation is not ideal, and PURPLE would ideally be implemented at the qdisc level, a desire that is not viable for the millions of legacy radios that experience bufferbloat.

PURPLE-AIMD offers further improvements to responsiveness by using unidirectional latency measurements as the sole input signal for CAKE bandwidth parameter control. A target latency is set (e.g., 5 milliseconds) and the Additive Increase Multiplicative Decrease (AIMD) algorithm. Resultantly, PURPLE-AIMD is platform agnostic and able to operate in environments where low-level queue metrics are not available.

Mathematical Formulation

PURPLE-AIMD maintains a bandwidth rate $C(t)$ that is updated based on latency measurements. The rate adaptation follows the classic AIMD paradigm, which has good stability properties, and has held the Internet together (as the primary TCP control algorithm) for many decades now.

For each control interval at time $t$, the rate is updated as follows:

C(t + \Delta t) = \begin{cases}
C(t) \cdot (1 - \beta_d) & \text{if } \ell(t) \geq \ell_{critical} \\
C(t) \cdot (1 - \beta_d/2) & \text{if } \ell_{target} + \delta_\ell < \ell(t) < \ell_{critical} \\
C(t) + \alpha_r \cdot \Delta t & \text{if } \ell(t) \leq \ell_{target} + \delta_\ell \text{ and recovery = true} \\
C(t) & \text{otherwise}
\end{cases}

where:

• $\ell(t)$ is the current latency measurement
• $\ell_{target}$ is the target latency (default 15 ms)
• $\ell_{critical}$ is the critical latency threshold (default 30 ms)
• $\delta_\ell$ is the latency tolerance (default 2 ms)
• $\beta_d$ is the decay factor for multiplicative decrease (default 0.1)
• $\alpha_r$ is the recovery rate for additive increase (default 0.5 Mbps)
• $\Delta t$ is the time elapsed since the last update

The rate is further constrained by minimum and maximum limits:

C(t) = \max(C_{min}, \min(C_{max}, C(t)))

Recovery Phase

PURPLE-AIMD maintains a counter for consecutive "good" latency measurements:

g(t) = \begin{cases}
g(t-1) + 1 & \text{if } \ell(t) \leq \ell_{target} + \delta_\ell \\
0 & \text{otherwise}
\end{cases}

It enters the recovery phase when this counter exceeds a threshold:

\text{recovery} = \begin{cases}
\text{true} & \text{if } g(t) \geq g_{threshold} \\
\text{false} & \text{if } \ell(t) \geq \ell_{critical} \text{ or } \ell(t) > \ell_{target} + \delta_\ell
\end{cases}

where $g_{threshold}$ is the "good" latency threshold (default 5).

<!-- Implementation is a work in progress --> <!-- ### Latency Trend Analysis PURPLE-AIMD determines a trend in latency values to anticipate change: ```math \tau(t) = \frac{n\sum_{i=0}^{n-1} i \cdot \ell_{t-i} - \sum_{i=0}^{n-1} i \cdot \sum_{i=0}^{n-1} \ell_{t-i}}{n\sum_{i=0}^{n-1} i^2 - (\sum_{i=0}^{n-1} i)^2} ``` where: - $\ell_{t-i}$ is the latency measured $i$ intervals ago - $n$ is the trend window size (default 5) This represents the slope of the linear regression of recent latency values. -->

Network State Classification

Similar to regular PURPLE, PURPLE-AIMD determines a state for the network via the unidirectional latency measurements:

\text{State} = \begin{cases}
\text{CRITICAL} & \text{if } \ell(t) \geq \ell_{critical} \\
\text{HIGH} & \text{if } \ell_{target} + \delta_\ell < \ell(t) < \ell_{critical} \\
\text{RECOVERY} & \text{if } \ell(t) \leq \ell_{target} + \delta_\ell \text{ and recovery = true} \\
\text{NORMAL} & \text{otherwise}
\end{cases}

PURPLE-AIMD Algorithm

PURPLE-AIMD Controller:
  Initialise: C ← C_initial, g ← 0, recovery ← false, t_last ← 0

  Procedure Update(ℓ, t_current):
    Δt ← t_current - t_last
    t_last ← t_current
    
    if ℓ ≤ ℓ_target + δ_ℓ then
      g ← g + 1
    else
      g ← 0
    end if
    
    if g ≥ g_threshold then
      recovery ← true
    end if
    
    if ℓ ≥ ℓ_critical then
      recovery ← false
      g ← 0
      C ← C · (1 - β_d)
    else if ℓ > ℓ_target + δ_ℓ then
      recovery ← false
      C ← C · (1 - β_d/2)
    else if recovery then
      C ← C + α_r · Δt
    end if
    
    C ← max(C_min, min(C_max, C))
    return C, ℓ_target

Practical Advantages of PURPLE-AIMD

Unlike the original PURPLE algorithm which required access to internal queue metrics, PURPLE-AIMD works as an equipment-agnostic solution, using only latency measurements (ICMP RTT or ideally unidirectional latency) as the control input. This means it can adapt to highly-variable dynamic wireless networks without requiring vendor-specific integrations or implementation.

In practice, PURPLE-AIMD should offer a more consistent user experience, as latency can be measured faster than queue build-up when we are constrained to poll-mode implementation of regular PURPLE, as opposed to a qdisc-level alternative. Furthermore, the platform agnosticism allows deployment across heterogeneous networks, assuming we have control of the device sending data immediately behind the bottleneck link.

However, this design assumes that high latency is indicative of congestion and requires a target latency to be set. In practice, this target latency might be derived through the network operator's intuition of a particular wireless link. It also assumes that repeated low-latency measurements indicate available capacity. The recovery rate should not be excessive to avoid oscillation in the available bandwidth (via adjustment of the CAKE bandwidth parameter).

<!-- Update needed for PURPLE-AIMD... -->

Comparison with BLUE

| Aspect | Original