Datagram priority algorithm fails to account for chunk size of reliable streams

[jan-ivar]

From #62 (comment):

Mathis Engelbart has looked at impact of prioritizing datagrams within a QUIC connection operating with NewReno. This results in high datagram latency, since the reliable stream fills the congestion window when datagrams aren't being sent.
Results are here.

A flaw in SendStream's write's primitive priority gating algorithm:

• 7. Wait for transport’s [[Datagrams]]'s [[OutgoingDatagramsQueue]] to be empty

...is we fail to account for chunk size, which, being app-controlled, may be magnitudes larger than a ~1024 byte datagram. So a single opening in the datagram queue may kick off:

• 8. Send [mega]bytes on stream’s [[InternalStream]] and wait for the operation to complete.

...which may take a while, and presumably compete for priority with subsequently sent datagrams (if not outright blocking them).

Even if we tried to control size through re-chunking, there might be N reliable streams ready to jump at this one opportunity.

[jan-ivar]

Proposed solution

A better solution might be:

• 8. Send [mega]bytes on stream’s [[InternalStream]] with priority X and wait for the operation to complete.

...where X is something we come up with, since Send (section 2.2) appears to expect and "relies on receiving priority information from the application", where "application" is us.

At minimum X should be "high" for datagrams and "low" for everything else, to solve this issue.

This may have further utility in solving #62.

[LPardue]

It sounds like you also need to explain some expectations how a QUIC implementation might actually act on this priority while scheduling work to frame and packetize. I wouldn't expect many QUIC implementations to have a unified view of prioritization across streams and datagrams.

[martinthomson]

Are we talking about a buffering operation here or not? That is, are we imagining this "send" operation blocking until the bytes are on the network?

Most QUIC implementations implement a "send" operation by buffering input data. This isn't always an unlimited amount of data (ours don't accept data unless there is flow control credit available so that users don't accidentally create deadlocks), but it can be more than the congestion window or what might be necessary for avoiding the priority problems that were mentioned.

What I would expect is that applications can buffer as much data as the stack is willing to buffer, but that the stack has some means to ensure that the prioritization of sending vs. any datagrams that might arrive later remains responsive (and respectful of priority).

Looking now at the description of write it seems overly prescriptive (which is consistent with Jan-Ivar's comment). While we want some amount of determinism, the general view of this should be that all sent data is fed to the stack (datagram or stream) and the stack is responsible for ensuring that the right thing happens. Adding prioritization information to the sending functions might create some guidance for how the stack operates.

[LPardue]

Yes. If if my stack's send() buffers streams or datagram bytes up to the order of cwnd bytes, then the next time a send() will work is when packets get transmitted and acks are processed. You could imagine that is in the region of RTT(s) time. If there's a phase mismatch between the availability of my important application data and the transport cwnd update, then less important data might always steal the transport stack's buffer.

[aboba]

Is the goal to deliver strict datagram priority, or are we now taking on the (larger) goal of supporting a priority scheme?

The current algorithm doesn't actually deliver strict datagram priority, since datagram sending can get stuck behind a backlog of reliable stream data, resulting in high (and variable) datagram latency. Also, it seems possible that the datagram queue could build until datagrams are discarded for exceeding outgoingMaxAge. We could avoid that by interrupting sending reliable stream data to check the datagram queue periodically (e.g. at least every outgoingMaxAge ).

RFC 8835 defines the prioritization scheme used in the WebRTC Priority API. For example, Section 4.1 says: "the ... endpoint SHOULD cause data to be emitted in such a way that each stream at each level of priority is being given approximately twice the transmission capacity (measured in payload bytes) of the level below." However, given the slow deployment of priority schemes, it seems like priority might be better handled as an extension to the WebTransport 1.0 spec, rather than a required feature.

[martinthomson]

@LPardue we can buffer much more than a congestion window, but sending is based on priority.

@aboba, I think that a holistic strategy is ultimately in our best interests, but I'm more concerned that the algorithm we have is just bad - along the lines you describe. I'm just looking to delegate the details of how things are prioritized to the browser rather than try to be prescriptive. Establishing expectations (along the lines of those in WebRTC...perhaps) is a good idea, but that can come as part of building that comprehensive picture.

[LPardue]

@LPardue we can buffer much more than a congestion window, but sending is based on priority.

That sounds decent, similar to how the non-browser implementations I know works, even if the buffer values vary. The important part you note is that implementations have a lot of discretion in these respects, despite how the QUIC specs might lead people towards an assumption or interpretation.

[jan-ivar]

I'm surprised to learn there's another layer of buffering in play. At least for datagrams, my impression was the w3c algorithm is the network send queue. We had to specify it prescriptively to detail its tight integration as a writable underlying sink in order to make sender-side back pressure work. Features like outgoingMaxAge seem defeated by another layer of buffering.

We have #236 to check the threading model, but the relevant pieces already run "in parallel", so I would hope this already maps to quic implementations without additional buffering.

This would be good to clarify. cc @yutakahirano

[LPardue]

I can't speak for the browser space (apologies if it sounded like I did) but fwiw some amount of buffering can, for example,mean that it's easier to prepare flights of QUIC packets that can then be batch written to a socket call to save on syscalls.

[martinthomson]

I would expect that browser APIs map directly into what happens in the stack so that there wouldn't be two buffers, sure. But either way, we should allow the stack (or browser, in effect) to manage priority.

[jan-ivar]

Meeting:

• Over-specified?
• What happens in practice is user agents make a priority decision at the point they put the packet on the wire.
• Data is buffered by the browser, and sent according to a particular prioritization arrangement that is guidance.
• Specify the behavior of the API, send queues, but add the prioritization as guidance: Probably make sure datagrams get out quickly.
• Some data that datagrams prioritization in practice backfired in one implementation.
• Walk back the mention of prioritization in algorithms, and turn it into guidance, or even no guidance.
• Long-term we hope HTTP might have a priority scheme we can rely on here.
• If behavior differs between browsers that's also bad