Subject: ACK Frame Issues

From: Martin Duke <[email-masked]>
Date: Wed, 6 Sep 2017 14:25:37 -0700

I've finally hacked my way through implementing the construction of an ACK
frame from the spec. In my opinion, the spec lacks enough explanatory text.
Furthermore, some aspects of this frame may require a fundamental rethink.

I would like to create issues for this, but there's a complicated web of
interrelated problems and I'd like to get some input on how to structure
this.

(1) *The spec sorely needs more normative text.*

It appears fairly straightforward to implement a sort of half-assed Ack
frame that doesn't have any optimizations. I can just ack data that I have
not acked before (not repeating in-flight acks); not send timestamps if
largest_acked have is more than 255 numbers ahead of the timestamp; and not
worry too much about optimizing packet space when playing with block length
sizes and so forth. However, sufficiently imaginative implementors worried
about corner cases can go down serious ratholes, as I ended up doing. For
example:

(a) The number of ack blocks I can fit is mostly a function of the block
length size. The block length size is a function of the block lengths I'm
sending, which is related to the number of blocks I'm sending if one is
especially large. So there's a recursive process where I compute the needed
block length (by scanning over all blocks), see that it doesn't fit,
eliminate some blocks, recompute the needed block length to see if it
shrank, see that now I can fit a few more blocks, etc.

(b) There are four ways to treat acks in flight on which the spec is silent:
    (i) Do not repeat them in subsequent acks
    (ii) Repeat them only if they do not require additional ack blocks
    (iii) Repeat them only if they require *neither *additional ack blocks
nor longer block lengths.
    (iv) Always repeat them until acked
Offline, Jana suggested that (iv) is what Google does, but you'd never
guess that. I settled on (ii), for what it's worth.

(c) One side effect of any option in (b) except (i) is that it will raise
largest_ack, which might make it impossible to send some timestamps that
are more than 255 packets below the maximum received. My workaround is to
send a second ACK frame with one ack block and a low largest-ack to mop up
these timestamps, as I SHOULD send them exactly once. But that might be
unintended behavior.

(d) One side effect of anything other than (iv) above is to possibly create
too large of a gap in packet number to send the next ack block.

(e) The spec is unclear if timestamps are sorted in order of arrival or
reverse order of arrival. At least it's unclear to me! BTW having to sort
new arrivals in both packet number and arrival order is unpleasant.

I don't think the spec should prohibit any of this behavior. However, some
normative text might indicate to implementors that they don't really need
to worry about some of this stuff.

(2) *The relationship between timestamps and ack blocks needs a rethink*

People are all over the map on this. On the implementer slack channel, a
lot of people are totally ignoring timestamps and don't think they're
useful. Jana seems to view as a purely advisory channel. On the other hand,
as issue #698 points out, a received timestamp means the packet has
arrived, and sending an ack block for it in the same frame seems redundant.

Finally, timestamps are a report with a completely different syntax.
*Especially* if they are advisory, I believe there is a strong case for
just putting it in its own frame and eliminating some of the weird
dependencies (see (c) above) between largest_acked and the timestamp fields.

Personally, I would recommend the following:
(1) Move timestamps into a separate frame.
(2) A host that receives a timestamp frame MUST interpret a timestamp for a
packet as an acknowledgement for that packet. Packet recievers MAY omit ack
blocks for packets for which a timestamp is in flight.
(3) (possibly) make timestamps something negotiable (in each direction) at
the start of a connection. For example, a host may only want timestamps
from its peer if it is using delay-based congestion control.

Martin Duke

---

From: Christian Huitema <[email-masked]>
Date: Wed, 6 Sep 2017 14:47:50 -0700

On 9/6/2017 2:25 PM, Martin Duke wrote:
> ...
> ...
>     (iii) Repeat them only if they require /neither /additional ack
> blocks nor longer block lengths.

Picoquic also does (vi). It provides redundancy, so if an ACK is lost
the next ACK will still acknowledge the received packets.

> ...
>
> (e) The spec is unclear if timestamps are sorted in order of arrival
> or reverse order of arrival. At least it's unclear to me! BTW having
> to sort new arrivals in both packet number and arrival order is
> unpleasant.

Picoquic does not attempt to sort arrivals, but maintain a SACK
structure similar to the "SACK dashboard" specified in TCP.
>
> I don't think the spec should prohibit any of this behavior. However,
> some normative text might indicate to implementors that they don't
> really need to worry about some of this stuff.
>
> *
> *
> People are all over the map on this. On the implementer slack channel,
> a lot of people are totally ignoring timestamps and don't think
> they're useful. Jana seems to view as a purely advisory channel. On
> the other hand, as issue #698 points out, a received timestamp means
> the packet has arrived, and sending an ack block for it in the same
> frame seems redundant.

Yes. That syntax is wrong, because it creates a potential conflict.

> /Especially/ if they are advisory, I believe there is a strong case
> for just putting it in its own frame and eliminating some of the weird

No. There would still be a conflict. For example, in Picoquic, receiving
at ACK erases the data related to the acknowledged packet -- including
the timestamps. If the proposed "timestamp frame" arrived after the ACK
frame, its information would be ignored because the packet was already
marked received and the data erased.
> (2) A host that receives a timestamp frame MUST interpret a timestamp
> for a packet as an acknowledgement for that packet. Packet recievers
> MAY omit ack blocks for packets for which a timestamp is in flight.
> (3) (possibly) make timestamps something negotiable (in each
> direction) at the start of a connection. For example, a host may only
> want timestamps from its peer if it is using delay-based congestion
> control.
>

My preference would be to have exactly one time stamp per ACK,
corresponding to the time at which the "largest acknowledged" packet was
received, and expressed as microseconds since the beginning of the
connection. 24 bits is probably OK, as long as the RTT is lower than 16
sec. 32 bit would be fine for anything but inter-planetary communications.

-- Christian Huitema

-- 
Christian Huitema

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 12 Sep 2017 16:53:31 -0700

Related to point (2), I've filed #774
<https://github.com/quicwg/base-drafts/issues/774>.

On Wed, Sep 6, 2017 at 2:47 PM, Christian Huitema <[email-masked]>
wrote:

>     (iii) Repeat them only if they require *neither *additional ack
> Picoquic also does (vi). It provides redundancy, so if an ACK is lost the
> next ACK will still acknowledge the received packets.
>
> ...
>
> Picoquic does not attempt to sort arrivals, but maintain a SACK structure
> similar to the "SACK dashboard" specified in TCP.
>
>
> at ACK erases the data related to the acknowledged packet -- including the
> timestamps. If the proposed "timestamp frame" arrived after the ACK frame,
> its information would be ignored because the packet was already marked
> received and the data erased.
>
>
> (2) A host that receives a timestamp frame MUST interpret a timestamp for
> a packet as an acknowledgement for that packet. Packet recievers MAY omit
> ack blocks for packets for which a timestamp is in flight.