Re: [Roll] Semantics of DAO ACK

[Joakim Eriksson <[e-mail]>]

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 <[e-mail]> 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
> 
> On 02/10/15 15:04, Pascal Thubert (pthubert) wrote:
>> 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
>> 
>>> -----Original Message-----
>>> From: Roll [mailto:[e-mail]] On Behalf Of Joakim Eriksson
>>> Sent: jeudi 1 octobre 2015 22:11
>>> To: Routing Over Low power and Lossy networks <[e-mail]>
>>> Subject: Re: [Roll] Semantics of DAO ACK
>>> 
>>> 
>>>> On 01 Oct 2015, at 21:03, Csaba Kiraly <[e-mail]> wrote:
>>>> 
>>>> 
>>>> 
>>>> On 30/09/15 17:55, Joakim Eriksson wrote:
>>>>>> On 30 Sep 2015, at 06:44, Csaba Kiraly <[e-mail]> 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?
>>> 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.
>>> 
>>>>> 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.
>>> 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
>>> 
>>>> 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
>>>>>>>> [e-mail]
>>>>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>>>> _______________________________________________
>>>>>>> Roll mailing list
>>>>>>> [e-mail]
>>>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>>> _______________________________________________
>>>>>> Roll mailing list
>>>>>> [e-mail]
>>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>> _______________________________________________
>>>>> Roll mailing list
>>>>> [e-mail]
>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>> _______________________________________________
>>>> Roll mailing list
>>>> [e-mail]
>>>> https://www.ietf.org/mailman/listinfo/roll
>>> _______________________________________________
>>> Roll mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/roll
>> _______________________________________________
>> Roll mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/roll
>> 
>> 
> 
> 
> _______________________________________________
> Roll mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll