Re: [core] [Technical Errata Reported] RFC7252 (5429)

[Marian Buschsieweke <[e-mail]>]

Dear Christian,

thanks for the fast reply.

> The memory requirements may have their point, but I think that this
> change would be far too severe for an erratum. If servers started
> relying on this change, that would easily invalidate duplicate message
> detection with existing implementations that use a single increasing
> message ID counter for all their peers.

The suggested change does not make it mandatory to have more than one counter.
The only mandatory change would be to actually use counters (one or more)
at all and to increment them for generating a new Message ID. It is
suggested to use more than one counter if a node is communicating with many
nodes at the same time, as it SHOULD keep jumps in Message IDs less than or
equal to 16. With messages coming in out of order or being lost a server still
expects jumps to be potentially bigger. But it is extremely likely that
Message IDs will remain in a range of lets say 64 consecutively numbers
(wrapping around at 65535). As a result, only the number of the lowest
expected Message ID needs to be stored and a 64 bit bitmask can be used to
store which Messages IDs have so far been used. This "window" can be moved
upwards as needed and any Message ID below that "window" is almost certainly a
duplicate. (I can provide more details how an efficient implementation could
look like and how also the time can be tracked efficiently regarding memory and
computational requirements - but I believe that might not be relevant for the
discussion.)

As far as I know, no CoAP implementation that is actively used employs a
different strategy than using counter(s) and increments it/them. If that is
true, it wouldn't hurt to make that behavior mandatory.

> That aside, I'm not sure the overhead estimations work that way.
> Duplicate message detection not only means that the message ID and the
> timestamp must be stored (your 4 bytes), but also the often much larger
> response message.

This is only partly true. With NSTART = 1 at most one request is outstanding. As
a result, at most one response needs to be cached per client - a client would
not send a new request without having the last response received or no longer
expecting to receive the response. The required memory for a single response is
usually much less than the 1 KiB for duplicate detection.

> Only non-idempotent (POST; which most applications will try to avoid)
> requests actually need the duplicate detection

In a scenario with many simultaneous clients this might not be true. E.g. if
Client A turns smart light on and Client B turns it off (e.g. "PUT /light on"
and "PUT /light off"), both requests would be idempotent. The expected result
would be that on requests comes in first - let's say the one of client A. So
the light turns first on and than off. But with many duplicates and no
duplicate detection, the light would be constantly switching on and off.

Kind regards,
Marian

-------------------------------------------------------------
M.Sc. Marian Buschsieweke
Dept. Communication and Networked Systems (ComSys)
Institute for Intelligent Cooperating Systems (IKS)
Otto-von-Guericke-University of Magdeburg
Universitätsplatz 2, Building 29, Room 314
39106 Magdeburg
Germany

http://www.comsys.ovgu.de/Team/Marian+Buschsieweke.html
Tel.: +49 - 391 - 67 - 52673
Fax:  +49 - 391 - 67 - 41161

-------------------------------------------------------------

On Thu, 19 Jul 2018 18:02:22 +0200
Christian Amsüss <[e-mail]> wrote:

> Hello Marian, hello CoRE WG,
> 
> (CC list stripped expecting that the authors are subscribed to CoRE)
> 
> On Wed, Jul 18, 2018 at 07:47:54AM -0700, RFC Errata System wrote:
> > [...] Message IDs of subsequence messages send to the
> > same endpoint within EXCHANGE_LIFETIME MUST be strictly ascending
> > (wrapping around at a value of 65535).  Additionally, two
> > subsequently send Message IDs to the same endpoint SHOULD have a
> > difference of at most 16.
> > [...]
> > 
> > Notes
> > -----
> > Without any restrictions on how Message IDs are generated, an
> > implementation of CoAP duplication detection must be prepared to
> > receive a random sequence of Message IDs.
> >
> > One simple implementation strategy would be to store the received
> > Message IDs along with a timestamp when they were received.
> >
> > If a 16 bit time stamp would be used, 4 Bytes per tracked Message ID
> > would be required.
> >
> > If additionaly a CoAP server expects requests to be received at a rate
> > of 1 message per second, at least 247 * 4 Byte or approximately 1 KiB
> > have to be allocated per client.
> >
> > A class 1 (see RFC 7228 Section 3) server could handle at most 10
> > clients in parallel, if anything apart duplicate detection could be
> > implemented without using any memory at all.
> > 
> > If instead Message IDs have to be generated by incrementing a (global
> > or per endpoint/network prefix/...) counter variable, duplicate
> > detection can be implemented in a time and memory efficient way
> > without limiting the rate of the message exchange between to nodes.
> 
> The memory requirements may have their point, but I think that this
> change would be far too severe for an erratum. If servers started
> relying on this change, that would easily invalidate duplicate message
> detection with existing implementations that use a single increasing
> message ID counter for all their peers.
> 
> That aside, I'm not sure the overhead estimations work that way.
> Duplicate message detection not only means that the message ID and the
> timestamp must be stored (your 4 bytes), but also the often much larger
> response message. As that is costly and should be avoided, constrained
> implementations will look into whether they need to deduplicate at all:
> 
> * For safe or idempotent request messages, message deduplication can be
>   skipped. (You'd build the response to a GET once again when a
>   duplicate hits you rather than storing the old response. For PUT,
>   you'll set the resource's state anew, and if that's part of a race
>   condition, so would a delayed package have been).
> 
>   Even some cases of POST can be treated like that (the application
>   would need to let the library know that).
> 
> * For observe notifications, the recipient would silently disregard the
>   apparently out-of-order package.
> 
> * For non-observe non-piggy-backed responses, the client would RST the
>   duplicate response rather than ACK it, which is just as good. (There
>   are no "The client received the response" semantics to the ACK).
> 
> Constrained implementations should avoid keeping MIDs and timestamps
> around for any of those.
> 
> Only non-idempotent (POST; which most applications will try to avoid)
> requests actually need the duplicate detection -- and then, there is
> also a response message to store, and then the overhead of actually
> storing the MID becomes far less significant.
> 
> 
> I'd be happy to be shown wrong, so please let's have the discussion if I
> am, but this is not something that should easily go into the errata.
> 
> Best regards
> Christian
>