Subject: [quicwg/base-drafts] Propose compressed zero stream frames or TRIM frames (#433)

From: MikkelFJ <[email-masked]>
Date: Mon, 10 Apr 2017 09:55:32 -0700

In anticipation of partially reliable streams I considered how it might be done today with minimal impact.

The application can ask the QUIC API to only transmit or retransmit within a specific range limit or within a specific timeframe. If this is not to violate the current protocol, the QUIC engine must still transmit data but it can then choose to send just zeroes in order to free up internal or application controlled buffers. This is a waste of good bandwidth.

The QUIC engine could support a stream frame with just zeroes, using a dedicated frame type, or just a flag in a the stream header if possible. When this is set, the frame data will be absent. At the receiving end, the engine can either just fill in zeroes, or inform the application of a zero block at a given range.

With a compressed zero frame, it is then possible to handle partially unreliable streams at the API level without involving the core protocol which need not care.

A zero frame can also be useful if transmitting a memory mapped file that contains large amount of zeroes - although of course one would normally apply compression.

A downside of zero frames is that the receiving end cannot tell if the zero block was lost data or just valid zero data. It may derive that from the application context, or perhaps there should be a distrinction between compresed zeroes and actual gap frames.

An upside is that the QUIC protocol need not deal with length markers within streams to identify what is a message boundary so only complete messages are dropped or retransmitted.

This is somewhat related to sparse files and TRIM sectors in SSD devices.

Of course, there are many other, and possibly better, ways to deal with partially reliable streams, so this is just one idea I wanted to share.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433

---

From: ianswett <[email-masked]>
Date: Mon, 10 Apr 2017 11:58:13 -0700

I'd like to understand better cases when you want partial reliability and you're not happy just cancelling the stream when you've decided it's no longer useful.

Can you outline the use cases?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-293045807

---

From: MikkelFJ <[email-masked]>
Date: Mon, 10 Apr 2017 13:02:07 -0700

It can be very inconvenient to not be able to map a fixed or slowly changing communciation path (a virtual path) between two software endpoints (object A to B). You loose any ordering, and you potentially have to send 128-bit sender and receiver addresses in each message. If you send a high volume of messages (millons per second), the stream state starts to be become expensive because you must maintain ordering queues and reader/write state - even optimized memory pools starts to become a bottleneck. You could to some extend get around this by creating dedicated stream objects in the QUIC api that have very limited buffering capacity, but it starts to couple application level with protocol level logic a bit too much, and you still miss the virtual path.

I can imagine other scenerarios than IoT for high volume messaging, but to be more concrete:

If you want to send messages from IoT devices over the MQTT protocol and decide to map each pub/sub channel to single stream but allow some messages to be lost if they don't arrive timely. A message may be just a few bytes long, such as valve pressure, but may also occasionally be a few KB for aggregated datalog uploads. If each message is a new stream, MQTT must carry the pub/sub channel name in each message, but it could have avoided that by using a dedicated stream. Furthermore, you might aggregrate multiple IoT devices from a peripheral hub, such that each has its own logical connection ID with several possible pub/sub connections. Now you also have to carry the connection ID for each device in every message, in addition to pub/sub channel and the stream header for each message, and also a timestamp since you don't have any ordering guarantees anymore.

If you could just assign a stream to each pub/sub of each device and provide mostly ordered connectivity with options for loss, it would be more resource friendly, likely a lot faster, and more convenient to implement because you can directly associate a stream with a context. There would still be problems with deciding if a message was lost or not. This could be handled by only trimming at certain sync markers explained to the API, e.g. after CRLF. I'm not saying TRIM solves the entire problem by itself.

For video and voice streaming you could more easily get away with a new stream per audio/video frame because the payload is significantly larger and the message rate is significantly lower.

For game applications the payload could be small, but the message rate would also be comparatively low, at least client side. However, you still need to associate each new stream with a context which is not necessarily that convenient, though possible. On the server side, you would deal with lots of connections. But, same or different connection, each message is a stream that requires state. So now you 100K connections with each 30 active streams which is 3 millions active streams instead of 100K, and this is 3 million new streams per second. Now consider more complex VR gamestate with player 3D coordinates measured by 24 devices and each stream starts to carry non-trivial payload. You don't have any option but to scale out on more servers. But you wouldn't be necessary if you could stream gamestate over 100K semi-permanent connections.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-293062302

---

From: MikkelFJ <[email-masked]>
Date: Tue, 11 Apr 2017 06:38:07 -0700

Another related use for the TRIM frame is to send zero frames after the application decides to cancel a stream while all data up to the final offset in each direction have not yet been acknowledged. This is more in line with the idea of disposable streams (not that I am saying it solves the above mentioned issues).

For example, the application may have given a memory mapped file to the API and halfway thorugh decides to cancel the stream. The QUIC engine may expect retransmissions to be based off the memory mapped file buffer rather than keeping internal copies. Once the client cancels the stream, the engine no longer has any data to transmit in order to oblige the protocol. It may then fill in zeroes, or be forced to copy data at the time of cancel in anticipation of potential retransmissions. Either way, it may be just wasted effort. In this case a TRIM frame would allow the engine to simply fill in the data and retire the stream gracefully after the application has long abandoned the stream.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-293265390

---

From: MikkelFJ <[email-masked]>
Date: Tue, 11 Apr 2017 23:05:17 -0700

If a TRIM frame can carry a FIN bit, it would also be possible to do away with the RST_STREAM dual use of send RST_FRAME, reply RST_FRAME. The sender can instead send a TRIM frame with a FIN bit, or a TRIM frame followed by an empty FIN stream frame. This would avoid keeping track of who send RST_STREAM first.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-293482505

---

From: MikkelFJ <[email-masked]>
Date: Wed, 12 Apr 2017 00:17:21 -0700

To develop this idea further, we can have can replace FIN with two mini
states in 3 bits GTT:

`<G:(GAP | VALID), TT:(MARK | FIN | MORE | TRIM)>`

MARK marks the end of a message at the end of the current frame, and
that more messages might follow. FIN marks the end of stream and
the end of a message at the end of the current frame. MORE indicates
that the current message will be continued in another (possibly empty)
frame.  TRIM indicates that the payload is absent and should be zero
filled. If TRIM is used at a boundary, it needs to be followed by a
subsequent frame to encode FIN or MARK.

GAP implies no payload like TRIM but allows for including MARK or TRIM
in the same frame. A GAP may be empty to suggest truncation.
`<GAP, FIN>` can be used replace the `RST_STREAM` response.

An application may not know if more messages will indeed follow. To
terminate a stream following a MARK, FIN zero length frame can be
used to terminate the stream. An application may also use the GAP flag
if zero-length messages can be valid.

If 3 bits is too much, the state can be simplified to:

`<FF:(MARK | FIN | MORE | GAP)>`

In this case we loose the option encode zeroes that are not gaps, and we
also cannot encode GAP and FIN at the same time.

Now let see how this could fit into the current STREAM header byte:

The stream frame currenlty has the form "1FDOOOSS" where 1 indicates a
stream frame. F is the FIN bit and D is the datalength present bit. OOO
is the offset field width, and SS is the stream identifier width.

If we use the simplified two bit FF approach we can reduce OOO to OO and
have "1FFDOOSS" and we are essentially done. Current streams behave as
before and have just a single message. Partially reliable streams can
introduce gaps into the stream and message markers help the engine to
decide how to best create gaps.

I also suggest moving to 64-bit stream identifiers because 32-bit
streams can drained withint a few hours and because they are more
dificult to map to unique vpath for object routing.

If we use the 3-bit GTT approach, we can steal the datalength present
bit:

- GAP, TRIM, MORE implies data length.
- MARK, FIN implies no data length.

But this does not appear to be very practical. So the "1FFDOOSS" with
64-bit stream identifiers is the solution I would suggest.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-293494625

---

From: MikkelFJ <[email-masked]>
Date: Wed, 12 Apr 2017 00:55:37 -0700

I forgot that the datalength bit implies filling to packet size, and not zero length, as for short FIN stream frames. The last discussion about GTT interaction with datalength is therefore incorrect.

In this light, a 3-bit GTT approach is more viable. We can either just steal the data length as it isn't all that useful to save two bytes on a full MTU whereas with GTT we can remove the RST_STREAM response and replace it with GAP, FIN.

I should also clarify that MARK is most useful to the receiving end: The receiver needs to deliver complete ordered messages and can decide to drop too old (by some measure) incomplete message when forwarding the stream to the application. Incomplete message can both be implicit gaps as in data not yet delivered, and explicit gaps as in data will never be delivered indicated by the GAP bit. The sender can choose to send GAPs anywhere it thinks but it cannot choose to drop random data in a stream without replacing with GAP.

The sender can also can also make use of MARK, for example when a stream is cancelled, it may choose to transmit all currently buffered complete messages, and send a GAP for the rest.

The API may also deliver messages out of order, so rather than dropping too old messages, it delivers them when completed.

A MARK need not indicate a logical message but it does not matter to QUIC. For example, when sending files, a mark could be inserted every 4K. Of course the application can derive this from the offset, but it makes it simpler to deliver out of order data in page chunks. This is useful for concurrent processing where each received chunk can be processed in parallel, but it must be a complete chunk.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-293502214

---

From: MikkelFJ <[email-masked]>
Date: Fri, 14 Apr 2017 10:30:29 -0700

With the latest change to the frame format, STREAM frames now have the format "11FDOOSS".
This still makes it possible to use the two-bit FF format: `<FF:(MARK | FIN | MORE | GAP)>` so the resulting encoding would be "11FFOOSS".

Another approach is to have separate TRIM/GAP frames:

- "0011OOSS" GAP/TRIM frame with 2 byte data len and no payload.
- "0010OOSS" MSG frame - always has a 1 byte length field encoding 1..256 bytes of payload.

A MSG frame is in most ways to be treated like a STREAM frame except it cannot end a stream, and it segments a stream into synchronization points useful when GAPS can be present. It is also more compact for short messages sent periodically.

A message can be continued with ordinary STREAM frames, a GAP frame, or a stream frame with FIN set. If a message contains GAP frames, content up to next message, or to FIN may be multiple conflated messages. It is up to the application and stream policy to decide how to discard data or make sense of this. A MSG can never start with a GAP.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-294197196

---

From: MikkelFJ <[email-masked]>
Date: Fri, 14 Apr 2017 10:42:00 -0700

To illustrate a zero copy API that can deal with partially reliable streams:

Ordinary zero copy without partial reliability:
A writer can write buffers which must remain valid until the write_flush_offset has advanced past the the affected buffers.  A read provides an empty iov vector the gets populated with network buffers that will remain valid until the reader calls flush_read for the affected range. The write flush is always ordered, but the read flush need not flush everything in order, but must respect buffer boundaries.

A partial reliable interface allows a writer to set mark 1 or 0 to indicate a buffer ends with a message separator (could also be start of buffer, not sure). A reader receives a similar array of marks, and a separate array to indicate which buffers are gaps. The reader also provide a list of offsets, which are sorted, but may have missing ranges. These ranges will always be filled in during later reads, possibly with a gap. Stream policy can decide more precisely how delivery is organized.

In addition there is a poll interface on the connection to get events associated with streams, such as end of stream. Not shown.

```
int quic_stream_readv(struct quic_stream *sp,
        struct iovec *iov, int iovcnt);

ssize_t quic_stream_writev(struct quic_stream *sp,
        const struct iovec *iov, int iovcnt);

int quic_stream_readv_partial(struct quic_stream *sp,
        struct iovec *iov, uint64_t *offset, int *status, int iovcnt);

ssize_t quic_stream_writev_partial(struct quic_stream *sp,
        const struct iovec *iov, int *mark, int iovcnt);

uint64_t quic_stream_get_write_flush_offset(struct quic_stream *sp);

int quic_stream_flush_read(struct quic_stream *sp,
        uint64_t offset, uint64_t len);
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-294199475

---

From: MikkelFJ <[email-masked]>
Date: Fri, 14 Apr 2017 11:12:51 -0700

To make encoding more robust to loss, it is probably best if the end and not the start is encoded, because if message is complete it cannot be concluded before the next message is sent. This was considered in the original GTT/FF proposal, but the MSG frame does not handle this. The api should probably have a status on readv that tells both if a buffer starts and/or ends a message or if it is a gap. 

For write, the mark should probably encode the end of message with the start being implied by 0 offset or previous end. This avoids having to wait for more data to encode the boundary even if there are no loss possible at this point.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/433#issuecomment-294205767