More flexible send orders

[vasilvv]

@martinduke had a nice presentation at TPAC this year in which he pointed out that if you want to pack all MOQ-related information into the send order, you need 144 bits or so.

I was wondering if instead of a number, we could make it a binary string (with lexicographical ordering). This seemed reasonable, though it's not clear to me as to what the default would be.

[martinthomson]

Do you have a link to that presentation you can share? (I know how to find IETF materials, but not W3C ones.)

I don't like the idea of having to sort arbitrary-length strings for every datagram. What are the bounds on this?

[vasilvv]

Do you have a link to that presentation you can share? (I know how to find IETF materials, but not W3C ones.)

Not readily, but the basic premise is that in MOQ, things are ordered by a (group ID, subgroup ID) tuple, and both are 64-bit (the other few bits are actual priorities). Now, of course, in practice you'd not have more than ~1000 (probably ~100), but then you'd have to juggle those on the application level.

I don't like the idea of having to sort arbitrary-length strings for every datagram. What are the bounds on this?

Well, presumably those go into some form of priority queue, so you'd get O(log N) per datagram regardless. I suspect 64 or 128 bytes would be enough?

[wilaw]

Do you have a link to that presentation you can share? (I know how to find IETF materials, but not W3C ones.)

W3C TPAC 2025 - WebTransport.pdf

The PDF is above. Martin's slides are 16-23.

[martinduke]

It's a bit more complicated than needing 144 bits.

All tracks (which in general consist of multiple streams) are assigned a 16 bit priority. If two tracks have the same priority, the transport SHOULD round-robin them.

Within a given track, individual streams or datagrams are prioritized based on the (Group ID, Subgroup ID) tuple, which is a total of 128 bits.

In fact the "sendGroup" construct briefed on slide 12 of that presentation largely fits the bill, IIUC.

See https://moq-wg.github.io/moq-transport/draft-ietf-moq-transport.html#name-priorities for the actual MOQ text.

[jan-ivar]

In fact the "sendGroup" construct briefed on slide 12 of that presentation largely fits the bill, IIUC.

This slide 12? I believe this matches the sendOrder that's already in the spec which is 64 bits.

So I'm a bit confused if there's a request for more bits here or if you're saying the spec is sufficient. @martinduke can you clarify?

[martinduke]

Sorry, slide 13 is a bit clearer.

In a perfect world:

• SendGroup would have a 16-bit priority. Higher priority is always delivered first.
• Two Send groups with the same priority would be round-robined.
• Streams within a send group would have 128-bit priority (as it stands today) It is not possible in moq for two streams in a send group to have the same priority, so how you resolve ties doesn't really matter for MOQ.

I would not say that the specifics of the third point are completely nailed down in terms of number of bits, etc.

Granted, this is way more functionality than most QUIC APIs will give you.

[martinthomson]

OK, I think that Victor's answer is clearest (the slides are clear as lead, sorry Martin, I'm sure the talk track was clear).

I can't imagine any situation where you would have more groups than you can have QUIC streams. Presumably each group involves sending at least one QUIC stream. (Or datagram; those aren't as clearly limited as streams, but the effective limit is within an order of magnitude, not 2^64.) And that's without subgroups.

So clearly, I do not understand MOQ yet. Except to the point that I don't think that standardizing an API at the proposed level of complexity is going to work out well. It will either be HTTP/2 levels of complex and not be implemented consistently. Or it won't address application needs. The budget for complexity is definitely higher in browsers and for things that don't need to be signaled, but there's a limit. Excessive complexity here is going to be paid in terms of performance tax for every send on every connection.

Maybe MOQ folks need to think carefully about what complexity MOQ can take on with regards to prioritization, because the externalities here look unacceptable to me.

Just to be perfectly frank, the complexity of prioritization in WebTransport is already too much. I'd welcome any proposal that reduced it, not one that seeks to make it more.

[afrind]

For reference, here's the MOQ scheduling algorithm: https://moq-wg.github.io/moq-transport/draft-ietf-moq-transport.html#name-scheduling-algorithm

Compared to HTTP for example, MOQ can use streams and datagrams in sophisticated ways.

Track 1 -- [Group 1] -------- [Group 2]
               |                  | 
               +--- Subgroup 1    +--- Subgroup 1
               +--- Subgroup 2    +--- Subgroup 2

Track 2 -- [Group 17] ------- [Group 22]
               |                  | 
               +--- Subgroup 10   +--- Subgroup 100
               +--- Subgroup 20   +--- Subgroup 200
               +--- Datagram A    +--- Datagram C   
               +--- Datagram B

Track 3 -- [Group 70]------- [Group 71] ------- [Group 72]
               |                 |                  | 
               +--- Datagram A   +--- Datagram B    +--- Datagram C

The subscriber can set a priority for the entire track, and all it encompasses (8 bits)
The publisher can set a priority on every Subgroup (stream) and Datagram (8 bits)
These two fields are effectively combined.

When the 16 bits are the same for any two things in the same track, they are ordered by their group/subgroup IDs. When they are the same across tracks, it's implementation defined but there's supposed to be some amount of sharing. Note that all ordering can only be compared within the same track. And honestly it's not fair that potentially uncoordinated publishers have their priorities compared when choosing what to send, but we punted on that.

I don't think any implementation has yet achieved complete conformance - most have not even tried and instead do some arbitrary smushing of bits (that can't rationally be compared to each other) into whatever their QUIC stack allows and hope for the best. It may not work, but it's fast.

Even if we had a massive bit field in a heap, I think it wouldn't quite get the sharing between tracks at the same priority quite fairly, because it would likely bias towards tracks with more streams/datagrams at that level.

If any simplifications jump out after reading this, I'd be interested in hearing them, though maybe an issue in moq-transport is a better place.

[jan-ivar]

It seems like we’re mixing up two things:

• MOQ has 16 bits of track/object priority plus 128 bits of IDs used as tie-breakers. That doesn’t mean the transport needs a 144-bit priority field; it just needs enough distinct values to order the active objects, and 2⁶⁴ is already astronomically larger than any realistic number of things competing on one connection.

• MOQ’s scheduling is more involved than “sort by a big key”: there’s per-track sharing and underspecified cross-track fairness, plus flow-control interactions. Those semantics don’t really fall out of a single lexicographically-sorted blob anyway.

From the WebTransport side, making sendOrder an arbitrary-length binary string would force all implementations to carry around and compare much larger keys on every send, for all use cases, not just MOQ. That’s a pretty big complexity/perf cost for something that’s still only a hint.

The existing model — 64-bit sendOrder within a sendGroup numberspace, with groups treated as equals for bandwidth — already gives MOQ a hook to approximate its priorities, as long as MOQ keeps its own scheduler and maps its (track, group, subgroup, priority) state onto the available bits. That’s a lot cheaper than baking MOQ’s full scheduling complexity into the generic WebTransport API.

[jan-ivar]

Meeting:

• 2⁶⁴ seems sufficient for the browser to prioritize its send queue
• Can MOQ implement a scheduler to translate this to the browser?
• Not right now, but interested in how we solve this later

[vasilvv]

I can't imagine any situation where you would have more groups than you can have QUIC streams.

Well, when you know all of your streams in advance, you obviously need just log n bits of send order. We don't know those in advance, so the problem becomes more complicated. In MOQ, streams have 64-bit group IDs associated with them, and those group IDs imply a priority. In practice, almost all of those will use at most 16 bits, it's just as a generic implementation, we're not guaranteed to know which ones are used.

Excessive complexity here is going to be paid in terms of performance tax for every send on every connection.

I don't think the complexity is different for uint64 vs a bytestring? At least in our implementation, any type that implements operator<=> (std::cmp::Ord in Rust case) can just work as-is.

Just to be perfectly frank, the complexity of prioritization in WebTransport is already too much. I'd welcome any proposal that reduced it, not one that seeks to make it more.

In my experience, 95% of complexity comes from having to support send groups (which our MOQT implementation does not use).