Implementing the PI AQM in the Linux Kernel

Introduction

Active Queue Management (AQM) algorithms have taken centerstage in today’s Internet age. Routers now have very large buffers that aren’t put into good use by standard Passive Queue Management (PQM) algorithms leading to the bufferbloat problem.

The Proportional Integral (PI) Controller is an AQM algorithm designed using classical control system techniques. The original paper also discusses how PI is an improvement over RED (Random Early Detection), another famous AQM. An extension of the PI Controller, PIE (Proportional Integral Extended) was implemented and merged in Linux 3.14.

Since PIE was already implemented in the Linux kernel, we merely had to alter the existing code without the extra bits in PIE. PI uses a different drop probability calculation and has a few other minor modifications.

Development

This is just a summary of the changes we’ve made till now. For more details, look at commit history.

• Created a copy of sch_pie.c
• Renamed all pie functions to pi.
• Removed burst_time related statements.
• Added tc_pi_xstats
• Updated include/uapi/linux/pkt_sched.h

In iproute2:

• Created tc/q_pi.c
• Updated include/uapi/linux/pkt_sched.h

Testbed

The testbed has two hosts with two routers in between. The hosts have a 100 Mbps bandwidth but the link between the routers have a 10 Mbps bandwidth which is a bottleneck. The testbed is an oversimplification of realworld networks but the bottleneck would allow us to showcase PI’s performance against other AQMs.

There are additional links which are USB-LAN interfaces from Peer-0 to Router 1 and Router 2 to facilitate flent being able to retrieve statistics from the routers

There are 12 TCP flows between the two hosts. Flent was used to gather statistics required for testing.

Analysis

We compared PI against PIE with the default knobs in each algorithm.

AQM	Queue Length
PI
PIE

AQM	Bandwidth and Ping
PI
PIE
AQM	Bandwidth and Ping Box and Whisker Plots
PI
PIE