The list of past posts including those previously published on Wordpress is available here.
For the past 6 months, I have been working on a new congestion control algorithm, called C4 for “Christian’s Congestion Control Code”, together with Suhas Nandakumar and Cullen Jennings at Cisco. Our goal is to design a congestion control algorithm that serves well real time communication applications, and is generally suitable for use with QUIC. This leads to the following priorities:
Out of those three priorities, the support for “questionable” Wi-Fi had a major influence on the design. We got reports of video not working well in some Wi-Fi networks, notably networks in office buildings shared by multiple tenants and appartment buildings. Analyzing traces showed that these networks could exhibit very large delay jitter, as seen in the following graph:
In presence of such jitter, we see transmission sometimes stalling if the congestion window is too small. To avoid that, we have to set the congestion window to be at least as large as the product of the target data rate by the maximum RTT. This leads to our design decision of tracking two main state variables in C4: the “nominal data rate”, which is very similar to the “bottleneck bandwidth” of BBR (see BBR-draft); and the “nominal max RTT” which is set to the largest recently experienced RTT as measured in the absence of congestion.
The support for application limited flows is achieved by keeping the nominal data rate stable in periods of low application traffic, and only reducing it when congestion is actually experienced. C4 keeps the bandwidth stable by adopting a cautious bandwidth probing strategy, so that in most cases probing does not cause applications to send excess data and cause priority inversions.
C4 uses a “sensitivity” curve to obtain fairness between multiple connections. The sensitivity curve computes sensitivity as function of the nominal data rate, ensuring that flows sending at a high data rate are more sensitive than flows using a lower data rate, and thus reduce their data rate faster in response to congestion signals. Our simulations shows that this drives to fair sharing of a bottleneck between C4 flows, and also ensure reasonable sharing when sharing the bottleneck with Cubic or BBR flows.
We have published three IETF drafts to describe the C4 design, C4 algorithm specifications, and the testing of C4. The C4 repository on Github contains our C implementation of the algorithm, designed to work in Picoquic, as well as testing tools and a variety of papers discussing elements of the design.
The code itself is rather simple, less than 1000 lines of C including lots of comments, but we will need more than one blog post to explain the details. Stay tuned, and please don’t hesitate to give us feedback!
This morning, I was contacted by Victor Stewart, who has been contributing to picoquic for a long time. Victor is using the new Codex extension that OpenAI released last week. He was impressed with the results and the amazing gains in productivity.
I started from a very skeptical point of view. I saw initial attempts at using various AI systems to generate code, and they required a rather large amount of prompting to create rather simple code. I have read reports like Death by a thousand slops by Daniel Steinberg, who rails about sloppy bug reports generated by AI. So I asked Victor whether we could do a simple trial, such as fixing a bug.
Victor picked one of the pending bugs in the list of issues, issue #1937. I had analyzed that bug before, but it was not yet fixed. So we tried. While we were chatting over slack, Victor prompted Codex, and got a first reply with an explanation of the bug and a proposed fixed, more or less in real time. I asked whether it could generate a regression test, and sure enough it did just that. Another prompt to solve some formatting issues, and voila, we got a complete PR.
I was impressed. The fix itself is rather simple, but even for simple bugs like that we need to spend time analysing, finding the repro, writing a regression test, and writing a patch. We did all that in a few minutes over a chat. It would probably have required at least a couple hours of busy work. The Codex system requires a monthly subscription fee, and probably spending some time learning the tool and practicing. But when I see this kind of productivity gain, I am very tempted to just buy it!
The Great Firewall Report, a “long-term censorship monitoring platform”, just published an analysis of how the “Great firewall” handles QUIC. I found that a very interesting read.
The firewall work is distributed between an analysis center and cooperating routers, presumably at the “internet borders” of the country. The router participation appears simple: monitor incoming UDP flows, as defined by the source and destination IP addresses and ports; capture the first packet of the flow and send it to the analysis center; and, receive and apply commands by the analysis center to block a given flow for 2 minutes. The analysis center performs “deep packet inspection”, looks at the “server name” parameter (SNI), and if that name is on a block list, sends the blocking command to the router.
The paper finds a number of weaknesses in the way the analysis is implemented, and suggests a set of techniques for evading the blockage. For example, clients could send a sacrificial packet full of random noise before sending the first QUIC packet, or they could split the content of the client first fly across several initial packets. These techniques will probably work today, but to me they feel like another of the “cat and mouse” game that gets plaid censors and their opponents. If the censors are willing to dedicate more resource to the problem, they could for example get copies of more than one of the first packets in a stream and perform some smarter analysis.
The client should of course use Encrypted Client Hello (ECH) to hide the name of the server, and thus escape the blockage. The IETF has spent 7 years designing ECH, aiming at exactly the “firewall censorship” scenario. In theory, it is good enough. Many clients have started using “ECH greasing”, sending a fake ECH parameter in the first packet even if they are not in fact hiding the SNI. (Picoquic supports ECH and greasing.) ECH greasing should prevent the firewall from merely “blocking ECH”.
On the other hand, censors will probably try to keep censoring. When the client uses ECH, the “real” SNI is hidden in an encrypted part of the ECH parameter, but there is still an “outer” SNI visible to observers. ECH requires that client fills this “outer” SNI parameter with the value specified by the fronting server in their DNS HTTPS record. We heard reports that some firewalls would just collect these “fronting server SNI values” and add them to their block list. They would block all servers that are fronted by the same server as a one of their blocking targets. Another “cat and mouse” game, probably.
The IETF draft defining multiparty extension for QUIC is almost ready, but there was an interesting debate during the IETF meeting in Bangkok about its status. One of the reasons is that we have only a few implementations, and not all that much deployment in production. The other reason is that congestion control for multiparty is still somewhat experimental. The draft is carefully worded to only use stable references, merely following RFC9000 and stating that there should be an independent congestion controller for each path, meaning that a QUIC multiparty connection with N paths will be equivalent to as many single path connections. Which seems reasonable, but is in fact a bit of a low bar. For example, in RFC6356, we see three more ambitious goals:
Goal 1 (Improve Throughput) A multipath flow should perform at least as well as a single path flow would on the best of the paths available to it.
Goal 2 (Do no harm) A multipath flow should not take up more capacity from any of the resources shared by its different paths than if it were a single flow using only one of these paths. This guarantees it will not unduly harm other flows.
Goal 3 (Balance congestion) A multipath flow should move as much traffic as possible off its most congested paths, subject to meeting the first two goals.
These goals are implicitly adopted in the latest specification for Multipath TCP in RFC8684.
The QUIC extension for multipath only mention a subset of these goals, stating that Congestion Control must be per-path, as specified in RFC9000. The guiding principle is the same as the Goal 2 of RFC6356, ensuring that a QUIC multipath connection using multiple paths will not use more resource than a set of independent QUIC connections running on each of these paths.
We could have a philosophical discussion about what constitute “fairness” in multipath. On one hand, we could consider that a connection between two endpoints A and B should be “fair” versus any other connections between these points. If it can use Wi-Fi and 5G at the same time, that means it should not be using more resource that the best of Wi-Fi and 5G. On the other hand, users can argue that they are paying for access to both networks, and should be able to use the sum of the resource provided by these two networks. The first approach requires users to be cooperative, the second accepts that users will be selfish. In practice, it is probably better to engineer the network as if users would be selfish – because indeed they will be. But even if we do accept selfishness, we still have at least two congestion control issues, such as shared bottleneck and simultaneous fallback.
Suppose that a QUIC congestion uses two paths, defined by two set of source and destination IP addresses. In practice, QUIC paths are initiated by clients, and the two paths are likely to use two different client IP addresses, but a single server address. We could easily find configuration in which the server side connection is the bottleneck. In that case, the congestion controllers on the two paths could be playing a zero-sum game. If one increases its sending rate, the other one will experience congestion and will need to slow down.
The counter-productive effects of this kind of shared path competition can be mitigated by “coupled congestion control” algorithms. The idea is to detect that multiple paths are using the same bottleneck, for example by noticing that congestion signals like packet losses, ECN marks or delay increases are happening simultaneously on these paths. When that happens, it might be wise for the congestion managers on each path to cooperate, for example by increasing sending rates slower than if they were alone.
The experimental algorithm proposed in RFC6356 is an example of that approach. It is a variation of the New Reno algorithm. Instead of always increasing the congestion window for a flow by “one packet per RTT per path”, it would use the minimum of that and something like “one packet per RTT across all paths”. (The actual formula is more complex, see the RFC text for details.)
I have two issues with that: it seems a bit too conservative, and in any case it will only be efficient on those paths where new Reno is adequate. Most of the Internet connections are using more modern congestion algorithms than new Reno, such as Cubic or BBR. We would have to develop an equivalent coupling algorithm for the these algorithms. But we can also notice that the formula will slow the congestion window increase even if the paths are not coupled, which is clearly not what selfish users would want. In short, this is still a research issue, which explains why the QUIC multipath draft does not mandate any particular solution.
Another issue with multipath is the “simultaneous backup” problem. Many multipath configurations are aiming for redundancy rather than load sharing. They will maintain an active path and a backup path, sending most of the traffic on the active path, and only switching to the backup path if they detect an issue. For example, they would use a Wi-Fi connection until it breaks, and then automatically start sending data on a 5G connection. The problem happens when multiple connections on multiple devices do that at the same time. They were all using the same Wi-Fi network, they all detect an issue are about the same time, so they all switch to using the 5G network around the same time. That’s the classic “thundering herd” problem – an instant surge of traffic causing immediate congestion as all these connections compete for the same 5G radio frequencies.
The “thundering herd” problem will solve itself eventually, as all connections notice the congestion and reduce their sending rate, but it would be nice if we avoided the packet losses and increased delays when these “simultaneous backups” happen. The classic solutions are to introduce random delays before backing up, and also to probe bandwidth cautiously after a backup. Again, this is largely a research issue. My main recommendation would be for networks to implement something like L4S (see RFC9330, so each connection will receive “congestion experienced” ECN marks and quickly react.
So, yes, we do have a couple of research issues for congestion control and multipath…
A couple weeks ago, I got a message from researchers who had found a couple
of pretty nasty bugs in Picoquic. These were quickly fixed, but they gave
me a bad feeling. In theory, the core functions of Picoquic were
well tested, and bugs of this kind were fixed a long time ago.
But the code went through quite a bit of churn, as more functionality
like multipath, ack frequency and web transport were implemented.
Expectations also changed. Was the testing still sufficient? In a word, no.
The measurement using gcov and gcovr showed that for the main libraries,
the test coverage stood at 84.5% of lines and
72.5% of branches. Some parts were well tested, but many of the new
additions had only minimal coverage. The two bugs found by the researchers
were found in HTTP3 parsing of queries, in HTTP3 code that was initially
meant as a quick demonstration but that most
users ended up using it as is. It was now time to suspend further
development of Web Transport, Media over
Quic or P2P Quic until the code quality has improved.
The effort concentrated on testing three main libraries:
In total, that’s 32,479 lines of code. I used the results of gcov to pick the
worst offending areas one by one. For each of those, I wrote additional tests to
reach the uncovered areas, and sometimes managed to remove existing code that
was not useful in our scenario – at the end of the exercise, the code was
345 lines smaller, or 1.07%.
In total, I did 12 PRs over the course of 3 weeks, before
hitting a goal of at least 90% lines and 75% branches. The list is available in
GitHub issue 1781
in the picoquic depot, summarized in this table:
| Cover lines | Cover functions | Cover branches | |
|---|---|---|---|
| As of 2024/11/20 | 84.5% | 89.5% | 72.5% |
| Siduck removal | 84.8% | 89.8% | 72.8% |
| Test getters and setters in the API | 85.4% | 91.6% | 73.4% |
| More frame parsing / formatting tests | 86.2% | 92.0% | 74.3% |
| Fix the spinbit tests | 86.2% | 92.1% | 74.3% |
| Add tests for BBRv1 | 86.8% | 92.7% | 74.9% |
| Add tests for TLS API | 87.3% | 93.4% | 75.2% |
| H3Zero Client Data tests | 87.6% | 93.6% | 75.6% |
| Test of transport parameter code | 87.7% | 93.8% | 75.7% |
| Demo client tests | 88.2% | 93.9% | 76.2% |
| Test of logging functions | 89.6% | 95.7% | 76.9% |
| Test of Web Transport & capsule | 89.8% | 95.8% | 77.0% |
| Remove unused packet code | 89.9% | 95.8% | 77.2% |
| Prune and test utility functions | 90.1% | 96.1% | 77.3% |
I tried to avoid writing tests that merely targeted the coverage metric. In some cases, that’s unavoidable. For example, the API includes a set of “getter” and “setter” functions, so applications can check variables without building a dependency on the implementation of the protocol. These are simple functions, but they do count in test coverage, so I ended up writing a bunch of simple tests for them. But in general, it is better to perform the test using a high level API. It won’t test only what happens when the code in the targeted branch is exercised, it will also test the impact of that behavior.
I kept the exercise focused on writing tests, changing the code as little as possible. Inspecting the code, it is obvious that some areas need improvement and possibly refactoring – particularly the way congestion control algorithms are written, see issue 1794, and the structure of the HTTP3 and Web Transport code, see issue 1795. But doing test improvement and code refactoring at the same time is risky, and could take much longer than expected.
The coverage of branches at the end of exercise remains at 77.3%. Many of the uncovered branches can only be triggered by a failure in memory allocation. There are known techniques for testing that, essentially replacing malloc by a test version, but I need to find a way to integrate this special version of malloc in the existing stress tests. An example would be driving the load on a server, accepting that some connections to the server will fail, but expecting that at least some will succeed and that the server will return to normal when the load diminishes. The problem is to isolate the malloc failures so they happen on the server but not on the client, knowing that for our tests client and server are running the same Quic code in the same process. Suggestions are welcome.
Did I find bugs? Of course. At the beginning of the exercise, I was concerned that merely driving the test metric may not improve the code all that much. But in practice it did. Many small bugs, but also a few big ones, the kind that lead to crashes or loops. Overall, it convinced me that not enforcing these test metrics earlier was a mistake!