Relative prioritization of streams and datagrams

[afrind]

Media over QUIC recently merged a PR defining how moq will use priorities (moq-wg/moq-transport#470). The scheme is based on the MoQ object model (track, group, object) and is independent of how that object model is mapped to QUIC or WebTransport constructs (streams and datagrams). It is possible for a MoQ application to specify a track that maps to a stream be given higher priority than a track that maps to datagrams. Jan-Ivar presented at IETF 120 and mentioned that WebTransport now gives priority to datagrams over streams unilaterally, which is incompatible with moq's scheme.

[wilaw]

There is a sendOrder and sendGroup scheme in the WebTransport API which would meet the MoQ requirements, but it only applies to Streams. One way to satisfy the MoQ requirement would be to also put flows of Datagrams into sendGroups of their own and then allow the application to assign the relative priority of those against other stream-based sendGroups. This has been discussed in #451 and #515 but after much discussion was never adopted.

[vasilvv]

I do wonder if we should just give datagrams a sendGroup/sendOrder, that would probably be better than the current wording. Maybe we could even have multiple datagram queues with different priorities.

[jan-ivar]

It is possible for a MoQ application to specify a track that maps to a stream be given higher priority than a track that maps to datagrams.

What's the use case? I understand putting audio in datagrams and video in stream-of-streams, and giving audio priority.

WebTransport now gives priority to datagrams over streams unilaterally, which is incompatible with moq's scheme.

I suspect it's incompatible even before #604 when things were implementation-defined, but agree we may have to rethink.

Chrome sends all datagrams > all streams whereas Firefox sends all streams > all datagrams. Neither seems moq compatible.

What are moq's requirements?

sendOrder

I think we're talking about weights here (between groups), not send ordering (within groups).

Maybe we could even have multiple datagram queues with different priorities.

Sounds like #419.

I'd like to first explore what the incompatibility is. At least for deterministic priorities, we've assumed the app can control the total datagram to stream ratio by how many total datagrams it queues per second. User agents could in theory base their send-buffer dequeuing strategy on its assessment of how quickly datagram send-queues build up, compared with other send-queues.

This was a benefit perhaps of keeping things vague. But how would we capture this in a spec? It would be unfortunate if we grew JS APIs for lack of ability to do so.

[afrind]

What's the use case? I understand putting audio in datagrams and video in stream-of-streams, and giving audio priority.

The simplest use-case is that moq control messages go on a stream, which should have higher priority than any media (streams or datagrams). We have also considered having N control streams (and still might).

What are moq's requirements?

moq needs WebTransport to expose a way to set the priority of a datagram in the same priority space as streams (eg: think of it as a 1 packet stream). If that proves too costly, some other way of assigning a flow of datagrams a priority within the same space.

I think we're talking about weights here

moqt doesn't define any weighting (eg bandwidth sharing) schemes at present. There's an algorithm to determine the highest priority "object" to send next, and only that will be sent until it is complete or becomes app limited.

[jan-ivar]

Meeting:

1. consider an API to associate a datagram writable to a send group
2. consider constructor to create additional datagram writables

[jan-ivar]

@wilaw and I were discussing an example to see if this would work (feel free to post your own):

Example 1. I'm sending:

1. 100 GB file "A"
2. 100 GB file "B"
3. A light control bidi stream "C"
4. An infinite flow of datagrams "D"

What should happen under congestion?
I want C to starve everything else if need be
Then I want D to be sent ahead of both A and B (but not C)

Today this won't work: D will be sent ahead of everything else (then A, B and C get ⅓ of what's left)

API option 1: wt.datagrams.sendGroup = S; wt.datagrams.sendOrder = n

• then put A, B, C and D in S, and assign fixed sendOrder 3 to C, 2, to D, and 1 to A and B.

Here, C would starve D would starve A and B if needed.

[jan-ivar]

The above puts different flows in the same sendGroup, breaking any notion that one was supposed to create a sendGroup per flow. Maybe that's fine since one clearly can, but it might come back to bite us.

E.g. two sendOrder-using stream-of-streams flows in the same sendGroup would yet again be forced to lockstep their increment/decrement strategies (why we introduced sendGroups in the first place).

If the main objection to #419 was "weights" being relative, we can replace it with strict priority:

API option 2: wt.datagrams.strictPriority = 1; S.strictPriority = 2

• then put C in S

Here datagrams acts as its own inherent send group (we can still consider constructing multiple).

[jan-ivar]

API option 1 doesn't work because datagrams don't fit in send groups
(sendGoup.getStats() produces WebTransportSendStreamStats which datagrams don't have).

API option 2 seems cleaner to me:

const a = await wt.createUnidirectionalStream();
const b = await wt.createUnidirectionalStream();
const s = wt.createSendGroup();
s.strictPriority = 2; // new
const c = await wt.createBidirectionalStream({sendGroup: s});
const d = wt.createDatagramsWritable(); // new
d.strictPriority = 1; // new

await readableDatagrams.pipeTo(d);

Less rope for web developers.

[jan-ivar]

Meeting:

• answers request
• strict priorities between groups and datagram writables
• Interest in Option 1: but treat datagram writable as a stream

[martinthomson]

The idea was to treat datagram writeables as streams for the purposes of prioritization. There would need to be differences in other aspects, like stats. My suggestion would be to expand the getStats to include datagram stats separate from stream stats.

[afrind]

The idea was to treat datagram writeables as streams for the purposes of prioritization.

I was recently looking at modifying the mvfst QUIC API to add datagram prioritization and came to a similar idea.

[jan-ivar]

Discussed at TPAC:

• Summary:
• We eliminate proposals 1, 3 and 4.
• We use proposal 2 with some modifications
• wt.datagrams.createWritable()
• Deprecate wt.datagrams.writable
• Question - What is the default priority/weight of streams in the “null” sendGroup (not assigned to an explicit sendGroup)?
• Proceed either with strict priorities, or integer weights for sendGroups and datagramWritables — a relative factor (e.g. of bytes) in the UA’s send dequeue round robin

[jan-ivar]

Meeting:

• Do we need to specify the send dequeue algorithm?
  • E.g. if 1, 1, 1, then the round-robin is the same as today (fairness)
  • E.g. if 1, 2, 1, then the round-robin is modified to dequeue twice from the middle one
• Seemed to be support for weights at the TPAC meeting
• Weights can emulate strict priority not vice versa
• Ready for PR for weights?

[jan-ivar]

Meeting (adding notes late from this morning):

• Looked at Add sendGroup.weight and datagramsWritable.weight #621.
• @vasilvv dissatisfied with proposal 2.
• MOQ desires 256 strict priority levels
• Let's try to make progress on the issue: chairs would like to hear what use cases are not satisfied by proposal 2 (with either weights or strict priorities).

[jan-ivar]

Proceed either with strict priorities, or integer weights for sendGroups and datagramWritables — a relative factor (e.g. of bytes) in the UA’s send dequeue round robin

• MOQ desires 256 strict priority levels

This appears directly supported in proposal 2 as shown in the slides.

If someone from MOQ could elaborate on the use case for this that would be great. In lieu of a better example, here's random one:

for (let i = 0; i < 256; i++) {
  const flow = (i % 2) ? wt.datagrams.createWritable() : wt.createSendGroup()
}

Without priority, the first-queued datagrams queued on each writable competes with the stream with the highest sendOrder in each group. Strict priority addresses this head on (higher numbers take precedence):

for (let i = 0; i < 256; i++) {
  const flow = (i % 2) ? wt.datagrams.createWritable() : wt.createSendGroup()
  flow.priority = i;
}

But strict priorities seem indistinguishable from (and can be accomplished using) really large weights:

for (let i = 0; i < 256; i++) {
  const flow = (i % 2) ? wt.datagrams.createWritable() : wt.createSendGroup()
  flow.weight = i * 1_000_000;
}

What use case is not covered here?

[afrind]

As someone who is not present at the meeting where proposal 2 was presented, it is difficult to distill the proposal from the slides. Can you provide a brief summary of the proposed priority algorithm, including the input signals (send groups, send order, priorities, weights) and how the algorithm picks the next thing based on the signals of elements that are in the queue?

I'm not sure "MoQ desires 256 strict priority levels" is an accurate description of the current moqt draft. The subscriber and the publisher can each set an 8 bit priority field for data in a track, which are combinable into a 16 bit field (subscriber > publisher). There's further ordering that happens when multiple elements (streams or datagrams) belong to the same track.

[vasilvv]

But strict priorities seem indistinguishable from (and can be accomplished using) really large weights:

Note that the proposed solution doesn't actually work. If the premise here is that we can simulate absolute priority between two streams by making their weights 1000000:1, the proposed formula (1000000 * p) doesn't work, since for, say, p=255 and p=256 it only provides a 256:255 advantage (they're almost equal weights). The correct formula would be Math.pow(1000000, p), but of course, in that case you can only fit ten levels of priorities into a uint64.

[wilaw]

We created some slides to help further discussion on this issue: https://docs.google.com/presentation/d/1ciJ3tdN0lOJbWkNg9jwgsjf3ye3Q9fTHQBucBK26Hlg/edit?usp=sharing

[jan-ivar]

Meeting:

• Proposal 5: assign datagramWritable to a sendGroup
• datagramWritable has a sendOrder
• rename sendOrder? priority or urgency?
• hearing priority, sendOrder has shipped in Firefox
• keeping sendOrder, higher number = higher priority, default to 0
• how can I send non-realtime and realtime data at the same time? Use sendGroups

[wilaw]

See revised slides #5 and #6 to illustrate additional use-cases based on what we perceive as the consensus from the last call.