Subject: Re: [Roll] Semantics of DAO ACK

From: Csaba Kiraly <[email-masked]>
Date: Thu, 1 Oct 2015 21:03:34 +0200

On 30/09/15 17:55, Joakim Eriksson wrote:
>> On 30 Sep 2015, at 06:44, Csaba Kiraly <[email-masked]> wrote:
>>
>> Hello Joakim,
>>
>> I have also worked on the Contiki DAO-ACK code, enabling ACKs, implementing fixes to the DAOSequence handling, and looking into multiple targets.
> Nice, I have a PR on Contiki now with what we have been doing to get Contiki RPL more scalable (but still only single targets / paths).
>
>> What Cenk is saying sounds a reasonable hack, but the standard itself is in my opinion a bit underspecified for the semantics of DAO-ACK messages in several ways.
> Yes, it is underspecified. There is need for clarifications and more details on the DAO / DAO ACK!
>
>> My preferred solution for ACKing DAO messages with multiple targets would be to have support for the same semantics that you would have had with one DAO message per Target, i.e., I would prefer an option field that gives an individual status for each Target.
> Yes, but that would require more memory in the sending node to keep track of things or full specification of the target in the response.
> I guess it might be solved by allowing multiple DAO ACKs for the same DAO and to have the Target options included in the DAO ACK.
This is a compromise to consider for sure. If you look at my 
implementation, you can see that I use the routing table entry to match 
the DAO ACK, and I keep only DAOSequence (SEQ) as extra state. I'm not 
sure it would work in all cases, but it did work for the case I 
considered. I'm keeping only the SEQ, and I think this is a must if you 
have no aggregation, and you want to match in case you forward multiple 
DAOs before getting the ACK or timing out on it. In fact, simply 
enabling ACKs in the original code was messing up the match between DAOs 
and their ACKs because it wasn't even keeping track of the DAO sequence 
numbers.

If you do aggregate ACKs, or you have more complex Target+Transit 
scenarios, the game changes, and I don't know what would be the balance 
between state you have to keep anyway and state you keep just to be able 
to interpret a later ACK correctly. I think it is implementation 
specific, so my suggestion would be a flag to indicate whether you 
request full ACK (bumping back all T+T info for rejected entries in the 
DAO) or a much smaller partial ACK with SEQ and similar IDs only. This 
flag (lets call it F for now), could go right next to K. As the DAO 
propagates, each node could set F based on whether it is able to store 
and/or reproduce info (F not set) or chose to remain stateless (set F ). 
This would exclude aggregation in the DAO-ACK sent down, but still allow 
for aggregation in the DAO sent up.

>
>> To give another example of subtle problems with DAO-ACK, it was not clear to me whether I want my implementation to ACK when the Target is added to the routing table, or only when this node itself receives an ACK for the same Target from its parent. Both makes sense, with the former giving a quick one-hop ACK, while the latter works as an end-to-end ACK, ensuring that the path is actually built. Both look conformant to the standard, but I suppose the original author was thinking of the former, and I can easily see interoperability problems arising between two implementations using different semantics.
>>
> We did go for the end-to-end ACK to achieve better scalability. There is to me no point having a route to the parent if it is not possible to
> get it all the way to root. But I totally agree - this is not obvious from the RPL RFC either.
Do you mean end-to-end ACK as in non-storing, or end-to-end ACK in the 
sense that it is still addressed to the next hop but you delay ACK till 
you know your parent (and all its parents) ACKed?

>
> Do you have your Contiki code somewhere in the open-source?
I did some cleanup and pushed the clean part of the code to github: 
https://github.com/cskiraly/contiki/tree/DAO-NACK
It is not yet rebased to the latest master, but it should apply. I 
suppose describing it would be too off-topic for the list.
There is also the more experimental part of the code in a PR, if interested.

Best regards,
Csaba
>
> Best regards,
> — Joakim
>
>> Best regards,
>> Csaba
>>
>> On 29/09/15 23:08, Cenk Gündogan wrote:
>>> Hello Joakim,
>>>
>>> This is an interesting question and I also couldn't find any answers in RFC 6550.
>>> However, my thoughts on this are as follows:
>>> Since a sub-set of the announced RPL targets could have been accepted before filling up
>>> the routing table (e.g.), I would choose a status code between 1 and 127.
>>> I would expect a node to choose another parent if a more aggressive status code is received ([128-255]).
>>> But a full routing table can have free space again until the next or any subsequent DAO arrives ..
>>> therefore I prefer a "mild rejection" with a status code of [1-127].
>>>
>>> To give some feedback to the originator of the DAO, it might be sensible to copy the
>>> rejected RPL Target options from the affected DAO to the DAO-ACK, so that the originator is fully
>>> aware of which Target prefixes got rejected (and which ones got accepted, implicitly).
>>> I would choose this method, because it doesn't require the originator of the DAO to save any extra state
>>> about the DAO and its contents.
>>>
>>> Nonetheless, everything I wrote is nonconform and I am also interested in the RPL experts' opinions
>>> and solutions.
>>>
>>> Best,
>>> Cenk
>>>
>>> On 29.09.2015 21:44, Joakim Eriksson wrote:
>>>> Hello All,
>>>>
>>>> I have spend quite some time to get a more stable implementation of DAO handling
>>>> for Contiki RPL and I am currently looking into DAO aggregation. But I realised that
>>>> it is for me not 100% clear what a node that receives a DAO with several prefixes to
>>>> be registered but can only accept a sub-set of them. Should it be a DAO_NACK in
>>>> this case or is there any other way to handle that case?
>>>>
>>>> If each would have been sent separately it is obvious that the receiving node can
>>>> do a NACK when the routing table is full and therefore it is possible to get fine-grained
>>>> answers. But with aggregation of DAOs this is not the case.
>>>>
>>>> Any ideas?
>>>>
>>>> Best regards,
>>>> — Joakim Eriksson, SICS
>>>> _______________________________________________
>>>> Roll mailing list
>>>> [email-masked]
>>>> https://www.ietf.org/mailman/listinfo/roll
>>> _______________________________________________
>>> Roll mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/roll
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Csaba Kiraly <[email-masked]>
Date: Thu, 1 Oct 2015 22:03:19 +0200

On 30/09/15 18:06, Joakim Eriksson wrote:
>> On 30 Sep 2015, at 09:58, Pascal Thubert (pthubert) <[email-masked]> wrote:
>>
>> Hello all:
>>
>> The DAO ACK status really is a summary that indicates that there was a problem or not, so if there is none, no need to dig further. With this, the only thing the child can do is globally pick another parent, and, depending on the range in the status, never come back.
>>
>> But the digging further, I agree, is not specified. If the groups wants it, we'll have to design additional stuff and draft it.
>>
> Yes - lets try to get this designed and detailed so that we can get interoperability between implementations!
> I would be happy to provide what we have been doing to get our implementation working!
>
>> * We could use the status as an enumeration the way people probably expect it. But you'll note that we did not create a registry for it.
> Not yet - I guess creating a registry might be fairly easy?
>
>> * Which hints you that we could also use it as a metric. A scalar degree of unwillingness to serve as a parent, that accounts for stuff like memory, available time slots in a chunk (for 6TiSCH) and/or battery depletion of the node. The status would translate in such things as serving as alternate but not as preferred parent.
> Not sure that degree of unwillingness can be specified in a clear way so that everybody will interpret it the same way. But
> sure - it is an option. I have done a “quick hack” and defined 255 as “Root is out of routes”. Because if you get that type of
> response - there is no immediate need to look for another parent and another path - it will not work anyway… (that is if the
>   node is desired to get a path all the way to/from root).
We did some tries with the memory aspect, and it is not bad, but not too 
good either. The information is simply not coming in at the right moment 
for a good decision logic. As Joakim said, squeezing it into one byte 
could also be too tight, and interoperability could be hindered. Would 
it be an absolute value with equations in the standard? If not, how 
would I confront the values received from two different implementations? 
How would I know that they are different and not comparable, in the 
first place?

I think it is better to keep the status as an enumeration, but also 
keeping the high level semantics, like now, so that implementations that 
do not know the enum have some default behavior. BTW, 127 is specified 
both for partial and for outright reject in RFC6550. For the enum 
values, we differentiate 2 cases now, and we have different decision 
logic for them.

I think it is a good idea to send the metrics you have described, but a 
DAO option or some DIO option is a better match.

>> For more selective stuff, we would have to indicate the problem in the dao-ack per route advertisement that is a problem. This is a step that we did not take with RFC 6550, people advising that the draft was workable and thick enough without it.
>>
> Yes, and we were tired of writing more I guess - and eager to implement ;-)
>
>> The path that is really accepted in storing mode is self as a transit for a given target. Transit can be aggregated for multiple targets. And there can be multiple transits for a target. The DAO Ack could include the pairs (transit/target) that are trouble  and indicate for each what the trouble is. It could in theory aggregate what's aggregatable, but the way the info in the dao ack is aggregated may have to differ from what was placed in the DAO.
> Yes, the thing with todays RFC is that there is not yet any defined options for the DAO ACK - but that is of course easy to add. One other option
> would be to add a flag into the DAO that says “all-or-nothing”. If it is set all routes or no-routes should be installed. It is a bit complex possibly but
> it would be very clear when the DAO sending node gets the ack what happened. < 128 means all routes are installed. >=128 means none was
> installed.
I think all-or-nothing flag is a good idea, and relatively easy to 
implement.

>> The path control delegates a right to propagate and eventually fan out the advertisement. If the T+T pair is placed in the dao ack, the path control could be used to refuse that right to propagate, so the child would be free to offer that particular pair to an alternate parent. We still have bits in the transit that could indicate stuff if we need it as well.
> Yes, but I my case I am doing the simple case of just registering with one single parent / one single DAO path per target.
>
>
> My current “plan” is to avoid aggregation when doing the regular DAO but possibly aggregate the no-path DAO since that one
> can not possibly cause out-of-memory or other problems (or?).
>
This reminds me that the status code is not yet defined for No-path, 
right? It can be interpreted, but the text for 1-127 and 128-255 doesn't 
really apply. I'm not sure asking for an ACK on a no-path would makes 
sense, but the option is in the standard, and behavior is unspecified.

Best regards,
Csaba

> Best regards,
> — Joakim
>
>> Thoughts?
>>
>> Pascal
>>
>>> -----Original Message-----
>>> From: Roll [mailto:[email-masked]] On Behalf Of Cenk Gündogan
>>> Sent: mardi 29 septembre 2015 23:08
>>> To: [email-masked]
>>> Subject: Re: [Roll] Semantics of DAO ACK
>>>
>>> Hello Joakim,
>>>
>>> Since a sub-set of the announced RPL targets could have been accepted
>>> before filling up the routing table (e.g.), I would choose a status code
>>> between 1 and 127.
>>> To give some feedback to the originator of the DAO, it might be sensible to
>>> copy the rejected RPL Target options from the affected DAO to the DAO-
>>> ACK, so that the originator is fully aware of which Target prefixes got
>>> rejected (and which ones got accepted, implicitly).
>>> I would choose this method, because it doesn't require the originator of the
>>> DAO to save any extra state about the DAO and its contents.
>>>
>>> Nonetheless, everything I wrote is nonconform and I am also interested in
>>> the RPL experts' opinions and solutions.
>>>
>>> Best,
>>> Cenk
>>>
>>>> I have spend quite some time to get a more stable implementation of
>>>> DAO handling for Contiki RPL and I am currently looking into DAO
>>>> aggregation. But I realised that it is for me not 100% clear what a
>>>> node that receives a DAO with several prefixes to be registered but
>>>> can only accept a sub-set of them. Should it be a DAO_NACK in this case
>>> or is there any other way to handle that case?
>>>> If each would have been sent separately it is obvious that the
>>>> receiving node can do a NACK when the routing table is full and
>>>> therefore it is possible to get fine-grained answers. But with aggregation
>>> of DAOs this is not the case.
>>>> Any ideas?
>>>>
>>>> Best regards,
>>>> — Joakim Eriksson, SICS

---

From: Joakim Eriksson <[email-masked]>
Date: Thu, 1 Oct 2015 22:11:24 +0200

> On 01 Oct 2015, at 21:03, Csaba Kiraly <[email-masked]> wrote:
> 
> 
> 
> This is a compromise to consider for sure. If you look at my implementation, you can see that I use the routing table entry to match the DAO ACK, and I keep only DAOSequence (SEQ) as extra state. I'm not sure it would work in all cases, but it did work for the case I considered. I'm keeping only the SEQ, and I think this is a must if you have no aggregation, and you want to match in case you forward multiple DAOs before getting the ACK or timing out on it. In fact, simply enabling ACKs in the original code was messing up the match between DAOs and their ACKs because it wasn't even keeping track of the DAO sequence numbers.
> 
> If you do aggregate ACKs, or you have more complex Target+Transit scenarios, the game changes, and I don't know what would be the balance between state you have to keep anyway and state you keep just to be able to interpret a later ACK correctly. I think it is implementation specific, so my suggestion would be a flag to indicate whether you request full ACK (bumping back all T+T info for rejected entries in the DAO) or a much smaller partial ACK with SEQ and similar IDs only. This flag (lets call it F for now), could go right next to K. As the DAO propagates, each node could set F based on whether it is able to store and/or reproduce info (F not set) or chose to remain stateless (set F ). This would exclude aggregation in the DAO-ACK sent down, but still allow for aggregation in the DAO sent up.
> 
>> 
> Do you mean end-to-end ACK as in non-storing, or end-to-end ACK in the sense that it is still addressed to the next hop but you delay ACK till you know your parent (and all its parents) ACKed?
> 

I mean end-to-end as in waiting for all the parents to ACK so that before ACKing it is known that the route is properly installed
where it needs to.

> I did some cleanup and pushed the clean part of the code to github: https://github.com/cskiraly/contiki/tree/DAO-NACK
> It is not yet rebased to the latest master, but it should apply. I suppose describing it would be too off-topic for the list.

Ok - I’ll take a look!

BTW: We have done a few deployments using our implementation using Yanzi networks products - take a look at this
video where 1000 nodes is deployed with Contiki RPL + our fixes and 20 neighbors and routes per node. If without our
fixes it would not work since Contiki RPL did not allow scaling beyond number of neighbors and routes / node that well 
before these fixes.

http://www.yanzi.se/video.jsp?id=7

Best regards,
— Joakim Eriksson

---

From: Joakim Eriksson <[email-masked]>
Date: Thu, 1 Oct 2015 22:27:00 +0200

> On 01 Oct 2015, at 22:03, Csaba Kiraly <[email-masked]> wrote:
> We did some tries with the memory aspect, and it is not bad, but not too good either. The information is simply not coming in at the right moment for a good decision logic. As Joakim said, squeezing it into one byte could also be too tight, and interoperability could be hindered. Would it be an absolute value with equations in the standard? If not, how would I confront the values received from two different implementations? How would I know that they are different and not comparable, in the first place?
> 
> I think it is better to keep the status as an enumeration, but also keeping the high level semantics, like now, so that implementations that do not know the enum have some default behavior. BTW, 127 is specified both for partial and for outright reject in RFC6550. For the enum values, we differentiate 2 cases now, and we have different decision logic for them.
> 
> I think it is a good idea to send the metrics you have described, but a DAO option or some DIO option is a better match.
> 
> I think all-or-nothing flag is a good idea, and relatively easy to implement.
> 
> This reminds me that the status code is not yet defined for No-path, right? It can be interpreted, but the text for 1-127 and 128-255 doesn't really apply. I'm not sure asking for an ACK on a no-path would makes sense, but the option is in the standard, and behavior is unspecified.

I think we do request the ACK on no-path but do not retransmit. I guess the only interpretation is “Yes the no-path was received” so I agree - only the unconditional accept seems like a valid answer. It is also forwarded but no wait for the “end-to-end” no-path before sending the ACK. Retransmitting
no-path might make sense if the packet got lost - just to ensure that the route is fully removed and no “memory leakage” is caused (but if feels that
is not going to happen that often).

Best regards,
— Joakim Eriksson

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 2 Oct 2015 13:04:54 +0000

Hello Joakim:

What I read here boils down to a limited diffusion algorithm. We tried to avoid that in RPL because any movement within the convergence would cause a deadlock. IOW if every node waits for (all of) the parents to ack, then this recursively takes you to the root, and if any node in the chain moves or dies, the diffusion will not be complete. 

Cheers,

Pascal

> From: Roll [mailto:[email-masked]] On Behalf Of Joakim Eriksson
> Sent: jeudi 1 octobre 2015 22:11
> To: Routing Over Low power and Lossy networks <[email-masked]>
> >>> I have also worked on the Contiki DAO-ACK code, enabling ACKs,
> implementing fixes to the DAOSequence handling, and looking into multiple
> targets.
> >> Nice, I have a PR on Contiki now with what we have been doing to get
> Contiki RPL more scalable (but still only single targets / paths).
> >>
> >>> What Cenk is saying sounds a reasonable hack, but the standard itself
> is in my opinion a bit underspecified for the semantics of DAO-ACK
> messages in several ways.
> >>> My preferred solution for ACKing DAO messages with multiple targets
> would be to have support for the same semantics that you would have had
> with one DAO message per Target, i.e., I would prefer an option field that
> gives an individual status for each Target.
> >> Yes, but that would require more memory in the sending node to keep
> track of things or full specification of the target in the response.
> >> I guess it might be solved by allowing multiple DAO ACKs for the same
> DAO and to have the Target options included in the DAO ACK.
> implementation, you can see that I use the routing table entry to match the
> DAO ACK, and I keep only DAOSequence (SEQ) as extra state. I'm not sure it
> would work in all cases, but it did work for the case I considered. I'm
> keeping only the SEQ, and I think this is a must if you have no aggregation,
> and you want to match in case you forward multiple DAOs before getting
> the ACK or timing out on it. In fact, simply enabling ACKs in the original
> code was messing up the match between DAOs and their ACKs because it
> wasn't even keeping track of the DAO sequence numbers.
> >
> to interpret a later ACK correctly. I think it is implementation specific, so my
> suggestion would be a flag to indicate whether you request full ACK
> (bumping back all T+T info for rejected entries in the DAO) or a much
> smaller partial ACK with SEQ and similar IDs only. This flag (lets call it F for
> now), could go right next to K. As the DAO propagates, each node could set
> F based on whether it is able to store and/or reproduce info (F not set) or
> chose to remain stateless (set F ). This would exclude aggregation in the
> DAO-ACK sent down, but still allow for aggregation in the DAO sent up.
> >
> >>
> >>> To give another example of subtle problems with DAO-ACK, it was not
> clear to me whether I want my implementation to ACK when the Target is
> added to the routing table, or only when this node itself receives an ACK for
> the same Target from its parent. Both makes sense, with the former giving a
> quick one-hop ACK, while the latter works as an end-to-end ACK, ensuring
> that the path is actually built. Both look conformant to the standard, but I
> suppose the original author was thinking of the former, and I can easily see
> interoperability problems arising between two implementations using
> different semantics.
> >>>
> >> We did go for the end-to-end ACK to achieve better scalability. There
> >> is to me no point having a route to the parent if it is not possible to get
> it all the way to root. But I totally agree - this is not obvious from the RPL
> RFC either.
> sense that it is still addressed to the next hop but you delay ACK till you
> know your parent (and all its parents) ACKed?
> >
> 
> I mean end-to-end as in waiting for all the parents to ACK so that before
> ACKing it is known that the route is properly installed where it needs to.
> 
> >>
> > It is not yet rebased to the latest master, but it should apply. I suppose
> describing it would be too off-topic for the list.
> BTW: We have done a few deployments using our implementation using
> Yanzi networks products - take a look at this video where 1000 nodes is
> deployed with Contiki RPL + our fixes and 20 neighbors and routes per
> node. If without our fixes it would not work since Contiki RPL did not allow
> scaling beyond number of neighbors and routes / node that well before
> these fixes.
> 
> >>>> Since a sub-set of the announced RPL targets could have been
> >>>> accepted before filling up the routing table (e.g.), I would choose a
> status code between 1 and 127.
> >>>> To give some feedback to the originator of the DAO, it might be
> >>>> sensible to copy the rejected RPL Target options from the affected
> >>>> DAO to the DAO-ACK, so that the originator is fully aware of which
> Target prefixes got rejected (and which ones got accepted, implicitly).
> >>>> I would choose this method, because it doesn't require the
> >>>> originator of the DAO to save any extra state about the DAO and its
> contents.
> >>>>
> >>>> Nonetheless, everything I wrote is nonconform and I am also
> >>>> interested in the RPL experts' opinions and solutions.
> >>>>
> >>>> Best,
> >>>> Cenk
> >>>>
> >>>>> I have spend quite some time to get a more stable implementation
> >>>>> of DAO handling for Contiki RPL and I am currently looking into
> >>>>> DAO aggregation. But I realised that it is for me not 100% clear
> >>>>> what a node that receives a DAO with several prefixes to be
> >>>>> registered but can only accept a sub-set of them. Should it be a
> DAO_NACK in this case or is there any other way to handle that case?
> >>>>>
> >>>>> therefore it is possible to get fine-grained answers. But with
> aggregation of DAOs this is not the case.
> >>>>>
> >>>>> Any ideas?
> >>>>>
> >>>>> Best regards,
> >>>>> — Joakim Eriksson, SICS

---

From: Csaba Kiraly <[email-masked]>
Date: Fri, 2 Oct 2015 17:18:50 +0200

Hi Pascal,

The core observation behind the end-to-end, or delayed ACK (at least on 
my side, I don't know for Joakim) is that while the one-hop NACK 
contains important information, the one-hop ACK is not really what you 
are interested in. In fact, implementations I've checked either don't 
even ask for it, or if they do, they still don't do anything on a 
positive ACK. If instead you delay ACKs, or in other words wait for all 
the parents to ACK, this ACK or NACK brings in an important piece of 
information.

Notice that if your immediate parent would NACK, it would NACK 
immediately in both interpretations. Feedback only changes where things 
go well, or things go well till some point on the recursive path, but 
fail after. In the first, you get an ACK and you know you are reachable. 
In the latter, you do get to know the problem and you can act upon. 
Convergence is surely something that needs to be studied carefully, but 
I think delayed ACK will not create more issues than what you already 
have with the one-hop ACK.

The point that I tried to raise when I brought this up, but maybe it 
wasn't clear, is that I think both are conformant to RFC6550. Which, if 
I'm correct, brings me to the point that clarifications might be needed 
about ACKs in an RFC to avoid interoperability problems, and I think it 
is needed independent of whether the end-to-end context is a good idea 
or not. You could even think of sending both types of ACKs, but that 
would bring the implementation out of RFC6550.

Cheers,
Csaba

---

From: Joakim Eriksson <[email-masked]>
Date: Fri, 2 Oct 2015 17:39:37 +0200

From my perspective we really need the end-to-end ACK that is needed - the single hop ACK is
of no use at all if you aim at building scalable RPL networks that have bi-directional communication.

We have worked with this for quite a while at Yanzi Networks and I would say that if we get a deadlock
somewhere that is probably an indication that the selected path/parent was a bad one and that the node
should look for alternatives. If we instead would have gotten a DAO ACK over single-hop the node would
assume connectivity - but be wrong and some other mechanism (usually the application) needs to kick in
and trigger repairs. This is for me not the wanted behaviour and I rather take the risk of one or a few 
(short-term) dead-locks if a node in the path towards root reboots or in other ways is gone.

Of course combining DAO ACK (end-to-end) with infinite lifetime routes is not an optimal configuration
if there are many reboots and dead-locks. That is why we try to keep routing lifetime reasonably short
(30 minutes) so that any routes that ended up being “stuck” somewhere will be garbage collected after
a while.

Best regards,
— Joakim Eriksson, SICS

> On 02 Oct 2015, at 17:18, Csaba Kiraly <[email-masked]> wrote:
> 
> Hi Pascal,
> 
> The core observation behind the end-to-end, or delayed ACK (at least on my side, I don't know for Joakim) is that while the one-hop NACK contains important information, the one-hop ACK is not really what you are interested in. In fact, implementations I've checked either don't even ask for it, or if they do, they still don't do anything on a positive ACK. If instead you delay ACKs, or in other words wait for all the parents to ACK, this ACK or NACK brings in an important piece of information.
> 
> Notice that if your immediate parent would NACK, it would NACK immediately in both interpretations. Feedback only changes where things go well, or things go well till some point on the recursive path, but fail after. In the first, you get an ACK and you know you are reachable. In the latter, you do get to know the problem and you can act upon. Convergence is surely something that needs to be studied carefully, but I think delayed ACK will not create more issues than what you already have with the one-hop ACK.
> 
> The point that I tried to raise when I brought this up, but maybe it wasn't clear, is that I think both are conformant to RFC6550. Which, if I'm correct, brings me to the point that clarifications might be needed about ACKs in an RFC to avoid interoperability problems, and I think it is needed independent of whether the end-to-end context is a good idea or not. You could even think of sending both types of ACKs, but that would bring the implementation out of RFC6550.
> 
> Cheers,
> Csaba
>

---

From: Csaba Kiraly <[email-masked]>
Date: Sat, 3 Oct 2015 06:41:02 +0200

Since we were jumping through several topics around the DAO-ACK 
semantics in this thread, I wrote a quick memo of what had been brought 
up till now. I thought it might worth sharing:

DAO-ACK semantics
-----------------

1, ACK for DAO with multiple T+T [Joakim]
  - status code 1-127, and copy rejected Target [Cenk]
  - new option with individual status codes (same semantics as with 
multiple individual messages) [Csaba]
    - send individual ACKs for each Target [Joakim]
      - memory concerns, better to include Target in response [Joakim]
        - “F” flag in DAO to request full ACK with T+T or partial ACK 
with status codes only [Csaba]
  - meaning of status code [Pascal]
    - enumeration
      - both Joakim and we use this (not for multiple T+T, but to 
differentiate different reasons of DAO rejection)
      - would need registry for interoperability [Pascal]
    - metric: as “scalar degree of unwillingness” calculated based on 
available resources [Pascal]
      - could be difficult to combine it into one scalar degree in one 
byte [Joakim, Csaba]
      - might be better to put the resource info in DIO or in a DAO 
option [Csaba]
  - ACK with rejected T+T and status code for each; relation to path 
control [Pascal]
  - “All-or-nothing” flag in DAO [Joakim]

2, ACK semantics: one-hop vs. end-to-end context [Csaba]
  - when speaking of end-to-end context, we do not refer to a DAO 
addressed directly to the root, like in non-storing, but to a different 
interpretation of the ACK of the one-hop DAO [Csaba, Joakim]
  - used in Yanzi [Joakim]
  - drafted advantages and disadvantages [Pascal, Csaba, Joakim]
    - possible deadlock [Pascal]
    - is it RFC6550?
    - one-hop ACK is not enough info, needs end-to-end for decision 
logic [Csaba, Joakim]

3, fix meaning of status code 127 (just a typo in the RFC) [Csaba]

4, status code in ACK for No-path DAO not defined clearly [Csaba]
  - only code 0 makes sense [Joakim]
  - not using end-to-end context in this case [Joakim]

5, multiple DAO ACKs for same DAO [Joakim, Csaba]
  - to handle multiple T+T [Joakim]
  - to have both end-to-end and one-hop ACK semantics [Csaba]

Disclaimer: this doesn't want to be a full summary, and I obviously 
skipped many detail in such a brief writeup.

Cheers,
Csaba

---

From: Michael Richardson <[email-masked]>
Date: Thu, 15 Oct 2015 11:06:06 -0400

> messages in several ways.

I think that a document that updates RFC6550 would be very welcome, even 
if it just describes this single issue.   I think it is premature to 
consider revising/advance RFC6550 from PS to Internet Standard, but a 
series of small updates would make that activity significantly easier.

(trying to post via Thunderbird from new IMAP list access)

---

From: Michael Richardson <[email-masked]>
Date: Thu, 15 Oct 2015 11:11:40 -0400

> messages in several ways.

A document which updated RFC6550 would be welcome here.

---

From: "Turner, Randy" <[email-masked]>
Date: Thu, 15 Oct 2015 15:13:22 +0000

There are already a number of inter-related RFCs to effectively implement RPL - maybe a "bis" or taxonomy that lays out a roadmap for implementation.

+1

Randy

-----Original Message-----
From: Roll [mailto:[email-masked]] On Behalf Of Michael Richardson
Sent: Thursday, October 15, 2015 11:12 AM
To: [email-masked]
Subject: Re: [Roll] Semantics of DAO ACK

P PLEASE CONSIDER OUR ENVIRONMENT BEFORE PRINTING THIS EMAIL.

This e-mail (including any attachments) is confidential and may be legally privileged. If you are not an intended recipient or an authorized representative of an intended recipient, you are prohibited from using, copying or distributing the information in this e-mail or its attachments. If you have received this e-mail in error, please notify the sender immediately by return e-mail and delete all copies of this message and any attachments. Thank you.

---

From: Csaba Kiraly <[email-masked]>
Date: Thu, 15 Oct 2015 17:22:53 +0200

> A document which updated RFC6550 would be welcome here.

I could extend my previous summary into a more proper document, but I 
have no experience with RFC writing, so I would prefer to team up with 
someone who is more knowledgeable in the writing style. Anyone willing 
to help?

Csaba

---

From: Joakim Eriksson <[email-masked]>
Date: Thu, 15 Oct 2015 19:00:53 +0200

Hello,

I am planning to help out to write our DAO ACK experiences down in an RFC!

Best regards,
— Joakim

> On 15 Oct 2015, at 17:22, Csaba Kiraly <[email-masked]> wrote:
> 
> 
> 
> I could extend my previous summary into a more proper document, but I have no experience with RFC writing, so I would prefer to team up with someone who is more knowledgeable in the writing style. Anyone willing to help?
> 
> Csaba
> 
>>

---

From: "Rahul Arvind Jadhav (Rahul Arvind Jadhav, 2012 Labs)" <[email-masked]>
Date: Fri, 16 Oct 2015 06:50:53 +0000

We have also implemented this end-to-end ACK feature in our solution in Huawei. And this end-to-end ACK has become important especially in context to bigger networks. Without this feature it is impossible for the node to know when to initiate the application traffic (especially bidirectional traffic, like Joakim mentioned). Secondly it also reduces network convergence time for bigger networks (of-course at the cost of additional ACK traffic), because the repairs are triggered soon when the ACKs do not arrive. We had found good performance improvements for 1K node network (with roughly 16 hops) and it certainly improves the network convergence time and the nodes have  more deterministic way of knowing when to initiate the traffic.

IMO, this extension will help in a big way.

There are few more points:
1. Can the E2E-ACK sent by the grounded root be aggregated ? This is possible with the E2E-ACK going one hop.
2. Some guidelines on what timers the end nodes should use for DAO retry in case the E2E-ACK is not received. The timers need to be set to a conservative (higher) value otherwise the cumulative DAO retries will negatively impact the network.

Regards,
Rahul

-----Original Message-----
From: Roll [mailto:[email-masked]] On Behalf Of Csaba Kiraly
Sent: 03 October 2015 AM 10:11
To: [email-masked]
Subject: Re: [Roll] Semantics of DAO ACK

Since we were jumping through several topics around the DAO-ACK semantics in this thread, I wrote a quick memo of what had been brought up till now. I thought it might worth sharing:

DAO-ACK semantics
-----------------

1, ACK for DAO with multiple T+T [Joakim]
  - status code 1-127, and copy rejected Target [Cenk]
  - new option with individual status codes (same semantics as with multiple individual messages) [Csaba]
    - send individual ACKs for each Target [Joakim]
      - memory concerns, better to include Target in response [Joakim]
        - “F” flag in DAO to request full ACK with T+T or partial ACK with status codes only [Csaba]
  - meaning of status code [Pascal]
    - enumeration
      - both Joakim and we use this (not for multiple T+T, but to differentiate different reasons of DAO rejection)
      - would need registry for interoperability [Pascal]
    - metric: as “scalar degree of unwillingness” calculated based on available resources [Pascal]
      - could be difficult to combine it into one scalar degree in one byte [Joakim, Csaba]
      - might be better to put the resource info in DIO or in a DAO option [Csaba]
  - ACK with rejected T+T and status code for each; relation to path control [Pascal]
  - “All-or-nothing” flag in DAO [Joakim]

2, ACK semantics: one-hop vs. end-to-end context [Csaba]
  - when speaking of end-to-end context, we do not refer to a DAO addressed directly to the root, like in non-storing, but to a different interpretation of the ACK of the one-hop DAO [Csaba, Joakim]
  - used in Yanzi [Joakim]
  - drafted advantages and disadvantages [Pascal, Csaba, Joakim]
    - possible deadlock [Pascal]
    - is it RFC6550?
    - one-hop ACK is not enough info, needs end-to-end for decision logic [Csaba, Joakim]

Disclaimer: this doesn't want to be a full summary, and I obviously skipped many detail in such a brief writeup.

Cheers,
Csaba

On 02/10/15 17:39, Joakim Eriksson wrote:
>  From my perspective we really need the end-to-end ACK that is needed 
> - the single hop ACK is of no use at all if you aim at building scalable RPL networks that have bi-directional communication.
>
> We have worked with this for quite a while at Yanzi Networks and I 
> would say that if we get a deadlock somewhere that is probably an 
> indication that the selected path/parent was a bad one and that the 
> node should look for alternatives. If we instead would have gotten a 
> DAO ACK over single-hop the node would assume connectivity - but be 
> wrong and some other mechanism (usually the application) needs to kick 
> in and trigger repairs. This is for me not the wanted behaviour and I 
> rather take the risk of one or a few
> Of course combining DAO ACK (end-to-end) with infinite lifetime routes 
> is not an optimal configuration if there are many reboots and 
> dead-locks. That is why we try to keep routing lifetime reasonably 
> short
> (30 minutes) so that any routes that ended up being “stuck” somewhere 
> will be garbage collected after a while.
>
> Best regards,
> — Joakim Eriksson, SICS
>
>
>>>> implementing fixes to the DAOSequence handling, and looking into 
>>>> multiple targets.
>>>>>> Yes, it is underspecified. There is need for clarifications and 
>>>>>> more details
>>>> on the DAO / DAO ACK!
>>>> would be to have support for the same semantics that you would have 
>>>> had with one DAO message per Target, i.e., I would prefer an option 
>>>> field that gives an individual status for each Target.
>>>> implementation, you can see that I use the routing table entry to 
>>>> match the DAO ACK, and I keep only DAOSequence (SEQ) as extra 
>>>> state. I'm not sure it would work in all cases, but it did work for 
>>>> the case I considered. I'm keeping only the SEQ, and I think this 
>>>> is a must if you have no aggregation, and you want to match in case 
>>>> you forward multiple DAOs before getting the ACK or timing out on 
>>>> it. In fact, simply enabling ACKs in the original code was messing 
>>>> up the match between DAOs and their ACKs because it wasn't even keeping track of the DAO sequence numbers.
>>>> scenarios, the game changes, and I don't know what would be the 
>>>> balance between state you have to keep anyway and state you keep 
>>>> just to be able to interpret a later ACK correctly. I think it is 
>>>> implementation specific, so my suggestion would be a flag to 
>>>> indicate whether you request full ACK (bumping back all T+T info 
>>>> for rejected entries in the DAO) or a much smaller partial ACK with 
>>>> SEQ and similar IDs only. This flag (lets call it F for now), could 
>>>> go right next to K. As the DAO propagates, each node could set F 
>>>> based on whether it is able to store and/or reproduce info (F not 
>>>> set) or chose to remain stateless (set F ). This would exclude aggregation in the DAO-ACK sent down, but still allow for aggregation in the DAO sent up.
>>>> clear to me whether I want my implementation to ACK when the Target 
>>>> is added to the routing table, or only when this node itself 
>>>> receives an ACK for the same Target from its parent. Both makes 
>>>> sense, with the former giving a quick one-hop ACK, while the latter 
>>>> works as an end-to-end ACK, ensuring that the path is actually 
>>>> built. Both look conformant to the standard, but I suppose the 
>>>> original author was thinking of the former, and I can easily see 
>>>> interoperability problems arising between two implementations using different semantics.
>>>>>> We did go for the end-to-end ACK to achieve better scalability. 
>>>>>> There is to me no point having a route to the parent if it is not 
>>>>>> possible to get
>>>> it all the way to root. But I totally agree - this is not obvious 
>>>> from the RPL RFC either.
>>>> sense that it is still addressed to the next hop but you delay ACK 
>>>> till you know your parent (and all its parents) ACKed?
>>>> I mean end-to-end as in waiting for all the parents to ACK so that 
>>>> before ACKing it is known that the route is properly installed where it needs to.
>>>>
>>>>> suppose
>>>> Yanzi networks products - take a look at this video where 1000 
>>>> nodes is deployed with Contiki RPL + our fixes and 20 neighbors and 
>>>> routes per node. If without our fixes it would not work since 
>>>> Contiki RPL did not allow scaling beyond number of neighbors and 
>>>> routes / node that well before these fixes.
>>>>
>>>>>>>> This is an interesting question and I also couldn't find any 
>>>>>>>> answers in
>>>> RFC 6550.
>>>>>>>> I would expect a node to choose another parent if a more 
>>>>>>>> aggressive
>>>> status code is received ([128-255]).
>>>>>>>> But a full routing table can have free space again until the 
>>>>>>>> next or any
>>>> subsequent DAO arrives ..
>>>>>>>> sensible to copy the rejected RPL Target options from the 
>>>>>>>> affected DAO to the DAO-ACK, so that the originator is fully 
>>>>>>>> aware of which
>>>>>>>>> I have spend quite some time to get a more stable 
>>>>>>>>> implementation of DAO handling for Contiki RPL and I am 
>>>>>>>>> currently looking into DAO aggregation. But I realised that it 
>>>>>>>>> is for me not 100% clear what a node that receives a DAO with 
>>>>>>>>> several prefixes to be registered but can only accept a 
>>>>>>>>> sub-set of them. Should it be a
>>>>>>>>> receiving node can do a NACK when the routing table is full 
>>>>>>>>> and therefore it is possible to get fine-grained answers. But 
>>>>>>>>> with

---

From: Csaba Kiraly <[email-masked]>
Date: Fri, 16 Oct 2015 10:28:12 +0200

Hi Rahul,

On 16/10/15 08:50, Rahul Arvind Jadhav (Rahul Arvind Jadhav, 2012 Labs) 
> IMO, this extension will help in a big way.
Glad to hear that you've came to the same conclusions. I think it really 
shows that the possibility is there among the lines of the RFC, but not 
spelled out in a way to make it evident. IMHO this could lead to 
interoperability problems, but I would be interested to know if anyone 
actually did interoperability tests between implementations going with 
different interpretations.

You speak of additional ACK traffic, which suggests that you use both 
end-to-end ACKs and one-hop ACKs. Is this the case, or are you just 
referring to more ACKs because of more information and thus more events 
to react to?

> 1. Can the E2E-ACK sent by the grounded root be aggregated ? This is possible with the E2E-ACK going one hop.
What you mean by E2E-ACK going one hop? I've seen ACK traffic near the 
root being a problem in our tests, and ACK aggregation could be 
supported at low implementation overhead, so I think it is a good 
option. If we don't want to mandate support for it, we can still 
consider a capability flag such as the "F" flag mentioned below to make 
it optional and interoperable.

> 2. Some guidelines on what timers the end nodes should use for DAO retry in case the E2E-ACK is not received. The timers need to be set to a conservative (higher) value otherwise the cumulative DAO…
Reasonable values for timers really depend on the decision logic. More 
precisely, on whether nodes in the chain can only forward DAO-NACKs or 
could also act on them e.g. by trying another parent (which takes some 
time). Since we don't want to mandate the decision logic, agreeing on 
limits on the timers without limiting scalability could be tough. I 
think having guidelines is a good idea, but we should be careful not to 
limit implementations and deployments.

What about a push-back mechanism which tells the originator of the DAO 
to slow down with retries? For example, as part of the ACK, you could 
set a the "S" flag with the following meaning: "while I was processing 
this, I've seen several identical DAOs from you". This wouldn't slow 
down the normal DAO sending, just the retry timeout. Then, how the end 
node should handle this flag can be left to the implementation. I don't 
think we need to mandate how the timeout should scale up and down, it 
will work even without mandating the logic.

Regards,
Csaba

---

From: "Rahul Arvind Jadhav (Rahul Arvind Jadhav, 2012 Labs)" <[email-masked]>
Date: Fri, 16 Oct 2015 12:09:33 +0000

Hi Csaba,

Responses inline...

Regards,
Rahul

-----Original Message-----
From: Roll [mailto:[email-masked]] On Behalf Of Csaba Kiraly
Sent: 16 October 2015 PM 01:58
To: Routing Over Low power and Lossy networks
Subject: Re: [Roll] Semantics of DAO ACK

Hi Rahul,

> IMO, this extension will help in a big way.
Glad to hear that you've came to the same conclusions. I think it really shows that the possibility is there among the lines of the RFC, but not spelled out in a way to make it evident. IMHO this could lead to interoperability problems, but I would be interested to know if anyone actually did interoperability tests between implementations going with different interpretations.

You speak of additional ACK traffic, which suggests that you use both end-to-end ACKs and one-hop ACKs. Is this the case, or are you just referring to more ACKs because of more information and thus more events to react to?

--[RJ]--
The additional ACK traffic that I talk of is of the end-to-end ACKs alone. One-hop ACKs are not useful in any case, imo, and we never have used it. I m referring to the additional traffic generated for E2E-ACKs and retransmissions of DAOs on not reception of these ACKs. My point is, in a bigger network, there is scope of aggregating these downstream ACKs provided these ACKs are sent back to the nodes on hop-by-hop basis (just like DAO travel upstream hop-by-hop, E2E aggregated Acks can travel downstream hop-by-hop). But then like DAO, these E2E-ACKs also need to carry target information in the payload for it to be aggregated.
--[RJ-End]--

> 1. Can the E2E-ACK sent by the grounded root be aggregated ? This is possible with the E2E-ACK going one hop.
What you mean by E2E-ACK going one hop? I've seen ACK traffic near the root being a problem in our tests, and ACK aggregation could be supported at low implementation overhead, so I think it is a good option. If we don't want to mandate support for it, we can still consider a capability flag such as the "F" flag mentioned below to make it optional and interoperable.

--[RJ]--
Sorry my statement above was incorrect. Sent the mail in a haste. I meant "E2E-ACK going on hop-by-hop basis".. This is needed for aggregation to work. But as mentioned above, for aggregation to work, one needs to add target information back in the E2E-ACK.
--[RJ-End]--

> 2. Some guidelines on what timers the end nodes should use for DAO retry in case the E2E-ACK is not received. The timers need to be set to a conservative (higher) value otherwise the cumulative DAO…
Reasonable values for timers really depend on the decision logic. More precisely, on whether nodes in the chain can only forward DAO-NACKs or could also act on them e.g. by trying another parent (which takes some time). Since we don't want to mandate the decision logic, agreeing on limits on the timers without limiting scalability could be tough. I think having guidelines is a good idea, but we should be careful not to limit implementations and deployments.

What about a push-back mechanism which tells the originator of the DAO to slow down with retries? For example, as part of the ACK, you could set a the "S" flag with the following meaning: "while I was processing this, I've seen several identical DAOs from you". This wouldn't slow down the normal DAO sending, just the retry timeout. Then, how the end node should handle this flag can be left to the implementation. I don't think we need to mandate how the timeout should scale up and down, it will work even without mandating the logic.

--[RJ]--
I think this flag is not necessary, since if the E2E-ACK reaches the node then anyways it will cease sending DAO.
--[RJ-End]--

Regards,
Csaba

>> wrong and some other mechanism (usually the application) needs to 
>> kick in and trigger repairs. This is for me not the wanted behaviour 
>> and I rather take the risk of one or a few
>> Of course combining DAO ACK (end-to-end) with infinite lifetime 
>> routes is not an optimal configuration if there are many reboots and 
>>>>> would be to have support for the same semantics that you would 
>>>>> have had with one DAO message per Target, i.e., I would prefer an 
>>>>> option field that gives an individual status for each Target.
>>>>> state. I'm not sure it would work in all cases, but it did work 
>>>>> for the case I considered. I'm keeping only the SEQ, and I think 
>>>>> this is a must if you have no aggregation, and you want to match 
>>>>> in case you forward multiple DAOs before getting the ACK or timing 
>>>>> out on it. In fact, simply enabling ACKs in the original code was 
>>>>> messing up the match between DAOs and their ACKs because it wasn't even keeping track of the DAO sequence numbers.
>>>>> for rejected entries in the DAO) or a much smaller partial ACK 
>>>>> with SEQ and similar IDs only. This flag (lets call it F for now), 
>>>>> could go right next to K. As the DAO propagates, each node could 
>>>>> set F based on whether it is able to store and/or reproduce info 
>>>>> (F not
>>>>> clear to me whether I want my implementation to ACK when the 
>>>>> Target is added to the routing table, or only when this node 
>>>>> itself receives an ACK for the same Target from its parent. Both 
>>>>> makes sense, with the former giving a quick one-hop ACK, while the 
>>>>> latter works as an end-to-end ACK, ensuring that the path is 
>>>>> actually built. Both look conformant to the standard, but I 
>>>>> suppose the original author was thinking of the former, and I can 
>>>>> easily see interoperability problems arising between two implementations using different semantics.
>>>>>>> There is to me no point having a route to the parent if it is 
>>>>>>> not possible to get
>>>>> nodes is deployed with Contiki RPL + our fixes and 20 neighbors 
>>>>> and routes per node. If without our fixes it would not work since 
>>>>>>>>> To give some feedback to the originator of the DAO, it might 
>>>>>>>>> be sensible to copy the rejected RPL Target options from the 
>>>>>>>>>> currently looking into DAO aggregation. But I realised that 
>>>>>>>>>> it is for me not 100% clear what a node that receives a DAO 
>>>>>>>>>> with several prefixes to be registered but can only accept a 
>>>>>>>>>> If each would have been sent separately it is obvious that 
>>>>>>>>>> the receiving node can do a NACK when the routing table is 
>>>>>>>>>> full and therefore it is possible to get fine-grained 
>>>>>>>>>> answers. But with

---

From: Michael Richardson <[email-masked]>
Date: Sat, 31 Oct 2015 00:55:00 -0400

Pascal Thubert (pthubert) <[email-masked]> wrote:
    > What I read here boils down to a limited diffusion algorithm. We tried
    > to avoid that in RPL because any movement within the convergence would
    > cause a deadlock. IOW if every node waits for (all of) the parents to

Are you saying that waiting for an ACK from the root will result in an
unstable/non-convergent algorithm?

-- 
Michael Richardson
-on the road-