Message ID generation

[ektrah]

Errata ID: 5429
Type: Technical
Reported By: Marian Buschsieweke
Date Reported: 2018-07-18

Section 4.4 says/should say:

 An Acknowledgement or Reset message is related to a Confirmable
 message or Non-confirmable message by means of a Message ID along
 with additional address information of the corresponding endpoint.
 The Message ID is a 16-bit unsigned integer that is generated by the
 sender of a Confirmable or Non-confirmable message and included in
-the CoAP header.  The Message ID MUST be echoed in the
+the CoAP header.  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.  The Message ID MUST be echoed in the
 Acknowledgement or Reset message by the recipient.

 The same Message ID MUST NOT be reused (in communicating with the
 same endpoint) within the EXCHANGE_LIFETIME (Section 4.8.2).

 Implementation Note:  Several implementation strategies can be
   employed for generating Message IDs.  In the simplest case, a CoAP
   endpoint generates Message IDs by keeping a single Message ID
-  variable, which is changed each time a new Confirmable or Non-
+  variable, which is incremented each time a new Confirmable or Non-
   confirmable message is sent, regardless of the destination address
   or port.  Endpoints dealing with large numbers of transactions
   could keep multiple Message ID variables, for example, per prefix
   or destination address.  (Note that some receiving endpoints may
   not be able to distinguish unicast and multicast packets addressed
   to it, so endpoints generating Message IDs need to make sure these
   do not overlap.)  It is strongly recommended that the initial
   value of the variable (e.g., on startup) be randomized, in order
   to make successful off-path attacks on the protocol less likely.

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.

[cabo]

There is text in the LWIG-COAP document. To be determined how this is referenced or moved to the corr/clar document. Start at a random point, not always at zero. Server still needs to be prepared to get random MIDs.

[ektrah]

https://mailarchive.ietf.org/arch/msg/core/FeKXd9d3Tkrwju0azwvwKiM3GyM etc. pp.

[chrysn]

The LWIG-CoAP cabo mentioned has some text currently in 2.3.3 on MID "relaxation on the server". We might want to expand a bit on how "designed with idempotent operations only and makes good use of the If-Match/If-None-Match options" works in practice; not sure where that can go and whether normative IETF documents or tutorial-/FAQ-style texts are the right place for this. (Especially, idempotency in presence of multiple client interactions like in the last paragraph of one mail in the linked thread may need some illustrative examples)

The "sequential MIDs" are outlined in section 3.5, including a recommendation that clients produce sequential MIDs, and are largely aligned with what Marian has suggested but keep it at a recommendation level. The text is a bit incomplete IMO, but that's not for here to discuss but for lwig-wg/coap#4.

"Where the text lives"-wise, I think LWIG is still suitable due to its implementation-guidance character, but it might be a good idea to pull "RECOMMEND that CoAP endpoint implementers employ the “sequential MID” scheme if there are no reasons to prefer another scheme" into Corrections, and have Clarifications point towards LWIG a la "Devices of Class 1 often do not need to exercise message deduplication, as their applications are usually designed to have idempotent requests; see LWIG-CoAP Section 2.3.3. If deduplication is still unavoidable, they may want to optimize for sequential MIDs as per LWIG-CoAP Section 3.5".

[boaks]

within EXCHANGE_LIFETIME MUST be strictly ascending (wrapping around at a value of 65535)

If the MUST includes the 65536, I object to comply with 8.1. Multicast CoAP -
Messaging Layer some implementations use reserved special ranges. So I would prefer no fixed upper border.

[cabo]

Good point.

[boaks]

Though it raised again in the e-mail list:

Additionally, two subsequently send Message IDs to the same endpoint SHOULD have a difference of at most 16.

Assuming, that some peers give up after some retries without having the message with the MID delivered, this may also be too strict. Maybe adding a "time range" for that will help to fix it. Anyway, even if I see the benefit, such a feature would in my opinion be more something for CoAP v2 ;-).

[boaks]

If we consider this optimization, I guess we need to consider #15 as relaxing variant as well.