Subject: Re: [core] Message ID sliding window

From: "Dijk, Esko" <[email-masked]>
Date: Wed, 14 Dec 2011 09:36:39 +0000

Hi Zach,

to attempt to conclude this thread: does the proposed text below make sense to you?

The key arguments for including it are 
 1) make developers aware of this possibility for efficient implementation of MID storage, assuming many CoAP end-points would use sequential MIDs; 
 2) suggest that developers use sequential MIDs if there's no reason to do otherwise; 

Esko

-----Original Message-----
From: Dijk, Esko 
Sent: Tuesday 25 October 2011 9:46
To: Zach Shelby
Cc: Jari Arkko; [email-masked]
Subject: RE: [core] Message ID sliding window

Here is a proposal that can be added at the end of the paragraph
   "Several implementation strategies can be employed for generating Message IDs .....
   ........ RESPONSE_RANDOM_FACTOR * (2 ^ MAX_RETRANSMIT - 1) plus the expected
   maximum round trip time."

[proposal:]
   To support efficient Message ID storage implementations for duplicate message 
   detection (which is detailed below), an end-point MAY generate sequential 
   Message IDs by increasing a Message ID variable by 1 each time a 
   new message is sent. 

This does not prescribe one or multiple MID variables, this is left to implementation strategies as stated in the current paragraph already.
Specific implementation strategies are mentioned as a motivation for this optional behaviour. The wrapping of value from highest to 0 is not explicitly mentioned but could be added.

Esko

-----Original Message-----
From: Zach Shelby [mailto:[email-masked]] 
Sent: Monday 24 October 2011 13:24
To: Dijk, Esko
Cc: Jari Arkko; [email-masked]
Subject: Re: [core] Message ID sliding window

So to conclude on this thread with a concrete action on the draft (or not). The current text says:

"Several implementation strategies can be employed for generating Message IDs. In the simplest case a CoAP end-point generates Message IDs by keeping a single Message ID variable, which is changed each time a new confirmable message is sent regardless of the destination address or port."

Esko is suggesting to make it more explicit that this MAY be sequentially incremented. There doesn't seem to be push-back on that as long is it isn't a SHOULD. Do you have a proposal for the new text that you think should be added? So far I haven't been able to come up with MAY text that would make much sense here considering the current text.

Zach

On Oct 17, 2011, at 5:56 PM, Dijk, Esko wrote:

> Hi,
> 
>> We should not mandate that in any sense in the spec, however, because otherwise someone will start trusting that all devices behave that way.
> 
> this was one of the reasons for me to propose a 'MAY' here. It does not create a barrier to interesting strategies e.g. as used in the tiny CoAP sensors. A 'SHOULD' is rather strong here ("but the full implications must be understood and carefully weighed before choosing a different course", RFC 2119). 
> 
> A 'MAY' serves as a note to implementers "you could do it this way, with these specific benefits" which should be enough push in the right direction in applications where an implementer doesn't really care what MID generation strategy is applied e.g. as in unconstrained nodes. 
> Interestingly a 'MAY' provides a _stronger_ requirement for CoAP nodes to support non-sequential MIDs from other nodes. Because then, implementers will not assume that everyone follows the 'SHOULD' from the spec. In fact they MUST NOT assume that the optional feature is there, as RFC 2119 indicates for a 'MAY' :)
> 
> (Downside is that there is less incentive for implementers to care about optimizing MID storage, though.)
> 
> regards,
> Esko
> 
> -----Original Message-----
> From: Jari Arkko [mailto:[email-masked]] 
> Sent: Monday 17 October 2011 13:43
> To: Zach Shelby
> Cc: Dijk, Esko; [email-masked]
> Subject: Re: [core] Message ID sliding window
> 
> 
> The original proposal that started this thread was to make some recommendation on using sequential IDs. I am against that (even as a SHOULD), on the grounds that it is unnecessary and any level of mandatory sequencing would break some implementation strategies (such as the one I used on my tiny device). Of course you can use any strategy you want, including sequencing. We should not mandate that in any sense in the spec, however, because otherwise someone will start trusting that all devices behave that way.
> 
> Anyway, I had a quick look at -07 and noticed this:
> 
>> End-points dealing with large numbers of
>> transactions could keep multiple Message ID variables, for example
>> per prefix or destination address.  The initial variable value SHOULD
>> be randomized.  The same Message ID MUST NOT be re-used within the
>> potential retransmission window, calculated as RESPONSE_TIMEOUT *
>> RESPONSE_RANDOM_FACTOR * (2 ^ MAX_RETRANSMIT - 1) plus the expected
>> maximum round trip time.
> 
> I think you should change s/window,/window to the same destination address,/ because otherwise those multiple variables are not going to be very useful.
> 
> (Or possibly a combination of source/destination address.)
> 
> Jari
> 
> On 17.10.2011 12:46, Zach Shelby wrote:
>> Esko,
>> 
>> Indeed, I do believe that sequential MIDs are going to be a common implementation strategy (of course with a random initial value). This is allowed by the current specification. What benefit do you see from adding MAY language around something that you may already do?
>> 
>> Seems instead we would need to point out to CoAP implementors that behavior could be used to optimize the storage of MIDs for duplication detection.
>> 
>> Now I think the reason why Carsten suggested a SHOULD is that this would make the optimization a whole lot more useful as it would encourage the majority of implementations to be compatible with this optimization. That makes sense.
>> 
>> Zach
>> 
>> On Oct 7, 2011, at 5:49 PM, Dijk, Esko wrote:
>> 
>>> To continue this discussion from a while ago: I agree with Jari on the freedom of assigning message IDs.
>>> After a reboot the MID value is likely randomized and receiving CoAP nodes have to deal with that. And a sending node may wish to store only one MID counter for whatever reasons, or generated randomly if storing state is expensive.
>>> 
>>> However, it can still be beneficial to suggest (MAY) using sequential MIDs (mid++) for the regular operation between reboots. As an advice to be followed in case no special/random/stateless MID generation is required by a sender. The reason is that this optionally enables to save RAM in receiving CoAP nodes that implement an optimized storage for MIDs close together, trading higher code complexity for lower RAM use. MIDs are stored then for deduplication purposes.
>>> 
>>> As Carsten phrased "if you believe supporting this specific optimization is worth it, we could RECOMMEND (i.e., mandate at the SHOULD level) to use message-IDs that are close (in modulo arithmetic) to recently used message-IDs". I think it is worth it as OPTIONAL/MAY behaviour.
>>> A use case may be a client sending a "toggle light" command to a CoAP (server) lamp.
>>> 
>>> best regards,
>>> Esko
>>> 
>>> -----Original Message-----
>>> From: [email-masked] [mailto:[email-masked]] On Behalf Of Jari Arkko
>>> Sent: Thursday 30 June 2011 1:47
>>> To: [email-masked]
>>> Subject: Re: [core] Message ID sliding window
>>> 
>>> I actually like the freedom to use any approach to assigning message
>>> IDs. I can imagine a few reasons why it might be easier in some cases to
>>> have that freedom. As a hypothetical example, maybe I want to store only
>>> one counter but send messages to multiple other nodes. Also, as Carsten
>>> pointed out, sequential assignment is not as trivial as it sounds. What
>>> do you or the receivers do after a reboot?
>>> 
>>> That being said, if you want your sender to use sequential message IDs,
>>> it can just go ahead and do it. On the receiver side the issue is more
>>> complex. COAP has acknowledgments to deal with those cases where you
>>> absolutely have to sequence some operations, and relying merely on
>>> sequence numbers would appear to not work in all cases, e.g., when a
>>> message is lost. Given the reboot problem, a simple sliding window
>>> approach might not be sufficient to keep track of which messages you
>>> have received.
>>> 
>>> As a side note, I scanned the COAP draft today and did not find anything
>>> about the scope of message IDs. Presumably message ID duplicate
>>> detection etc should only apply for a given IP source and destination
>>> pair. Otherwise there will be too many collisions. Is this specified
>>> somewhere?
>>> 
>>> Jari
>>> 
>>> _______________________________________________
>>> core mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/core
>>> 
>>> The information contained in this message may be confidential and legally protected under applicable law. The message is intended solely for the addressee(s). If you are not the intended recipient, you are hereby notified that any use, forwarding, dissemination, or reproduction of this message is strictly prohibited and may be unlawful. If you are not the intended recipient, please contact the sender by return e-mail and destroy all copies of the original message.
>>> 
>>> _______________________________________________
>>> core mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/core
> 
> 

-- 
Zach Shelby, Chief Nerd, Sensinode Ltd.
http://www.sensinode.com
http://zachshelby.org  - My blog "On the Internet of Things"
http://6lowpan.net - My book "6LoWPAN: The Wireless Embedded Internet"
Mobile: +358 40 7796297

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 14 Dec 2011 11:45:06 +0100

On Dec 14, 2011, at 10:36, Dijk, Esko wrote:

> suggest that developers use sequential MIDs

I think such a suggestion would work best if there also were a short description of what the implementation benefits are.
This description need not be in the CoAP spec -- I'd love to have a paragraph or two about MID processing in the LWIG guidance document.

Grüße, Carsten

---

From: "Dijk, Esko" <[email-masked]>
Date: Wed, 14 Dec 2011 12:13:29 +0000

Ok, I could produce some text for that in January.

thanks
Esko

-----Original Message-----
From: Carsten Bormann [mailto:[email-masked]]
Sent: Wednesday 14 December 2011 11:45
To: Dijk, Esko
Cc: 'Zach Shelby'; [email-masked]'
Subject: Re: [core] Message ID sliding window

Grüße, Carsten

________________________________
The information contained in this message may be confidential and legally protected under applicable law. The message is intended solely for the addressee(s). If you are not the intended recipient, you are hereby notified that any use, forwarding, dissemination, or reproduction of this message is strictly prohibited and may be unlawful. If you are not the intended recipient, please contact the sender by return e-mail and destroy all copies of the original message.