Root Node Failure Detector (RNFD): Fast Detection of Border Router Crashes in the Routing Protocol for Low-Power and Lossy Networks (RPL)
Extracted elements (29)
GLOBALLY DOWN forces the root to prove liveness by issuing a new DODAG Version rather than attempting in-place recovery, because a crashed-and-restarted root inherently loses its prior state anyway. This makes recovery unambiguous: any new version resets all RNFD state network-wide.
Linear counting (Whang90) was chosen as the CFRC implementation because bitwise OR satisfies the required idempotent, commutative, and associative merge semantics, enabling eventual consistency of counters regardless of merge order, DODAG shape, or network topology. The bit length is constrained to the largest prime below the byte-aligned bound to improve hash collision properties.
PositiveCFRC tracks all Sentinels that ever monitored the root (not just current ones) so that the NegativeCFRC/PositiveCFRC ratio reflects historical consensus rather than instantaneous membership. Nodes add themselves to NegativeCFRC when reverting from Sentinel to Acceptor in UP/SUSPECTED DOWN states, preserving the invariant that PositiveCFRC >= NegativeCFRC.
RNFD is designed to operate in the background independently of RPL and to be deactivatable at any time without affecting RPL's operation. This minimizes changes to RPL's existing algorithms and allows RNFD to be an opt-in extension rather than a mandatory modification.
RNFD uses explicit collaborative monitoring with CFRCs rather than relying on RPL's emergent per-node behavior because independent operation generates slow, traffic-heavy DODAG repair with routing loops; the paper cites detection periods spanning many low-data-rate link timeouts followed by cascaded Trickle timer resets. Coordination cuts detection latency by enabling concurrent suspicion-checking across all Sentinels simultaneously.
The SUSPECTED DOWN state exists as an intermediate verification opportunity before committing to LOCALLY DOWN, because each LOCALLY DOWN transition saturates NegativeCFRC bits. Skipping verification on direct observations (e.g., missing L2 ACKs) is explicitly allowed as an optimization since such evidence is already strong.
RNFD CFRC updates may trigger resets of RPL's DIO Trickle timer; a dedicated Trickle timer for RNFD is RECOMMENDED to decouple RNFD-driven resets from RPL's normal DIO scheduling. Without a dedicated timer, implementations SHOULD ensure the RNFD Option appears in multicast DIOs sufficiently often to propagate CFRC changes quickly.
RNFD is largely unaffected by the virtual root primary/backup realization (Section 6.2), since Sentinel eligibility conditions ensure only the current primary is monitored. For the multi-primary realization, RNFD is only beneficial when crashes among root nodes are correlated (e.g., shared power supply).
A node MUST reset its Trickle timer when LORS changes to GLOBALLY DOWN to expedite crash dissemination. A dedicated Trickle timer for RNFD is RECOMMENDED, with minimal and maximal intervals not smaller than RPL's original DIO Trickle timer intervals.
A Sentinel having LORS UP MUST set its LORS to SUSPECTED DOWN or LOCALLY DOWN upon concluding there may be problems with the DODAG root link. Additionally, any node MUST switch directly to LOCALLY DOWN if the DODAG root is removed from RPL's DODAG parent set or becomes unreachable via its link-local address.
For a switch from Acceptor to Sentinel, all four conditions MUST hold simultaneously: LORS is UP; saturated(PositiveCFRC) is FALSE; a neighbor entry for the DODAG root exists in RPL's DODAG parent set; and the neighbor is reachable via its link-local IPv6 address.
RNFD activation and deactivation MUST be controlled by the DODAG root; other nodes MUST comply. A non-root node MUST NOT activate RNFD unless it receives a valid RNFD Option with positive Option Length. An explicit deactivation MUST occur upon receiving an RNFD Option with Option Length equal to zero, after which RNFD MUST NOT be reactivated within the same DODAG Version.
The DODAG root MUST assume the Acceptor role and MUST NOT ever switch from it. The root MUST generate a new DODAG Version if it changes its LORS to GLOBALLY DOWN, whether due to a post-crash restart or a false detection by nodes.
Upon receiving an RNFD Option, a node MUST merge received PosCFRC and NegCFRC into its local PositiveCFRC and NegativeCFRC. If value(NegativeCFRC)/value(PositiveCFRC) then reaches at least RNFD_CONSENSUS_THRESHOLD (default 0.51), the node MUST set LORS to GLOBALLY DOWN and both CFRCs to infinity().
When a node joins a DODAG Version, RNFD MUST assume the Acceptor role, set LORS to UP, and initialize both PositiveCFRC and NegativeCFRC to zero().
When a received RNFD Option has PosCFRC/NegCFRC bit length smaller than the node's local CFRCs, the node MUST ignore the option (and MAY reset its Trickle timer). This prevents downgrade of CFRC resolution.
When a virtual DODAG root transitions to a new primary node, a new DODAG Version MUST be issued to avoid polluting CFRCs with observations on the previous primary node.
When becoming a Sentinel, a node MUST add itself to PositiveCFRC via merge(oldpc, self()). When switching from Sentinel to Acceptor in states UP or SUSPECTED DOWN, the node MUST add itself to NegativeCFRC using the same selfc value generated when it last added itself to PositiveCFRC; this accounts for the node no longer monitoring the root.
While LORS is GLOBALLY DOWN, RNFD MUST prevent RPL from having any DODAG parent and MUST prevent it from advertising any Rank other than INFINITE_RANK. The node MUST NOT change LORS or CFRCs until it joins a new DODAG Version.
CFRC operations are implemented via linear counting: value(c) returns ceiling(-LT*ln(L0/LT)) where L0 is the zero-bit count and LT is the prime bit length; merge is bitwise OR; self() sets a single uniformly random bit; infinity() sets all bits; saturated(c) returns TRUE when more than RNFD_CFRC_SATURATION_THRESHOLD of bits are 1.
Each node maintains two Conflict-Free Replicated Counters: PositiveCFRC (counting Sentinels that consider or previously considered the root alive) and NegativeCFRC (counting Sentinels that consider or previously considered the root dead). The non-negative difference estimates the number of Sentinels still considering the root alive.
Each RNFD node maintains a Locally Observed DODAG Root's State (LORS) encoding its current knowledge of root liveness. LORS takes values UP, SUSPECTED DOWN, LOCALLY DOWN, or GLOBALLY DOWN; only Sentinels may enter the middle two states.
RNFD defines three configurable thresholds: RNFD_CONSENSUS_THRESHOLD (default 0.51, ratio of NegCFRC to PosCFRC that triggers GLOBALLY DOWN), RNFD_SUSPICION_GROWTH_THRESHOLD (default 0.12, ratio growth since last UP that triggers suspicion), and RNFD_CFRC_SATURATION_THRESHOLD (default 0.63, fraction of 1-bits indicating CFRC saturation).
RNFD divides non-root nodes into two disjoint roles per DODAG Version: Sentinels (DODAG root's neighbors that actively monitor the root's link status) and Acceptors (all other nodes that collect and propagate Sentinel observations). The DODAG root is always an Acceptor and MUST NOT switch roles.
IANA allocated value 0x0E in the 'RPL Control Message Options' registry within the 'Routing Protocol for Low Power and Lossy Networks (RPL)' registry group, assigned to the RNFD Option defined in this document.
If the RNFD Option is compromised, false positives may cause all nodes to set LORS to GLOBALLY DOWN and halt routing until a new DODAG Version is issued; false negatives may prevent crash detection, leaving RPL to rely on its slower built-in mechanisms. Compromised options may also generate increased DIO traffic via Trickle timer resets.
RNFD deployments are RECOMMENDED to use RPL security mechanisms (RFC 6550, RFC 7416) when control information might be modified or spoofed. RNFD does not introduce new traffic patterns or message types requiring mitigation beyond what RPL already provides. The DODAG root can detect false positives from its local CFRCs unless all its neighbors are compromised.
RNFD defines four node states: UP (root alive), SUSPECTED DOWN (Sentinel suspects crash, Sentinel-only), LOCALLY DOWN (Sentinel has confirmed suspicion, Sentinel-only), and GLOBALLY DOWN (consensus reached, all nodes). GLOBALLY DOWN is terminal until the node joins a new DODAG Version, at which point transition 5 fires.
The RNFD Option (Type=0x0E) carries an 8-bit Option Length (MUST be even; 0 indicates RNFD disabled) followed by two equal-length octet-aligned bit arrays PosCFRC and NegCFRC. Each array's actual bit length is the largest prime less than (Option Length / 2) * 8; unused bits MUST be zero.