FQ-PIE (Flow Queue Proportional Integral controller Enhanced) - Linux Kernel Implementation

This repository contains a Linux kernel module implementation of the FQ-PIE (Flow Queue Proportional Integral controller Enhanced) queuing discipline, as specified in RFC 8033.

Overview

FQ-PIE is an active queue management (AQM) algorithm that combines the benefits of:

• Flow Queue (FQ): Provides fairness by maintaining separate queues for different flows
• PIE (Proportional Integral controller Enhanced): Provides low latency by actively managing queue delay

Key Features

• Per-flow queuing: Packets are classified into flows using a hash-based approach
• Stochastic fairness: Uses hash-based flow classification (multiple flows may map to same slot)
• PIE-based drop decisions: Each flow uses PIE algorithm for congestion control
• ECN support: Optional Explicit Congestion Notification capability
• Memory management: Configurable memory limits per queue and total memory usage
• Round-robin scheduling: Flows are scheduled using deficit round-robin
• Timestamp-based delay calculation: Uses packet timestamps for accurate queue delay measurement

Architecture

Core Components

1. Flow Management

   • Each flow maintains its own PIE variables, deficit counter, and packet queue
   • Flows are organized into "new" and "old" flow lists for scheduling fairness
   • Hash-based flow classification using skb_get_hash()

2. PIE Integration

   • Each flow runs independent PIE algorithm
   • Configurable PIE parameters: target delay, update interval, alpha, beta
   • Support for both byte-mode and packet-mode operation

3. Scheduling

   • Deficit Round Robin (DRR) scheduling between flows
   • New flows get priority over old flows to prevent starvation
   • Configurable quantum (byte credits per round)

Files Description

Kernel Module Files

• sch_fq_pie.c - Main kernel module implementing the FQ-PIE queueing discipline
• Kconfig - Kernel configuration options for FQ-PIE
• Kbuild - Kernel build configuration
• pkt_sched-snippet.h - Netlink API definitions and statistics structures

User-space Tools

• q_fq_pie.c - iproute2 tc utility for configuring FQ-PIE parameters
• Makefile - Build system for compiling and installing the module

Installation

Prerequisites

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

Build and Install

# Compile the kernel module
make

# Install the module (requires root)
sudo make install

# Load the module
sudo modprobe sch_fq_pie

Verify Installation

# Check if module is loaded
lsmod | grep sch_fq_pie

# Check available queueing disciplines
tc qdisc show

Configuration

Basic Usage

# Add FQ-PIE qdisc to interface eth0
sudo tc qdisc add dev eth0 root fq_pie

# Configure with custom parameters
sudo tc qdisc add dev eth0 root fq_pie \
    limit 1000 \
    flows 1024 \
    target 15ms \
    tupdate 15ms \
    alpha 2 \
    beta 20 \
    quantum 1514 \
    memory_limit 32MB \
    ecn

Configuration Parameters

Parameter	Description	Default	Range
limit	Maximum packets in qdisc	10240	1+
flows	Number of flow buckets	1024	1+
target	PIE target delay	15ms	1+
tupdate	PIE update interval	15ms	1+
alpha	PIE alpha parameter	2	0-32
beta	PIE beta parameter	20	0-32
quantum	DRR quantum (bytes)	1514	1-1048576
memory_limit	Memory limit (bytes)	32MB	1+
ecn_prob	ECN marking threshold	10%	0-100
ecn	Enable ECN marking	disabled	-
bytemode	Use byte-mode PIE	disabled	-
dq_rate_estimator	Enable dequeue rate estimation	enabled	-

Viewing Statistics

# Show qdisc statistics
tc -s qdisc show dev eth0

# Show detailed FQ-PIE statistics
tc -s -d qdisc show dev eth0

Statistics Explanation

Qdisc-level Statistics

• packets_in: Total packets enqueued
• dropped: Packets dropped by PIE algorithm
• overlimit: Packets dropped due to queue limit
• overmemory: Packets dropped due to memory limit
• ecn_mark: Packets marked with ECN
• new_flow_count: Number of new flows created
• new_flows_len: Current flows in new list
• old_flows_len: Current flows in old list
• memory_usage: Total memory usage across all queues

Per-flow Statistics

• prob: Current drop probability for the flow
• delay: Current queue delay (milliseconds)
• avg_dq_rate: Average dequeue rate (bits per update interval)

Use Cases

FQ-PIE is particularly useful in scenarios requiring:

1. Fairness between flows: Prevents bandwidth monopolization by single flows
2. Low latency: PIE algorithm maintains low queue delays
3. High throughput: Efficient scheduling and memory management
4. ECN-aware applications: Support for explicit congestion notification

Typical Deployment Scenarios

• Home routers: Fair bandwidth sharing between devices/applications
• Enterprise networks: QoS for different traffic types
• Data centers: Low-latency networking for applications
• ISP networks: Fair queuing for subscriber traffic

Implementation Details

Flow Classification

Flows are identified using a hash of the packet's flow tuple (src/dst IP, ports, protocol). The hash is computed using skb_get_hash() and mapped to flow buckets using reciprocal scaling.

PIE Algorithm Integration

Each flow maintains independent PIE state:

• Probability calculation based on queue delay
• Exponential weighted moving average for delay estimation
• Burst tolerance and dequeue rate estimation

Memory Management

The implementation tracks memory usage per packet and enforces configurable limits to prevent memory exhaustion.

Performance Considerations

• CPU overhead: Hash computation and per-flow PIE calculations
• Memory usage: Scales with number of flows and queue depths
• Scalability: Performance depends on flow count and packet rate

Troubleshooting

Common Issues

1. Module fails to load

   • Check kernel version compatibility
   • Ensure kernel headers are installed
   • Verify PIE module dependencies

2. Configuration rejected

   • Check parameter ranges and syntax
   • Ensure interface exists and is up
   • Verify sufficient privileges

3. Performance issues

   • Monitor CPU usage and memory consumption
   • Adjust flow count and quantum parameters
   • Consider hardware capabilities

Debug Information

# Enable debug messages
echo 'module sch_fq_pie +p' > /sys/kernel/debug/dynamic_debug/control

# Check kernel logs
dmesg | grep fq_pie

Authors and Contributors

• Mohit P. Tahiliani tahiliani@nitk.edu.in
• Sachin D. Patil sdp.sachin@gmail.com
• V. Saicharan vsaicharan1998@gmail.com
• Mohit Bhasi mohitbhasi1998@gmail.com
• Leslie Monis lesliemonis@gmail.com
• Gautam Ramakrishnan gautamramk@gmail.com

License

This project is licensed under the GPL-2.0-only License - see the individual source files for details.

References

• RFC 8033: Proportional Integral Controller Enhanced (PIE)
• Linux Kernel Traffic Control Documentation
• iproute2 Documentation