Subject: [quicwg/base-drafts] Packet number encoding appendix (#4315)

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Oct 2020 08:20:05 -0700

Fixes #4301.

I took some liberties with data types here, but... pseudocode.  I do wonder if the slice notation is sufficiently clear; I was hesitant to just do bit-shifts and masks because the number of bytes returned is key.  An alternative would be simply to return the number of bytes, I suppose.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/4315

-- Commit Summary --

  * Packet number encoding in appendix, move examples
  * Expand example

-- File Changes --

    M draft-ietf-quic-transport.md (61)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/4315.patch
https://github.com/quicwg/base-drafts/pull/4315.diff

-- 
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/pull/4315

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 16:44:31 -0700

@martinthomson approved this pull request.

I think that this is good, though you need to eliminate a shortcut in the pseudocode.

> +  recipient in the current packet number space, if any
+
+~~~
+EncodePacketNumber(full_pn, largest_acked):
+  // If no packets in the current space have been
+  // acknowledged, the full packet number is used.
+  if largest_acked is None:
+    return full_pn
+
+  // The number of bits must be at least one more
+  // than the base-2 logarithm of the number of contiguous
+  // unacknowledged packet numbers, including the new packet.
+  num_unacked = full_pn - largest_acked
+  min_bits = log(num_unacked, 2) + 1
+  num_bytes = ceil(min_bits / 8)
+  return full_pn[-num_bytes:]

Someone has been doing too much python.

As the value is not encoded into bytes before you index it, this is hard to follow.

```suggestion
  let encoded = []
  for i in 0..num_bytes:
    encoded.unshift((full_pn >> (8 * i)) & 0xff)
    // encoded.unshift((full_pn / (256^i)) % 256) ?
  return encoded
```

> +    return full_pn
+
+  // The number of bits must be at least one more
+  // than the base-2 logarithm of the number of contiguous
+  // unacknowledged packet numbers, including the new packet.
+  num_unacked = full_pn - largest_acked
+  min_bits = log(num_unacked, 2) + 1
+  num_bytes = ceil(min_bits / 8)
+  return full_pn[-num_bytes:]
+~~~
+{: #alg-encode-pn title="Sample Packet Number Encoding Algorithm"}
+
+For example, if an endpoint has received an acknowledgment for packet 0xabe8bc
+and is sending a packet with a number of 0xac5c02, there are 29,519 (0x734f)
+outstanding packets.  In order to represent at least twice this range (59,038
+packets, or 0xe69e), 16 bits will be required.

```suggestion
packets, or 0xe69e), 16 bits are required.
```

-- 
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/pull/4315#pullrequestreview-520161851

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 16:45:29 -0700

@martinthomson commented on this pull request.

+The pseudo-code in {{alg-encode-pn}} shows how an implementation can select
+an appropriate size for packet number encodings.
+
+The EncodePacketNumber function takes two arguments:
+
+* full_pn is the full packet number of the packet being sent.
+* largest_acked is the largest packet number which has been acknowledged by the
+  recipient in the current packet number space, if any
+
+~~~
+EncodePacketNumber(full_pn, largest_acked):
+  // If no packets in the current space have been
+  // acknowledged, the full packet number is used.
+  if largest_acked is None:
+    return full_pn

Whoops, missed this.  You can safely assign num_acked to `full_pn + 1` in this case.  Returning early is bad for the same reasons.

-- 
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/pull/4315#pullrequestreview-520163407

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 16:46:17 -0700

You can set min_bits to log2(full_pn) (without the +1) as well, I guess.

-- 
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/pull/4315#discussion_r514629891

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 29 Oct 2020 17:29:42 -0700

@janaiyengar commented on this pull request.

This is a great improvement, and I like the symmetry with the decoding algorithm. Thanks, @MikeBishop ! A few comments.

> @@ -7411,6 +7402,43 @@ The initial contents of this registry are shown in {{iana-error-table}}.
 
 --- back
 
+# Sample Packet Number Encoding Algorithm {#sample-packet-number-encoding}
+

```suggestion
* largest_acked is the largest packet number that has been acknowledged by the
```

> @@ -7411,6 +7402,43 @@ The initial contents of this registry are shown in {{iana-error-table}}.
 
 --- back
 
+# Sample Packet Number Encoding Algorithm {#sample-packet-number-encoding}
+

```suggestion
  peer in the current packet number space, if any
```

+
+~~~

Someone has been doing too much Javascript :-)
I don't think `.unshift` can be used without definition like this (I had to look it up).

This will be tricky to do without language conventions. I would recommend simply:
```
// return the value after truncating the full packet
// number to num_bytes least significant bytes
return truncate(full_pn, num_bytes)

@martinthomson : I don't follow what setting num_acked to `full_pn + 1` gets you. Why is this early return not good enough?

> @@ -7411,6 +7402,43 @@ The initial contents of this registry are shown in {{iana-error-table}}.
 
 --- back
 
+# Sample Packet Number Encoding Algorithm {#sample-packet-number-encoding}
+

Can you also modify the variable definitions in the Decode part to match these?

-- 
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/pull/4315#pullrequestreview-520183351

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 17:40:06 -0700

The early return takes a number and returns it.  We are looking for an encoded value that includes a length (in bytes).  If full_pn is 10, returning that doesn't tell the caller how many bytes to write out.

Running this through the full encoding algorithm avoids that problem.

-- 
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/pull/4315#discussion_r514644355

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 17:41:09 -0700

+
+~~~

So do it this way instead?

```
    encoded = [(either expression), encoded...]
```

-- 
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/pull/4315#discussion_r514644632

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 29 Oct 2020 18:19:57 -0700

@kazuho commented on this pull request.

> @@ -4382,17 +4382,10 @@ the difference between the largest acknowledged packet and packet number being
 sent.  A peer receiving the packet will then correctly decode the packet number,
 unless the packet is delayed in transit such that it arrives after many
 higher-numbered packets have been received.  An endpoint SHOULD use a large
-enough packet number encoding to allow the packet number to be recovered even
-if the packet arrives after packets that are sent afterwards.
-
-As a result, the size of the packet number encoding is at least one bit more
-than the base-2 logarithm of the number of contiguous unacknowledged packet
-numbers, including the new packet.

I think my preferences goes to retaining this sentence.

Having pseudo code makes sense, but IMO it is better to state the constraints that a function has to meet.

-- 
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/pull/4315#pullrequestreview-520304459

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 07:38:07 -0700

@MikeBishop commented on this pull request.

 --- back

There's already a PR for that, which I was emulating.

-- 
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/pull/4315#discussion_r515144265

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 07:45:15 -0700

@MikeBishop pushed 1 commit.

64c74e5dfac3eb87fb0068476811feb99eac8e30  Apply suggestions from code review

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4315/files/4ff09667a1b7d1b218d5a97c4ee2115d7217311a..64c74e5dfac3eb87fb0068476811feb99eac8e30

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 07:49:37 -0700

3bc25c1ff62913c7982966dcf259319fd4871324  Less python, more handwaving

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4315/files/64c74e5dfac3eb87fb0068476811feb99eac8e30..3bc25c1ff62913c7982966dcf259319fd4871324

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 07:50:24 -0700

+
+~~~

I like the solution of throwing it to an undefined function with a comment describing what it does.  The implementer can do that however their language best permits.

-- 
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/pull/4315#discussion_r515152541

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 07:52:48 -0700

It's not actually gone, it's a comment in the pseudo-code.  The paragraph above describes the constraints, while this describes the math which would satisfy those complaints.

-- 
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/pull/4315#discussion_r515155565

---

From: ianswett <[email-masked]>
Date: Sat, 31 Oct 2020 11:24:13 -0700

@ianswett approved this pull request.

> @@ -7411,6 +7402,46 @@ The initial contents of this registry are shown in {{iana-error-table}}.
 
 --- back
 
+  peer in the current packet number space, if any

```suggestion
  peer in the current packet number space, if any.
```

-- 
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/pull/4315#pullrequestreview-521159242

---

From: Martin Thomson <[email-masked]>
Date: Sat, 31 Oct 2020 18:11:40 -0700

@martinthomson pushed 1 commit.

9608dc4f7ee751fd906876d76992dea6ef03b493  period

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4315/files/3bc25c1ff62913c7982966dcf259319fd4871324..9608dc4f7ee751fd906876d76992dea6ef03b493