Proposal for Stream Priorities

[marten-seemann]

This has been a long-standing TODO in our code and now that the QUIC WG draft contains a section about stream prioritization (https://quicwg.github.io/base-drafts/draft-ietf-quic-transport.html#rfc.section.9.5) it's a good time to address this properly.

In HTTP/2 streams can have a priority between 1 and 256 (see http://httpwg.org/specs/rfc7540.html#rfc.section.5.3.2), and I can't think of any situation where one would need a more fine-grained control (or where it would make a significant difference on the wire).

quic package

We add a method SetPriority(weight uint8) to the Stream interface. The weight is a value between 0 and 255, and adding 1 gives the priority of the stream. SetPriority may be called at any time, so it allows reprioritizing existing streams. The default priority is 1.
When two streams both have data to send, the number of packets containing stream data for each stream is proportional to its priority, i.e. if there stream 1 has priority 100 and stream 2 has priority 200, data will be transferred twice as fast for stream 2.

h2quic package

The easiest solution is to give the header stream(s) (stream 3 for now, soon every stream 4n+3) should have the highest priority (256). Data streams have priority 1.

For a more sophisticated solution, we can think about using the H2 stream priority to reprioritize QUIC streams. We need to evaluate if this makes sense (i.e. how the Go H2 implementation currently handles prioritization and if this gives any benefits) and how to map the H2 priority to the QUIC priority (should a data stream be allowed to have the same priority as a header stream?).

[jared2501]

Hey @marten-seemann, I have a use case for quic that requires stream prioritization. I'm thinking of implementing the proposal mentioned above for quic. I have a couple quic(k) questions:

• Would you accept an implementation as a contribution?
• If so, it appears that in order to implement the SetPriority method on the Stream interface I'd need to make the streamFramer.streamQueue a priority queue instead of a list and make some changes to streamFramer.PopStreamFrames to pop frames in priority order. Does that sound about right?

[marten-seemann]

Hi @jared2501, thanks for reaching out. We're always happy about contributions :)

I discussed your proposal today with @lucas-clemente, and we're not convinced that a priority queue is the right approach here. First of all, there seem to be few use cases where strict prioritization (one streams gets everything, all the other streams get nothing) is actually useful. It's really easy to use such a priority scheme in the wrong way. Take an HTTP connection for example, where the user decides to give priority to a large download. This would effectively make the connection unusable for everything else, since not even writes on the header stream(s) could be performed.
We therefore concluded that my initial proposal is the more useful scheduling. There are a lot of design considerations that I didn't mention above and that would be worth discussing before starting to implement this.

[jared2501]

Ah yup, makes sense. Although, it just so happens that the use case I'm trying to support does want strict prioritization (since it's trying to send data in realtime).

I understand you may not have bandwidth for the design work, but is there there any chance you could help me make this area of the codebase pluggable through an appropriate interface? My initial attempt at a StreamScheduler in #1245 is not sufficient, but perhaps it can be improved so that I can implement strict priority scheduling in my code base and weighted scheduling can be implemented later?

[yangl1996]

Hi, I'm wondering if it is still on the table. If so, I may be able to implement an interleaved weighted round robin in the Framer. Anything specific I should take care when forking?

[marten-seemann]

The proposal is quite old, and I'm not sure if it's a sufficient solution for the problem of prioritization. Round-robin is a quite primitive algorithm, and even if we introduce weights, it will be a poor choice for many applications.

I haven't really put a lot of thought into a reasonable API here, but maybe we need to expose an interface that allows an application to decide which streams to bundle (and provide a fallback implementation that would do round-robin).

[yangl1996]

I guess the first question is: Is generalized processor sharing (GPS) the proper abstraction here? If it is, then we may look into what particular algorithm we should implement to approximate GPS. One good candidate is weighted fair queuing, and I think weighted round robin won't be pretty bad here either in terms of the accuracy of approximating GPS.

According to the discussion above, I sense that there are needs for both strict prioritization (what @jared2501 proposed) and GPS. I guess it might be good to have pluggable schedulers here, so that one can choose between GPS, strict prioritization, and probably a default scheduler that provides Max-Min fairness among all active streams. I think with GPS, we can let the upper layer protocol to deal with HTTP/2-style stream bundling. For example, the HTTP/2 library should monitor the dependency (bundling) between HTTP/2 streams and frequently reconfigure the weights of the respective QUIC streams that are carrying these HTTP/2 streams.

[marten-seemann]

Update: Obviously, this proposal here is old. Really old.

We should implement an API modeled very closely for the needs of RFC 9218 (see #3470). This will make supporting RFC 9218 at the HTTP/3 layer very straightforward as well.