Scheduling HTTP streams

Scheduling problem arise in many subsystems such as the CPU scheduler, disk IO or Qdisc. Despite extensive research during several decades, this problem remain challenging to solve due to varying workload requirements, diversity of scheduled resources, latency versus throughput considerations, scheduler overhead and many others. For instance, the Linux CPU scheduler continues to evolve.

In this talk, we’ll explore another scheduling scenario: HTTP streams prioritization. Having that a busy web server can manage millions of TCP connections, each potentially containing hundreds of HTTP/2 or HTTP/3 streams, a pretty efficient stream is essential. It should be fair, say, for progressive JPEGs, but it should prioritize shorter load times for PNG images. It should also be smart enough, particularly if browsers don’t adequately prioritize streams (which is still could be an issue for mainstream browsers in 2024). Additionally, it must be resilient against DDoS attacks.

This talk will cover the following topics:

• The different nature of resources, their relationships, and how these factrors affect streams scheduling used for delivering these resources

• Fair O(logN) and fast O(1) scheduling algorithms

• Discussions on underlying data structures to optimize the scheduler for a large number of streams

• HTTP/2 streams prioritization in servers such as Nginx, H2O, nghttp2 (Envoy, Apache HTTPD) and Tempesta FW

• Differences between stream prioritization in HTTP/2 and HTTP/3, along with corresponding RFCs

• How modern browsers construct stream priority trees

• Server-side optimizations for streams scheduling in Cloudflare and Tempesta FW

• Known vulnerabilities exploiting the HTTP/2 prioritization mechanisms