Subject: [core] Message ID & Token: high overhead?

From: "Angelo P. Castellani" <[email-masked]>
Date: Wed, 26 Jan 2011 12:48:57 +0100

For convenience of reading, I cut-and-paste some definitions from the
CoAP-04 release:

###################

   Message ID:  16-bit unsigned integer.  Used for the detection of
      message duplication, and to match messages of type
      Acknowledgement/Reset and messages of type Confirmable.  See
      Section 4 for Message ID generation rules and how messages are
      matched.

###################

5.10.1.  Token

   The Token Option is used to match a response with a request.  Every
   request has a client-generated token which the server MUST echo in
   any response.

   A token is intended for use as a client-local identifier for
   differentiating between concurrent requests.  A client SHOULD
   generate tokens in a way that tokens currently in use are unique.  An
   end-point receiving a token MUST treat it as opaque and make no
   assumptions about its format.

   A default value of a zero-length token is assumed in the absence of
   the option.

   This option is "critical".  It MUST NOT occur more than once.

###################

By reading the Message ID definition, it should be useful for two main reasons:
- avoid duplication
- match "transaction"-level request/responses (CON/ACKs)

Following the Section 5.10.1 definition, Token is mainly required to
match concurrent application-level sessions.

Please correct me if this assumptions are not valid. I know that Token
is required for other "parts" of the specification (e.g. -observe &
-block), but right now I am considering only the CoAP-04 release.

Message ID overhead is 2 bytes, and Token overhead ranges from 2 bytes
to 9 bytes.

In my opinion and if my assumptions are right, the overhead related to
concurrency matching is quite high.

A sample analysis is briefly outlined in the following part of the
message, by evaluating the example present in Section 2.2.

The example is related to the immediate response sample, however the
same considerations can be applied to the deferred response example.

      |   CON [0xbc90]   |             |   CON [0xbc91]   |
      | GET /temperature |             | GET /temperature |
      |   (Token 0x71)   |             |   (Token 0x72)   |
      +----------------->|             +----------------->|

Base message: 4 bytes (2 bytes of message ID)
Token: 2 bytes
URI-Path: 12 bytes

Overhead analysis:
- URI 66%
- concurrency 22%
- base/other 11%

      |   ACK [0xbc90]   |             |   ACK [0xbc91]   |
      |     2.00 OK      |             |  4.04 Not Found  |
      |   (Token 0x71)   |             |   (Token 0x72)   |
      |     "22.5 C"     |             |   "Not found"    |
      |<-----------------+             |<-----------------+

Base message: 4 bytes (2 bytes of message ID)
Token: 2 bytes

Content: 6 bytes

Overhead analysis:
- content 50%
- concurrency 33%
- base/other 16%

Obviously vendors/implementors can enhance the URI representation and
content representation, in order to reduce the overhead.

Example:
# URI can be "/t" using 2 bytes
# Content can be represented using various smaller formats (2 bytes?)

Using this "optimizations" the ratios will change respectively:
- concurrency 50%
- base/other 25%
- URI 25%

- concurrency 50%
- base/other 25%
- content 25%

Following this reasoning seems that concurrency has a great impact in
the current CoAP overhead.

However in my opinion duplicate message detection can be realized
using a cross-layer optimization, by exploiting the checksum field of
UDP (a similar cross-layer optimization has been used to drop the need
for Content-Length).

If this duplicate detection technique is suitable, then in my opinion
and with some further reasoning about concurrency detection, the
"Message ID" field can be sufficient to operate the matching.

Moreover further cross-layer optimizations are available to soften the
concurrency matching requirement: source IP address and source UDP
port are very useful to this end.

However Token option is used by other WG specifications, probably a
deeper investigation of that proposals can help.

In Appendix A of the recently released document
"draft-castellani-core-http-coap-mapping-00", some alternatives are
discussed that remove or readdress the need for Token option.

Best,
Angelo

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 26 Jan 2011 13:52:23 +0100

> Message ID overhead is 2 bytes, and Token overhead ranges from 2 bytes

I'm in a Dagstuhl seminar right now, where we happened to talk about "the fallacy of overhead" a couple of hours ago...

But really, as I explained, as the token has a default value, the token overhead is zero, unless and until you do really need it.
Unfortunately, I don't have time to explain this in more detail right now, maybe later in the call...

Gruesse, Carsten

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Wed, 26 Jan 2011 14:57:45 +0100

Carsten
thanks again for the feedback.

> But really, as I explained, as the token has a default value, the token overhead is zero, unless and until you do really need it.

As far as I can understand from the current CoAP-04 specification,
Token has a great importance in the request/response matching process.

See especially Section 5.3, and other text about it in Sections 2.2
and 5.2; moreover it is present in a lot of examples (every?).

For convenience of who has less time to read the email, my previous
message can synthetized as follows:

Conclusions:
- for REQ/RES matching purposes can be investigated the use of
"Message ID" field *only*
- the fact that Token is used also in other documents can suggests a
deeper investigation of that methods too

2 useful considerations:
- duplicate message detection function can be operated using UDP checksum field
- REQ/RES matching can be done using  "Message ID" paired with the
source IP address and source UDP port of the datagram

However please look at the whole previous message if you have doubts about this.

Best,
Angelo

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 26 Jan 2011 15:13:25 +0100

> UDP (a similar cross-layer optimization has been used to drop the need

Implementations on larger hosts typically don't have access to the checksum and would have to recompute them.
Also, I don't know how to avoid collisions here.

I don't think saving the two bytes of message ID is worth any additional complexity.

(The IP address and port usually are available, even though it is not always easy to get at both sides.  
See CoAP-04 security considerations, last para of 10.3.3.)

Gruesse, Carsten

---

From: <[email-masked]>
Date: Wed, 26 Jan 2011 14:32:15 +0000

> > using a cross-layer optimization, by exploiting the 
> > checksum field of UDP 

That won't work with implementations, as UDP-Lite showed; it wound
up getting its own protocol number because implementations relied
on the UDP checksum field.

>(a similar cross-layer optimization has been used to 
> drop the need for Content-Length).

Unlikely... details, please.

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 26 Jan 2011 15:35:45 +0100

> Unlikely... details, please.

I think he is saying we use the length of the datagram.
But that is information that is exposed on the UDP service interface (as are at least the source addresses); the checksum isn't.

Gruesse, Carsten

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Wed, 26 Jan 2011 15:43:44 +0100

> I think he is saying we use the length of the datagram.

Exactly.

> But that is information that is exposed on the UDP service interface (as are at least the source addresses); the checksum isn't.

Sure the checksum isn't available always, but is always possible
recompute it (as said in your previous message).

Implementors can choose whether they prefer/can read that information
(usually is possible on constrained devices) or recompute it (easier
on larger hosts, as you said).

In my opinion seems useful to explore this idea and its consequences..

Best,
Angelo