Subject: [Ntp] Draft on Interleave Mode -- Keeping "preemptive" per-client state

From: [email-masked]
Date: Mon, 13 Nov 2017 15:26:07 +0100

​Hello all,

I wanted to start/revive a discussion about the interleave mode described 
in https://tools.ietf.org/pdf/draft-mlichvar-ntp-interleaved-modes-00.pdf.

Currently, the behavioral scheme for a server seems to be roughly the 
following:
Whenever a client "basic" request comes in, the server answers it with a 
"basic" response (so far, so obvious), but it additionally keeps state for 
this association/this specific exchange(?), in case that there is ever 
going to be an additional client "interleave" request. As long as the 
server wishes to offer interleaved mode, this happens always, regardless 
of need.
This is completely reasonable if it can be expected that every "basic" 
request (or at least a very large portion of them) will eventually be 
followed up upon with an "interleave" request.
It does, however, seem like serious overkill for any association where 
such a follow-up call can not be expected.

I would therefore advise some additional communication, to get rid of the 
cases where state is kept unnecessarily.
We can go into specifics if there is interest, but I wanted to keep this 
discussion starter short.

Best regards,
Kristof

---

From: Miroslav Lichvar <[email-masked]>
Date: Mon, 13 Nov 2017 15:56:07 +0100

> cases where state is kept unnecessarily.

That is a good point.

One option would be to check if the origin timestamp is not zero
before saving/updating the state. Majority of public NTP traffic is
from various SNTP clients, which send packets with zero origin
timestamp. Full NTP clients using the basic mode and following the
data minimization draft will do that too.

In order to avoid delaying the first response in the interleaved mode
by one client/server exchange, the clients could send the first
request with a dummy (random?) origin timestamp.

-- 
Miroslav Lichvar

---

From: Aanchal Malhotra <[email-masked]>
Date: Mon, 13 Nov 2017 17:32:26 +0000

As far as I understand, kristoff is trying to say is the following:
1) we should be able to get rid of the preemptively stored "state" on the
server supporting interleaved mode for each client.

2) Look for options where a client can tell in its basic mode request,
somehow, if he wants the next response to be in the interleaved mode, thus
indicating to the server that it should now start to save the state for
this client to be able to respond in the interleaved mode in the next
response.

Correct me if I am wrong Kristof?

Solution: If we are really conservative about saving even a little
additional information for each client on the server preemptively, we could
have a couple of choices here:

1) as Miroslav mentioned, the origin time stamp on the client basic mode
request can be random, thus indicating to the server that the next request
from this client is going to be an interleaved request and so the server
should start saving the state for this client.

2) have something (a bit) in the extensions field of the client basic mode
request packet that indicates to the server that the next request from the
client is going to be in the interleaved mode and that it should start
saving the state for this client.

Miroslav and I had a discussion on having a separate mode number for
interleaved mode but since there is just 3 bits for the mode field in the
NTP packet, that does not seem like a feasible option.

In short, my point is that what Kristof is concerned about is the "state"
that the server has to keep preemptively for each of its client!

Thx!
Aanchal.

-- 
Sent from iPhone

---

From: [email-masked]
Date: Tue, 14 Nov 2017 09:04:02 +0100

Hello all,

when I wrote my last mail (cited below), I had already fleshed out some 
detailed text, but I did not want to include it yet, because that would 
have made for an overall quite large wall-of-text.
I'm submitting it now, since there appears to be interest in the topic. 
This is just my more detailed input, it is not yet to be understood as a 
response to Miroslav or Aanchal. I will get to that later today.

Details:

In the working group session this afternoon in Singapore, Aanchal hinted 
that the reasoning fopr this decision has to do with state that would be 
kept anyway (for traffic limitaions, as far as I understood). I would like 
to point out that

A) I don't believe it to be a healthy assumption that this happens 
"anyway".
In principle, traffic limitation do not necessarily have to be done at the 
same place where NTP responses are generated. Also, traffic limitations do 
not necessarily have to be done on a per-client basis.
Overall, I'm saying that in the interest of a potentially modular approach 
to implementing all the different specifications that are being written 
currently, I don't like to have unnecessary assumptions about a module X 
in the design for module Y.Which brings me to my next point:

B) I don't see how it is in anyway necessary (or even significantly 
beneficial) to do it this way.
Specifically, I don't see how it is better than either of the following 
alternatives:
  - RESTRICT the behavior above (keeping state) to happen only if the 
first ("basic") request has some kind of signalling flag in it.
  - REPLACE the "interleave" request on the client side with a signalling 
flag in the "basic" request. Semantically, this would basically say "send 
me an additional 'interleave' response as soon as possible".
Both of these seem to cause very little additional cost themselves (a few 
more bits in the communication, a bit more processing), and would cut 100% 
of the additional costs in the unnecessary cases described above (where 
clients do not intend to follow up with "interleave" requests).

Best regards,
Kristof

Von:    [email-masked]
An:     [email-masked]
Kopie:  Aanchal Malhotra <[email-masked]>
Datum:  13.11.2017 15:27
Betreff:        [Ntp] Draft on Interleave Mode -- Keeping "preemptive" 
per-client state
Gesendet von:   "ntp" <[email-masked]>

​Hello all, 

Best regards, 
Kristof _______________________________________________
ntp mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ntp

---

From: Miroslav Lichvar <[email-masked]>
Date: Tue, 14 Nov 2017 11:41:57 +0100

On Tue, Nov 14, 2017 at 09:04:02AM +0100, [email-masked] wrote:
> in the design for module Y.

I agree that the specification should allow the server to avoid saving
state for clients that do not use the interleaved mode, if it can be
easily without breaking compatibility, e.g. using a new extension
field. A check of the origin or receive timestamp seems like a good
candidate.

However, I'm not sure how much of a difference this will really make.
How would an implementation where "saving state" for all clients had
a significant cost on performance look like?

I think there are basically two options how the server mode can be
implemented. One uses a hash table to map IP addresses to one or two
pairs of receive and transmit timestamps. The other uses a hash table
to map receive timestamps to transmit timestamps, where all clients
are mixed together and it's not necessary to save any IP address.

In both cases I'd expect that saving the receive timestamp in order to
detect a request in the interleaved mode is cheap. At least in my
tests I didn't see a significant impact on performance. The transmit
timestamp is more expensive, but that can be delayed until the client
sends an actual request in the interleaved mode (i.e. origin timestamp
matches a saved receive timestamp).

> Which brings me to my next point:
> 

Please keep in mind that the draft is trying to specify a protocol
which is compatible with existing implementations of the "interleaved"
mode. The interleaved client/server mode is just a special case of the
interleaved symmetric mode. If you take an old version of ntpd and
use the xleave option, a peer with no association which behaves like a
server in the client/server mode and follows the specification should
be able to detect and respond in the interleaved mode.

> me an additional 'interleave' response as soon as possible".

Wouldn't this be something like the follow-up message in PTP? I think
the biggest issue is that it would allow traffic amplification. The
request could be made longer than response to make the traffic
symmetric, but that would create an asymmetric network delay and ruin
the accuracy.

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 23 Nov 2017 16:39:01 +0100

> data minimization draft will do that too.

And if there was a need to avoid saving timestamps for old NTP
clients, which set the origin timestamp in their requests to the last
transmit timestamp of the server, I think the server could encode an
RX bit in the timestamps themselves in their low-order bits below
precision of the clock.

For example, all receive timestamps of the server could end with 1
and transmit timestamps end with 0. When the server receives a request
with an origin timestamp ending with 0, it will know it's an NTP
client using the basic mode and it does not need to save any
timestamps for the interleaved mode.

To make the bit random, the server could add to it a hash of a secret
key, the other bits, and the IP address of the client for instance.
This could be extended to all bits below the precision to make it less
likely a random origin timestamp will be interpreted as a receive
timestamp. I'm not sure if we need to specify how exactly the bit
should be encoded.

I'm considering to add to the end of the client/server section of the
draft something like this:

  The server MAY limit saving of the receive and transmit timestamps
  to requests which have an origin timestamp specific to the
  interleaved mode in order to not waste resources on clients using
  the basic mode. Such an optimization delays the first interleaved
  response of the server by one exchange.
  
  A check for a non-zero origin timestamp works with clients that
  implement the NTP data minimization [I-D.ietf-ntp-data-minimization].
  To detect requests in the basic mode from clients that do not
  implement the data minimization, the server can encode in low-order
  bits of the receive and transmit timestamps below precision of the
  clock a bit indicating whether the timestamp is a receive timestamp.
  If the server receives a request with a non-zero origin timestamp
  which does not indicate it is receive timestamp of the server, the
  request is in the basic mode and it is not necessary to save the new
  receive and transmit timestamp.

What do you think?

-- 
Miroslav Lichvar