Ayush Mishra

Nash Equilibira in Internet Congestion Control

Studying the incentives behind switching from CUBIC to BBR on the Internet.

Keeping up with the Joneses

The Internet’s congestion control landscape is currently in the midst of an unprecedented paradigm shift. A recent measurement study found that BBR, a congestion control algorithm introduced by Google in 2016, has seen rapid adoption and is deployed at more than 20% of the Alexa Top 20,000 websites. Encouraging early deployment results from Google, Dropbox and Spotify suggest that BBR could potentially replace traditional loss-based congestion control algorithms like CUBIC.

Game on

Most recent deployments have cited better throughput as a key reason to switch from CUBIC to BBR [3, 5, 9]. This is not surprising and it seems perfectly plausible that a website would decide to switch from one TCP variant to the other if the switch will result in higher throughput. Hence, we can think of the Internet abstractly as a system of 𝑛 flows and model it as a normal form game.

Conjecture: Nash Equilibria in Internet Congestion Control

Our game-theoretic analysis and testbed measurements suggest that while BBR seems to achieve somewhat better performance than CUBIC on the Internet today, this advantage will decrease as the proportion of BBR flows increases. The distribution of congestion control algorithms on the Internet would likely reach a Nash Equilibrium, where no flow has the incentive to switch from CUBIC to BBR, or vice versa. We also found that the distribution of CUBIC and BBR flows in this Nash Equilibrium will be dependent mainly on the size of the bottleneck buffer, and marginally on the RTT distribution of the flows.

The Great Internet TCP Congestion Control Census

Surveying the Congestion Control landscape of the Internet.

There's a new kid on the block.

In 2016, Google proposed and deployed a new TCP variant called BBR. BBR represents a major departure from traditional congestion-window-based congestion control. Instead of using loss as a congestion signal, BBR uses estimates of the bandwidth and round-trip delays to regulate its sending rate. The last major study on the distribution of TCP variants on the Internet was done in 2011, so it is timely to conduct a new census given the recent developments around BBR.

Fingerprinting a web server's CC algorithm.

To this end, we designed and implemented Gordon, a tool that allows us to measure the exact congestion window (cwnd) corresponding to each successive RTT in the TCP connection response of a congestion control algorithm. To compare a measured flow to the known variants, we created a localized bottleneck where we can introduce a variety of network changes like loss events, bandwidth change, and increased delay, and normalize all measurements by RTT. An offline classifier is used to identify the TCP variant based on the cwnd trace over time.

The Internet is undergoing a paradigm shift.

Our results suggest that CUBIC is currently the dominant TCP variant on the Internet, and it is deployed on about 36% of the websites in the Alexa Top 20,000 list. While BBR and its variant BBR G1.1 are currently in second place with a 22% share by website count, their present share of total Internet traffic volume is estimated to be larger than 40%. We also found that Akamai has deployed a unique loss-agnostic rate-based TCP variant on some 6% of the Alexa Top 20,000 websites and there are likely other undocumented variants. The traditional assumption that TCP variants “in the wild” will come from a small known set is not likely to be true anymore. We predict that some variant of BBR seems poised to replace CUBIC as the next dominant TCP variant on the Internet.

Home / Research