Subject: Idea for packet numbers

From: Magnus Westerlund <[email-masked]>
Date: Thu, 20 Jul 2017 11:59:54 +0200

Hi,

There has been some discussion around packet numbers. For passive 
detection of packet loss in measurements and network management, it 
would be really good if the packet numbers where continuous and not only 
monotonically increasing. As this enables one to determine losses 
upstream of the measurement point. At the same time I understand there 
are benefits with being able to introduce gaps into the packet number to 
test the receiver's behaviour.

To enable both of these capabilities I would propose that the N least 
significant bits of the packet number are strictly increased by one. 
Then one can introduce gaps in the bits above the N ones. Yes, that will 
burn through the packet number space faster as the gaps may become 
larger than was the case without this. However, I don't see that this 
will have significant effect unless the sender introduce gaps very 
frequently so that the length of the packet number field needs to be 
much larger due to the outstanding sequence number space is much larger.

The value of N can clearly be discussed but it should be selected so 
that reordering and common burst durations are shorter than the time to 
wrap the strictly increase amount of bits. If the higher bits are 
available to measurement node, some possibility to infer gaps will also 
be possible. It might be that N needs to be scaled with throughput with 
a minimal value. N=8 would mean 256 packets between wraps. I think that 
is a reasonable minimal value. However, that will wrap in 28 ms at 100 
mbps of payload (assuming 1400 bytes of payload per packet).

So what people think about this idea?

Cheers

Magnus Westerlund

----------------------------------------------------------------------
Media Technologies, Ericsson Research
----------------------------------------------------------------------
Ericsson AB                 | Phone  +46 10 7148287
Torshamnsgatan 23           | Mobile +46 73 0949079
SE-164 80 Stockholm, Sweden | mailto: [email-masked]
----------------------------------------------------------------------

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Jul 2017 12:38:04 +0200

Are you talking about the use of the NEW_CONNECTION_ID message,
because what you propose would be possible, but it would cause an
improvement to linkability.

On 20 July 2017 at 11:59, Magnus Westerlund
<[email-masked]> wrote:
> Hi,
>
> There has been some discussion around packet numbers. For passive detection
> of packet loss in measurements and network management, it would be really
> good if the packet numbers where continuous and not only monotonically
> increasing. As this enables one to determine losses upstream of the
> measurement point. At the same time I understand there are benefits with
> being able to introduce gaps into the packet number to test the receiver's
> behaviour.
>
> significant bits of the packet number are strictly increased by one. Then
> one can introduce gaps in the bits above the N ones. Yes, that will burn
> through the packet number space faster as the gaps may become larger than
> was the case without this. However, I don't see that this will have
> significant effect unless the sender introduce gaps very frequently so that
> the length of the packet number field needs to be much larger due to the
> outstanding sequence number space is much larger.
>
> The value of N can clearly be discussed but it should be selected so that
> reordering and common burst durations are shorter than the time to wrap the
> strictly increase amount of bits. If the higher bits are available to
> measurement node, some possibility to infer gaps will also be possible. It
> might be that N needs to be scaled with throughput with a minimal value. N=8
> would mean 256 packets between wraps. I think that is a reasonable minimal
> value. However, that will wrap in 28 ms at 100 mbps of payload (assuming
> 1400 bytes of payload per packet).
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 20 Jul 2017 07:10:11 -0400

For other reasons I would like the packet numbers to be close, preferably
without gaps except during connection migration.

This relates to storing interval maps as groups of bitmaps instead of
binary trees to track already received packets. This both provides are more
efficient implementation, and it reduces some modes of DoS where an
attacker can create a lot of small intervals which cause the data structure
to inflate.

If packet numbers can only jump in higher bits and if we make a constraint
that such jumps must not be happen without filling at least one full packet
block, then it is possible to pack received packets efficiently into their
respective lower bit groups and the DoS concern would be mitigated, and it
would be easy to reject abuse. There is still the issue of blocks of lost
packets - so it is not that simple in praxis.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 20 July 2017 at 12.00.04, Magnus Westerlund (
[email-masked]) wrote:

Hi,

Cheers

Magnus Westerlund

---

From: Magnus Westerlund <[email-masked]>
Date: Thu, 20 Jul 2017 13:17:41 +0200

Hi Martin,

> improvement to linkability.

This is in reference to any changes to the public header information. 
The current draft version do have the packet number as part of the 
public header. I understand we will continue the discussion on what is 
public, and I think there has been suggestions all over the place. Thus, 
I want add this as a possibility assuming that the consensus is that we 
will have any parts of the packet number in the non-encrypted part of 
the packet.

I personally do think there are reasons for keeping at least the least 
significant parts of the packet number being non-encrypted. I don't see 
the linkability need to be significantly impacted. A single QUIC flow 
will still have the 5-tuple of IPvX+UDP that enables to identify where 
it comes from and where it goes. I still haven't seen any good 
motivation why you would actually have multiple QUIC connections on the 
same 5-tuple. Thus, the single path of the connection will leak very 
little additional information other than how the flow is being treated 
by the network.

For a 3rd party observing this from the outside, for flows with little 
losses you still see most packets, in this case I don't see that 
determining that losses are present upstream affects how you can 
correlate this with other. In the case of continuing a flow on another 
path, I would not really have problem with introducing a larger gap to 
reduce the linkability between the different flows that are used by the 
connection. Because, from my perspective, it would be preferable that 
each flow over different path actually are treated as individual 
sub-flow. Thus, they could have completely independent packet numbers. 
Such a direction appear to reduce linkability, without preventing 
exposing the basic flows transport progress.

Cheers

Magnus

-- 

Magnus Westerlund

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Jul 2017 13:25:49 +0200

That wasn't the question: the question was "if I decide to break
linkability by using a new connection ID, would you also insist on
having the lower bits remain contiguous?"

On 20 July 2017 at 13:17, Magnus Westerlund
<[email-masked]> wrote:
> This is in reference to any changes to the public header information. The
> current draft version do have the packet number as part of the public
> header. I understand we will continue the discussion on what is public, and
> I think there has been suggestions all over the place. Thus, I want add this
> as a possibility assuming that the consensus is that we will have any parts
> of the packet number in the non-encrypted part of the packet.
>
> significant parts of the packet number being non-encrypted. I don't see the
> linkability need to be significantly impacted. A single QUIC flow will still
> have the 5-tuple of IPvX+UDP that enables to identify where it comes from
> and where it goes. I still haven't seen any good motivation why you would
> actually have multiple QUIC connections on the same 5-tuple. Thus, the
> single path of the connection will leak very little additional information
> other than how the flow is being treated by the network.
>
> losses you still see most packets, in this case I don't see that determining
> that losses are present upstream affects how you can correlate this with
> other. In the case of continuing a flow on another path, I would not really
> have problem with introducing a larger gap to reduce the linkability between
> the different flows that are used by the connection. Because, from my
> perspective, it would be preferable that each flow over different path
> actually are treated as individual sub-flow. Thus, they could have
> completely independent packet numbers. Such a direction appear to reduce
> linkability, without preventing exposing the basic flows transport progress.
>
> Cheers
>
> Magnus
>
>
>>> detection

---

From: Magnus Westerlund <[email-masked]>
Date: Thu, 20 Jul 2017 13:35:57 +0200

> having the lower bits remain contiguous?"

No, that would be a new connection, and a new flow so no problem from my 
perspective to have new random start point for the packet numbers.

/Magnus

-- 

Magnus Westerlund

---

From: Martin Thomson <[email-masked]>
Date: Thu, 20 Jul 2017 13:51:57 +0200

> perspective to have new random start point for the packet numbers.

OK, thanks.  In that case, I think that this is good input into the
packet number encryption discussion.

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Fri, 21 Jul 2017 09:53:13 +0200

(Speaking as an individual),

> packet number encryption discussion.

ISTM that we need to decide how big a deal breaks in the sequence numbers
are supposed to be. In TCP, that's usually a big deal (retransmission and
backoff). QUIC is not TCP.

If it turns out that operators can understand what a normal level of
sequence number breaks looks like, perhaps they can assume that's
background noise, and concentrate on the times where the rate of sequence
number breaks is significantly larger than normal.

<Spencer puts on AD hat, and voice changes here>

But, regardless of whether this is a good idea or not, I appreciate the
effort people are making to work across the tussle on this topic. That's
going to matter, no matter what the working group consensus on any
particular topic turns out to be.

So, thanks much.

Spencer, swapping hats ...

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 21 Jul 2017 05:37:32 -0400

On Thu, Jul 20, 2017 at 07:10:11AM -0400, Mikkel Fahnøe Jørgensen wrote:
> For other reasons I would like the packet numbers to be close,
> preferably without gaps except during connection migration.
>
> This relates to storing interval maps as groups of bitmaps
> instead of binary trees to track already received packets. This
> both provides are more efficient implementation, and it reduces
> some modes of DoS where an attacker can create a lot of small
> intervals which cause the data structure to inflate.

The receive history gets truncated automatically, and so the receiver
does not have to worry about a lot of data to keep track of.  From
[draft-ietf-quic-transport] 8.13:

 " To limit ACK blocks to those that have not yet been received
 " by the sender, the receiver SHOULD track which ACK frames
 " have been acknowledged by its peer.  Once an ACK frame has
 " been acknowledged, the packets it acknowledges SHOULD not be
 " acknowledged again.

Send history is another matter.  Ibid., 8.13:

 " The sender SHOULD close the connection if an unsent packet
 " number is acknowledged.

(Previous versions of the draft had a MUST instead of a SHOULD.)

Thus it is in the interest of the sender either to create few gaps
or to create them in a manner that does not blow up its own send
history data structures if it wants to check whether an unsent packet
is ACKed.

  - Dmitri.

---

From: "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Tue, 25 Jul 2017 10:04:52 +0000

I've been thinking about packet numbers and what it is safe to reason about them.

With regards to packet numbers the key parts of the spec appear to be:
a)  The packet number for sending MUST increase by at least one after sending any packet, unless otherwise specified
b) A QUIC endpoint MUST NOT reuse a packet number within the same connection
c) The sender MUST use a packet number size able to represent more than twice as large a range than the difference between the largest acknowledged packet and packet number being sent.
d) An endpoint SHOULD retain old keys for a short period to allow it to decrypt packets with smaller packet numbers than the packet that triggered the key update. This allows an endpoint to consume packets that are reordered around the transition between keys. Packets with higher packet numbers always use the updated keys and MUST NOT be decrypted with old keys.

>From a receivers point of view we actively ignore a and assume that there may be packet reordering and packet loss in the network. 
Packet reordering means that packet numbers won't appear in order. Packet loss and the subsequent retransmission with a new packet number means that (retransmitted) lower offset stream data may arrive with a higher packet number. The receiver is expected to deal with these as part of normal operation.

>From the senders perspective the process it goes through is:
1. Get data to send
2. Get packet number
3. encrypt packet
4. queue packet on NIC
5. NIC sends packet.

On a single threaded single stream application an implementation written to spec would sequentially create packets in order, encrypt them and the nic should then send them out in order onto the network.
However on a multi-cpu server sending multiple streams in the same connections things get much harder to reason about. We can assume that each stream is likely being generated by a different application thread (to avoid server side head of line blocking etc) and so be producing packets concurrently.
One option is to serialise the sending, so that after step 1 the request enters a synchronized serialized process and proceeds with strict ordering allowing requirement a to be met.
This option isn't however efficient or desirable for a performance optimized solution.
On a multi-cpu system, for optimal performance you want to take advantage of data locality (it is expensive to shuffle data between CPU cores when you don't have to). The obvious design would be to have an atomic counter for the packet number and do steps 1-4 within the thread (or at least CPU) that is generating the data. With multiple streams being generated on multiple cpu cores there is no guarantee that the order the packet numbers are assigned for the packets will match the order that the packets are queued on the NIC. The higher numbered packet may get encrypted quicker and so enqueued and sent ahead of the earlier packet number. At the wire level this would give an egress pattern where the packet numbers weren't increasing after every packet, only over the longer run.
If the server has multiple NICS then the problem has potential of occurring even if steps 1-4 had been serialized via a cross cpu semaphore/lock. Different NICS will be attached to different CPU cores and an efficient OS could try to avoid cross CPU communication by queuing the packet on a NIC connected to the same CPU as the thread that generated the packet. If different threads are generating the packets on different cores then potentially the packets could be queued on different NICS and therefore be sent out of order even if they were queued in order.

Obviously we have established that a receiver should be designed to expect and handle packet re-ordering and it is unknown to the receiver whether it is in the network or host where the re-ordering occurs. From an end to end point of view a multi-threaded implementation would work. If the multi-threaded implementation strictly complies with a then I'm unsure, it depends what part of the process is defined as 'sending' and where the measurement to validate it should be taken (e.g. the point the packets appear on the network vs the point the intention to create a packet to send is actioned).

To complicate matters further, an implementer may not want to allocated packet numbers one by one. If they know they have 32 packets worth of data to send then perhaps it is more efficient to request 32 packet numbers in a single atomic operation and then encrypt and enqueue the packets in turn. If another thread on a less loaded cpu is also generating stream data then packet number re-ordering may occur to an even greater extend. Again (within limits) the receiver should cope with this level of packet re-ordering - as long as the packet number size constraints aren't violated and the packets arrive in a timely manner. However it does break the assumption that you can generally rely on the low order bits of packet numbers to be generally sent in order.

The packet re-ordering issue also impact requirements around streams ids being created sequentially in order as the same set of race conditions can occur.

I think it may be worthwhile clarifying what the packet number behaviour is expected to look like from an external observers perspective. Is there actually a desire to attempt to force the sender to serialize packet sending? That is, does quic require that the egress from the host is strictly in order and only the network can introduce re-ordering? Whilst keeping within the constraints of b-d, is/should it be acceptable that an implementation allocates blocks of contiguous packet numbers for each stream? If probably would mean you end up with gaps in packet numbers when a stream doesn't use all of its allocation in time (e.g a key change requires it to move to a new allocation). If it isn't acceptable then what are the constraints the sender should keep within?

Thomas

> -----Original Message-----
> From: QUIC [mailto:[email-masked]] On Behalf Of Dmitri Tikhonov
> Sent: 21 July 2017 10:38
> To: Mikkel Fahnøe Jørgensen <[email-masked]>
> Cc: Magnus Westerlund <[email-masked]>; IETF QUIC WG
> <[email-masked]>
> Subject: Re: Idea for packet numbers
> 
> > binary trees to track already received packets. This both provides are
> > more efficient implementation, and it reduces some modes of DoS where
> > an attacker can create a lot of small intervals which cause the data
> > structure to inflate.
> 
> The receive history gets truncated automatically, and so the receiver does not
> have to worry about a lot of data to keep track of.  From [draft-ietf-quic-
> transport] 8.13:
> 
>  " To limit ACK blocks to those that have not yet been received  " by the
> sender, the receiver SHOULD track which ACK frames  " have been
> acknowledged by its peer.  Once an ACK frame has  " been acknowledged, the
> packets it acknowledges SHOULD not be  " acknowledged again.
> 
>  " The sender SHOULD close the connection if an unsent packet  " number is
> acknowledged.
> 
> Thus it is in the interest of the sender either to create few gaps or to create
> them in a manner that does not blow up its own send history data structures if
> it wants to check whether an unsent packet is ACKed.
> 
>   - Dmitri.

---

From: Ian Swett <[email-masked]>
Date: Tue, 25 Jul 2017 08:24:47 -0400

Some thoughts.

1) Sending packet numbers in order is not required, but the farther out of
order packets get, the more acks the receiver is going to send, the larger
they'll be, and the more complex loss detection is.  In particular, you
won't be able to rely on QUIC's packet numbers being in time order.  TLDR;
It's easier to send packets in order than it is to correctly deal with the
implications of sending them out of order.

2) I don't think there's a compelling reason to use multiple CPUs for a
single QUIC connection in any circumstances I've encountered.  And if it is
necessary, it'd be much simpler and faster to avoid any locking and use
multiple QUIC connections(or possibly multipath if it existed).  This also
has the benefit of sending the packet numbers sequentially for a given
connection ID.

3) I'm happy to treat reordering in the NIC as a form of network
reordering, since it's not something the QUIC implementation may be able to
control.

On Tue, Jul 25, 2017 at 6:04 AM, Swindells, Thomas (Nokia - GB/Cambridge,
UK) <[email-masked]> wrote:

> a)  The packet number for sending MUST increase by at least one after
> sending any packet, unless otherwise specified
> c) The sender MUST use a packet number size able to represent more than
> twice as large a range than the difference between the largest acknowledged
> packet and packet number being sent.
> d) An endpoint SHOULD retain old keys for a short period to allow it to
> decrypt packets with smaller packet numbers than the packet that triggered
> the key update. This allows an endpoint to consume packets that are
> reordered around the transition between keys. Packets with higher packet
> numbers always use the updated keys and MUST NOT be decrypted with old keys.
>
> >From a receivers point of view we actively ignore a and assume that there
> may be packet reordering and packet loss in the network.
> Packet reordering means that packet numbers won't appear in order. Packet
> loss and the subsequent retransmission with a new packet number means that
> (retransmitted) lower offset stream data may arrive with a higher packet
> number. The receiver is expected to deal with these as part of normal
> operation.
>
> On a single threaded single stream application an implementation written
> to spec would sequentially create packets in order, encrypt them and the
> nic should then send them out in order onto the network.
> However on a multi-cpu server sending multiple streams in the same
> connections things get much harder to reason about. We can assume that each
> stream is likely being generated by a different application thread (to
> avoid server side head of line blocking etc) and so be producing packets
> concurrently.
> One option is to serialise the sending, so that after step 1 the request
> enters a synchronized serialized process and proceeds with strict ordering
> allowing requirement a to be met.
> On a multi-cpu system, for optimal performance you want to take advantage
> of data locality (it is expensive to shuffle data between CPU cores when
> you don't have to). The obvious design would be to have an atomic counter
> for the packet number and do steps 1-4 within the thread (or at least CPU)
> that is generating the data. With multiple streams being generated on
> multiple cpu cores there is no guarantee that the order the packet numbers
> are assigned for the packets will match the order that the packets are
> queued on the NIC. The higher numbered packet may get encrypted quicker and
> so enqueued and sent ahead of the earlier packet number. At the wire level
> this would give an egress pattern where the packet numbers weren't
> increasing after every packet, only over the longer run.
> If the server has multiple NICS then the problem has potential of
> occurring even if steps 1-4 had been serialized via a cross cpu
> semaphore/lock. Different NICS will be attached to different CPU cores and
> an efficient OS could try to avoid cross CPU communication by queuing the
> packet on a NIC connected to the same CPU as the thread that generated the
> packet. If different threads are generating the packets on different cores
> then potentially the packets could be queued on different NICS and
> therefore be sent out of order even if they were queued in order.
>
> Obviously we have established that a receiver should be designed to expect
> and handle packet re-ordering and it is unknown to the receiver whether it
> is in the network or host where the re-ordering occurs. From an end to end
> point of view a multi-threaded implementation would work. If the
> multi-threaded implementation strictly complies with a then I'm unsure, it
> depends what part of the process is defined as 'sending' and where the
> measurement to validate it should be taken (e.g. the point the packets
> appear on the network vs the point the intention to create a packet to send
> is actioned).
>
> To complicate matters further, an implementer may not want to allocated
> packet numbers one by one. If they know they have 32 packets worth of data
> to send then perhaps it is more efficient to request 32 packet numbers in a
> single atomic operation and then encrypt and enqueue the packets in turn.
> If another thread on a less loaded cpu is also generating stream data then
> packet number re-ordering may occur to an even greater extend. Again
> (within limits) the receiver should cope with this level of packet
> re-ordering - as long as the packet number size constraints aren't violated
> and the packets arrive in a timely manner. However it does break the
> assumption that you can generally rely on the low order bits of packet
> numbers to be generally sent in order.
>
> The packet re-ordering issue also impact requirements around streams ids
> being created sequentially in order as the same set of race conditions can
> occur.
>
> I think it may be worthwhile clarifying what the packet number behaviour
> is expected to look like from an external observers perspective. Is there
> actually a desire to attempt to force the sender to serialize packet
> sending? That is, does quic require that the egress from the host is
> strictly in order and only the network can introduce re-ordering? Whilst
> keeping within the constraints of b-d, is/should it be acceptable that an
> implementation allocates blocks of contiguous packet numbers for each
> stream? If probably would mean you end up with gaps in packet numbers when
> a stream doesn't use all of its allocation in time (e.g a key change
> requires it to move to a new allocation). If it isn't acceptable then what
> are the constraints the sender should keep within?
>
> Thomas
>
>
> does not

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 25 Jul 2017 14:34:48 +0200

Wrt. complexity of loss control, I don’t think reordering within short time
intervals is a major concern because you would expect to fill the gaps
eventually. If receiver side assumptions are not met, it could be assumed
to be poor line quality or malicious intent, thus warranting dropping the
connection, or at least a larger transmission block. The problem is when
you don’t know if a packet gap is due to valid deliberate omission or
failure / delay.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 25 July 2017 at 14.25.08, Ian Swett ([email-masked]) wrote:

Some thoughts.

---

From: "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Tue, 25 Jul 2017 12:36:14 +0000

From: Ian Swett [mailto:[email-masked]]
Sent: 25 July 2017 13:25
To: Swindells, Thomas (Nokia - GB/Cambridge, UK) <[email-masked]>
Cc: Dmitri Tikhonov <[email-masked]>; Mikkel Fahnøe Jørgensen <[email-masked]>; Magnus Westerlund <[email-masked]>; IETF QUIC WG <[email-masked]>
Subject: Re: Idea for packet numbers

Some thoughts.

1) Sending packet numbers in order is not required, but the farther out of order packets get, the more acks the receiver is going to send, the larger they'll be, and the more complex loss detection is.  In particular, you won't be able to rely on QUIC's packet numbers being in time order.  TLDR; It's easier to send packets in order than it is to correctly deal with the implications of sending them out of order.

2) I don't think there's a compelling reason to use multiple CPUs for a single QUIC connection in any circumstances I've encountered.  And if it is necessary, it'd be much simpler and faster to avoid any locking and use multiple QUIC connections(or possibly multipath if it existed).  This also has the benefit of sending the packet numbers sequentially for a given connection ID.
[Thomas Swindells] Performance seems to me to be a compelling reason. Firstly if you have different assets/data in memory (particularly CPU cache) to get the most out of a system you want to keep the data processing local to the cpu. Secondly encryption is still a relatively expensive operation, CPUs have acceleration to help so you are going to want to do work in parallel – particularly when delivering multiple streams. These can make a significant impact on a server delivering 80Gbps of live video traffic. One of the big advertised benefits of QUIC is its support for stream multiplexing and it is mostly up to the client rather than the server about whether to use it, I don’t think its viable to say just don’t use it?

3) I'm happy to treat reordering in the NIC as a form of network reordering, since it's not something the QUIC implementation may be able to control.

On Tue, Jul 25, 2017 at 6:04 AM, Swindells, Thomas (Nokia - GB/Cambridge, UK) <[email-masked]<mailto:[email-masked]>> wrote:
I've been thinking about packet numbers and what it is safe to reason about them.

1. Get data to send
2. Get packet number
3. encrypt packet
4. queue packet on NIC
5. NIC sends packet.

Thomas

> From: QUIC [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Dmitri Tikhonov
> Sent: 21 July 2017 10:38
> To: Mikkel Fahnøe Jørgensen <[email-masked]<mailto:[email-masked]>>
> Cc: Magnus Westerlund <[email-masked]<mailto:[email-masked]>>; IETF QUIC WG
> <[email-masked]<mailto:[email-masked]>>

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 25 Jul 2017 08:41:09 -0400

> From the senders perspective the process it goes through is:

I think this model needs to account for the OS.

A normal application does not write to NIC directly: it goes through
the kernel.  A socket's send buffer may get full and queueing a packet
may fail.  Let's assume that happens and the application waits to queue
a packet.  (If instead you just throw this packet out and pretend that
you queued it, then it is conceptually the same as the "write to NIC
directly" model above, but I don't think many people are ready to take
that route.)  While the application waits for the socket to become
writeable, an ACK alarm may go off or new packets may arrive for this
connection: generating and sending an ACK is in order.  Since we want
to send the ACK first, the buffered, not-yet-sent packet may need to be
renumbered, have its contents changed, or both:

    - Either the packet does not contain an ACK, in which case the
      new ACK frame is put into a new packet and the buffered packet
      gets a new packet number; or
    - The packet contains an ACK which can be replaced with the new
      ACK (if there is room), in which case the packet gets to keep
      the number, but the packet contents change.

Another scenario where butchering unsent packets is required is when
RST_STREAM comes in: application must then drop outgoing STREAM frames
for that stream.

The process is, then:

    1. Get data to send
    2. Get packet number
    3. Encrypt packet
    4. Try enqueuing packet
        a) If successful, "commit" packet number and go to (1)
        b) If unsuccessful, wait and do something smart later,
           depending on circumstances

Just my $.02,

  - Dmitri.

---

From: Kyle Rose <[email-masked]>
Date: Tue, 25 Jul 2017 09:26:11 -0400

On Jul 25, 2017 8:36 AM, "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <
[email-masked]> wrote:

* encryption is still a relatively expensive operation, CPUs have
acceleration to help so you are going to want to do work in parallel –
particularly when delivering multiple streams. These can make a significant
impact on a server delivering 80Gbps of live video traffic. One of the big
advertised benefits of QUIC is its support for stream multiplexing and it
is mostly up to the client rather than the server about whether to use it,
I don’t think its viable to say just don’t use it?*

Are you planning to serve 80 Gb/s on a single connection? If yes, then I
assume that's an infrastructure connection (e.g., cache to cache). I'm
skeptical of the comparative advantage of one connection vs. N for N CPUs
when compared to the complexity/cost of supporting parallel senders that
need to share at least some state.

Kyle

---

From: "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Tue, 25 Jul 2017 14:28:52 +0000

4 wasn't meant to imply how you queue the packet on the NIC - I was assuming via a kernel API call into normal udp send buffers, but both methods are valid.
You are right though there is the potential for the queuing operation to be blocked/rejected.
As I understand it the packet number is used in the encryption process, so changing a packets number is a non-trivial operation. 
A fast path route for queuing acks makes sense, again however the only real way to do that would be to give the ack packet a higher packet number but then send it before lower marked packets - even potentially if they do also contain ack frames.
For RST_STREAM I think it is permitted that currently queued packets are still sent, but if they only contain that streams packets then it is a beneficial optimization if they weren't sent (leaving packet number gaps).

Thomas

> From: Dmitri Tikhonov [mailto:[email-masked]]
> Sent: 25 July 2017 13:41
> Cc: Mikkel Fahnøe Jørgensen <[email-masked]>; Magnus Westerlund
> <[email-masked]>; IETF QUIC WG <[email-masked]>
> A normal application does not write to NIC directly: it goes through the kernel.
> A socket's send buffer may get full and queueing a packet may fail.  Let's
> assume that happens and the application waits to queue a packet.  (If instead
> you just throw this packet out and pretend that you queued it, then it is
> conceptually the same as the "write to NIC directly" model above, but I don't
> think many people are ready to take that route.)  While the application waits
> for the socket to become writeable, an ACK alarm may go off or new packets
> may arrive for this
> connection: generating and sending an ACK is in order.  Since we want to
> send the ACK first, the buffered, not-yet-sent packet may need to be

---

From: "MORTON, ALFRED C (AL)" <[email-masked]>
Date: Tue, 25 Jul 2017 14:33:42 +0000

Hi Ian, Thomas,

From: QUIC [mailto:[email-masked]] On Behalf Of Ian Swett
Sent: Tuesday, July 25, 2017 8:25 AM
To: Swindells, Thomas (Nokia - GB/Cambridge, UK)
Cc: Magnus Westerlund; Mikkel Fahnøe Jørgensen; IETF QUIC WG; Dmitri Tikhonov
Subject: Re: Idea for packet numbers

Some thoughts.

1) Sending packet numbers in order is not required, but the farther out of order packets get, the more acks the receiver is going to send, the larger they'll be, and the more complex loss detection is.  In particular, you won't be able to rely on QUIC's packet numbers being in time order.  TLDR; It's easier to send packets in order than it is to correctly deal with the implications of sending them out of order.
<snip>
[ACM]
Although this thread is on longer packet numbers,
I think it’s worth pointing out that
routine reordering at the Sender would have
implications for the single-bit alternate marking
(Spin-bit) approach. The boundary between
packets marked “0” and “1” would not be reliable;
there would appear to be very short RTTs along with longer RTTs:

  ... 0 0 0 1 1 0 1 1 1 1 1 ...
            ^ ^
   ^ = reordered
The single bit doesn’t have enough info to
restore order. Avoid reordering if possible.

Al

---

From: Ian Swett <[email-masked]>
Date: Tue, 25 Jul 2017 10:39:55 -0400

Agreed Al, but as long as the packet number(or a portion of it) is exposed,
the middlebox can easily detect the reordering and realize where the real
edge is.  If it wasn't exposed, it has to use some heuristics and do some
filtering(ie: it seems unlikely the RTT decreased from 40 milliseconds to
100 microseconds) to filter out false edges.

On Tue, Jul 25, 2017 at 10:33 AM, MORTON, ALFRED C (AL) <[email-masked]>
wrote:

> Hi Ian, Thomas,
>
>
>
> *From:* QUIC [mailto:[email-masked]] *On Behalf Of *Ian Swett
> *Sent:* Tuesday, July 25, 2017 8:25 AM
> *To:* Swindells, Thomas (Nokia - GB/Cambridge, UK)
> *Cc:* Magnus Westerlund; Mikkel Fahnøe Jørgensen; IETF QUIC WG; Dmitri
> Tikhonov
> *Subject:* Re: Idea for packet numbers
>
>
>
> Some thoughts.
>
>
>

---

From: "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Tue, 25 Jul 2017 14:46:27 +0000

That is partly my concern, if implementations/mechanisms are assuming a low level of reordering (such as middle boxes using a spin bit) how confident are we that those assumptions are accurate and a good thing to ossify?
With a multi-threaded multi-nic system I’m not certain it is actually that it is necessarily easy to (performantly) avoid re-ordering - even if the implementation doesn’t deliberately intend to introduce it.

One solution is to decide that spin bit and less complex lost packet tracking (and whatever else benefits from low amounts of packet reordering) are worthwhile properties and so mandate clearly that packet generation must be serialised and the egress of the packets strictly ordered as much as possible (e.g. each connection is locked to a nic with the packets sent in the correct order). I’ve no idea if this is a property current implementations actually have today or if multiple streams are encrypted on different threads with just the implicit assumption the output will end up in the right order.

Thomas

From: MORTON, ALFRED C (AL) [mailto:[email-masked]]
Sent: 25 July 2017 15:34
To: Ian Swett <[email-masked]>; Swindells, Thomas (Nokia - GB/Cambridge, UK) <[email-masked]>
Cc: Magnus Westerlund <[email-masked]>; Mikkel Fahnøe Jørgensen <[email-masked]>; IETF QUIC WG <[email-masked]>; Dmitri Tikhonov <[email-masked]>
Subject: RE: Idea for packet numbers

Hi Ian, Thomas,

Some thoughts.

Al

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 25 Jul 2017 12:27:01 -0400

On Tue, Jul 25, 2017 at 02:28:52PM +0000, Swindells, Thomas (Nokia - GB/Cambridge, UK) wrote:
> 4 wasn't meant to imply how you queue the packet on the NIC - I was
> assuming via a kernel API call into normal udp send buffers, but both
> methods are valid.  You are right though there is the potential for the
> queuing operation to be blocked/rejected.

Since we were talking about implementation, I wanted to point out that
packet number allocation is more complicated in practice.  I realize
this is not what you meant. :)

> As I understand it the packet number is used in the encryption process,
> so changing a packets number is a non-trivial operation.  A fast path
> route for queuing acks makes sense, again however the only real way
                                                        ^^^^^^^^^^^^^

By this, do you mean "without encrypting data twice?"

> to do that would be to give the ack packet a higher packet number but
> then send it before lower marked packets - even potentially if they
> do also contain ack frames.

That is a good approach if it does not break packet number derivation.
I am not sure whether it can...  The draft says:

  " A packet number is decoded by finding the packet number
  " value that is closest to the next expected packet.

Thus, after receiving ACK packet with large gap, which is the next
expected packet number from the point of view of the peer?

> For RST_STREAM I think it is permitted that currently queued packets
> are still sent, but if they only contain that streams packets then
> it is a beneficial optimization if they weren't sent (leaving packet
> number gaps).

Current draft says:

  " An endpoint that receives a RST_STREAM frame (and which
  " has not sent a FIN or a RST_STREAM) MUST immediately
  " respond with a RST_STREAM frame, and MUST NOT send any
  " more data on the stream.

I suppose one could interpret "send" to mean "enqueue," but I would
err on the side of caution.

  - Dmitri.

---

From: "Swindells, Thomas (Nokia - GB/Cambridge, UK)" <[email-masked]>
Date: Wed, 26 Jul 2017 09:27:19 +0000

> Sent: 25 July 2017 17:27
> <[email-masked]>
> > methods are valid.  You are right though there is the potential for
> > the queuing operation to be blocked/rejected.
> 
> Since we were talking about implementation, I wanted to point out that packet
> number allocation is more complicated in practice.  I realize this is not what
> you meant. :)
> 
> > As I understand it the packet number is used in the encryption
> > process, so changing a packets number is a non-trivial operation.  A
> > fast path route for queuing acks makes sense, again however the only
> > real way
>                                                         ^^^^^^^^^^^^^
> 
Yes - re-encrypting can't really be considered a 'trivial' operation
 
> > then send it before lower marked packets - even potentially if they do
> > also contain ack frames.
> 
> Thus, after receiving ACK packet with large gap, which is the next expected
> packet number from the point of view of the peer?
The spec says that you should give plenty of room in the number space, so as long as you haven't reached half your number space across that period this should be extremely rare or perhaps impossible. 
The worst case is that if you do violate it then either you may be requested to retransmit some packets, or you just send the original packets first and then the ack.
 
> > are still sent, but if they only contain that streams packets then it
> > is a beneficial optimization if they weren't sent (leaving packet
> > number gaps).
> 
> Current draft says:
> 
> I suppose one could interpret "send" to mean "enqueue," but I would err on
> the side of caution.
With a basic integration between an application and quic stack the api would likely just be the application writing a load of data onto a stream which then gets multiplexed into a quic connection.
In this case the application view would be once it has written it to the stream it is being 'sent' - in the same way the assumption is held for TCP transmission. 
Packetization and enqueuing for transmission would therefore be considered part of the sending process and with that API it would seem to be fair to send queued data but not allow new writes from the application.
Assuming no re-encryption/packetization, that is pretty much all you can do if packets contain data from multiple stream frames anyway. 
The "immediately respond with a RST_STREAM" perhaps then needs to be read as: "immediately, after any pending packets have been transmitted, such that no new packets with data from that stream are generated with a higher packet number than the RST_STREAM response frame."?

Thomas

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 26 Jul 2017 14:16:37 +0000

(Going back to the original discussion)

Magnus,

IIUC, you are asking for a network device to be able to observe packets
within a flow.  don't understand what the value of encrypting the high
order bits is if there are enough low order bits to allow linkability
across packets within a flow. After all, the point of encyptimg packet
number is to avoid linkability, isn't it?

- jana

On Jul 20, 2017 3:00 AM, "Magnus Westerlund" <[email-masked]>
wrote:

> detection of packet loss in measurements and network management, it would
> be really good if the packet numbers where continuous and not only
> monotonically increasing. As this enables one to determine losses upstream
> of the measurement point. At the same time I understand there are benefits
> with being able to introduce gaps into the packet number to test the
> receiver's behaviour.
>
> might be that N needs to be scaled with throughput with a minimal value.
> N=8 would mean 256 packets between wraps. I think that is a reasonable
> minimal value. However, that will wrap in 28 ms at 100 mbps of payload
> (assuming 1400 bytes of payload per packet).
>

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 28 Jul 2017 08:32:08 -0400

On Wed, Jul 26, 2017 at 09:27:19AM +0000, Swindells, Thomas (Nokia - GB/Cambridge, UK) wrote:
> The spec says that you should give plenty of room in the number space,
> so as long as you haven't reached half your number space across that
> period this should be extremely rare or perhaps impossible.  The worst
> case is that if you do violate it then either you may be requested to
> retransmit some packets, or you just send the original packets first
> and then the ack.

OK -- this should work.  I'd have to work out the math to prove it to
myself, though. :)

> With a basic integration between an application and quic stack the
> api would likely just be the application writing a load of data onto
> a stream which then gets multiplexed into a quic connection.  In this
> case the application view would be once it has written it to the
> stream it is being 'sent' - in the same way the assumption is held for
> TCP transmission.  Packetization and enqueuing for transmission would
> therefore be considered part of the sending process and with that API
> it would seem to be fair to send queued data but not allow new writes
> from the application.

Sure, I agree -- I was not talking about the application level at all,
just the QUIC layer.  The application should not be in the business of
sending RST_STREAM frames.

> Assuming no re-encryption/packetization, that is pretty much all you
> can do if packets contain data from multiple stream frames anyway.

If one assumes that, then yes.

> The "immediately respond with a RST_STREAM" perhaps then needs to be
> read as: "immediately, after any pending packets have been transmitted,
> such that no new packets with data from that stream are generated with
> a higher packet number than the RST_STREAM response frame."?

Not unless the "MUST NOT" in the quoted draft paragraph above be changed
to "SHOULD NOT:"  An eager implementation may check whether its peer has
sent stream data after receiving RST_STREAM (which it would know by the]
ACK frame) and terminate the connection.

  - Dmitri.