Christian Huitema's blog

Cloudy sky, waves on the sea, the sun is

Debugging the implementation of BBR in Picoquic

19 Sep 2020

I have spent quite some time developing Picoquic, an implementation of the standard version of QUIC developed in the IETF. My initial goal was just to test whether the standard could be easily implemented, and provide informed feedback to the working group as the standard progressed. Then, I realized that many other developers were happy to use my implementation as test tool, especially in 2017 and 2018 when there were few such implementations available. And then, I got a little bit carried away, started to work on performance, and starting to experiment with congestion control algorithms such as BBR.

It turns out that testing the implementation of an algorithm like BBR is really hard if you are not part of a big company. My colleagues at Google and other places have access to a lot of telemetry. They can test a new version of their software on a "slice" of their vast user base. They will get reports about what work and what doesn't, discover corner cases that defeat their initial design, improve the code, and iterate.

What can a developer do without access to this kind of telemetry? In some cases, the big company teams will describe use cases and issues cases in academic conferences, or in contributions to IETF standards. When they do that, that's great. Otherwise, we may hear from some users, or get bug reports. My approach has been to collect these cases, add them to the suite of tests, and then check that the Picoquic code behaves properly in all those cases.

The Picoquic code is specially designed to make such tests easy to implement. In the test environment, the UDP layer can be replaced by a simulation, and the time services are replaced by a "virtual clock". With that, client, server and network are simulated in a single thread, which can be executed under debugger. Virtual time also means that execution is fast -- an exchange that last minutes in real time can be executed in a fraction of a second.

For example, I noticed by looking at server logs that when a client just abandoned a connection without notice, the server might send a whole lot of packets before realizing that the client is gone. So I added a test to simulate just that. The test reproduced the issue, specifically with my implementation of BBR. Once a connection was established, that implementation did not use packet losses to detect congestion, and so it would continue transmitting packets and re transmitting lost ones even if the client was not responding at all. It would eventually give up, but not before sending a whole lot of traffic. Nice bug...

I would have liked to fix that issue by implementing BBRv2, and benefit from the nice work of my colleagues at Google. Since I have yet to locate the BBRv2 specifications, I ended up doing my personal modifications to the BBRv1 specification. I added code to detect repeated losses, and shrink the congestion window when such losses occur. The "client going away" problem, is now fixed, the Picoquic server does not retransmit more packets in this scenario when using BBR than when using Cubic. The tests tell me that the code is working fine in all the other tested scenarios. Not quite as good as getting telemetry from millions of users, but much less expensive...