Subject: Re: [Roll] Border router failure detection

From: Konrad Iwanicki <[email-masked]>
Date: Wed, 7 Apr 2021 21:36:54 +0200

Dear all,

Approximately a year ago, I joined the WG and advertised an extension to 
RPL that I had been working on for some time with a goal of describing 
it in a draft. Unfortunately, just when I got the necessary pointers and 
a few initial comments, the pandemic broke out. The resulting surge of 
professional and personal obligations made it literally impossible for 
me to participate in and, at some point, even follow the group's 
activities, for which I am sorry.

However, I did strive to regularly find a little time to get somewhat 
acquainted with IETF's procedures and write up something that may 
resemble a draft. I have just submitted it as:

    draft-iwanicki-roll-rnfd-00

and created a dedicated repository on the group's GitHub.

Since I have no experience writing IETF documents, I would really 
appreciate your collaboration on either turning the text into a true 
draft or concluding that this should not be done.

Please, keep mind in mind that I decided to maximally cut down the 
original algorithms, so that the extension is as simple as possible 
without losing key properties. Therefore, it is likely that if the 
extension as a whole or any of its parts turn out relevant or 
interesting, still a considerable amount of work may be necessary to 
have it or them described properly. Your contribution is most welcome.

Thanks in advance.

Best regards,
-- 
- Konrad Iwanicki.

---

From: Michael Richardson <[email-masked]>
Date: Wed, 07 Apr 2021 19:46:24 -0400

Konrad Iwanicki <[email-masked]> wrote:
    > draft. Unfortunately, just when I got the necessary pointers and a few
    > initial comments, the pandemic broke out.

I know the feeling.
I keep thinking I should be able to do *more* since I can't go out.

    > and created a dedicated repository on the group's GitHub.

I see it at:
  https://github.com/roll-wg/draft-rnfd

You might want to add a Makefile, either via
    https://github.com/martinthomson/i-d-template/blob/master/doc/SETUP.md
or rip of my minimal one, such as:
    https://github.com/roll-wg/draft-ietf-roll-enrollment-priority/blob/master/Makefile

    > Since I have no experience writing IETF documents, I would really appreciate
    > your collaboration on either turning the text into a true draft or concluding
    > that this should not be done.

It looks like you did a really good job.

RPL is being used in storing mode the ANIMA WG's Autonomic Control Plane.
See: https://datatracker.ietf.org/doc/draft-ietf-anima-autonomic-control-plane/
( section 6.12. ).   The document is minutes away from getting an RFC#.

We think that the border router, DODAG root, will be a device in the NOC.
The NOC may get replicated into multiple locations so there could potentially
be more than one candidate DODAG root.  Given nodes are not constrained in
the RFC7228 sense, supporting multiple DODAGs could be done, but we
simplified our life by not mandating (actually, at this point, forbidding)
the RPI header, so we are lacking an instanceID.

The short of it is that I'd really like nodes to be able to float
non-grounded DODAG roots if they don't hear a DIO after a few seconds.

----

It seems that you might want a term for the LBR's children.
That is, the devices at rank "1", that hear the LBR's DIOs.

I think that I would move some of section 3.2 further forward in the
document.  I think that I need a gentler introduction to CFRCs here, and I
don't really need to know the properties, rather I need a higher-level idea
of things.    Since section 4 goes over the operations again, I would leave
it for that spot, and make it a section 4.1.

Having gone forward and back a bit, I'm still a bit uncertain how nodes
assign themselves a bit... oh, self() in section 4 says "random".
Why not make this a function (hash?) of the short-IPv6 address or something?

Not every media has ACK frames at the L2 to establish that there are
failures.  It might be worth putting the Detecting and the Verifying into
separate sections.  Aside from the ANIMA case (which is usually pure ethernet),
there are also situations where there is an ethernet backbone connecting a
few 6LBRs (RFC8929), and your protocol would sensibly run on both the
wireless and the wired side of the 6LBRs.

I also wonder if the RNFD could be included in DAOs (particularly storing
mode ones) sent to the DODAG root.
I know that probably seems senseless: why tell the root that you are
observing it to be dying....  But, it acts as interesting telemetry about
what the nodes are seeing, and might serve as a useful indication of imminent
failure, or some kind of systematic long-cycle pathology.

Your IANA considerations are how the document will look after IANA has
processed it.  Prior to that point, you need to write it as a request.

Something like:

   IANA is requested to allocate the value TBD1 from the "RPL Control Message
   Options" sub-registry of the "Routing Protocol for Low Power and Lossy
   Networks (RPL)" registry.

I like to include the URL of the registry in my request to be really really
clear, and to save everyone else the time to find it.

Your security considerations will want to cite RFC7416.
In particular, 7.2.4, and section 7.3.4 and 7.3.5 might be relevant.

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 8 Apr 2021 14:05:53 +0000

Hello Michael and Konrad

I concur that this is excellent work and that we want to discuss it. As context:

If I may add: At the (early) time I contributed to the ACP design, the idea was that the Root's children were configured with a DODAGPreference (prf) that is more than the default value (of 0) inside the network. Different children may be given different prf to enforce an order in which they become the replacement for the LBR serving as Root. 

When losing connectivity to the LBR, a child that does not have connectivity to the main DODAG becomes floating Root of its own DODAG. If the LBR dies, all the children lose their parent, and the floating DODAG reforms from the child with the highest prf. Nodes that are willing to jump to an alternate DODAG that is grounded will do so. This is supposed to be somewhat fast because the Trickle timers are reset.

I understand that the idea here is to be faster than that. 

Keep safe;

Pascal

> -----Original Message-----
> From: Roll <[email-masked]> On Behalf Of Michael Richardson
> Sent: jeudi 8 avril 2021 1:46
> To: Routing Over Low power and Lossy networks <[email-masked]>
> Subject: Re: [Roll] Border router failure detection
> 
> 
> appreciate
> The NOC may get replicated into multiple locations so there could
> potentially be more than one candidate DODAG root.  Given nodes are not
> constrained in the RFC7228 sense, supporting multiple DODAGs could be
> done, but we simplified our life by not mandating (actually, at this
> point, forbidding) the RPI header, so we are lacking an instanceID.
> 
> The short of it is that I'd really like nodes to be able to float non-
> grounded DODAG roots if they don't hear a DIO after a few seconds.
> 
> ----
> 
> separate sections.  Aside from the ANIMA case (which is usually pure
> ethernet), there are also situations where there is an ethernet backbone
> connecting a few 6LBRs (RFC8929), and your protocol would sensibly run on
> both the wireless and the wired side of the 6LBRs.
> 
> what the nodes are seeing, and might serve as a useful indication of
> imminent failure, or some kind of systematic long-cycle pathology.
> 
> I like to include the URL of the registry in my request to be really
> really clear, and to save everyone else the time to find it.
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 8 Apr 2021 14:16:04 +0000

Hello Konrad

About this text
"

   Since all DODAG paths lead to the corresponding LBR, detecting its
   crash by a node entails dropping all parents and adopting an infinite
   rank, which reflects the node's inability to reach the LBR.  However,
   achieving this state for all nodes is slow, can generate heavy
   traffic, and is difficult to implement correctly [Iwanicki16]
   [Paszkowska19] [Ciolkosz19].
"

Please note that this may be what an implementation decides to do, but is by far not my favorite option.
The alternate is to rest the "G" but and become floating root. The benefit is that the DODAG structure is mostly maintained and that routing inside may persist.

See https://tools.ietf.org/html/rfc6550#section-18.2.4 for how to configure this.

Keep safe;

Pascal

> From: Roll <[email-masked]> On Behalf Of Konrad Iwanicki
> Sent: mercredi 7 avril 2021 21:37
> RPL that I had been working on for some time with a goal of describing it
> in a draft. Unfortunately, just when I got the necessary pointers and a
> few initial comments, the pandemic broke out. The resulting surge of
> professional and personal obligations made it literally impossible for me
> to participate in and, at some point, even follow the group's activities,
> for which I am sorry.
> 
> acquainted with IETF's procedures and write up something that may resemble
> a draft. I have just submitted it as:
> 
> appreciate your collaboration on either turning the text into a true draft
> or concluding that this should not be done.
> 
> extension as a whole or any of its parts turn out relevant or interesting,
> still a considerable amount of work may be necessary to have it or them
> described properly. Your contribution is most welcome.
> 
> Thanks in advance.
> 
> Best regards,
> --
> - Konrad Iwanicki.
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Michael Richardson <[email-masked]>
Date: Thu, 08 Apr 2021 10:59:39 -0400

> The alternate is to rest the "G" but and become floating root. The
    > benefit is that the DODAG structure is mostly maintained and that
    > routing inside may persist.

This works well for storing mode where one expects that all 6LR are pretty
much equivalently capable.

For Non-Storing Mode, it could be that only the LBR (and it's redundant
backup...), are capable of accepting the DAOs, maintaining that table and
generating the right routing headers.

Perhaps this is where the gap lies.

---

From: Konrad Iwanicki <[email-masked]>
Date: Thu, 8 Apr 2021 23:17:01 +0200

Hi Pascal, Michael,

First of all, thanks for your interest, encouragement, and feedback!

I'll try to answer in the "stack mode" (from your last email to the 
first) and as much as I can tonight because my throughput this week 
again became very limited due to another lockdown.

> Perhaps this is where the gap lies.

Floating DODAGs are really the best option to keep routing inside a 
DODAG possible in the face of failures. RNFD, however, deals with an 
orthogonal problem and can actually help spawning floating DODAGs faster 
after a grounded DODAG's root dies, as I try to explain below.

To start with, the envisioned use of RNFD concerns "important" DODAG 
roots (e.g., providing connectivity with the rest of the Internet) that 
in addition have an increased risk of failures (because of e.g. power 
supply interruptions or bugs resulting from greater HW/SW complexity 
compared to "normal" nodes). In practice, these will be LBRs that are 
roots of grounded DODAGs, and hence they are emphasized in the text. 
Nevertheless, one can use the algorithm also for any other DODAG roots. 
The cost is the overhead on DIOs and DISs due to the extra option and 
possible Trickle timer resets.

Moreover, RNFD aims at minimal requirements with respect to RPL. In 
particular, it works even if a DODAG is completely degenerated. 
Likewise, it works for all RPL MOPs, notably even MOP 0 without any 
downward routes (which I believe is a particularly attractive feature).

Therefore, regarding floating DODAGs, irrespective of nodes' 
capabilities, a major question is: When should a node leave a grounded 
DODAG and start advertising a floating one?

More specifically, https://tools.ietf.org/html/rfc6550#section-18.2.4, 
quoted by Pascal in the previous e-mail, states that this is done by a 
node whose parent set becomes empty. And this moment is justified 
because---before---a node always has a possibility to select some node 
as the preferred parent.

However, normally having an empty parent set implies that the node has 
already performed multiple unnecessary parent switches after a crash of 
the DODAG root, as the ranks of its subsequent parents grew repeatedly 
due to the lack of root. These switches must have taken time and 
generated control traffic resulting from Trickle timer resets.

What RNFD can do is reduce the time from the crash of a DODAG root to 
the moment a node empties its parent set (which is done when RNFD sets 
its LORS to GLOBALLY DOWN) by an order of magnitude. This means that a 
node can much quicker conclude that the root node of a grounded DODAG is 
dead, empty its parent set, and start being the root of a floating 
DODAG. Note that this is independent of whether a storing or non-storing 
mode is utilized.

What is more, this reduction of the root's crash detection period also 
reduces RPL's opportunities to switch the node's parents and degenerate 
downward routes in effect. Therefore, with RNFD it is likely that 
downward routes in the floating DODAG remain closer to what where in the 
original grounded DODAG, which is probably more important in a storing mode.

To sum up, when operating together with RPL in a deployment where nodes 
can spawn floating DODAGs, RNFD can significantly reduce the 
interruption period of downward routing as well.

What I see in the text of the draft is that indeed I did not mention the 
possibility of starting a floating DODAG when the GLOBALLY DOWN value of 
LORS is attained. Thanks a lot for these observations!

Where do you think it would be best to put this information in the text?

Best,
-- 
- Konrad Iwanicki.

---

From: Konrad Iwanicki <[email-masked]>
Date: Thu, 8 Apr 2021 23:19:33 +0200

Hi again Pascal,

> See https://tools.ietf.org/html/rfc6550#section-18.2.4 for how to configure this.

OK, I think I addressed this in my previous e-mail to you and Michael.

(The next two e-mails will have to wait till tomorrow I am affraid.)

Best,
-- 
- Konrad Iwanicki.

---

From: Konrad Iwanicki <[email-masked]>
Date: Fri, 9 Apr 2021 22:57:01 +0200

Hello Pascal,

> I understand that the idea here is to be faster than that.

That's an interesting idea, which is again orthogonal to RNFD and 
related to what I wrote in the previous e-mail: RNFD's operation is 
focused on the period from the DODAG root's crash to the moment of 
detecting it by all nodes. In this case, RNFD would thus speed up the 
occurrence of the moment the root's neighbors promote themselves to the 
roots of floating DODAGs.

As to the promotion itself, I was wondering if one could additionally 
integrate the election of the root's neighbor with the best prf into 
RNFD to speed up the formation of the newly created floating DODAG. 
However, as you pointed out, DODAG construction is rapid because of 
Trickle, so modifying RNFD to also perform the election of the neighbor 
with the best prf would bring little benefit and would only make the 
algorithm more involved.

To sum up, as I mentioned in the previous e-mail, RNFD can significantly 
accelerate the detection of the DODAG root's crash and bootstrapping of 
floating DODAGs by the root's neighbors, and the prf algorithm kicks in 
after the DODAG root's crash has been detected.

Best,
-- 
- Konrad Iwanicki.

---

From: Konrad Iwanicki <[email-masked]>
Date: Wed, 14 Apr 2021 14:12:23 +0200

Dear Michael,

>      https://github.com/roll-wg/draft-ietf-roll-enrollment-priority/blob/master/Makefile

Thanks for the suggestion! I did borrow your getver and Makefile, 
slightly adapting the latter.

> non-grounded DODAG roots if they don't hear a DIO after a few seconds.

I have read the relevant section of the ANIMA ACP draft. I do not know 
if I got all the details, so correct me if I am wrong.

Indeed, the draft adopts RPL in a storing MOP with a single RPLInstance. 
It assumes that NOC can be replicated and seems to suggest that the 
DODAG Root is a node within an NOC. More specifically, though I may not 
have gotten this correctly, there would be a single primary DODAG root 
and when it malfunctions, another node, possibly in a different NOC, 
takes over this role so that at any time at most one DODAG root is active.

I did not find the details of the failover mechanisms but I presume that 
the nodes that can act as DODAG roots synchronize with each other using 
regular RPL control messages over non-LLN links (perhaps inter-NOC 
ones). Therefore, DIOs over such links can be exchanged at a much higher 
frequency than over LLN links. In effect, indeed, if one of such 
NOC-based DODAG root candidate nodes does not hear a DIO from the acting 
DODAG root node within a few seconds, it may take over.

In such a setting, RNFD may not have a lot of advantages: depending on a 
number of factors, it could offer comparable performance, and hence 
could serve as a support for the DIO timeout mechanism. As I explained 
in the previous e-mails, the possibility of spawning floating DODAGs is 
actually not an obstacle.

There is, however, at least one situation in which RNFD could help. More 
specifically, it may be the case that the LLN interface of the NOC-based 
DODAG root does not work but the one used for synchronizing with other 
NOC-based candidates works normally. In this scenario, simply exchanging 
DIOs between the DODAG root candidates need not detect the failure, in 
contrast to RNFD, which would monitor the actual LLN links.

All in all, I believe that to some extent RNFD can be beneficial even 
with ACP.

What is more, your remark actually got me thinking about Virtual DODAG 
Roots (as per https://tools.ietf.org/html/rfc6550#section-8.2.2.2), 
where multiple nodes, potentially NOC-based, coordinate to transparently 
and simultaneously (not in a primary-backup fashion) act as a single 
DODAG root. In such a deployment, RNFD also works but need not detect 
crashes of an individual node comprising the virtual root. This is, 
however, an expected behavior because, despite the crash of the node, 
the root as a whole continues to function. Depending on the deployment 
policies, RNFD may need to be configured with a different threshold, 
though. Consequently, I believe that virtual DODAG roots also need to be 
mentioned in the draft, which I forgot about. Thanks for the remark!

As for the comments below, I will try to apply them to the draft, 
together with addressing the previous issues, and get back to you when 
this has been done.

Best,
-- 
- Konrad Iwanicki.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 14 Apr 2021 14:47:59 +0000

Hello Konrad

At an abstract level I see your proposal as a form of BFD where the network assesses the liveliness of the root. The operation is done by a number of representatives that must agree that the root is gone. The draft does a good job at addressing the Byzantine problem once we know who the generals are, but it's unclear to me how they are elected and how they converse.

That's a family of questions around the issue of how we avoid false positive. Seems that the more sentinels the less of them. But the less efficient the algorithm is. 

- do the sentinels encompass all first hop nodes?
- how do we compute the right number of sentinels?
- do the sentinels needs direct connectivity to one another?
- how quick should the protocol react ? 
- I mean, if the root reboots, is that worth the hassle of breaking and forming the DODAG again?
- do the sentinels form a connected group ? how ? if not, what happens if one group loose connectivity to the root but the other does not?

Keep safe;

Pascal

> Sent: jeudi 8 avril 2021 23:20
> To: Routing Over Low power and Lossy networks <[email-masked]>; Pascal
> Thubert (pthubert) <pthubert=[email-masked]>
> benefit is that the DODAG structure is mostly maintained and that routing
> inside may persist.
> >
> >> Approximately a year ago, I joined the WG and advertised an extension
> >> to RPL that I had been working on for some time with a goal of
> >> describing it in a draft. Unfortunately, just when I got the
> >> necessary pointers and a few initial comments, the pandemic broke
> >> out. The resulting surge of professional and personal obligations
> >> made it literally impossible for me to participate in and, at some
> >> point, even follow the group's activities, for which I am sorry.
> >>

---

From: Konrad Iwanicki <[email-masked]>
Date: Tue, 20 Apr 2021 13:34:49 +0200

Hi Michael,

Below, you can find my replies to your detailed comments, which I 
promised in my previous e-mail.

> That is, the devices at rank "1", that hear the LBR's DIOs.

That would be useful. However, I am really bad at inventing names. Any 
ideas for a fitting one-word term?

Also, if you have better names for the two node roles, they may be worth 
considering because I am not perfectly satisfied with "sentinel" and 
"acceptor".

> it for that spot, and make it a section 4.1.

True. Will do that.

> Why not make this a function (hash?) of the short-IPv6 address or something?

Hash could work. However, the choice of the random function allows a 
node to become sentinel, then give up, then become sentinel again, and 
so on, possibly multiple times. Having a hash based on the short-IPv6 
address would allow for only one such transition, unless for instance 
the node kept an additional counter that was hashed together with the 
address.

> wireless and the wired side of the 6LBRs.

Indeed, RNFD can work with other link layers. L2 ACKs are only given as 
an example of an event that can be relevant to RNFD. In link-layers 
without ACKs, results from probing or other relevant events can be used 
(e.g., medium disconnection event). I tried to keep the example list 
brief, but perhaps more examples could be given for other underlying 
technologies?

Likewise, I was actually considering separating detection from 
verification but they are related as the same mechanisms can be used for 
both purposes. Therefore, ultimately they ended up in a single section.

> failure, or some kind of systematic long-cycle pathology.

Actually, the RNFD Option can be embedded into any control/data messages 
for which the DODAG ID and DODAG Version can be inferred unambiguously. 
In particular, in multi-hop messages, the option could even be updated 
and acted upon at each hop, which would speed up information 
propagation. The draft focuses on DIOs and DISs as they are basic 
messages that are exchanged irrespective of the current DODAG condition 
and existence of particular paths. Do you think this should be mentioned 
somewhere?

BTW. The root, if alive, sees that it is being observed and what the 
outcome of this observation is based on its local CFRCs.

> clear, and to save everyone else the time to find it.

Thanks, I did not know how to formulate this. I will correct the section.

> In particular, 7.2.4, and section 7.3.4 and 7.3.5 might be relevant.

Thanks for the pointer. I was not aware that such a RPL-oriented 
document exists. Gathering all major threats and possible 
counter-measures, which would otherwise had to be picked from various 
works in the literature, it seems extremely valuable for prospective 
RPL's adopters.

As to the particular sections you mentioned, RNFD essentially relies of 
DIO and DIS messages. Since these messages are broadcast, sinkhole 
attacks (7.3.4) are of limited threat (to the RNFD itself): for any two 
nodes, if there exists any path in the network (comprising L2-induced 
communication links and non-compromised nodes), then eventually CFRCs 
from one of the nodes will reach (indirectly, through merging) the other 
node, irrespective of the sinkholes that may attract routed L3 traffic. 
Wormhole attacks (7.3.5) in turn would speed up the propagation of CFRC 
updates, so they actually can help RNFD.

Therefore, in my view, the major threats are indeed those already 
mentioned in the draft, which are referred to as 
overclaiming/misclaiming in the RFC you pointed at (7.2.4). Looking 
again at the security section of the RNFD draft, I am leaning toward 
expanding it a bit. In any case, an advantage of RNFD is that its 
construction allows for detecting such attacks to some extent and 
disabling the algorithm if necessary (though under such attacks, RPL 
would likely have more problems on its own).

The preferred means of disabling and enabling the algorithm at runtime 
is actually one of the issues I would like to discuss with the WG but 
probably after I have addressed all other issues that you and Pascal 
have raised (I think Pascal's last e-mail is next).

Best regards,
-- 
- Konrad Iwanicki.

---

From: Konrad Iwanicki <[email-masked]>
Date: Wed, 21 Apr 2021 10:39:05 +0200

Hi Pascal,

Thanks for reading the draft in such a great depth!

A short answer to your questions: sentinel selection and other issues 
you mention are very much dependent on a particular deployment (i.e., 
network topology, application, other technologies used with RPL); RNFD 
thus focuses on providing mechanism for enforcing deployment-specific 
policies in that matter, including possibilities for dynamically 
changing the policies at runtime.

A much longer answer follows.

> At an abstract level I see your proposal as a form of BFD where the network assesses the liveliness of the root. The operation is done by a number of representatives that must agree that the root i…

This intuition is correct. Just one remark to be precise: the algorithm 
assumes no Byzantine nodes, merely ones that may have incorrect 
observations about the state of the DODAG root but otherwise follow the 
protocol.

> That's a family of questions around the issue of how we avoid false positive. Seems that the more sentinels the less of them. But the less efficient the algorithm is.

I think this intuition is by and large justified. However, it need not 
be correct formally, especially if one considers corner cases. Let me 
try to build up more intuition, which will hopefully also clarify some 
of my answers to your detailed questions.

To start with, as you pointed up above, the decision that the root is 
down is a collective one. It is based on observations of multiple 
sentinel nodes. Each observation regards the direct link between the 
corresponding sentinel and the root. The observations are communicated 
between nodes---both sentinels and acceptors---in CFRCs. A decision 
based on such accumulated observations can be made by any node: sentinel 
or acceptor.

It is important to note that "multiple" here means a number above some 
threshold, referred to in the draft as RNFD_CONSENSUS_THRESHOLD. The 
threshold should be reasonably large (e.g., more than 50%). However, it 
should not be too large (in particular, equal to 100%) because some 
sentinels may be dead as well or may be too slow detecting the failure.

Formally, this implies that false positives are unavoidable. For 
example, assume that you have N>=3 sentinels, your threshold is 51%, 1 
sentinel is certain that the root is up while the other N-1 sentinels 
claim the opposite, and the root is actually up and communicating with 
the 1 sentinel. In such a case, the N-1 sentinels claiming that the root 
is dead will outvote the 1 sentinel claiming otherwise and a global 
decision will be made that the root has crashed, which---formally---is a 
false positive irrespective of how large N is. What will happen is that, 
being able to communicate with the 1 sentinel, the root will learn the 
decision and rapidly initiate DODAG rebuilding by generating a new DODAG 
Version. In the new version, the N-1 old sentinels will likely not be 
sentinels anymore because they will not satisfy the necessary condition 
(unless their connectivity to the root is restored).

Are such false positives bad? A sentinel claims that the root is dead if 
and only if its link with the root seems to be down. If a significant 
number of sentinels (e.g., more than the aforementioned 50%) claim this, 
then something undesirable must have happened to the connectivity within 
the DODAG. Therefore, in practice, even if the root has not crashed, it 
may make a lot of sense to rebuild the DODAG to account for the 
connectivity changes, especially since RPL's rank assignment algorithms 
may preclude some nodes from assigning ranks significantly larger than 
their minimal ones.

Is there anything to be done to prevent such rebuilding from disrupting 
routing? First of all, if so many links are broken to make nodes believe 
that the root is dead, then routing is likely already significantly 
disrupted. Nevertheless, one may still want to avoid all nodes emptying 
their parent sets, which happens when RNFD's LORS transits to GLOBALLY 
DOWN. In this case, the root may act proactively, as mentioned in 
paragraph 2, Section 5.5 of the draft:

     It [the root] MAY also generate a new DODAG Version if fraction
     value(NegativeCFRC)/value(PositiveCFRC) approaches
     RNFD_CONSENSUS_THRESHOLD, so as to avoid potential interruptions
     to routing.

For example, if the fraction exceeds 50% or 80% of the aforementioned 
threshold. Also, additional solutions are possible to further alleviate 
the problem but I think we have never needed to implement them, and 
hence they are omitted in the draft.

So let's proceed to your detailed questions.

> - do the sentinels encompass all first hop nodes?

The formal answer is "not necessarily", which is what the draft states: 
to be sentinel a node must be a first-hop node but not every first-hop 
node has to be sentinel.

The practical answer is that if one can accommodate all such nodes as 
sentinels (see the next question), then why not.

> - how do we compute the right number of sentinels?

The formal answer is that an optimal selection of sentinels depends on a 
number of deployment-specific factors and may thus be extremely hard to 
compute.

Therefore, rather than an exact formula describing the number (and the 
placement) of sentinels, it is better to think in terms of trade-offs, 
precisely as in your intuition:
- on the one hand, the more sentinels and the higher the decision 
threshold, the more "confidence" one can feel about their decisions on 
the root's crashes being correct but
- on the other hand, the greater the overhead in that: the larger the 
CFRCs (which implies longer DIOs, possibly even fragmented), the more 
trickle timer resets, and potentially the more load on the root during 
suspicion verification.
Given this, ideally, to select root's neighbors acting as sentinels, one 
would do a thorough statistical analysis factoring in all major risks. 
This may also be too difficult, though.

My practical, experience-based recommendation for the sentinel selection 
procedure is thus roughly as follows:
1. Select the CFRC size such that the RNFD Option fits a DIO without 
causing too much overhead (especially to avoid fragmentation).
2. Let the root's neighbors become sentinels at random and gradually 
adapt their behavior such that PositiveCFRCs do not fill up (as 
described in Section 6) of the draft. More specifically,
- start with all neighbors having the possibility of becoming sentinels;
- if PositiveCFRCs do fill up (without a significant increase in 
NegativeCFRC), decrease the probability of becoming sentinel by half and 
issue a new DODAG version (this can be done autonomously by the 
individual nodes observing filling up of PositiveCFRC);
- repeat the last step unless satisfied.
3. Furthermore, if some of the root's neighbors tend to switch roles too 
often or have unstable links to the root, blacklist them from becoming 
sentinels (again, this can be done autonomously by the nodes -- they can 
self-blacklist).
4. Finally, if RNFD experiences too many false positives nevertheless 
(which at this point probably means that the root is poorly connected in 
general), simply disable the algorithm (never happened in our deployments).
To give some absolute numbers, I would aim at ~10, at most ~20 sentinels 
with stable links to the root. In the end, they are just representatives 
of the root's neighbors' population.

After going though this a few times, one will probably have a good 
setting of initial parameters for similar deployments and the particular 
technologies employed with RPL. In effect, one would have to fine-tune 
them only in extreme cases, like ultra-sparse or ultra-dense networks.

What I am trying to convey here is that sentinel selection is a matter 
of managing the network rather than a responsibility of the RNFD 
protocol itself. The protocol strives to provide only mechanisms that 
enable effective management by network administrators. Equipped with 
such tools, it is the administrators who will come up with the best 
management policies, which are inherently deployment-specific. What is 
more, the mechanisms provided by RNFD allow for having the policy 
enforcement automated to a large extent.

> - do the sentinels needs direct connectivity to one another?

No. The sentinels alone do not even need to form a connected graph on 
their own (decisions are made by sentinels or acceptors), which makes 
the algorithm really broadly applicable (including the aforementioned 
possibility of random sentinel selection and robustness to some of the 
security threats mentioned earlier by Michael).

> - how quick should the protocol react ?

This also depends on the particular technologies one uses RPL with. At 
worst, RNFD must react as soon as routing adjacency maintenance at a 
root's neighbor acting as sentinel detects that the link to the root is 
down. More aggressive approaches can be adopted though, especially since 
for some neighbor unreachability detection solutions, the precise 
convergence criteria need not be straightforward to infer.

> - I mean, if the root reboots, is that worth the hassle of breaking and forming the DODAG again?

This also depends on a particular deployment, the duration of the 
reboot, and other technologies that RPL is used with (e.g., how quickly 
a link failure is detected by routing adjacency maintenance). In our 
settings, an immediate LBR reboot could pass undetected, unless we did 
not want it to. In this context, I believe that one DODAG rebuilding due 
to an LBR reboot probably does not hurt. However, repeated reboots may 
indicate some problems with the LBR that may require attention, 
irrespective of whether RNFD is used or not.

> - do the sentinels form a connected group ? how ? if not, what happens if one group loose connectivity to the root but the other does not?

Ad 1.
No (see one of the previous answers).

Ad 2.
N/A

Ad 3.
To answer precisely, one would need to know the sizes of the groups with 
respect to the total number of sentinels and the decision threshold. In 
short, in a pessimistic scenario in which in addition to the crash of 
the root the whole network partitions into multiple groups none of which 
has enough sentinels to exceed the decision threshold, RNFD would not 
detect the crash in any of the groups; it would be detected with RPL's 
own mechanisms, which are much slower though (provided RPL is correctly 
configured).

To close this e-mail, I would like to emphasize that, as mentioned in 
the draft, RNFD is inherently probabilistic. It can significantly 
improve RPL's performance in a wide range of deployment settings. 
However, like for any other protocol, this range is not infinite, and 
beyond it, no gains will be observed. Similarly, like any other 
protocol, it may require some maintenance, but this maintenance can be 
largely automated. Finally, should such a need arise, RNFD can always be 
disabled at runtime.

Once again, thank you for your insightful questions Pascal.

Best regards,
-- 
- Konrad Iwanicki.