Subject: [core] Message ID sliding window

From: Brian Frank <[email-masked]>
Date: Thu, 16 Jun 2011 10:04:26 -0400

The way the current spec is written a client is free to pick random Message
ID with each new request.  I propose to restrict this to require that a
client must serially increment the Message ID for each new request.

On one hand, I don't see that allowing clients use randomized Message IDs
provides any value.  But on the other hand knowing that Message IDs
increment in order allows many potential server-side optimizations:

- today a server is required to allocate a buffer of X message IDs per
client.  Lets say we store the last 10 message IDs received using 20 bytes.
 In the same 20 bytes using a sliding window bitmask we could potentially
store a window of up to 144 messages received.  It may or not make sense
dependent on the application, but seems nice to have that implementation
option.

- serial Message IDs make it easy to detect out-of-order messages (if the
application level needs to know)

So this seems like one of those cases where taking a away a bit of dubious
client flexibility provides a lot more server flexibility.

On a similar note, the spec requires that a client share the same MessageId
variable with communication to all destination servers.  Does that actually
have to be a MUST level requirement?  It seems like an implementation detail
to me since we can also route responses using the tuple of (addr, port,
message-id).

---

From: [email-masked]
Date: Thu, 16 Jun 2011 10:15:42 -0400

Brian,

Good catch and I concur with both of your recommendations.  CoAP is (among 
other things) an alternative to TCP at OSI Layer 4 .  From that 
standpoint, monotonically increasing message IDs per connection are a 
significant optimization.  In a disconnected pattern, the Message ID is 
merely a correlator; and in a highly congested environment, randomizing 
per client actually makes message ID collision more likely.  (I continue 
to feel that 16 bits are not enough.)

Thanks

Frank Wilhoit
Enterprise Information Architect
Enterprise Architecture and Strategy
American Electric Power
Direct Dial 614.716.3878
Audinet 8.200.3878

Scraping the bottom of a different barrel, since 1958.

From:   Brian Frank <[email-masked]>
To:     core <[email-masked]>
Date:   06/16/2011 10:04 AM
Subject:        [core] Message ID sliding window
Sent by:        [email-masked]

The way the current spec is written a client is free to pick random 
Message ID with each new request.  I propose to restrict this to require 
that a client must serially increment the Message ID for each new 
request. 

- today a server is required to allocate a buffer of X message IDs per 
client.  Lets say we store the last 10 message IDs received using 20 
bytes.  In the same 20 bytes using a sliding window bitmask we could 
potentially store a window of up to 144 messages received.  It may or not 
make sense dependent on the application, but seems nice to have that 
implementation option.

On a similar note, the spec requires that a client share the same 
MessageId variable with communication to all destination servers.  Does 
that actually have to be a MUST level requirement?  It seems like an 
implementation detail to me since we can also route responses using the 
tuple of (addr, port, message-id).
_______________________________________________
core mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/core

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 16 Jun 2011 20:07:48 +0200

Brian,

You lost me.

> - today a server is required to allocate a buffer of X message IDs per client.  

Why/what for?
Most servers are completely stateless, they don't need to allocate anything.
Where they do need to (non-idempotent methods like POST), they also usually need to store responses, so there is little savings in just being able to compress message-IDs.

Can you explain the usage scenario some more where this would make a difference?

> - serial Message IDs make it easy to detect out-of-order messages (if the application level needs to know)

Danger, Will Robinson.  Are you suggesting that we start giving application semantics to message-IDs?
That would be serious conflation.

(Yes, we do have an out-of-order detection problem, which is addressed in -observe.
If there were a way to simplify this with message IDs, that might be interesting -- but I think the current way is already rather simple as it is.)

Gruesse, Carsten

---

From: [email-masked]
Date: Thu, 16 Jun 2011 17:55:03 -0400

Carsten,

Sequential message IDs are not an application semantic.  They are a Layer 
4 semantic.  It appears to me that doing Layer 4 with random message IDs 
would  require the maintenance of more state, viz. a lookup table of 
message IDs that have not yet been ACKed or timed out.  Again, to Brian's 
point, clients do not gain anything from the privilege of randomizing 
message IDs .  When I read the spec, I silently assumed that message IDs 
would be sequential and per-connection.

Out-of-order messages and dropped messages are going to be a constant 
problem on RF mesh networks.

It is a fine idea to supplant TCP in a semi-connected environment, but you 
have to get to Layer 4 somehow.

thx

Frank Wilhoit

From:   Carsten Bormann <[email-masked]>
To:     Brian Frank <[email-masked]>
Cc:     core <[email-masked]>
Date:   06/16/2011 05:36 PM
Subject:        Re: [core] Message ID sliding window
Sent by:        [email-masked]

Brian,

You lost me.

> - today a server is required to allocate a buffer of X message IDs per 
client. 

Why/what for?
Most servers are completely stateless, they don't need to allocate 
anything.
Where they do need to (non-idempotent methods like POST), they also 
usually need to store responses, so there is little savings in just being 
able to compress message-IDs.

Can you explain the usage scenario some more where this would make a 
difference?

> - serial Message IDs make it easy to detect out-of-order messages (if 
the application level needs to know)

Danger, Will Robinson.  Are you suggesting that we start giving 
application semantics to message-IDs?
That would be serious conflation.

(Yes, we do have an out-of-order detection problem, which is addressed in 
-observe.
If there were a way to simplify this with message IDs, that might be 
interesting -- but I think the current way is already rather simple as it 
is.)

Gruesse, Carsten

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Fri, 17 Jun 2011 12:16:29 +0200

Dear Brian F., Frank W.,

you may want to take a look at this draft where sequential message IDs
are discussed:
http://tools.ietf.org/html/draft-castellani-core-coap-overhead-01
( and probably you want also to take a look at this one
http://tools.ietf.org/html/draft-castellani-core-transport-00 )

However this discussion seems currently out-of-scope for CoAP, which
as far as I know has already closed the "bigger"-part of the design of
its message-layer using different assumptions/features.

I am still working on something similar for different reasons..

Best,
Angelo

On Thu, Jun 16, 2011 at 23:55,  <[email-masked]> wrote:
> Carsten,
>
> Sequential message IDs are not an application semantic.  They are a Layer 4
> semantic.  It appears to me that doing Layer 4 with random message IDs would
>  require the maintenance of more state, viz. a lookup table of message IDs
> that have not yet been ACKed or timed out.  Again, to Brian's point, clients
> do not gain anything from the privilege of randomizing message IDs .  When I
> read the spec, I silently assumed that message IDs would be sequential and
> per-connection.
>
> ________________________________
>
>
> Brian,
>
> You lost me.
>
> Where they do need to (non-idempotent methods like POST), they also usually
> need to store responses, so there is little savings in just being able to
> compress message-IDs.
>

---

From: Brian Frank <[email-masked]>
Date: Fri, 17 Jun 2011 19:30:58 -0400

> need to store responses, so there is little savings in just being able to
Because often a non-idempotent POST request might not have a response
payload or the payload can be reconstructed from application state, in which
case the server only needs to keep track of whether it has seen the message
or not.

Let's rephrase the issue:

What value is there in allowing a client to not use serial IDs?  I can't
think of any use-case where this flexibility provides any value, but maybe
something was discussed?

On the other hand, there seems like lots of different use cases where
serially incrementing Message IDs might have value.

The spec just doesn't seem to make a good engineering trade-off on this
issue.

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 18 Jun 2011 08:39:17 +0200

On Jun 18, 2011, at 01:30, Brian Frank wrote:

> Because often a non-idempotent POST request might not have a response payload or the payload can be reconstructed from application state, in which case the server only needs to keep track of whether it has seen the message or not.

So this is all about optimizing one very special case.

(I'd still like to understand the use case, in specific terms.
If the response options/payload indeed can be reconstructed from application state, that might also provide any deduplication needed.)

> What value is there in allowing a client to not use serial IDs?  

First of all, what does this question mean?
When is a message ID "serial"?
What would a server do when a client does something slightly non-serial?
(Messages do get lost or reordered.)
What would a server do when a client's message IDs are all over the place?
Reject the request with "your message ID's aren't as close to each other as I'd like"?
What would a server do when a client reboots?  How do you ensure the server's state has timed out quickly enough for the rebooted client to send messages again?
This gets ugly very quickly.

> I can't think of any use-case where this flexibility provides any value, but maybe something was discussed?
> 
> On the other hand, there seems like lots of different use cases where serially incrementing Message IDs might have value. 
> 
> The spec just doesn't seem to make a good engineering trade-off on this issue.

The spec does the right thing from a protocol design point of view: It does not provide a constraint where none is needed.

However, 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'm not yet convinced of the use case.

Gruesse, Carsten

---

From: Brian Frank <[email-masked]>
Date: Tue, 21 Jun 2011 08:08:28 -0400

This seems like a fairly simple question to me: which is the better
engineering tradeoff: to force IDs to be allocated in order, or allow them
to be generated randomly.

If there are ordered:
  - can use a sliding window to keep track of messages received more
compactly
  - can detect out of order messages
  - can more easily detect duplicate messages
  - safest course for clients to ensure maximum time before ID is recycled

If there are not ordered:
  - no value

On Sat, Jun 18, 2011 at 2:39 AM, Carsten Bormann <[email-masked]> wrote:

> If the response options/payload indeed can be reconstructed from
> application state, that might also provide any deduplication needed.)
>
> What would a server do when a client reboots?  How do you ensure the
> server's state has timed out quickly enough for the rebooted client to send
> messages again?
> The spec does the right thing from a protocol design point of view: It does
> not provide a constraint where none is needed.
>
> However, 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.
>

---

From: "Dijk, Esko" <[email-masked]>
Date: Wed, 29 Jun 2011 11:52:50 +0200

Dear Brian,

for clarification - do you mean here ordered with a separate 16-bit MID counter kept for each CoAP destination node, or ordered with simply one MID counter that is used for all communications (like defined in the current coap-06 spec; a single MID variable) ?

Or could a CoAP node even choose between these two ways of ordering?

best regards,
Esko

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]<mailto:[mailto:[email-masked]]> On Behalf Of Brian Frank
Sent: Tuesday 21 June 2011 14:08
To: Carsten Bormann
Cc: core
Subject: Re: [core] Message ID sliding window

This seems like a fairly simple question to me: which is the better engineering tradeoff: to force IDs to be allocated in order, or allow them to be generated randomly.

If there are ordered:
  - can use a sliding window to keep track of messages received more compactly
  - can detect out of order messages
  - can more easily detect duplicate messages
  - safest course for clients to ensure maximum time before ID is recycled

On Sat, Jun 18, 2011 at 2:39 AM, Carsten Bormann <[email-masked]<mailto:[email-masked]>> wrote:

Gruesse, 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.