Subject: [core] Message supersedure as a domain concept

From: "Peter A. Bigot" <[email-masked]>
Date: Sun, 27 Oct 2013 11:07:10 -0500

This is all architecture-level discussion related to the topics in:

* http://www.ietf.org/mail-archive/web/core/current/msg04938.html
* http://www.ietf.org/mail-archive/web/core/current/msg04990.html
* http://www.ietf.org/mail-archive/web/core/current/msg05037.html

Its purpose is to explain how CoAP led me down the garden path, and to
identify inconsistency in what "message supersedure" might mean.  Here
we go:

Many network stacks that use an unreliable underlying transport include
a reliability layer.  The concept is that an upper layer submits a
message and a lower layer transmits it multiple times until the
recipient confirms receipt or a timeout is reached or something else
stops the retransmissions.

CoAP calls this a "confirmable message".  In its simplest form a message
of type CON with a specific Message ID (MID) is transmitted to a
destination endpoint up to 1+MAX_RETRANSMIT times with binary
exponential backoff (BEBO) until a message of type ACK or RST with the
same MID is received from the destination endpoint.

The naive reader will see all this as consistent with the expected
behavior of a reliability layer, and will proceed assuming s/he
understands what a confirmable message is.

The first deviation from expectation comes in section 5.10.5 of coap-18,
discussing management of the Max-Age option value:

    The value is intended to be current at the time of transmission.
    Servers that provide resources with strict tolerances on the value of
    Max-Age SHOULD update the value before each retransmission.  (See
    also Section 5.7.1.)

Let's go back and clarify terms (some of these I'm creating on the fly
because CoAP doesn't distinguish them).

* A "(CoAP) message transmission" is the act of sending a CoAP message
   of type CON or NON.  This message has a source-defined message ID
   (MID), which is a 16-bit integral value.  The "message transmission"
   event occurs once for each message, regardless of CON or NON type
   (yes, once for CON messages: keep reading).

* A "(CoAP) message reply" is a CoAP message of type ACK or RST.  A CoAP
   message of type CON may evoke a reply of type ACK or RST; a CoAP
   message of type NON may evoke a reply of type RST.  In both cases, the
   MID of the reply is the same as the MID of the message that evoked the
   reply.  Neither ACK nor RST may evoke replies themselves.  A CoAP
   message transmission should evoke at most one CoAP message reply.

* A "transport layer transmission" is the act of submitting to the
   transport layer (UDP in this case) a block of data that is to be
   conveyed to a destination endpoint (IP address + port).  Messages of
   type NON, ACK, and RST normally have exactly one transport layer
   transmission (an exception occurs for reply messages under
   deduplication rules).  Messages of type CON may involve up to
   1+MAX_RETRANSMIT transport layer transmissions, terminating when the
   timeout of the last transmission completes or a reply message is
   received.

Back to the deviation.  When an upper layer submits a message to be
delivered reliably in most network stacks, the expectation is that any
lower-layer retransmissions are indistinguishable, i.e. the same bits
are transmitted each time (ignoring transport layer envelopes).  But
5.10.5 suggests that a transport layer retransmission of a confirmable
message containing a Max-Age option may have changed the value of that
option.

Cognitive dissonance.  What to do?

Answer: Appeal to the model of what a confirmable message is.  Naively,
it conveys some data.  But what we want it to convey is *information*.
Max-Age is an integral value that denotes an absolute time by providing
an offset, in seconds, from the time the message was created (as
estimated by the time it was sent, as estimated by the time it was
received).  So what 5.10.5 does is require the reliability layer to
change the *data* in the retransmitted message so that the *information*
(the absolute time) is unchanged.

Excellent: this makes sense, and is obviously the right thing to do.
(That it's optional and only applies to messages for resources with
strict tolerances on Max-Age is an inconsistency, but too late to do
anything about that now.  That it requires the reliability layer to be
able to recognize and mutate Max-Age options within the message content
is only slightly messy.)

Now we come to observe, which proposes that under certain circumstances
the entire representation of a resource, along with the Observe option
value, must be changed prior to transport layer retransmission of a
confirmable message.

Conceptually, what does this mean?  Technically, how is it done?

There are at least two approaches.

* One, which is what I believe is intended, says we should interpret the
   information conveyed by a response that includes the Observe option as
   "the current representation of the observed resource".  This allows us
   to replace the option value and the payload while retaining the same
   message ID and Token, without violating the concept of what a
   confirmable message means.

* The other, which is what I thought Klaus meant until Matthias
   corrected me, says that we cancel the previous confirmable message and
   replace it with a brand new notification message with its own message
   ID.  The new message then is granted the unused BEBO
   right-to-transmits from the cancelled message (because congestion
   requirements would normally prevent further transmissions to the
   endpoint until the original BEBO expired, since they are not relaxed
   by the act of cancelling a message).

Both these concepts need further refinement, but for my purposes here
they should be clear enough.  These are different techniques, and before
one is used in a CoAP specification it should have a distinct name and a
clear definition.

The latter is what I meant by "message supersedure" in all my previous
discussions: MID x is superseded by MID y (x != y) in terms of the BEBO
retransmission process and congestion control for the destination
endpoint.  It is a general technique that would not be restricted to
observe: it might also apply, for example, if the upper layers cancelled
the transmission, but the lower layers had other messages to be
transmitted to the same endpoint.  The superseding message need not have
any relation to the superseded message in terms of purpose: all it does
is advance the time at which a message is transmitted to a given
endpoint, at (potentially) a cost to the number of retransmissions.
Whether this is a good thing or not is another question.

But the term "message supersedure" might also be applied to the first
approach: The payload and some (all?) option values, but not the Token,
Code, or MID of the message may be replaced in retransmissions.  This
too might be a general technique, (e.g. if Max-Age reduces to zero in
non-observe responses).

The overall point remains: observe introduces a (IMO bizarre)
manipulation of what most readers would consider immutable message
content.  CoAP lacks the domain concepts to interpret that manipulation,
the precise terminology to describe how it is to be implemented, and the
generalizations that would lift the concept from being defined only
under deeply specific circumstances.

Peter

---

From: Klaus Hartke <[email-masked]>
Date: Sun, 27 Oct 2013 19:19:21 +0200

>   timeout of the last transmission completes or a reply message is

Huge +1.

> (the absolute time) is unchanged.

+1

> value, must be changed prior to transport layer retransmission of a

More precisely, when a resource changes its state, the representation
of that state changes.

The purpose of -observe is to let a client interested in the resource
always have a representation of the latest resource state. (This is
not perfectly possible because of network latency and message loss,
but the idea is to have client and server constantly work towards this
goal, limited by congestion control.)

So -observe proposes that, after a state change, a server starts
working towards getting the new representation to the client and stops
working on getting the old representation to the client.

Indeed. The second approach is what -observe currently aims to describe:

> * [...] we cancel the previous confirmable message and

This is what I mean, including that the new notification message has
its own message ID.

>   confirmable message means.

I don't think that retaining the same message ID works. If the client
implements deduplication based on the message ID, then it would reject
the new representation as duplicate when it already received an old
representation with the same message ID but the acknowledgement to the
server was lost.

So the server has to replace the payload, the Observe option, the
Max-Age option, potentially the ETag option, the response code
(2.05/2.03/4.xx/5.xx), etc., and can retain only the token and the
Content-Format option.

I agree that this manipulation of a message in transmission (CoAP
message transmission) is quite bizarre. That's why I prefer to think
in terms of the other approach.

> endpoint, at (potentially) a cost to the number of retransmissions.

+1

Klaus

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 27 Oct 2013 18:25:02 +0100

> representation with the same message ID but the acknowledgement to the

Worse: If the server receives an ACK, it does not know whether that acknowledges the old or the new state.  To maintain eventual consistency, it has to continue notifying the new state.

Grüße, Carsten

---

From: "Peter A. Bigot" <[email-masked]>
Date: Sun, 27 Oct 2013 15:24:39 -0500

> Huge +1.

Thanks.

> More precisely, when a resource changes its state, the representation

I'm gonna nitpick here and say no, just because we're trying to be
really precise.

Requests and responses (not messages) carry resource representations,
but the representation belongs to the request or response, not to the
resource.  When the state (value) of a resource changes (internally or
by receiving a request that carries a representation) the representation
(encoding) *almost certainly, but not necessarily,* changes.  Consider a
content format that represents the resource by its SHA1 hash code.

Further, a representation that resides outside the resource (e.g., in a
pending notification) does not change.  If that were allowed we'd have
to figure out how to track down and replace those representations.  This
would be another way to model my first (wrong) alternative
interpretation of -observe, but is really messy.

The distinction makes no difference to the rest of your response, but it
is important to keep very clear that the resource state and its
representation are not the same thing or even in one-to-one
correspondence.

Therefore, to satisfy the expectations of -observe, what we say is when
the resource changes we SHOULD/MUST cancel all previous notifications
(if any), and MUST initiate the transmission of new notification for
each active observation transaction.

Further, the second notification MAY/MUST *supersede* (reference
definition) a cancelled notification.

(Slashes here separate design alternatives.)  (I do not think we should
try detect the really special case where the resource state changed but
the representation did not.)

As for the rest: With a little effort we could define message rejection
from the perspective of the sender of a confirmable message (can't do it
for non-confirmable message transmission for reasons I won't get into),
what cancellation of a confirmable message means, and how rejection
propagates to cancellation of higher-order entities like exchanges and
transactions.  Should also document the restrictions on when message
supersedure is appropriate (for observe it's a good technique; for other
situations it's not).  A couple more steps and we could define the
behavior of observe quite clearly in terms of more primitive concepts,
eliminating detailed steps and special cases.

Peter

---

From: "Rahman, Akbar" <[email-masked]>
Date: Sun, 27 Oct 2013 16:36:56 -0400

Hi Peter/Klaus,

Thanks for the good definitions.  I found them extremely useful.  One naïve question.  Will these definitions be affected if DTLS is running underneath CoAP?

Akbar

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Peter A. Bigot
Sent: Sunday, October 27, 2013 4:25 PM
To: Klaus Hartke
Cc: core
Subject: Re: [core] Message supersedure as a domain concept

Thanks.

>> Now we come to observe, which proposes that under certain 
>> circumstances the entire representation of a resource, along with the 
>> Observe option value, must be changed prior to transport layer 
>> retransmission of a confirmable message.
>

I'm gonna nitpick here and say no, just because we're trying to be really precise.

Requests and responses (not messages) carry resource representations, but the representation belongs to the request or response, not to the resource.  When the state (value) of a resource changes (internally or by receiving a request that carries a representation) the representation
(encoding) *almost certainly, but not necessarily,* changes.  Consider a content format that represents the resource by its SHA1 hash code.

Further, a representation that resides outside the resource (e.g., in a pending notification) does not change.  If that were allowed we'd have to figure out how to track down and replace those representations.  This would be another way to model my first (wrong) alternative interpretation of -observe, but is really messy.

The distinction makes no difference to the rest of your response, but it is important to keep very clear that the resource state and its representation are not the same thing or even in one-to-one correspondence.

Therefore, to satisfy the expectations of -observe, what we say is when the resource changes we SHOULD/MUST cancel all previous notifications (if any), and MUST initiate the transmission of new notification for each active observation transaction.

(Slashes here separate design alternatives.)  (I do not think we should try detect the really special case where the resource state changed but the representation did not.)

As for the rest: With a little effort we could define message rejection from the perspective of the sender of a confirmable message (can't do it for non-confirmable message transmission for reasons I won't get into), what cancellation of a confirmable message means, and how rejection propagates to cancellation of higher-order entities like exchanges and transactions.  Should also document the restrictions on when message supersedure is appropriate (for observe it's a good technique; for other situations it's not).  A couple more steps and we could define the behavior of observe quite clearly in terms of more primitive concepts, eliminating detailed steps and special cases.

Peter

_______________________________________________
core mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/core

---

From: "Peter A. Bigot" <[email-masked]>
Date: Sun, 27 Oct 2013 15:42:13 -0500

On 10/27/2013 03:36 PM, Rahman, Akbar wrote:
> Hi Peter/Klaus,
>
> Thanks for the good definitions.  I found them extremely useful.  One
> naïve question.  Will these definitions be affected if DTLS is
> running underneath CoAP?

I haven't looked at the DTLS interface for CoAP, but from my perspective 
they MUST NOT be affected.  If they are, they (or the DTLS abstraction 
for CoAP) need to be fixed.  I would expect DTLS to be a transport-layer 
wrapper; at most, it might introduce a new mechanism by which a message 
is rejected.

Again, though: haven't researched it, can't say for sure.

Peter

---

From: "Kovatsch Matthias" <[email-masked]>
Date: Sun, 27 Oct 2013 21:16:10 +0000

> > representation with the same message ID but the acknowledgement to

Just to clarify: The deduplication mechanism must send the same reply as for the first message. An endpoint cannot reject a message that it previously acknowledged and successfully forwarded to the application.

> Worse: If the server receives an ACK, it does not know whether that
> acknowledges the old or the new state.  To maintain eventual consistency, it
> has to continue notifying the new state.

Okay, then we need not only clear text on the MID (only the long discussion revealed what is actually intended), but figure out how to solve the Token lifetime (when is it in use by any party) issue. Honestly, I lost track about the current status here with all the excursions...

My notes:
- A Token is in use until the (final) matching response is received
- For Groupcomm this is hard to decide; practically, we need NON_LIFETIME here
- Observe even extends the scope of the Token towards the server and the Token is active until both client and server have consensus on a Observe cancellation
- With Observe the client even loses sovereignty over the Token, since it depends on the server to send a CON notification for cancellation
- Since a RST can get lost, the Token must be considered in use for EXCHANGE_LIFETIME after rejecting a CON notification

Ciao
Matthias

---

From: "Peter A. Bigot" <[email-masked]>
Date: Sun, 27 Oct 2013 19:07:21 -0500

> - Since a RST can get lost, the Token must be considered in use for EXCHANGE_LIFETIME after rejecting a CON notification

Let's approach token lifetime from a different direction.

Assume client C establishes observe relations with two resources R1 and
R2 hosted by server S, using tokens T1 and T2.  Then assume client C
resets, losing all knowledge of the state of its connections with S.  It
needs to re-establish the observe relations.  How does it do so without
responses from previous observations being mis-interpreted?

Consider that without some sort of constraint it might re-establish the
relationship with the tokens swapped so T2 is used for R1 and T1 for R2.
In that case, each time either R1 or R2 changes two notifications would
be sent, one for each token.  There is nothing inherent about the
subsequent exchanges that would allow the client to detect the problem.
Is the server obliged to diagnose this?

One solution would be to require that the client reserve unique tokens
for any observe relationship it might establish.  Is this reasonable?

Peter

---

From: Maciej Wasilak <[email-masked]>
Date: Mon, 28 Oct 2013 10:05:21 +0100

> for any observe relationship it might establish.  Is this reasonable?

One solution is to key entries in the list of observers on server by a
tuple (uri_path, client_endpoint) - as it is currently with blockwise
transfers. New request from the same client to the same resource would
overwrite the old one.

Maciek

---

From: Klaus Hartke <[email-masked]>
Date: Mon, 28 Oct 2013 12:57:55 +0200

> Is the server obliged to diagnose this?

Assume we have the following sequence of events:

1. S has (C,T1) in the list of observers of R1, and (C,T2) in the list
of observers of R2.
2. C resets, losing all knowledge of tokens previously used.
3. C sends requests to re-establish observations with the tokens
swapped so T2 is used for R1 and T1 for R2.
4. The state of R1 changes and the server sends a notification to C with T1.
5. C receives the notification and believes it is a notification for R2.
6. S receives C's requests and informs C with some kind of error
messages that T1 and T2 are still in use.
-or-
6. S receives C's requests and cancels the existing observations and
creates new observations.

It doesn't really matter what the server does in step 6, because the
mishap already occurred in step 5.

This is, by the way, not specific to -observe:

0. C makes a GET/POST/PUT/DELETE request with token T3.
1. S receives the request and returns an empty Acknowledgement.
2. C resets, losing all knowledge of tokens previously used.
3. C makes a new, unrelated request with the same token T3.
4. The processing of the request from step 0 completes and the server
sends a separate response to C with T3.
5. C receives the separate response and believes it is the response for step 3.
6. S receives C's request from step 3, and so on.

The question is, when does this actually happen?

If we use CoAP over DTLS or WebSockets, then all responses are
returned over the same connection as the request, and all tokens are
local to the connection. When a client resets, it creates a new
connection. So any token from a previous connection can be freely
reused.

If we use CoAP over UDP, then -coap recommends the client to use a
non-trivial, randomized token with at least 32 bits of randomness for
each new request. It's also a good idea to randomize the client port
number when a client resets. So, while not impossible, it's quite
unlikely that a client accidentally makes a request from the same port
with a token that is still in use.

Klaus

---

From: "Peter A. Bigot" <[email-masked]>
Date: Mon, 28 Oct 2013 06:42:49 -0500

> transfers. New request from the same client to the same resource would

Could work.  This inhibits a client from observing the same resource 
with distinct Content-Format options, which might be desirable.

Peter

---

From: "Peter A. Bigot" <[email-masked]>
Date: Mon, 28 Oct 2013 06:58:12 -0500

> connection. So any token from a previous connection can be freely

This is a good point, but CoAP doesn't require use of these techniques 
so all they do is provide a robust solution in a special case.  The 
protocol-level general case remains.

> with a token that is still in use.

Token randomization is discussed only in terms of security; if I don't 
care whether somebody sees the temperature and humidity in my 
greenhouse, I probably wouldn't bother with it, especially if I don't 
have a good source of randomness in the first couple seconds after my 
MCU powers up.

I don't think randomizing the client port number is explicitly 
recommended, and besides I'd probably use the same socket as both client 
and server so the source port will generally be 5683.

If the best we can do is "probably won't happen", that's fine.

Though then we don't get any help understanding what token lifetime 
should be.  My point in raising the question was that a client reset is 
one of the things that causes the token lifetime to end from the 
client's perspective while servers may still be using it.  It happens 
with and without observe, as you note, so it's a general issue; it's 
just worse with observe because it's ongoing, and observe is one place 
where it might be possible to have the client cancel it.

Peter

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 28 Oct 2013 13:42:25 +0100

On 28 Oct 2013, at 12:58, Peter A. Bigot <[email-masked]> wrote:

> Token randomization is discussed only in terms of security;

Indeed.  If the security objectives are met in some other way, using the same (e.g., empty) token until it is kept busy by an empty ACK (separate response) or an observation relationship is a quite viable strategy.

> I don't think randomizing the client port number is explicitly recommended, and besides I'd probably use the same socket as both client and server so the source port will generally be 5683.

I imagine many constrained implementations will do something simple like this.

(It is probably a good idea to combine token randomness with some client port randomness in powerful clients.  But we don’t have to go to the lengths DNS clients do these days.)

> Though then we don't get any help understanding what token lifetime should be.  

We need to write this up; my plan was to have some of that in draft-kovatsch-lwig-coap.
The discussion here seems to show that we probably have to add some requirements on the server to make the rules really useful.

Grüße, Carsten

---

From: "Peter A. Bigot" <[email-masked]>
Date: Tue, 29 Oct 2013 06:39:29 -0500

> This is what I mean, including that the new notification message has

OK, let's drill down.

At a high level what this does is circumvent the requirements of coap-18
section 4.7 which say that only NSTART outstanding interactions can be
active.  A confirmable message transmission is outstanding at the
message layer if an ACK is still expected.  (In this context we're
talking about observe transmitting responses so the message is never
outstanding at the transaction layer.)

That the sender no longer cares about the reply/response (because the
send is "cancelled") does not affect whether it should still expect an
ACK, because cancellation is not visible to the receiver.

The implication here is that if the sender cancels a confirmable
transmission, as long as the original message remains outstanding no new
messages may be sent until the original BEBO state expires at
MAX_TRANSMIT_WAIT after the first transport layer transmission.  (Assume
for now that NSTART=1, otherwise this gets messier.)

What message supersedure does is allow remaining BEBO-authorized
transmission to be donated to new messages, shortening this delay.

Under default transmission parameters, as many as five distinct messages
(with unique message IDs) may be transmitted when supersedure is
allowed.

Question: What happens if an ACK or RST is received within
MAX_TRANSMIT_WAIT seconds but is for a message that was cancelled?  Had
supersedure not been invoked, that message is no longer outstanding (at
the message layer), so a new message transmission could begin
immediately.

Note that -observe uses failure of the confirmable notification as the
cue to drop the observation relationship at the server.  Assume message
supersedure occurred, and the notification that was last transmitted was
never acknowledged but late arrival provides an ack for a previous
notification, within the required MAX_TRANSMIT_WAIT.  Is the server
entitled to drop the observation relationship in this case, given that
the client is clearly still interested?  Or does it have to track all
(up to 1+MAX_RETRANSMIT) message IDs that were transmitted to avert this
case?

Peter

---

From: Klaus Hartke <[email-masked]>
Date: Wed, 30 Oct 2013 08:23:42 +0200

Peter A. Bigot wrote:
> each active observation transaction. Further, the second notification
> MAY/MUST *supersede* (reference definition) a cancelled notification.

You can't really start a new notification transmission (CoAP message
transmission) while a previous notification transmission is still
active when NSTART=1.

So either you wait until no previous transmission is active, or you
cancel the active transmission and initiate the new transmission when
the retransmission timer fires with the unused BEBO right-to-transmits
from the cancelled transmission.

Klaus

---

From: Klaus Hartke <[email-masked]>
Date: Wed, 30 Oct 2013 08:28:19 +0200

Peter A. Bigot wrote:
> active.

Section 4.7 of draft-ietf-core-coap-18 says that

   *Clients* (including proxies) MUST
   strictly limit the number of simultaneous outstanding interactions
   that they maintain to a given server (including proxies) to NSTART.

It seems it's up to draft-ietf-core-observe to define congestion
control for servers.

So -observe-11 follows -coap-18 here and says that

   The server MUST limit the number of confirmable notifications for
   which an acknowledgement has not been received from a client yet to
   NSTART (1 by default).

I'm not sure if -observe needs to circumvent itself :-)

But it is indeed the intention that -observe-11 modifies the algorithm
specified in section 4.2 of coap-18 such that a server can start
working towards getting the representation of a new resource state to
a client sooner.

> the message layer), so a new message transmission could begin

If it's an ACK, then it just confirms that the client is interested in
further notifications. Sending a further notification is what the
server already did. So I'd say everything is fine if the server just
ignores the ACK.

To properly handle RSTs, a server in principle would need to remember
the message IDs of all notification it sends for 2*MAX_LATENCY after
the transport layer transmission. That may be a bit impractical
though...

> (up to 1+MAX_RETRANSMIT) message IDs that were transmitted to avert this

Since the server tries to get the representation of the latest
resource state to the client, and the ACK doesn't acknowledge the
latest notification, the server would retransmit the latest
notification when the retransmission timer fires. If there are no
retransmissions left, then the observation is dropped. The late
arrival of an ACK for a previous notification does not cut short the
retransmission timer or reset the retransmission counter.

Klaus

---

From: "Peter A. Bigot" <[email-masked]>
Date: Wed, 30 Oct 2013 06:10:51 -0500

> I'm not sure if -observe needs to circumvent itself :-)

Huh?

Oh, never mind.  Failure to communicate, not worth wasting more time.

> retransmission timer or reset the retransmission counter.

Right.  So here we have a case where the server would drop the 
observation because supersedure occurred, when it would not have done so 
had supersedure not occurred.  Net result is loss of information as a 
consequence of trying to game the system.

If that works for you, ok.

FWIW: Having defined precisely what cancellation would have to mean in 
the context of other CoAP requirements, my conclusion is that a clear 
and consistent definition of supersedure is difficult and results in 
undesirable behavior.  Which is what my intuition told me when this 
whole mess started.

Peter