PIE (Proportional Integral controller Enhanced) Qdisc for Linux

A Linux kernel module implementation of the PIE (Proportional Integral controller Enhanced) queue discipline (qdisc), designed for Active Queue Management (AQM) to control network congestion and reduce bufferbloat.

Overview

PIE is an Active Queue Management (AQM) algorithm that uses a control theory approach to maintain low latency while maximizing throughput. It dynamically calculates a drop probability based on the current queue delay and trend, providing better performance than traditional tail-drop queues.

Key Features

• Active Queue Management: Proactively drops packets before buffer overflow
• Latency Control: Maintains target queue delay to reduce bufferbloat
• ECN Support: Marks ECN-capable packets instead of dropping when possible
• Adaptive Algorithm: Uses proportional-integral control theory for stability
• Burst Allowance: Handles traffic bursts without excessive drops
• Configurable Parameters: Tunable target delay, drop probability coefficients, and more

Algorithm Details

PIE operates by:

1. Measuring Queue Delay: Tracks current queuing delay using packet timestamps or dequeue rate estimation
2. Calculating Drop Probability: Uses PI controller with configurable alpha (proportional) and beta (integral) coefficients
3. Making Drop/Mark Decisions: Drops packets probabilistically or marks ECN-capable packets
4. Adapting to Conditions: Automatically adjusts to changing network conditions

References

• RFC 8033: Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem

Project Structure

PIE-qdisc-linux/
├── sch_pie.c          # Main PIE qdisc kernel module implementation
├── q_pie.c            # User-space tc utility for PIE configuration
├── Makefile           # Build configuration for kernel module
├── Kbuild             # Kernel build configuration
├── Kconfig            # Kernel configuration options
└── README.md          # This file

Files Description

• sch_pie.c: Core kernel module implementing the PIE qdisc algorithm
• q_pie.c: User-space utility for configuring PIE parameters via tc command
• Makefile: Build system for compiling and installing the kernel module
• Kbuild: Kernel build system integration
• Kconfig: Configuration options for kernel integration

Installation

Prerequisites

• Linux kernel headers for your running kernel
• Build tools (gcc, make)
• Root privileges for module installation

Build and Install

1. Clone or download the source code

2. Build the kernel module:

   make

3. Install the module:

   sudo make install

4. Load the module:

   sudo modprobe sch_pie

Uninstallation

To remove the module:

sudo make unload

Usage

Basic Configuration

Configure PIE on a network interface using the tc command:

# Add PIE qdisc to interface eth0
sudo tc qdisc add dev eth0 root pie

# Configure with custom parameters
sudo tc qdisc add dev eth0 root pie \
    limit 1000 \
    target 15ms \
    tupdate 30ms \
    alpha 2 \
    beta 20 \
    ecn

Configuration Parameters

Parameter	Description	Default	Range
limit	Maximum queue size (packets)	200	1-∞
target	Target queue delay	15ms	1ms-∞
tupdate	Update frequency	30ms	1ms-∞
alpha	Proportional coefficient	2	0-32
beta	Integral coefficient	20	0-32
ecn	Enable ECN marking	disabled	ecn/noecn
bytemode	Use packet size in drop calculation	disabled	bytemode/nobytemode
dq_rate_estimator	Enable dequeue rate estimation	disabled	dq_rate_estimator/no_dq_rate_estimator

Examples

1. Basic PIE with ECN:

   sudo tc qdisc add dev eth0 root pie ecn

2. PIE with custom target delay:

   sudo tc qdisc add dev eth0 root pie target 20ms

3. PIE with byte-mode enabled:

   sudo tc qdisc add dev eth0 root pie bytemode

4. View current configuration:

   tc qdisc show dev eth0

5. View statistics:

   tc -s qdisc show dev eth0

Statistics Output

PIE provides detailed statistics including:

• prob: Current drop probability
• delay: Current queue delay
• pkts_in: Packets enqueued
• overlimit: Packets dropped due to queue limit
• dropped: Packets dropped by PIE algorithm
• maxq: Maximum queue length observed
• ecn_mark: ECN packets marked
• avg_dq_rate: Average dequeue rate (if estimator enabled)

Algorithm Configuration

Tuning Guidelines

1. Target Delay: Set based on application requirements

   • Real-time applications: 5-15ms
   • General internet traffic: 15-30ms
   • Bulk transfers: 30-50ms

2. Alpha (Proportional): Controls responsiveness

   • Higher values: More aggressive dropping
   • Lower values: More conservative approach
   • Typical range: 1-8

3. Beta (Integral): Controls stability

   • Higher values: Better steady-state accuracy
   • Lower values: Reduced oscillation
   • Typical range: 10-50

4. Update Frequency: Balance between responsiveness and stability

   • Higher frequency (lower tupdate): More responsive
   • Lower frequency (higher tupdate): More stable
   • Typical range: 15-50ms

Development

Authors

• Vijay Subramanian (vijaynsu@cisco.com) - Cisco Systems
• Mythili Prabhu (mysuryan@cisco.com) - Cisco Systems
• Naeem Khademi (naeemk@ifi.uio.no) - University of Oslo (ECN support)

License

This project is licensed under GPL-2.0-only. See the SPDX license identifier in source files.

Contributing

This is an experimental/research implementation. For production use or contributions to the mainline Linux kernel, please refer to the official kernel development process.

Troubleshooting

Common Issues

1. Module fails to load:

   • Check kernel headers are installed
   • Verify kernel version compatibility
   • Check dmesg for error messages

2. tc command not found:

   • Install iproute2 package: sudo apt install iproute2

Debug Information

Enable kernel debugging to see PIE algorithm decisions:

echo 8 > /proc/sys/kernel/printk
dmesg -w

Performance Considerations

• PIE adds minimal computational overhead compared to other AQM algorithms
• Memory usage scales with queue limit setting
• Performance impact is generally negligible on modern systems
• Consider disabling dq_rate_estimator for very high-speed interfaces if CPU usage is a concern

Related Work

• CoDel: Another AQM algorithm focusing on controlling delay
• RED: Traditional Random Early Detection algorithm
• FQ-PIE: Flow-queuing variant of PIE for better fairness
• CAKE: Comprehensive AQM solution with additional features

---

For more information about PIE algorithm theory and implementation details, refer to RFC 8033 and the Linux kernel networking documentation.