Subject: [core] WGLC draft-ietf-core-coap-09 Reuse of MID

From: Cullen Jennings <[email-masked]>
Date: Tue, 17 Apr 2012 22:57:12 -0600

I don't understand when a MID can be reused. I'm primarily concerned about use of default MID. 

Say I am on a network with 5 seconds latency but no packets are lost. 

A sends Req1 to B. Due to latency, A retransmits Req1 to B. B sends response 1 to A which A receives. No A decided to immediately send Req2 to B. In the meantime, B had received the retransmission of Req1 and resent the response. The response arrives at A after A has send the second request but because the MID are the same, A mistakenly thinks that the response is a response to Request2 when really it was a response to Req1.  

It seems to me that that once a MID is used, it can't be re-used for some significant amount of time.

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Wed, 18 Apr 2012 09:11:36 +0200

> It seems to me that that once a MID is used, it can't be re-used for some significant amount of time.

Yes, this is true in transmission and in reception, and it cannot be
re-used during the whole retransmission window (better said the
*potential* retransmission window).

See also the discussion related to this
http://www.ietf.org/mail-archive/web/core/current/msg02875.html

Best,
Angelo

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 18 Apr 2012 09:20:34 +0200

On Apr 18, 2012, at 06:57, Cullen Jennings wrote:

> 
> 
> I don't understand when a MID can be reused.

A MID is to be used again for retransmitting the same message.

After completing (re-)transmitting a message, the MID should not be used for a while.
In my implementation, I don't *re*use a MID (i.e., for a different message) 256 seconds after having used it.

> I'm primarily concerned about use of default MID. 

I don't think anyone implements a default MID. Do you mean a default token?

We had a discussion around the Paris plug test about the way MID and Token together make sure that there is no confusion.
Angelo Castellani has written up some of that in draft-castellani-lwig-coap-separate-responses-00.txt -- the title is a bit misleading, this draft collects a number of examples for packet exchanges.  I hope we can develop this into an informational RFC that explains the finer points of why this works.

Note that the complexity of *implementation* is quite limited here; the discussion in the draft is extensive as it shows a large number of cases.

See also ticket #201.

> A sends Req1 to B. Due to latency, A retransmits Req1 to B.

Both use, say, MID 47, and, for minimal packet size, Token 0 (default token),

> B sends response 1 to A which A receives.

If this is piggybacked in an ACK, it will have MID 47, too.

> No A decided to immediately send Req2 to B.

This would *have* to have a new MID, say, 48.

> In the meantime, B had received the retransmission of Req1 and resent the response. The response arrives at A after A has send the second request but because the MID are the same,

Even if the second request carries the same token 0 (which is allowed as the token of the first request has been "put back" by the first response), it still has to have a different MID if it is so close.

> A mistakenly thinks that the response is a response to Request2 when really it was a response to Req1.  

The important observation here is that the protection against duplicate packets (which are quite likely to occur because of retransmission and lost/delayed ACKs) comes from the MID.

> It seems to me that that once a MID is used, it can't be re-used for some significant amount of time. 

I don't know if 256 s is "significant", but yes, the "2 MSL" argument applies here.

There is no such need for timeout-based blocking for the reuse of token values.

Grüße, Carsten

---

From: Cullen Jennings <[email-masked]>
Date: Wed, 18 Apr 2012 09:15:23 -0600

Ok, sounds like we need the spec to say MUST not reuse for "awhile" and define "awhile" in seconds. I really hope it can be less than 256. 

On Apr 18, 2012, at 1:20 AM, Carsten Bormann wrote:

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

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Wed, 18 Apr 2012 17:21:46 +0200

> Ok, sounds like we need the spec to say MUST not reuse for "awhile" and define "awhile" in seconds. I really hope it can be less than 256.

The problem itself is not related to the client reusing it, which
since it is paired to destination host, destination port and token, it
is hard that a collision happens.

The real problem is on the recipient side, that has to track the
received MIDs paired with source host, source port and token, to
really enable deduplication... This is hard and leads to heavy RAM
usage, and may hardly limit the ability to receive messages.

See the related discussion happening on the thread pointed in the previous mail.

Best,
Angelo

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 18 Apr 2012 18:41:44 +0200

Well, both client and server need to process the MID.

Let "awhile1" be the time constant that is equivalent to TCP's "2 MSL", i.e. the sum of the maximum latency we expect on the way forward and the maximum latency.
"awhile0" is just the difference between minimum and maximum forward latency ("MSL" for all intents and purposes).
"retransmission window" is awhile1 + the maximum time between the first and the last transmission in a CON retransmission sequence.  (There is also a related number that can be built from awhile0.)

It is relatively easy for the emitter of a CON/NON to choose non-conflicting MIDs, unless it sends at a rate of more than 65536/"retransmission window" messages from/to the same endpoint, or it forgets its state and comes up again before retransmission window expires: just keep a number (per endpoint pair, or if 65536/retrwin is enough for this, even for the entire client), and increment it per message use.

The duplicate detection at the receiver is more work.  One strategy for this is discussed in 3.4.2.3 in draft-bormann-lwig-guidance-01.txt.  As Esko notes there, this is easier if the emitter uses the "sequential" (i.e., one counter per peer end-point) strategy.

If we want to standardize MSL values, we need to consider sleeping nodes.
Where a node is aware (e.g., on L2) of the sleep schedule of the next-hop node, it may buffer a packet for quite some time.  There is *no* reasonable upper bound for this.  However, traditional IP-based protocols become less useful once this storage time exceeds a couple of minutes.  Hence my shot in the dark of "256 s" for the retransmission window.  But we don't have any *assurance* that all packets will have left the network within that time.

Grüße, Carsten

PS.: My personal record for an RTT actually measured in an in-use, production IPv4 network with real-world users surfing the Web and sending email is 385 s.

---

From: Cullen Jennings <[email-masked]>
Date: Wed, 18 Apr 2012 11:08:32 -0600

> PS.: My personal record for an RTT actually measured in an in-use, production IPv4 network with real-world users surfing the Web and sending email is 385 s.

This sounds fascinating. Can you tell me more.

---

From: "Dijk, Esko" <[email-masked]>
Date: Thu, 19 Apr 2012 09:56:48 +0000

The RAM reduction strategy of 3.4.2.3 in draft-bormann-lwig-guidance-01 is more successful, the more CoAP end-points use sequential MIDs.
Hence my previous proposals to mention sequential MIDs and potential benefits in core-coap
(see thread http://www.ietf.org/mail-archive/web/core/current/msg02517.html).

A SHOULD requirement for sequential MIDs was found too strong by the WG, a MAY requirement is very weak but at least mentions the point.
The discussion on the MAY is in my view not yet concluded, so if not pursued on the ML could we add this to the list for the WG interim meeting?

Esko

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Carsten Bormann
Sent: Wednesday 18 April 2012 18:42
To: Angelo P. Castellani
Cc: Cullen Jennings; core WG
Subject: Re: [core] WGLC draft-ietf-core-coap-09 Reuse of MID

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.

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 19 Apr 2012 11:58:18 +0200

> could we add this to the list for the WG interim meeting?

(this = implementation note to encourage sequential MIDs)
I will make a ticket.

I expect that Klaus and I will make on the order of 200 tickets in the next 48 hours.
We should work on closing as many as possible on the list; otherwise this will be a very long phone call :-)

Grüße, Carsten

---

From: Cullen Jennings <[email-masked]>
Date: Thu, 19 Apr 2012 08:11:26 -0600

> Where a node is aware (e.g., on L2) of the sleep schedule of the next-hop node, it may buffer a packet for quite some time.  There is *no* reasonable upper bound for this.  However, traditional IP-…

OK, but what I am reading here is it's broken if you don't wait long enough. And there is no upper bound on how long, long enough is. The logical conclusion is this sounds broken and we are going to need to constrain something to be able to solve this. 

My natural tendency is the thing to break is the idea that nodes will buffer packets for long periods of time waiting to deliver them to a sleeping node. I can see that working in something like an ATM network but I think that is likely to break too many assumptions of an IP network.

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 19 Apr 2012 16:21:02 +0200

> OK, but what I am reading here is it's broken if you don't wait long enough. And there is no upper bound on how long, long enough is. The logical conclusion is this sounds broken and we are going t…

Yes.  All I was trying to say was that "awhile1 = 20 s" may be an order of magnitude too low.

> My natural tendency is the thing to break is the idea that nodes will buffer packets for long periods of time waiting to deliver them to a sleeping node. I can see that working in something like an…

Right.  Almost nothing we do over IP today continues to work when you suddenly get these long-term sleeper IP packets.  (TTL used to be a "time to live" and was 8-bit... This thinking is heavily ingrained in our protocols.)  So nodes that buffer for more than ~ 1e2 seconds may need to participate in the application protocols instead.  Good that we have the proxy model in CoRE to make this possible...

But I stick to the order of magnitude in my "256 s" strawman.

Grüße, Carsten

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Fri, 20 Apr 2012 09:45:45 +0200

On Thu, Apr 19, 2012 at 16:21, Carsten Bormann <[email-masked]> wrote:
> [...]

256 seconds are a pain for class-I devices... I cite a still
unanswered message that you find in a related thread
(http://www.ietf.org/mail-archive/web/core/current/msg03082.html)

On Wed, Apr 18, 2012 at 09:49, Angelo P. Castellani
<[email-masked]> wrote:
> Can we define how much smaller can be the timeout for NONs?
>
> On class-I devices, I will have only a very limited set of slots for
> deduplication, depending upon available resources, and at some point I
> cannot receive any more messages since the deduplication slots have
> exhausted... So having a smaller timeout is a real benefit for me.

If this timeout is 256 seconds, then the fill this deduplication slots
in this devices is really easy!

> When deduplication cannot be assured anymore, since the deduplication
> slots in my buffer are all busy, new messages should be ignored?

Is it right?

> I think that this is probably the best solution. Moreover if the
> message is a CON I will have another opportunity to receive it on
> retransmission. I will prefer avoiding sending a  RST in this
> situation.
>
> But let's imagine that I have some observation in place, and the
> servers are sending to me NON notifications at an aggregate rate
> higher than the maximum one that I can receive.
>
> Suppose that my bottleneck is the deduplication buffer, which has N
> slots. The maximum rate R at which I can receive messages, if the
> timeout is T will be:
> R = N / T

If this timeout is 256, to be able to receive one message every second
I need 256 slots which are really a lot and hardly available on class-I devices.

> Probably in this case sending some RST will be benificial.

Even using the aggregation technique (where possible) proposed by you
and Esko, the problem itself is not solved for class-I devices.
Typically servers and clients talk to different endpoints, and a
(small?) part of the slots may be aggregated using that technique.

In my opinion we need a window smaller than 256 seconds.

A possible solution would be to use an adaptive value, proportional to
the measured RTT. However there is no easy way to measure RTT,
especially for a CoAP server.

Best,
Angelo