Subject: [quicwg/base-drafts] varint packet numbers (#989)

From: Brian Trammell <[email-masked]>
Date: Tue, 05 Dec 2017 03:22:03 -0800

Now that we have varints in the protocol, the only integers not using them are packet numbers. This seems a little odd. Using varints for packet numbers could simplify implementations, as well as s simplifying the short header, by removing the need for a Type field.

There seem to be to be two broad approaches for doing this (well, three, including "don't")

- Do nothing. Packet numbers continue to be defined as modular, and to have a separate integer encoding from varint encoding in the frames. This requires two separate bits of code for handling packet numbers and all other integers in the protocol.

- Use varint packet numbers, and require the full packet number to always be transmitted. This has the advantage that integer code can be used everywhere, but now that we're starting the packet number space between 0 and 2^32-1 (which would probably be 2^29-1 with this proposal to ensure that varint 30 could always be used for short flows), would be less efficient on the wire.

- Use varint packet numbers, but allow the sender to choose to use a 6-, 14-, 30-, or 62-byte varint to represent the least significant 6, 14, 30, or 62 bytes of the packet number as with the current logic. This would retain the advantage of simplifying the short header, and following the principle of least surprise, but nullifies some of the code simplification advantages.

-- 
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/989

---

From: ianswett <[email-masked]>
Date: Tue, 05 Dec 2017 15:50:02 +0000 (UTC)

I like the fact this would allow us to specify the full 62 bit packet number if we wanted.

If we do this, I think we should do this for both the short and long header.  

I do not want to require the full packet number always be transmitted.  TCP has used a similar approach for wrapping sequence numbers for decades without issue.

-- 
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/989#issuecomment-349346145

---

From: Brian Trammell <[email-masked]>
Date: Tue, 05 Dec 2017 16:29:43 +0000 (UTC)

Agree; this should appear the same in both the long and short header. Reducing the number of encodings is the point.

To be clear, IMO the third option (allow sender to choose truncation, require receiver to interpret wrapping) is the preferred one, and the second one is probably worse than doing nothing, but I wanted to point out all the options for completeness.

-- 
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/989#issuecomment-349359351

---

From: ekr <[email-masked]>
Date: Tue, 05 Dec 2017 16:45:49 +0000 (UTC)

I also favor the third option.

On Tue, Dec 5, 2017 at 8:29 AM, Brian Trammell <[email-masked]>
wrote:

> Agree; this should appear the same in both the long and short header.
> Reducing the number of encodings is the point.
>
> To be clear, IMO the third option (allow sender to choose truncation,
> require receiver to interpret wrapping) is the preferred one, and the
> second one is probably worse than doing nothing, but I wanted to point out
> all the options for completeness.
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/quicwg/base-drafts/issues/989#issuecomment-349359351>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABD1oa5zxcfd8Y1Jy3ZLm3BI8pjQwgJEks5s9W91gaJpZM4Q2Id8>
> .
>

-- 
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/989#issuecomment-349364622

---

From: MikkelFJ <[email-masked]>
Date: Tue, 05 Dec 2017 16:56:13 +0000 (UTC)

I also prefer the third option. The single byte variant is not very useful unless you only send a ping every other minute or so. It could be used for encoding 126-bit packet numbers in some future QUIC version.

Using the varint format throughout while only encoding the modulo would make such a change fairly easy. There are probably some gremlins hidden in the frame headers - for example the flow control max values could be module 2^64.

-- 
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/989#issuecomment-349368175

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 Dec 2017 00:15:29 +0000 (UTC)

Since the varints won't affect the invariants [1], we can decide this more or less at our leisure.  For the record, this won't be in -08.

Note that this isn't as simple as is being made out.  With a varint encoder you pass a byte offset and you get back a number and a new byte offset.  With a varint, you need to pay attention to how much the byte offset moves so that you can overwrite the correct number of bits to the left of the bits you got.

[1] ... not to mention the varmints.

-- 
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/989#issuecomment-349485782

---

From: Brian Trammell <[email-masked]>
Date: Wed, 06 Dec 2017 06:29:46 +0000 (UTC)

> Since the varints won't affect the invariants [1], we can decide this more or less at our leisure...

Yep, I mainly filed this now because it seems logical enough that I figured someone else had already filed it, and I couldn't find it. 

Re: difficulty: agreed, this is not *quite* as simple as overlaying 32 LSB on a 64 bit internal packet number and wrapping around (as with the present headers), but an informational appendix on How To Use Varints / a wiki / a reference implementation would go a long way to showing people how to keep the gremlins at bay.

-- 
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/989#issuecomment-349548184

---

From: martinduke <[email-masked]>
Date: Wed, 06 Dec 2017 23:23:03 +0000 (UTC)

I'm not sure if this is a related issue or not, but the "Packet Numbers" section is very clear on how to size the packet number in the packet header, but there is no corresponding advice for sizing the largest_acknowledged field in the ACK frame. In general Varints refer to numbers that start at zero, so there is a natural occasion to truncate them. Packet numbers have 32 bits, so right away we're at 32.

To be specific, the packet header part requires enough bits to encode 2 * (max_pkt - lowest_pkt_unacked). This obviously doesn't work so well on the receiver side. We could just mandate a de facto min size of 4, tie it to the peer's packet number size, or something else.

-- 
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/989#issuecomment-349808535

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 Dec 2017 21:10:55 -0800

The largest_acknowledged is NOT truncated.  I made that same assumption once too, but I thought we'd addressed that with text...  It is the entire packet number.  It's also the reason that packet numbers can't exceed 2^62-1 now.  That means that it will be rare to ever find an ACK packet with a short encoding for largest_acknowledged.  That said, if you read some of the ideas in my new draft, maybe we can turn that around.

You might recall that the packet number size in STOP_WAITING was tied to the packet header.  And it was loathsome to implement.  There is probably some way to shorten the packet number in ACK, but I'd want to see a complete write-up.

-- 
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/989#issuecomment-349864949

---

From: martinduke <[email-masked]>
Date: Wed, 06 Dec 2017 21:24:58 -0800

The draft just says "variable length". I suppose this means that it's variable as in 30 or 62 bits. If there's clarifying language somewhere I simply missed it. If not, it could probably use some.

-- 
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/989#issuecomment-349866686

---

From: MikkelFJ <[email-masked]>
Date: Thu, 07 Dec 2017 09:45:11 +0000 (UTC)

There is AFAIK no requirement for varints to be stored in the shortest possible form, i.e. in canonical form.

For packet numbers the canonical form would include leading zeroes as an exception because it is a modulo operation but for other values that would not be the case. This makes it fairly easy to conclude how much of the stored reference packet number to update.

I'm not sure if there is value in requiring canonical form in general, but I guess some implementations would make that assumption anyway which could lead to problems down the road.

-- 
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/989#issuecomment-349915784

---

From: Patrick McManus <[email-masked]>
Date: Thu, 07 Dec 2017 14:58:09 +0000 (UTC)

> It is the entire packet number. It's also the reason that packet numbers can't exceed 2^62-1 now. That means that it will be rare to ever find an ACK packet with a short encoding for largest_acknowledged. 

I think that the benefits of starting PN at 0 in order to get better encoding in ack frames is a good reason to not go with random PN. It looks like you make a couple non-random grease suggestions in your new draft which sounds promising.

-- 
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/989#issuecomment-349991675

---

From: Patrick McManus <[email-masked]>
Date: Thu, 07 Dec 2017 15:00:22 +0000 (UTC)

> he draft just says "variable length". I suppose this means that it's variable as in 30 or 62 bits. If there's clarifying language somewhere I simply missed it. If not, it could probably use some.

the PN in the ack has to be explicit because of reordering.. ack the wrong implicit thing and you're not a reliable protocol anymore.. the envelope PN can get away with implicit because its the nonce to the trial decrpytion.

-- 
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/989#issuecomment-349992352

---

From: ianswett <[email-masked]>
Date: Thu, 07 Dec 2017 15:52:46 +0000 (UTC)

> I think that the benefits of starting PN at 0 in order to get better encoding in ack frames is a good reason to not go with random PN. It looks like you make a couple non-random grease suggestions…

If we have varint packet numbers in the header, then we can do 'random' packet numbers only within a single byte, instead of the current 4 bytes of randomness, which I think achieves both greasing and low byte overhead.

-- 
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/989#issuecomment-350009005

---

From: martinduke <[email-masked]>
Date: Thu, 07 Dec 2017 16:02:52 +0000 (UTC)

Varints aren't strictly necessary to have one-byte packet numbers. Just the first 3 bytes have to be zero. But I'm fine with varint packet numbers.

-- 
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/989#issuecomment-350012254

---

From: Patrick McManus <[email-masked]>
Date: Fri, 08 Dec 2017 23:49:55 +0000 (UTC)

> If we have varint packet numbers in the header, then we can do 'random' packet numbers only within a single byte, instead of the current 4 bytes of randomness, which I think achieves both greasing…

its pretty obvious looking at 08 logs that we are currently using a lot of 8 byte varints in acks on trivially short connections. 3/4 of initial packet numbers require them immediately. 

-- 
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/989#issuecomment-350401124