rfc9866v1.txt   rfc9866.txt 
skipping to change at line 103 skipping to change at line 103
variable qualities and support low data rates. Therefore, a variable qualities and support low data rates. Therefore, a
significant challenge that a routing protocol for LLNs has to address significant challenge that a routing protocol for LLNs has to address
is minimizing resource consumption without sacrificing reaction time is minimizing resource consumption without sacrificing reaction time
to network changes. to network changes.
One of the main design principles adopted in RPL to minimize node One of the main design principles adopted in RPL to minimize node
resource consumption is delegating much of the responsibility for resource consumption is delegating much of the responsibility for
routing to LLN Border Routers (LBRs). A network is organized into routing to LLN Border Routers (LBRs). A network is organized into
Destination-Oriented Directed Acyclic Graphs (DODAGs), each Destination-Oriented Directed Acyclic Graphs (DODAGs), each
corresponding to an LBR and having all its paths terminate at the corresponding to an LBR and having all its paths terminate at the
LBR. To this end, every node is dynamically assigned a rank LBR. To this end, every node is dynamically assigned a Rank
representing its distance to a given LBR, measured in some metric, representing its distance to a given LBR, measured in some metric,
with the LBR having the minimal rank, which reflects its role as the with the LBR having the minimal Rank, which reflects its role as the
DODAG root. The ranks allow each non-LBR node to select from among DODAG root. The Ranks allow each non-LBR node to select from among
its neighbors (i.e., nodes to which the node has links) those that its neighbors (i.e., nodes to which the node has links) those that
are closer to the LBR than the node itself (i.e., the node's parents are closer to the LBR than the node itself (i.e., the node's parents
in the graph). The resulting DODAG paths, consisting of the node- in the graph). The resulting DODAG paths, consisting of the node-
parent links, are utilized for routing packets upward to the LBR and parent links, are utilized for routing packets upward to the LBR and
outside the LLN. They are also used by nodes to periodically report outside the LLN. They are also used by nodes to periodically report
their connectivity upward to the LBR, which allows for directing their connectivity upward to the LBR, which allows for directing
packets downward from the LBR to these nodes (for instance, by means packets downward from the LBR to these nodes (e.g., by means of
of source routing [RFC6554]). All in all, not only do LBRs source routing [RFC6554]). All in all, not only do LBRs participate
participate in routing, but they also drive the process of DODAG in routing, but they also drive the process of DODAG construction and
construction and maintenance underlying the protocol. maintenance underlying the protocol.
To play this central role, LBRs are expected to be more capable than To play this central role, LBRs are expected to be more capable than
regular LLN nodes. They are assumed not to be constrained in regular LLN nodes. They are assumed not to be constrained in
computing power, memory, and energy, which often entails a more computing power, memory, and energy, which often entails a more
involved hardware-software architecture and tethered power supply. involved hardware-software architecture and tethered power supply.
However, this also makes them prone to failures, especially since it However, this also makes them prone to failures, especially since it
is often difficult to ensure a backup power supply for every LBR in is often difficult to ensure a backup power supply for every LBR in
large deployments. large deployments.
1.1. Effects of LBR Crashes 1.1. Effects of LBR Crashes
skipping to change at line 143 skipping to change at line 143
also degenerate as a result of DODAG repair attempts, which are bound also degenerate as a result of DODAG repair attempts, which are bound
to fail. In effect, routing inside the DODAG also becomes largely to fail. In effect, routing inside the DODAG also becomes largely
impossible. Consequently, it is desirable that an LBR crash be impossible. Consequently, it is desirable that an LBR crash be
detected by the nodes fast, so that they can leave the broken DODAG detected by the nodes fast, so that they can leave the broken DODAG
and join another one or trigger additional application- or and join another one or trigger additional application- or
deployment-dependent fallback mechanisms, thereby minimizing the deployment-dependent fallback mechanisms, thereby minimizing the
negative impact of the disconnection. negative impact of the disconnection.
Since all DODAG paths lead to the corresponding LBR, detecting its Since all DODAG paths lead to the corresponding LBR, detecting its
crash by a node entails dropping all parents and adopting an infinite crash by a node entails dropping all parents and adopting an infinite
rank, which reflects the node's inability to reach the dead LBR. Rank, which reflects the node's inability to reach the dead LBR.
Depending on the deployment settings, the node can then remain in Depending on the deployment settings, the node can then remain in
such a state, join a different DODAG, or even become the root of a such a state, join a different DODAG, or even become the root of a
floating DODAG. In any case, however, achieving this state for all floating DODAG. In any case, however, achieving this state for all
nodes is slow, can generate heavy traffic, and is difficult to nodes is slow, can generate heavy traffic, and is difficult to
implement correctly [Iwanicki16] [Paszkowska19] [Ciolkosz19]. implement correctly [Iwanicki16] [Paszkowska19] [Ciolkosz19].
To start with, tearing down all DODAG paths requires each of the dead To start with, tearing down all DODAG paths requires each of the dead
LBR's neighbors to detect that its link with the LBR is no longer up. LBR's neighbors to detect that its link with the LBR is no longer up.
Otherwise, any of the neighbors unaware of this fact can keep Otherwise, any of the neighbors unaware of this fact can keep
advertising a finite rank and can thus be other nodes' parent or advertising a finite Rank and can thus be other nodes' parent or
ancestor in the DODAG; such nodes will incorrectly believe they have ancestor in the DODAG; such nodes will incorrectly believe they have
a valid path to the dead LBR. Detecting a crash of a link by a node a valid path to the dead LBR. Detecting a crash of a link by a node
normally happens when the node has sufficiently observed many normally happens when the node has observed a sufficient number of
forwarding failures over the link. Therefore, considering the low- forwarding failures over the link. Therefore, considering the low-
data-rate applications of LLNs, the period from the crash to the data-rate applications of LLNs, the period from the crash to the
moment of eliminating the last link to the dead LBR from the DODAG moment of eliminating the last link to the dead LBR from the DODAG
may be long. Subsequently, learning by all nodes that none of their may be long. Subsequently, learning by all nodes that none of their
links can form any path leading to the dead LBR also adds latency, links can form any path leading to the dead LBR also adds latency,
partly due to parent changes that the nodes independently perform in partly due to parent changes that the nodes independently perform in
attempts to repair their broken paths locally. Since a non-LBR node attempts to repair their broken paths locally. Since a non-LBR node
has only local knowledge of the network, potentially inconsistent has only local knowledge of the network, potentially inconsistent
with that of other nodes, such parent changes often produce paths with that of other nodes, such parent changes often produce paths
containing loops, which have to be broken before all nodes can containing loops, which have to be broken before all nodes can
conclude that no path to the dead LBR exists globally. Even with conclude that no path to the dead LBR exists globally. Even with
RPL's dedicated loop detection mechanisms [RFC6553], this also RPL's dedicated loop detection mechanisms [RFC6553], this also
requires traffic and hence time. Finally, switching a parent or requires traffic and hence time. Finally, switching a parent or
discovering a loop can also generate cascaded bursts of control discovering a loop can also generate cascaded bursts of control
traffic, owing to the adaptive Trickle algorithm for exchanging DODAG traffic, owing to the adaptive Trickle algorithm for exchanging DODAG
information [RFC6202]. Overall, the behavior of the network when information [RFC6206]. Overall, the behavior of the network when
handling an LBR crash is highly suboptimal, thereby not being in line handling an LBR crash is highly suboptimal, thereby not being in line
with RPL's goals of minimizing resource consumption and reaction with RPL's goals of minimizing resource consumption and reaction
latencies. latencies.
1.2. Design Principles 1.2. Design Principles
To address this issue, this document proposes an extension to RPL, To address this issue, this document proposes an extension to RPL,
dubbed the "Root Node Failure Detector (RNFD)". To minimize the time dubbed the "Root Node Failure Detector (RNFD)". To minimize the time
and traffic required to handle an LBR crash, the RNFD algorithm and traffic required to handle an LBR crash, the RNFD algorithm
adopts the following design principles, derived directly from the adopts the following design principles, derived directly from the
skipping to change at line 214 skipping to change at line 214
scenarios, RNFD's operation may result in false negatives, but these scenarios, RNFD's operation may result in false negatives, but these
situations are peculiar and will eventually be handled by RPL's own situations are peculiar and will eventually be handled by RPL's own
aforementioned mechanisms. Likewise, in some scenarios, notably aforementioned mechanisms. Likewise, in some scenarios, notably
involving highly unstable links, false positives may occur, but they involving highly unstable links, false positives may occur, but they
can be alleviated as well. In any case, the principles also can be alleviated as well. In any case, the principles also
guarantee that RNFD can be deactivated at any time if needed, in guarantee that RNFD can be deactivated at any time if needed, in
which case RPL's operation is unaffected. which case RPL's operation is unaffected.
1.3. Other Solutions 1.3. Other Solutions
Given the consequences of LBR failures, if possible, it is also worth Given the consequences of LBR failures, it is also worth considering
considering other solutions to the problem. More specifically, power other solutions to the problem. More specifically, power outages can
outages can be alleviated by provisioning redundant power sources or be alleviated by provisioning redundant power sources or emergency
emergency batteries. Likewise, RPL's so-called virtual DODAG roots batteries. Likewise, RPL's so-called virtual DODAG roots can help
can help tolerate some failures of individual LBRs. tolerate some failures of individual LBRs.
As mentioned previously, RNFD has been designed to be largely As mentioned previously, RNFD has been designed to be largely
independent of those solutions; that is, rather than aiming to be independent of those solutions; that is, rather than aiming to be
their replacement, RNFD can complement them. In particular, the their replacement, RNFD can complement them. In particular, the
operation of RNFD with different variants of virtual DODAG roots is operation of RNFD with different variants of virtual DODAG roots is
covered in Section 6.2. covered in Section 6.2.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
skipping to change at line 325 skipping to change at line 325
| +---------------------------+ 5 | | +---------------------------+ 5 |
+--------------------------------------------------+ +--------------------------------------------------+
Figure 1: RNFD States and Transitions Figure 1: RNFD States and Transitions
To begin with, when any node joins a DODAG Version, the DODAG root To begin with, when any node joins a DODAG Version, the DODAG root
must appear alive, so the node initializes RNFD with its LORS equal must appear alive, so the node initializes RNFD with its LORS equal
to "UP". For a properly working DODAG root, the node remains in to "UP". For a properly working DODAG root, the node remains in
state "UP". state "UP".
However, when a node (acting as a Sentinel) starts suspecting that However, when a node acting as a Sentinel starts suspecting that the
the root may have crashed, it changes its LORS to "SUSPECTED DOWN" root may have crashed, it changes its LORS to "SUSPECTED DOWN"
(transition 1 in Figure 1). The transition from "UP" to "SUSPECTED (transition 1 in Figure 1). The transition from "UP" to "SUSPECTED
DOWN" can happen based on the node's observations at either the data DOWN" can happen based on the node's observations at either the data
plane (for instance, link-layer triggers about missing hop-by-hop plane (e.g., link-layer triggers about missing hop-by-hop
acknowledgments for packets forwarded over the node's link to the acknowledgments for packets forwarded over the node's link to the
root) or at the control plane (for example, a significant growth in root) or at the control plane (e.g., a significant growth in the
the number of Sentinels already suspecting the root to be dead). In number of Sentinels already suspecting the root to be dead). In
state "SUSPECTED DOWN", the Sentinel node may verify its suspicion state "SUSPECTED DOWN", the Sentinel node may verify its suspicion
and/or inform other nodes about the suspicion. When this has been and/or inform other nodes about the suspicion. When this has been
done, it changes its LORS to "LOCALLY DOWN" (transition 2a). In some done, it changes its LORS to "LOCALLY DOWN" (transition 2a). In some
cases, the verification need not be performed, and as an cases, the verification need not be performed, and as an
optimization, a direct transition from "UP" to "LOCALLY DOWN" optimization, a direct transition from "UP" to "LOCALLY DOWN"
(transition 2b) can be done instead. (transition 2b) can be done instead.
If a sufficient number of Sentinels have their LORS equal to "LOCALLY If a sufficient number of Sentinels have their LORS equal to "LOCALLY
DOWN", all nodes (Sentinels and Acceptors) consent globally that the DOWN", all nodes (Sentinels and Acceptors) consent globally that the
DODAG root must have crashed and set their LORS to "GLOBALLY DOWN", DODAG root must have crashed and set their LORS to "GLOBALLY DOWN",
irrespective of the previous value (transitions 3a, 3b, and 3c). irrespective of the previous value (transitions 3a, 3b, and 3c).
State "GLOBALLY DOWN" is terminal in that the only transition any State "GLOBALLY DOWN" is terminal in that the only transition any
node can perform from this to another state (transition 5) takes node can perform from this to another state (transition 5) takes
place when the node joins a new DODAG version. When a node is in place when the node joins a new DODAG Version. When a node is in
state "GLOBALLY DOWN", RNFD forces RPL to maintain an infinite rank state "GLOBALLY DOWN", RNFD forces RPL to maintain an infinite Rank
and no parent, thereby preventing routing packets upward in the and no parent, thereby preventing routing packets upward in the
DODAG. In other words, this state represents a situation in which DODAG. In other words, this state represents a situation in which
all non-root nodes agree that the current DODAG version is unusable; all non-root nodes agree that the current DODAG Version is unusable;
hence, to recover, the root has to give a proof of being alive by hence, to recover, the root has to give a proof of being alive by
initiating a new DODAG Version. initiating a new DODAG Version.
In contrast, if a node (either a Sentinel or Acceptor) is in state In contrast, if a node (either a Sentinel or Acceptor) is in state
"UP", RNFD does not influence RPL's packet forwarding; a node can "UP", RNFD does not influence RPL's packet forwarding; a node can
route packets upward if it has a parent. The same is true for states route packets upward if it has a parent. The same is true for states
"SUSPECTED DOWN" and "LOCALLY DOWN", attainable only by Sentinels. "SUSPECTED DOWN" and "LOCALLY DOWN", attainable only by Sentinels.
Finally, while in any of the two states, a Sentinel node may observe Finally, while in any of the two states, a Sentinel node may observe
some activity of the DODAG root and hence decide that its suspicion some activity of the DODAG root and hence decide that its suspicion
is a mistake. In such a case, it returns to state "UP" (transitions is a mistake. In such a case, it returns to state "UP" (transitions
skipping to change at line 477 skipping to change at line 477
infinity()) always equals infinity(). infinity()) always equals infinity().
There are many algorithmic structures that can provide the There are many algorithmic structures that can provide the
aforementioned properties of CFRC. Although in principle RNFD does aforementioned properties of CFRC. Although in principle RNFD does
not rely on any specific one, the option adopts so-called linear not rely on any specific one, the option adopts so-called linear
counting [Whang90]. counting [Whang90].
4.2. Format of the Option 4.2. Format of the Option
The format of the RNFD Option conforms to the generic format of RPL The format of the RNFD Option conforms to the generic format of RPL
Control Message Options: Control Message Options (see Section 6.7.1 of [RFC6550]):
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 0x0E | Option Length | | | Type = 0x0E | Option Length | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| | | |
+ + + +
| PosCFRC, NegCFRC (Variable Length*) | | PosCFRC, NegCFRC (Variable Length*) |
. . . .
skipping to change at line 597 skipping to change at line 597
3. a neighbor entry for the DODAG root is present in RPL's DODAG 3. a neighbor entry for the DODAG root is present in RPL's DODAG
parent set; and parent set; and
4. the neighbor is considered reachable via its link-local IPv6 4. the neighbor is considered reachable via its link-local IPv6
address. address.
A role change also requires appropriate updates to LORS and CFRCs, so A role change also requires appropriate updates to LORS and CFRCs, so
that the node is properly accounted for. More specifically, when that the node is properly accounted for. More specifically, when
changing its role from Acceptor to Sentinel, the node MUST add itself changing its role from Acceptor to Sentinel, the node MUST add itself
to its PositiveCFRC as follows. It MUST generate a new CFRC value, to its PositiveCFRC as follows. It MUST generate a new CFRC value,
selfc = self(), and it MUST replace its PositiveCFRC (denoted oldpc) selfc = self(), and it MUST replace its PositiveCFRC, denoted oldpc,
with newpc = merge(oldpc, selfc). In contrast, the effects of a with newpc = merge(oldpc, selfc). In contrast, the effects of a
switch from Sentinel to Acceptor vary depending on the node's value switch from Sentinel to Acceptor vary depending on the node's value
of LORS before the switch: of LORS before the switch:
* For "GLOBALLY DOWN", the node MUST NOT modify its LORS, * For "GLOBALLY DOWN", the node MUST NOT modify its LORS,
PositiveCFRC, and NegativeCFRC. PositiveCFRC, and NegativeCFRC.
* For "LOCALLY DOWN", the node MUST set its LORS to "UP" but MUST * For "LOCALLY DOWN", the node MUST set its LORS to "UP" but MUST
NOT modify its PositiveCFRC and NegativeCFRC. NOT modify its PositiveCFRC and NegativeCFRC.
* For "UP" and "SUSPECTED DOWN", the node MUST set its LORS to "UP" * For "UP" and "SUSPECTED DOWN", the node MUST set its LORS to "UP"
and MUST NOT modify its PositiveCFRC, but it MUST add itself to and MUST NOT modify its PositiveCFRC, but the node MUST add itself
NegativeCFRC. That is, it MUST replace its NegativeCFRC (denoted to NegativeCFRC, by replacing its NegativeCFRC, denoted oldnc,
oldnc) with newnc = merge(oldnc, selfc), where selfc is the with newnc = merge(oldnc, selfc), where selfc is the counter
counter generated with self() when the node last added itself to generated with self() when the node last added itself to its
its PositiveCFRC. PositiveCFRC.
5.2. Detecting and Verifying Problems with the DODAG Root 5.2. Detecting and Verifying Problems with the DODAG Root
Only nodes that are Sentinels take an active part in detecting Only nodes that are Sentinels take an active part in detecting
crashes of the DODAG root; Acceptors just disseminate their crashes of the DODAG root; Acceptors just disseminate their
observations, reflected in the CFRCs. observations, reflected in the CFRCs.
The DODAG root monitoring SHOULD be based on both internal inputs, The DODAG root monitoring SHOULD be based on both internal inputs,
notably the values of CFRCs and LORS, and external inputs, such as notably the values of CFRCs and LORS, and external inputs, such as
triggers from RPL and other protocols. External input monitoring triggers from RPL and other protocols. External input monitoring
skipping to change at line 636 skipping to change at line 636
In particular, it is RECOMMENDED that RNFD be directly notified of In particular, it is RECOMMENDED that RNFD be directly notified of
events relevant to the routing adjacency maintenance mechanisms on events relevant to the routing adjacency maintenance mechanisms on
which RPL relies, such as Layer 2 (L2) triggers [RFC5184] or the which RPL relies, such as Layer 2 (L2) triggers [RFC5184] or the
Neighbor Unreachability Detection [RFC4861] mechanism. In addition, Neighbor Unreachability Detection [RFC4861] mechanism. In addition,
depending on the underlying protocol stack, there may be other depending on the underlying protocol stack, there may be other
potential sources of such events, for instance, neighbor potential sources of such events, for instance, neighbor
communication overhearing. In any case, only events concerning the communication overhearing. In any case, only events concerning the
DODAG root need to be monitored. For example, RNFD can conclude that DODAG root need to be monitored. For example, RNFD can conclude that
there may be problems with the DODAG root if it observes a lack of there may be problems with the DODAG root if it observes a lack of
multiple consecutive L2 acknowledgments for packets transmitted by multiple consecutive L2 acknowledgments for packets transmitted by
the node via the link to the DODAG root. Internally, it is the node via the link to the DODAG root. Internally, in turn, it is
RECOMMENDED that RNFD take action whenever there is a change to its RECOMMENDED that RNFD take action whenever there is a change to its
local CFRCs, so that a node can have a chance to participate in local CFRCs, so that a node can have a chance to participate in
detecting potential problems even when normally it would not exchange detecting potential problems even when normally it would not exchange
packets over the link with the DODAG root during some period. In packets over the link with the DODAG root during some period. In
particular, RNFD SHOULD conclude that there may be problems with the particular, RNFD SHOULD conclude that there may be problems with the
DODAG root when the fraction value(NegativeCFRC)/value(PositiveCFRC) DODAG root when the fraction value(NegativeCFRC)/value(PositiveCFRC)
has grown by at least RNFD_SUSPICION_GROWTH_THRESHOLD since the node has grown by at least RNFD_SUSPICION_GROWTH_THRESHOLD since the node
last set its LORS to "UP". last set its LORS to "UP".
Whenever its LORS is set to "UP" and RNFD concludes (based on either Whenever, having its LORS set to "UP", RNFD concludes (based on
external or internal inputs) that there may be problems with the link either external or internal inputs) that there may be problems with
with the DODAG root, it MUST set its LORS either to "SUSPECTED DOWN" the link with the DODAG root, it MUST set its LORS either to
or, as an optimization, to "LOCALLY DOWN". "SUSPECTED DOWN" or, as an optimization, to "LOCALLY DOWN".
The "SUSPECTED DOWN" value of LORS is temporary: its aim is to give The "SUSPECTED DOWN" value of LORS is temporary: its aim is to give
RNFD an additional opportunity to verify whether the link with the RNFD an additional opportunity to verify whether the link with the
DODAG root is indeed down. Depending on the outcome of such DODAG root is indeed down. Depending on the outcome of such
verification, RNFD MUST set its LORS to either "UP", if the link has verification, RNFD MUST set its LORS to either "UP", if the link has
been confirmed not to be down, or "LOCALLY DOWN", otherwise. The been confirmed not to be down, or "LOCALLY DOWN", otherwise. The
verification can be performed, for example, by transmitting RPL DIS verification can be performed, for example, by transmitting RPL DIS
or ICMPv6 Echo Request messages to the DODAG root's link-local IPv6 or ICMPv6 Echo Request messages to the DODAG root's link-local IPv6
address and expecting replies confirming that the root is up and address and expecting replies confirming that the root is up and
reachable through the link. Care should be taken not to overload the reachable through the link. Care should be taken not to overload the
skipping to change at line 680 skipping to change at line 680
For consistency with RPL, when detecting potential problems with the For consistency with RPL, when detecting potential problems with the
DODAG root, RNFD also must make use of RPL's independent knowledge. DODAG root, RNFD also must make use of RPL's independent knowledge.
More specifically, a node MUST switch its LORS from "UP" or More specifically, a node MUST switch its LORS from "UP" or
"SUSPECTED DOWN" directly to "LOCALLY DOWN" if a neighbor entry for "SUSPECTED DOWN" directly to "LOCALLY DOWN" if a neighbor entry for
the DODAG root is removed from RPL's DODAG parent set or the neighbor the DODAG root is removed from RPL's DODAG parent set or the neighbor
ceases to be considered reachable via its link-local IPv6 address. ceases to be considered reachable via its link-local IPv6 address.
Finally, while having its LORS already equal to "LOCALLY DOWN", a Finally, while having its LORS already equal to "LOCALLY DOWN", a
node may make an observation confirming that its link with the DODAG node may make an observation confirming that its link with the DODAG
root is actually up. In such a case, it SHOULD set its LORS back to root is actually up. In such a case, it SHOULD set its LORS back to
"UP" but MUST NOT do this before the previous conditions 2-4 "UP" but MUST NOT do this before conditions 2-4 in Section 5.1, which
necessary for a node to change its role from Acceptor to Sentinel all are necessary for a node to change its role from Acceptor to
hold (see Section 5.1). Sentinel, all hold.
To appropriately account for the node's observations on the state of To appropriately account for the node's observations on the state of
the DODAG root, the aforementioned LORS transitions are accompanied the DODAG root, the aforementioned LORS transitions are accompanied
by changes to the node's local CFRCs as follows. Transitions between by changes to the node's local CFRCs as follows. Transitions between
"UP" and "SUSPECTED DOWN" do not affect either of the two CFRCs. "UP" and "SUSPECTED DOWN" do not affect either of the two CFRCs. In
During a switch from "UP" or "SUSPECTED DOWN" to "LOCALLY DOWN", the contrast, during a switch from "UP" or "SUSPECTED DOWN" to "LOCALLY
node MUST add itself to its NegativeCFRC, as explained previously. DOWN", the node MUST add itself to its NegativeCFRC, as explained
By symmetry, if there is a transition from "LOCALLY DOWN" to "UP", previously. By symmetry, if there is a transition from "LOCALLY
the node MUST add itself to its PositiveCFRC, again, as explained DOWN" to "UP", the node MUST add itself to its PositiveCFRC, as
previously. explained previously.
Such changes to a node's local CFRCs, if performed repeatedly due to Such changes to a node's local CFRCs, if performed repeatedly due to
incorrect decisions regarding the status of the node's link with the incorrect decisions regarding the status of the node's link with the
DODAG root, may lead to those CFRCs becoming saturated. An DODAG root, may lead to those CFRCs becoming saturated. An
implementation should thus try to minimize false-positive transitions implementation should thus try to minimize false-positive transitions
from "UP" and "SUSPECTED DOWN" to "LOCALLY DOWN". The exact approach from "UP" and "SUSPECTED DOWN" to "LOCALLY DOWN". The exact approach
depends on the specific solutions employed for assessing the state of depends on the specific solutions employed for assessing the state of
a link. For instance, one can utilize additional mechanisms for a link. For instance, one can utilize additional mechanisms for
increasing the confidence of individual decisions, such as during the increasing the confidence of individual decisions, such as during the
aforementioned verification in the "SUSPECTED DOWN" state, or can aforementioned verification in the "SUSPECTED DOWN" state, or can
skipping to change at line 813 skipping to change at line 813
to the current DODAG Version. to the current DODAG Version.
When RNFD at a node is initially inactive for a DODAG Version, the When RNFD at a node is initially inactive for a DODAG Version, the
node MUST NOT attach any RNFD Option to the messages it sends (in node MUST NOT attach any RNFD Option to the messages it sends (in
particular, because it may not know the desired CFRC length; see particular, because it may not know the desired CFRC length; see
Section 5.6). When the protocol has been explicitly deactivated, the Section 5.6). When the protocol has been explicitly deactivated, the
node MAY also decide not to attach the option to its outgoing node MAY also decide not to attach the option to its outgoing
messages. However, it is RECOMMENDED that it send a sufficient messages. However, it is RECOMMENDED that it send a sufficient
number of messages with the option to the link-local all-RPL-nodes number of messages with the option to the link-local all-RPL-nodes
multicast IPv6 address to allow its neighbors to learn that RNFD has multicast IPv6 address to allow its neighbors to learn that RNFD has
been deactivated in the current DODAG version. In particular, it MAY been deactivated in the current DODAG Version. In particular, it MAY
reset its Trickle timer to this end but MAY also use some reactive reset its Trickle timer to this end but MAY also use some reactive
mechanisms. For example, it MAY reply with a unicast DIO or DIS mechanisms. For example, it might reply with a unicast DIO or DIS
containing the RNFD Option with no CFRCs to a message from a neighbor containing the RNFD Option with no CFRCs to a message from a neighbor
that contains the option with some CFRCs, as such a neighbor appears that contains the option with some CFRCs, as such a neighbor appears
not to have learned about the deactivation of RNFD. not to have learned about the deactivation of RNFD.
5.6. Processing CFRCs of Incompatible Lengths 5.6. Processing CFRCs of Incompatible Lengths
The merge() and compare() operations on CFRCs require both arguments The merge() and compare() operations on CFRCs require both arguments
to be compatible, that is, to have the same bit length. However, the to be compatible, that is, to have the same bit length. However, the
processing rules for the RNFD Option (see Section 4.2) do not processing rules for the RNFD Option (see Section 4.2) do not
necessitate this. This fact is made use of not only in the necessitate this. This fact is made use of not only in the
skipping to change at line 856 skipping to change at line 856
option and set the CFRCs as follows: option and set the CFRCs as follows:
* If the node's LORS is "GLOBALLY DOWN", then both of its local * If the node's LORS is "GLOBALLY DOWN", then both of its local
CFRCs MUST be set to infinity(). CFRCs MUST be set to infinity().
* Otherwise, they both MUST be set to zero(), and the node MUST * Otherwise, they both MUST be set to zero(), and the node MUST
account for itself in so initialized CFRCs. More specifically, if account for itself in so initialized CFRCs. More specifically, if
the node is a Sentinel, then it MUST add itself to its the node is a Sentinel, then it MUST add itself to its
PositiveCFRC, as detailed previously. In addition, if its LORS is PositiveCFRC, as detailed previously. In addition, if its LORS is
"LOCALLY DOWN", then it MUST also add itself to its NegativeCFRC, "LOCALLY DOWN", then it MUST also add itself to its NegativeCFRC,
again, as explained previously. Finally, the node MUST perform as explained previously. Finally, the node MUST perform merges of
merges of its local CFRCs and the ones received in the option (see its local CFRCs and the ones received in the option (see
Section 5.3) and MAY reset its Trickle timer. Section 5.3) and MAY reset its Trickle timer.
In contrast, if the node is unable to extend its local CFRCs, for In contrast, if the node is unable to extend its local CFRCs, for
example, because it lacks resources, then it MUST stop participating example, because it lacks resources, then it MUST stop participating
in RNFD. That is, until it joins a new DODAG Version, it MUST NOT in RNFD. That is, until it joins a new DODAG Version, it MUST NOT
send the RNFD Option and MUST ignore this option in received send the RNFD Option and MUST ignore this option in received
messages. messages.
A DODAG root node can be requested to increase the bit length of its A DODAG root node can be requested to increase the bit length of its
CFRCs externally, as part of the management policies (see CFRCs externally, as part of the management policies (see
skipping to change at line 915 skipping to change at line 915
The following is a summary of RNFD's constants: The following is a summary of RNFD's constants:
RNFD_CONSENSUS_THRESHOLD: A threshold concerning the value of the RNFD_CONSENSUS_THRESHOLD: A threshold concerning the value of the
fraction value(NegativeCFRC)/value(PositiveCFRC). If the value at fraction value(NegativeCFRC)/value(PositiveCFRC). If the value at
a Sentinel or Acceptor node reaches the threshold, then the node's a Sentinel or Acceptor node reaches the threshold, then the node's
LORS is set to "GLOBALLY DOWN", which implies that consensus has LORS is set to "GLOBALLY DOWN", which implies that consensus has
been reached on the DODAG root node being down (see Section 5.3). been reached on the DODAG root node being down (see Section 5.3).
The default value of the threshold is 0.51, which indicates that a The default value of the threshold is 0.51, which indicates that a
majority of Sentinels must consider the root to be down to reach majority of Sentinels must consider the root to be down to reach
the consensus. In general, the higher the value, the longer the the consensus. In general, when the value is higher, the
detection period but the lower the risk of false positives. detection period is longer, but the risk of false positives is
lower.
RNFD_SUSPICION_GROWTH_THRESHOLD: A threshold concerning the value of RNFD_SUSPICION_GROWTH_THRESHOLD: A threshold concerning the value of
the fraction value(NegativeCFRC)/value(PositiveCFRC). If the the fraction value(NegativeCFRC)/value(PositiveCFRC). If the
value at a Sentinel node grows at least by this threshold since value at a Sentinel node grows at least by this threshold since
the time the node's LORS was last set to "UP", then the node's the time the node's LORS was last set to "UP", then the node's
LORS is set to "SUSPECTED DOWN" or "LOCALLY DOWN", which implies LORS is set to "SUSPECTED DOWN" or "LOCALLY DOWN", which implies
that the node starts suspecting or assumes a crash of the DODAG that the node starts suspecting or assumes a crash of the DODAG
root (see Section 5.2). The higher the value, the longer the root (see Section 5.2). When the value is higher, the duration of
duration of detecting true crashes but the lower the risk of detecting true crashes is longer, but the risk of increased
increased traffic due to verifying false suspicions. The default traffic due to verifying false suspicions is lower. The default
value of the threshold is 0.12, which in sparse networks (up to 8 value of the threshold is 0.12, which in sparse networks (up to 8
neighbors per node) triggers a suspicion at a Sentinel node after neighbors per node) triggers a suspicion at a Sentinel node after
just one other Sentinel starts considering the root as dead, while just one other Sentinel starts considering the root as dead, while
being gradually more conservative in denser networks. being gradually more conservative in denser networks.
RNFD_CFRC_SATURATION_THRESHOLD: A threshold concerning the RNFD_CFRC_SATURATION_THRESHOLD: A threshold concerning the
percentage of bits set to 1 in a CFRC, c. If the percentage for c percentage of bits set to 1 in a CFRC, c. If the percentage for c
is equal to or greater than this threshold, then saturated(c) is equal to or greater than this threshold, then saturated(c)
returns TRUE, which hints the DODAG root to generate a new DODAG returns TRUE, which hints the DODAG root to generate a new DODAG
Version or increase the bit length of the CFRCs (see Section 5.4). Version or increase the bit length of the CFRCs (see Section 5.4).
The default value of the threshold is 0.63. The higher the value, The default value of the threshold is 0.63. When the value is
the higher the probability of bit collisions and hence the more higher, the probability of bit collisions is higher, and the
erratic the results of function value(c) may be. results of function value(c) may thus be more erratic.
The means of configuring the constants at individual nodes are The means of configuring the constants at individual nodes are
outside the scope of this document. outside the scope of this document.
6. Manageability Considerations 6. Manageability Considerations
RNFD is largely self-managed, with the exception of protocol RNFD is largely self-managed, with the exception of protocol
activation and deactivation, as well as node role assignment and the activation and deactivation, as well as node role assignment and the
related CFRC size adjustment, for which only the aforementioned related CFRC size adjustment, for which only the aforementioned
mechanisms are defined, so as to enable adopting deployment-specific mechanisms are defined, so as to enable adopting deployment-specific
policies. This section discusses the manageability issues. policies. This section discusses the manageability issues.
6.1. Role Assignment and CFRC Size Adjustment 6.1. Role Assignment and CFRC Size Adjustment
One approach to node role and CFRC size selection is to manually One approach to node role and CFRC size selection is to manually
designate specific nodes as Sentinels in RNFD, assuming that they designate specific nodes as Sentinels in RNFD, assuming that they
will have chances to satisfy the necessary conditions for attaining will have chances to satisfy the necessary conditions for attaining
this role (see Section 5.1), and fixing the CFRC bit length to this role (see Section 5.1), and to fix the CFRC bit length to
accommodate these nodes. accommodate these nodes.
Another approach is to automate the selection process. In principle, Another approach is to automate the selection process. In principle,
any node satisfying the necessary conditions for becoming a Sentinel any node satisfying the necessary conditions for becoming a Sentinel
(see Section 5.1) can attain this role. However, in networks where (see Section 5.1) can attain this role. However, in networks where
the DODAG root node has many neighbors, this approach may lead to the DODAG root node has many neighbors, this approach may lead to
saturated(PositiveCFRC) quickly becoming TRUE, which may degrade saturated(PositiveCFRC) quickly becoming TRUE, which may degrade
RNFD's performance without additional measures. This issue can be RNFD's performance without additional measures. This issue can be
handled with a probabilistic solution: if PositiveCFRC becomes handled with a probabilistic solution: if PositiveCFRC becomes
saturated with little or no increase in NegativeCFRC, then a new saturated with little or no increase in NegativeCFRC, then a new
DODAG Version can be issued, and a node satisfying the necessary DODAG Version can be issued, and a node satisfying the necessary
conditions can become a Sentinel in this version only with conditions can become a Sentinel in this version only with
probability 1/2. This process can be continued with the probability probability 1/2. This process can be continued with the probability
being halved in each new DODAG Version until PositiveCFRC is no being halved in each new DODAG Version until PositiveCFRC is no
longer quickly saturated. Another solution is to increase, longer quickly saturated. Another solution is to increase,
potentially multiple times, the bit length of the CFRCs by the DODAG potentially multiple times, the bit length of the CFRCs by the DODAG
root if PositiveCFRC becomes saturated with little or no growth in root if PositiveCFRC becomes saturated with little or no growth in
NegativeCFRC. This does not require issuing a new DODAG Version but NegativeCFRC. This does not require issuing a new DODAG Version but
lengthens the RNFD Option. In this way, again, a sufficient bit lengthens the RNFD Option. In this way, a sufficient bit length can
length can be dynamically discovered, or the root can conclude that a be dynamically discovered, or the root can conclude that a given bit
given bit length is excessive for (some) nodes and resort to the length is excessive for (some) nodes and resort to the previous
previous solution. Increasing the bit length can be done, for solution. Increasing the bit length can be done, for instance, by
instance, by doubling it, respecting the condition that it has to be doubling it, respecting the condition that it has to be a prime
a prime number (see Section 4.2). number (see Section 4.2).
In either of the solutions, Sentinel nodes should preferably be In either of the solutions, Sentinel nodes should preferably be
stable themselves and have stable links to the DODAG root. stable themselves and have stable links to the DODAG root.
Otherwise, they may often exhibit LORS transitions between "UP" and Otherwise, they may often exhibit LORS transitions between "UP" and
"LOCALLY DOWN" or switches between Acceptor and Sentinel roles, which "LOCALLY DOWN" or switches between Acceptor and Sentinel roles, which
gradually saturates CFRCs. As a mitigation, the number of such gradually saturates CFRCs. As a mitigation, the number of such
transitions and switches per node MAY be limited; however, having transitions and switches per node MAY be limited; however, having
Sentinels be stable SHOULD be preferred. Sentinels be stable SHOULD be preferred.
6.2. Virtual DODAG Roots 6.2. Virtual DODAG Roots
skipping to change at line 1016 skipping to change at line 1017
actual roots of the DODAG, all advertising the same Rank in the actual roots of the DODAG, all advertising the same Rank in the
DODAG. When some of the nodes fail, the other nodes may or may DODAG. When some of the nodes fail, the other nodes may or may
not react in any specific way. In other words, at any time, more not react in any specific way. In other words, at any time, more
than one node can be the actual root. than one node can be the actual root.
In the first realization, RNFD's operation is largely unaffected. In the first realization, RNFD's operation is largely unaffected.
The necessary conditions for a node to become a Sentinel The necessary conditions for a node to become a Sentinel
(Section 5.1) guarantee that only the current primary root node is (Section 5.1) guarantee that only the current primary root node is
monitored by the protocol. This SHOULD be taken into account in the monitored by the protocol. This SHOULD be taken into account in the
policies for node role assignment, CFRC size selection, and, policies for node role assignment, CFRC size selection, and,
possibly, the setting of the two thresholds (Section 5.8). Moreover, possibly, the setting of the three thresholds (Section 5.8).
when a new primary has been elected, a new DODAG Version MUST be Moreover, when a new primary has been elected, a new DODAG Version
issued to avoid polluting CFRCs with observations on the previous MUST be issued to avoid polluting CFRCs with observations on the
primary. previous primary.
In the second realization, the fact that the virtual root consists of In the second realization, the fact that the virtual root consists of
multiple nodes is transparent to RNFD. Therefore, employing RNFD in multiple nodes is transparent to RNFD. Therefore, employing RNFD in
such a setting can be beneficial only if the nodes comprising the such a setting can be beneficial only if the nodes comprising the
virtual root may suffer from correlated crashes, for instance, due to virtual root may suffer from correlated crashes, for instance, due to
global power outages. global power outages.
6.3. Monitoring 6.3. Monitoring
For monitoring the operation of RNFD, its implementation SHOULD For monitoring the operation of RNFD, its implementation SHOULD
provide the following information about a node: provide the following information about a node:
* whether the protocol is active, and * whether the protocol is active, and
* whether LORS is "GLOBALLY DOWN". * whether LORS is "GLOBALLY DOWN".
This information is accompanied by the recommended monitoring This information MUST be accompanied by the monitoring parameters
parameters provided by RPL itself [RFC6550], notably the DODAG defined by RPL [RFC6550], including at least the DODAG Version Number
Version number and the Rank. To offer even finer-grained visibility and the Rank. To offer even finer-grained visibility into RNFD's
into RNFD's state at the node, the implementation MAY also provide: state at the node, the implementation MAY also provide:
* the assigned role (i.e., Sentinel or Acceptor), * the assigned role (i.e., Sentinel or Acceptor),
* the exact value of LORS (i.e., "UP", "SUSPECTED DOWN", "LOCALLY * the exact value of LORS (i.e., "UP", "SUSPECTED DOWN", "LOCALLY
DOWN", or "GLOBALLY DOWN"), DOWN", or "GLOBALLY DOWN"),
* the two CFRCs (i.e., PositiveCFRC and NegativeCFRC), and * the two CFRCs (i.e., PositiveCFRC and NegativeCFRC), and
* the constants listed in Section 5.8. * the constants listed in Section 5.8.
skipping to change at line 1079 skipping to change at line 1080
RECOMMENDED to use RPL security mechanisms if there is a risk that RECOMMENDED to use RPL security mechanisms if there is a risk that
control information might be modified or spoofed. control information might be modified or spoofed.
In this context, two features of RNFD are worth highlighting. First, In this context, two features of RNFD are worth highlighting. First,
unless all neighbors of a DODAG root are compromised, a false unless all neighbors of a DODAG root are compromised, a false
positive can always be detected by the root based on its local CFRCs. positive can always be detected by the root based on its local CFRCs.
If the frequency of such false positives becomes problematic, RNFD If the frequency of such false positives becomes problematic, RNFD
can be disabled altogether, for instance, until the problem has been can be disabled altogether, for instance, until the problem has been
diagnosed. This procedure can be largely automated at LBRs. Second, diagnosed. This procedure can be largely automated at LBRs. Second,
some types of false negatives can also be detected this way. Those some types of false negatives can also be detected this way. Those
that pass undetected are likely not to have major negative that do pass undetected are likely not to have major negative
consequences on RPL apart from the lack of improvement to its consequences on RPL apart from the lack of improvement to its
performance upon a DODAG root's crash, at least if RPL's other performance upon a DODAG root's crash, at least if RPL's other
components are not attacked as well. components are not attacked as well.
8. IANA Considerations 8. IANA Considerations
IANA has allocated the following value in the "RPL Control Message IANA has allocated the following value in the "RPL Control Message
Options" registry within the "Routing Protocol for Low Power and Options" registry within the "Routing Protocol for Low Power and
Lossy Networks (RPL)" registry group Lossy Networks (RPL)" registry group
(https://www.iana.org/assignments/rpl). (https://www.iana.org/assignments/rpl).
skipping to change at line 1170 skipping to change at line 1171
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
DOI 10.17487/RFC4861, September 2007, DOI 10.17487/RFC4861, September 2007,
<https://www.rfc-editor.org/info/rfc4861>. <https://www.rfc-editor.org/info/rfc4861>.
[RFC5184] Teraoka, F., Gogo, K., Mitsuya, K., Shibui, R., and K. [RFC5184] Teraoka, F., Gogo, K., Mitsuya, K., Shibui, R., and K.
Mitani, "Unified Layer 2 (L2) Abstractions for Layer 3 Mitani, "Unified Layer 2 (L2) Abstractions for Layer 3
(L3)-Driven Fast Handover", RFC 5184, (L3)-Driven Fast Handover", RFC 5184,
DOI 10.17487/RFC5184, May 2008, DOI 10.17487/RFC5184, May 2008,
<https://www.rfc-editor.org/info/rfc5184>. <https://www.rfc-editor.org/info/rfc5184>.
[RFC6202] Loreto, S., Saint-Andre, P., Salsano, S., and G. Wilkins,
"Known Issues and Best Practices for the Use of Long
Polling and Streaming in Bidirectional HTTP", RFC 6202,
DOI 10.17487/RFC6202, April 2011,
<https://www.rfc-editor.org/info/rfc6202>.
[RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and [RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and
Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January
2014, <https://www.rfc-editor.org/info/rfc7102>. 2014, <https://www.rfc-editor.org/info/rfc7102>.
[RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for [RFC7228] Bormann, C., Ersue, M., and A. Keranen, "Terminology for
Constrained-Node Networks", RFC 7228, Constrained-Node Networks", RFC 7228,
DOI 10.17487/RFC7228, May 2014, DOI 10.17487/RFC7228, May 2014,
<https://www.rfc-editor.org/info/rfc7228>. <https://www.rfc-editor.org/info/rfc7228>.
[RFC7416] Tsao, T., Alexander, R., Dohler, M., Daza, V., Lozano, A., [RFC7416] Tsao, T., Alexander, R., Dohler, M., Daza, V., Lozano, A.,
 End of changes. 32 change blocks. 
79 lines changed or deleted 74 lines changed or added

This html diff was produced by rfcdiff 1.48.