RFC 6550
RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks
7. Sequence Counters
This section describes the general scheme for bootstrap and operation of sequence counters in RPL, such as the DODAGVersionNumber in the DIO message, the DAOSequence in the DAO message, and the Path Sequence in the Transit Information option.7.1. Sequence Counter Overview
This specification utilizes three different sequence numbers to validate the freshness and the synchronization of protocol information: DODAGVersionNumber: This sequence counter is present in the DIO Base to indicate the Version of the DODAG being formed. The DODAGVersionNumber is monotonically incremented by the root each time the root decides to form a new Version of the DODAG in order to revalidate the integrity and allow a global repair to occur. The DODAGVersionNumber is propagated unchanged Down
the DODAG as routers join the new DODAG Version. The
DODAGVersionNumber is globally significant in a DODAG and
indicates the Version of the DODAG in which a router is
operating. An older (lesser) value indicates that the
originating router has not migrated to the new DODAG Version
and cannot be used as a parent once the receiving node has
migrated to the newer DODAG Version.
DAOSequence: This sequence counter is present in the DAO Base to
correlate a DAO message and a DAO ACK message. The DAOSequence
number is locally significant to the node that issues a DAO
message for its own consumption to detect the loss of a DAO
message and enable retries.
Path Sequence: This sequence counter is present in the Transit
Information option in a DAO message. The purpose of this
counter is to differentiate a movement where a newer route
supersedes a stale one from a route redundancy scenario where
multiple routes exist in parallel for the same target. The
Path Sequence is globally significant in a DODAG and indicates
the freshness of the route to the associated target. An older
(lesser) value received from an originating router indicates
that the originating router holds stale routing states and the
originating router should not be considered anymore as a
potential next hop for the target. The Path Sequence is
computed by the node that advertises the target, that is the
Target itself or a router that advertises a Target on behalf of
a host, and is unchanged as the DAO content is propagated
towards the root by parent routers. If a host does not pass a
counter to its router, then the router is in charge of
computing the Path Sequence on behalf of the host and the host
can only register to one router for that purpose. If a DAO
message containing the same Target is issued to multiple
parents at a given point in time for the purpose of route
redundancy, then the Path Sequence is the same in all the DAO
messages for that same target.
7.2. Sequence Counter Operation
RPL sequence counters are subdivided in a 'lollipop' fashion
[Perlman83], where the values from 128 and greater are used as a
linear sequence to indicate a restart and bootstrap the counter, and
the values less than or equal to 127 used as a circular sequence
number space of size 128 as in [RFC1982]. Consideration is given to
the mode of operation when transitioning from the linear region to
the circular region. Finally, when operating in the circular region,
if sequence numbers are detected to be too far apart, then they are
not comparable, as detailed below.
A window of comparison, SEQUENCE_WINDOW = 16, is configured based on
a value of 2^N, where N is defined to be 4 in this specification.
For a given sequence counter:
1. The sequence counter SHOULD be initialized to an implementation
defined value, which is 128 or greater prior to use. A
recommended value is 240 (256 - SEQUENCE_WINDOW).
2. When a sequence counter increment would cause the sequence
counter to increment beyond its maximum value, the sequence
counter MUST wrap back to zero. When incrementing a sequence
counter greater than or equal to 128, the maximum value is 255.
When incrementing a sequence counter less than 128, the maximum
value is 127.
3. When comparing two sequence counters, the following rules MUST be
applied:
1. When a first sequence counter A is in the interval [128..255]
and a second sequence counter B is in [0..127]:
1. If (256 + B - A) is less than or equal to
SEQUENCE_WINDOW, then B is greater than A, A is less than
B, and the two are not equal.
2. If (256 + B - A) is greater than SEQUENCE_WINDOW, then A
is greater than B, B is less than A, and the two are not
equal.
For example, if A is 240, and B is 5, then (256 + 5 - 240) is
21. 21 is greater than SEQUENCE_WINDOW (16); thus, 240 is
greater than 5. As another example, if A is 250 and B is 5,
then (256 + 5 - 250) is 11. 11 is less than SEQUENCE_WINDOW
(16); thus, 250 is less than 5.
2. In the case where both sequence counters to be compared are
less than or equal to 127, and in the case where both
sequence counters to be compared are greater than or equal to
128:
1. If the absolute magnitude of difference between the two
sequence counters is less than or equal to
SEQUENCE_WINDOW, then a comparison as described in
[RFC1982] is used to determine the relationships greater
than, less than, and equal.
2. If the absolute magnitude of difference of the two
sequence counters is greater than SEQUENCE_WINDOW, then a
desynchronization has occurred and the two sequence
numbers are not comparable.
4. If two sequence numbers are determined not to be comparable,
i.e., the results of the comparison are not defined, then a node
should consider the comparison as if it has evaluated in such a
way so as to give precedence to the sequence number that has most
recently been observed to increment. Failing this, the node
should consider the comparison as if it has evaluated in such a
way so as to minimize the resulting changes to its own state.
8. Upward Routes
This section describes how RPL discovers and maintains Upward routes.
It describes the use of DODAG Information Objects (DIOs), the
messages used to discover and maintain these routes. It specifies
how RPL generates and responds to DIOs. It also describes DODAG
Information Solicitation (DIS) messages, which are used to trigger
DIO transmissions.
As mentioned in Section 3.2.8, nodes that decide to join a DODAG MUST
provision at least one DODAG parent as a default route for the
associated instance. This default route enables a packet to be
forwarded Upward until it eventually hits a common ancestor from
which it will be routed Downward to the destination. If the
destination is not in the DODAG, then the DODAG root may be able to
forward the packet using connectivity to the outside of the DODAG; if
it cannot forward the packet outside, then the DODAG root has to drop
it.
A DIO message can also transport explicit routing information:
DODAGID: The DODAGID is a Global or Unique Local IPv6 address of the
root. A node that joins a DODAG SHOULD provision a host route
via a DODAG parent to the address used by the root as the
DODAGID.
RIO Prefix: The root MAY place one or more Route Information options
in a DIO message. The RIO is used to advertise an external
route that is reachable via the root, associated with a
preference, as presented in Section 6.7.5, which incorporates
the RIO from [RFC4191]. It is interpreted as a capability of
the root as opposed to a routing advertisement, and it MUST NOT
be redistributed in another routing protocol though it SHOULD
be used by an ingress RPL router to select a DODAG when a
packet is injected in a RPL domain from a node attached to that
RPL router. An Objective Function MAY use the routes
advertised in RIO or the preference for those routes in order
to favor a DODAG versus another one for the same instance.
8.1. DIO Base Rules
1. For the following DIO Base fields, a node that is not a DODAG
root MUST advertise the same values as its preferred DODAG parent
(defined in Section 8.2.1). In this way, these values will
propagate Down the DODAG unchanged and advertised by every node
that has a route to that DODAG root. These fields are as
follows:
1. Grounded (G)
2. Mode of Operation (MOP)
3. DAGPreference (Prf)
4. Version
5. RPLInstanceID
6. DODAGID
2. A node MAY update the following fields at each hop:
1. Rank
2. DTSN
3. The DODAGID field each root sets MUST be unique within the RPL
Instance and MUST be a routable IPv6 address belonging to the
root.
8.2. Upward Route Discovery and Maintenance
Upward route discovery allows a node to join a DODAG by discovering
neighbors that are members of the DODAG of interest and identifying a
set of parents. The exact policies for selecting neighbors and
parents is implementation dependent and driven by the OF. This
section specifies the set of rules those policies must follow for
interoperability.
8.2.1. Neighbors and Parents within a DODAG Version
RPL's Upward route discovery algorithms and processing are in terms
of three logical sets of link-local nodes. First, the candidate
neighbor set is a subset of the nodes that can be reached via link-
local multicast. The selection of this set is implementation and OF
dependent. Second, the parent set is a restricted subset of the
candidate neighbor set. Finally, the preferred parent is a member of
the parent set that is the preferred next hop in Upward routes.
Conceptually, the preferred parent is a single parent; although, it
may be a set of multiple parents if those parents are equally
preferred and have identical Rank.
More precisely:
1. The DODAG parent set MUST be a subset of the candidate neighbor
set.
2. A DODAG root MUST have a DODAG parent set of size zero.
3. A node that is not a DODAG root MAY maintain a DODAG parent set
of size greater than or equal to one.
4. A node's preferred DODAG parent MUST be a member of its DODAG
parent set.
5. A node's Rank MUST be greater than all elements of its DODAG
parent set.
6. When Neighbor Unreachability Detection (NUD) [RFC4861], or an
equivalent mechanism, determines that a neighbor is no longer
reachable, a RPL node MUST NOT consider this node in the
candidate neighbor set when calculating and advertising routes
until it determines that it is again reachable. Routes through
an unreachable neighbor MUST be removed from the routing table.
These rules ensure that there is a consistent partial order on nodes
within the DODAG. As long as node Ranks do not change, following the
above rules ensures that every node's route to a DODAG root is loop-
free, as Rank decreases on each hop to the root.
The OF can guide candidate neighbor set and parent set selection, as
discussed in [RFC6552].
8.2.2. Neighbors and Parents across DODAG Versions
The above rules govern a single DODAG Version. The rules in this
section define how RPL operates when there are multiple DODAG
Versions.
8.2.2.1. DODAG Version
1. The tuple (RPLInstanceID, DODAGID, DODAGVersionNumber) uniquely
defines a DODAG Version. Every element of a node's DODAG parent
set, as conveyed by the last heard DIO message from each DODAG
parent, MUST belong to the same DODAG Version. Elements of a
node's candidate neighbor set MAY belong to different DODAG
Versions.
2. A node is a member of a DODAG Version if every element of its
DODAG parent set belongs to that DODAG Version, or if that node
is the root of the corresponding DODAG.
3. A node MUST NOT send DIOs for DODAG Versions of which it is not a
member.
4. DODAG roots MAY increment the DODAGVersionNumber that they
advertise and thus move to a new DODAG Version. When a DODAG
root increments its DODAGVersionNumber, it MUST follow the
conventions of Serial Number Arithmetic as described in
Section 7. Events triggering the increment of the
DODAGVersionNumber are described later in this section and in
Section 18.
5. Within a given DODAG, a node that is a not a root MUST NOT
advertise a DODAGVersionNumber higher than the highest
DODAGVersionNumber it has heard. Higher is defined as the
greater-than operator in Section 7.
6. Once a node has advertised a DODAG Version by sending a DIO, it
MUST NOT be a member of a previous DODAG Version of the same
DODAG (i.e., with the same RPLInstanceID, the same DODAGID, and a
lower DODAGVersionNumber). Lower is defined as the less-than
operator in Section 7.
When the DODAG parent set becomes empty on a node that is not a root,
(i.e., the last parent has been removed, causing the node no longer
to be associated with that DODAG), then the DODAG information should
not be suppressed until after the expiration of an implementation-
specific local timer. During the interval prior to suppression of
the "old" DODAG state, the node will be able to observe if the
DODAGVersionNumber has been incremented should any new parents
appear. This will help protect against the possibility of loops that
may occur if that node were to inadvertently rejoin the old DODAG
Version in its own prior sub-DODAG.
As the DODAGVersionNumber is incremented, a new DODAG Version spreads
outward from the DODAG root. A parent that advertises the new
DODAGVersionNumber cannot belong to the sub-DODAG of a node
advertising an older DODAGVersionNumber. Therefore, a node can
safely add a parent of any Rank with a newer DODAGVersionNumber
without forming a loop.
For example, suppose that a node has left a DODAG with
DODAGVersionNumber N. Suppose that a node had a sub-DODAG and did
attempt to poison that sub-DODAG by advertising a Rank of
INFINITE_RANK, but those advertisements may have become lost in the
LLN. Then, if the node did observe a candidate neighbor advertising a position in that original DODAG at DODAGVersionNumber N, that candidate neighbor could possibly have been in the node's former sub- DODAG, and there is a possible case where adding that candidate neighbor as a parent could cause a loop. In this case, if that candidate neighbor is observed to advertise a DODAGVersionNumber N+1, then that candidate neighbor is certain to be safe, since it is certain not to be in that original node's sub-DODAG, as it has been able to increment the DODAGVersionNumber by hearing from the DODAG root while that original node was detached. For this reason, it is useful for the detached node to remember the original DODAG information, including the DODAGVersionNumber N. Exactly when a DODAG root increments the DODAGVersionNumber is implementation dependent and out of scope for this specification. Examples include incrementing the DODAGVersionNumber periodically, upon administrative intervention, or on application-level detection of lost connectivity or DODAG inefficiency. After a node transitions to and advertises a new DODAG Version, the rules above make it unable to advertise the previous DODAG Version (prior DODAGVersionNumber) once it has committed to advertising the new DODAG Version.8.2.2.2. DODAG Roots
1. A DODAG root without possibility to satisfy the application- defined goal MUST NOT set the Grounded bit. 2. A DODAG root MUST advertise a Rank of ROOT_RANK. 3. A node whose DODAG parent set is empty MAY become the DODAG root of a floating DODAG. It MAY also set its DAGPreference such that it is less preferred. In a deployment that uses non-LLN links to federate a number of LLN roots, it is possible to run RPL over those non-RPL links and use one router as a "backbone root". The backbone root is the virtual root of the DODAG and exposes a Rank of BASE_RANK over the backbone. All the LLN roots that are parented to that backbone root, including the backbone root if it also serves as the LLN root itself, expose a Rank of ROOT_RANK to the LLN. These virtual roots are part of the same DODAG and advertise the same DODAGID. They coordinate DODAGVersionNumbers and other DODAG parameters with the virtual root over the backbone. The method of coordination is out of scope for this specification (to be defined in future companion specifications).
8.2.2.3. DODAG Selection
The Objective Function and the set of advertised routing metrics and constraints of a DAG determine how a node selects its neighbor set, parent set, and preferred parents. This selection implicitly also determines the DODAG within a DAG. Such selection can include administrative preference (Prf) as well as metrics or other considerations. If a node has the option to join a more preferred DODAG while still meeting other optimization objectives, then the node will generally seek to join the more preferred DODAG as determined by the OF. All else being equal, it is left to the implementation to determine which DODAG is most preferred (since, as a reminder, a node must only join one DODAG per RPL Instance).8.2.2.4. Rank and Movement within a DODAG Version
1. A node MUST NOT advertise a Rank less than or equal to any member of its parent set within the DODAG Version. 2. A node MAY advertise a Rank lower than its prior advertisement within the DODAG Version. 3. Let L be the lowest Rank within a DODAG Version that a given node has advertised. Within the same DODAG Version, that node MUST NOT advertise an effective Rank higher than L + DAGMaxRankIncrease. INFINITE_RANK is an exception to this rule: a node MAY advertise an INFINITE_RANK within a DODAG Version without restriction. If a node's Rank were to be higher than allowed by L + DAGMaxRankIncrease, when it advertises Rank, it MUST advertise its Rank as INFINITE_RANK. 4. A node MAY, at any time, choose to join a different DODAG within a RPL Instance. Such a join has no Rank restrictions, unless that different DODAG is a DODAG Version of which this node has previously been a member; in which case, the rule of the previous bullet (3) must be observed. Until a node transmits a DIO indicating its new DODAG membership, it MUST forward packets along the previous DODAG. 5. A node MAY, at any time after hearing the next DODAGVersionNumber advertised from suitable DODAG parents, choose to migrate to the next DODAG Version within the DODAG.
Conceptually, an implementation is maintaining a DODAG parent set within the DODAG Version. Movement entails changes to the DODAG parent set. Moving Up does not present the risk to create a loop but moving Down might, so that operation is subject to additional constraints. When a node migrates to the next DODAG Version, the DODAG parent set needs to be rebuilt for the new Version. An implementation could defer to migrate for some reasonable amount of time, to see if some other neighbors with potentially better metrics but higher Rank announce themselves. Similarly, when a node jumps into a new DODAG, it needs to construct a new DODAG parent set for this new DODAG. If a node needs to move Down a DODAG that it is attached to, increasing its Rank, then it MAY poison its routes and delay before moving as described in Section 8.2.2.5. A node is allowed to join any DODAG Version that it has never been a prior member of without any restrictions, but if the node has been a prior member of the DODAG Version, then it must continue to observe the rule that it may not advertise a Rank higher than L+DAGMaxRankIncrease at any point in the life of the DODAG Version. This rule must be observed so as not to create a loophole that would allow the node to effectively increment its Rank all the way to INFINITE_RANK, which may have impact on other nodes and create a resource-wasting count-to-infinity scenario.8.2.2.5. Poisoning
1. A node poisons routes by advertising a Rank of INFINITE_RANK. 2. A node MUST NOT have any nodes with a Rank of INFINITE_RANK in its parent set. Although an implementation may advertise INFINITE_RANK for the purposes of poisoning, doing so is not the same as setting Rank to INFINITE_RANK. For example, a node may continue to send data packets whose RPL Packet Information includes a Rank that is not INFINITE_RANK, yet still advertise INFINITE_RANK in its DIOs. When a (former) parent is observed to advertise a Rank of INFINITE_RANK, that (former) parent has detached from the DODAG and is no longer able to act as a parent, nor is there any way that another node may be considered to have a Rank greater-than INFINITE_RANK. Therefore, that (former) parent cannot act as a parent any longer and is removed from the parent set.
8.2.2.6. Detaching
1. A node unable to stay connected to a DODAG within a given DODAG Version, i.e., that cannot retain non-empty parent set without violating the rules of this specification, MAY detach from this DODAG Version. A node that detaches becomes the root of its own floating DODAG and SHOULD immediately advertise this new situation in a DIO as an alternate to poisoning.8.2.2.7. Following a Parent
1. If a node receives a DIO from one of its DODAG parents, indicating that the parent has left the DODAG, that node SHOULD stay in its current DODAG through an alternative DODAG parent, if possible. It MAY follow the leaving parent. A DODAG parent may have moved, migrated to the next DODAG Version, or jumped to a different DODAG. A node ought to give some preference to remaining in the current DODAG, if possible via an alternate parent, but ought to follow the parent if there are no other options.8.2.3. DIO Message Communication
When a DIO message is received, the receiving node must first determine whether or not the DIO message should be accepted for further processing, and subsequently present the DIO message for further processing if eligible. 1. If the DIO message is malformed, then the DIO message is not eligible for further processing and a node MUST silently discard it. (See Section 18 for error logging). 2. If the sender of the DIO message is a member of the candidate neighbor set and the DIO message is not malformed, the node MUST process the DIO.8.2.3.1. DIO Message Processing
As DIO messages are received from candidate neighbors, the neighbors may be promoted to DODAG parents by following the rules of DODAG discovery as described in Section 8.2. When a node places a neighbor into the DODAG parent set, the node becomes attached to the DODAG through the new DODAG parent node.
The most preferred parent should be used to restrict which other nodes may become DODAG parents. Some nodes in the DODAG parent set may be of a Rank less than or equal to the most preferred DODAG parent. (This case may occur, for example, if an energy-constrained device is at a lesser Rank but should be avoided per an optimization objective, resulting in a more preferred parent at a greater Rank.)8.3. DIO Transmission
RPL nodes transmit DIOs using a Trickle timer [RFC6206]. A DIO from a sender with a lesser DAGRank that causes no changes to the recipient's parent set, preferred parent, or Rank SHOULD be considered consistent with respect to the Trickle timer. The following packets and events MUST be considered inconsistencies with respect to the Trickle timer, and cause the Trickle timer to reset: o When a node detects an inconsistency when forwarding a packet, as detailed in Section 11.2. o When a node receives a multicast DIS message without a Solicited Information option, unless a DIS flag restricts this behavior. o When a node receives a multicast DIS with a Solicited Information option and the node matches all of the predicates in the Solicited Information option, unless a DIS flag restricts this behavior. o When a node joins a new DODAG Version (e.g., by updating its DODAGVersionNumber, joining a new RPL Instance, etc.). Note that this list is not exhaustive, and an implementation MAY consider other messages or events to be inconsistencies. A node SHOULD NOT reset its DIO Trickle timer in response to unicast DIS messages. When a node receives a unicast DIS without a Solicited Information option, it MUST unicast a DIO to the sender in response. This DIO MUST include a DODAG Configuration option. When a node receives a unicast DIS message with a Solicited Information option and matches the predicates of that Solicited Information option, it MUST unicast a DIO to the sender in response. This unicast DIO MUST include a DODAG Configuration option. Thus, a node MAY transmit a unicast DIS message to a potential DODAG parent in order to probe for DODAG Configuration and other parameters.
8.3.1. Trickle Parameters
The configuration parameters of the Trickle timer are specified as follows: Imin: learned from the DIO message as (2^DIOIntervalMin) ms. The default value of DIOIntervalMin is DEFAULT_DIO_INTERVAL_MIN. Imax: learned from the DIO message as DIOIntervalDoublings. The default value of DIOIntervalDoublings is DEFAULT_DIO_INTERVAL_DOUBLINGS. k: learned from the DIO message as DIORedundancyConstant. The default value of DIORedundancyConstant is DEFAULT_DIO_REDUNDANCY_CONSTANT. In RPL, when k has the value of 0x00, this is to be treated as a redundancy constant of infinity in RPL, i.e., Trickle never suppresses messages.8.4. DODAG Selection
The DODAG selection is implementation and OF dependent. In order to limit erratic movements, and all metrics being equal, nodes SHOULD keep their previous selection. Also, nodes SHOULD provide a means to filter out a parent whose availability is detected as fluctuating, at least when more stable choices are available. When connection to a grounded DODAG is not possible or preferable for security or other reasons, scattered DODAGs MAY aggregate as much as possible into larger DODAGs in order to allow connectivity within the LLN. A node SHOULD verify that bidirectional connectivity and adequate link quality is available with a candidate neighbor before it considers that candidate as a DODAG parent.8.5. Operation as a Leaf Node
In some cases, a RPL node may attach to a DODAG as a leaf node only. One example of such a case is when a node does not understand or does not support (policy) the RPL Instance's OF or advertised metric/ constraint. As specified in Section 18.6, related to policy function, the node may either join the DODAG as a leaf node or may not join the DODAG. As mentioned in Section 18.5, it is then recommended to log a fault.
A leaf node does not extend DODAG connectivity; however, in some
cases, the leaf node may still need to transmit DIOs on occasion, in
particular, when the leaf node may not have always been acting as a
leaf node and an inconsistency is detected.
A node operating as a leaf node must obey the following rules:
1. It MUST NOT transmit DIOs containing the DAG Metric Container.
2. Its DIOs MUST advertise a DAGRank of INFINITE_RANK.
3. It MAY suppress DIO transmission, unless the DIO transmission has
been triggered due to detection of inconsistency when a packet is
being forwarded or in response to a unicast DIS message, in which
case the DIO transmission MUST NOT be suppressed.
4. It MAY transmit unicast DAOs as described in Section 9.2.
5. It MAY transmit multicast DAOs to the '1 hop' neighborhood as
described in Section 9.10.
A particular case that requires a leaf node to send a DIO is if that
leaf node was a prior member of another DODAG and another node
forwards a message assuming the old topology, triggering an
inconsistency. The leaf node needs to transmit a DIO in order to
repair the inconsistency. Note that due to the lossy nature of LLNs,
even though the leaf node may have optimistically poisoned its routes
by advertising a Rank of INFINITE_RANK in the old DODAG prior to
becoming a leaf node, that advertisement may have become lost and a
leaf node must be capable to send a DIO later in order to repair the
inconsistency.
In the general case, the leaf node MUST NOT advertise itself as a
router (i.e., send DIOs).
8.6. Administrative Rank
In some cases, it might be beneficial to adjust the Rank advertised
by a node beyond that computed by the OF based on some
implementation-specific policy and properties of the node. For
example, a node that has a limited battery should be a leaf unless
there is no other choice, and may then augment the Rank computation
specified by the OF in order to expose an exaggerated Rank.
9. Downward Routes
This section describes how RPL discovers and maintains Downward routes. RPL constructs and maintains Downward routes with Destination Advertisement Object (DAO) messages. Downward routes support P2MP flows, from the DODAG roots toward the leaves. Downward routes also support P2P flows: P2P messages can flow toward a DODAG root (or a common ancestor) through an Upward route, then away from the DODAG root to a destination through a Downward route. This specification describes the two modes a RPL Instance may choose from for maintaining Downward routes. In the first mode, called "Storing", nodes store Downward routing tables for their sub-DODAG. Each hop on a Downward route in a storing network examines its routing table to decide on the next hop. In the second mode, called "Non-Storing", nodes do not store Downward routing tables. Downward packets are routed with source routes populated by a DODAG root [RFC6554]. RPL allows a simple one-hop P2P optimization for both storing and non-storing networks. A node may send a P2P packet destined to a one-hop neighbor directly to that node.9.1. Destination Advertisement Parents
To establish Downward routes, RPL nodes send DAO messages Upward. The next-hop destinations of these DAO messages are called "DAO parents". The collection of a node's DAO parents is called the "DAO parent set". 1. A node MAY send DAO messages using the all-RPL-nodes multicast address, which is an optimization to provision one-hop routing. The 'K' bit MUST be cleared on transmission of the multicast DAO. 2. A node's DAO parent set MUST be a subset of its DODAG parent set. 3. In Storing mode operation, a node MUST NOT address unicast DAO messages to nodes that are not DAO parents. 4. In Storing mode operation, the IPv6 source and destination addresses of a DAO message MUST be link-local addresses. 5. In Non-Storing mode operation, a node MUST NOT address unicast DAO messages to nodes that are not DODAG roots. 6. In Non-Storing mode operation, the IPv6 source and destination addresses of a DAO message MUST be a unique-local or a global address.
The selection of DAO parents is implementation and Objective Function specific.9.2. Downward Route Discovery and Maintenance
Destination Advertisement may be configured to be entirely disabled, or operate in either a Storing or Non-Storing mode, as reported in the MOP in the DIO message. 1. All nodes who join a DODAG MUST abide by the MOP setting from the root. Nodes that do not have the capability to fully participate as a router, e.g., that do not match the advertised MOP, MAY join the DODAG as a leaf. 2. If the MOP is 0, indicating no Downward routing, nodes MUST NOT transmit DAO messages and MAY ignore DAO messages. 3. In Non-Storing mode, the DODAG root SHOULD store source routing table entries for destinations learned from DAOs. The DODAG root MUST be able to generate source routes for those destinations learned from DAOs that were stored. 4. In Storing mode, all non-root, non-leaf nodes MUST store routing table entries for destinations learned from DAOs. A DODAG can have one of several possible modes of operation, as defined by the MOP field. Either it does not support Downward routes, it supports Downward routes through source routing from DODAG roots, or it supports Downward routes through in-network routing tables. When Downward routes are supported through source routing from DODAG roots, it is generally expected that the DODAG root has stored the source routing information learned from DAOs in order to construct the source routes. If the DODAG root fails to store some information, then some destinations may be unreachable. When Downward routes are supported through in-network routing tables, the multicast operation defined in this specification may or may not be supported, also as indicated by the MOP field. When Downward routes are supported through in-network routing tables, as described in this specification, it is expected that nodes acting as routers have been provisioned sufficiently to hold the required routing table state. If a node acting as a router is unable to hold the full routing table state then the routing state is not complete,
messages may be dropped as a consequence, and a fault may be logged (Section 18.5). Future extensions to RPL may elaborate on refined actions/behaviors to manage this case. As of the writing of this specification, RPL does not support mixed- mode operation, where some nodes source route and other store routing tables: future extensions to RPL may support this mode of operation.9.2.1. Maintenance of Path Sequence
For each Target that is associated with (owned by) a node, that node is responsible to emit DAO messages in order to provision the Downward routes. The Target+Transit information contained in those DAO messages subsequently propagates Up the DODAG. The Path Sequence counter in the Transit information option is used to indicate freshness and update stale Downward routing information as described in Section 7. For a Target that is associated with (owned by) a node, that node MUST increment the Path Sequence counter, and generate a new DAO message, when: 1. the Path Lifetime is to be updated (e.g., a refresh or a no- Path). 2. the DODAG Parent Address subfield list is to be changed. For a Target that is associated with (owned by) a node, that node MAY increment the Path Sequence counter, and generate a new DAO message, on occasion in order to refresh the Downward routing information. In Storing mode, the node generates such a DAO to each of its DAO parents in order to enable multipath. All DAOs generated at the same time for the same Target MUST be sent with the same Path Sequence in the Transit Information.9.2.2. Generation of DAO Messages
A node might send DAO messages when it receives DAO messages, as a result of changes in its DAO parent set, or in response to another event such as the expiry of a related prefix lifetime. In the case of receiving DAOs, it matters whether the DAO message is "new" or contains new information. In Non-Storing mode, every DAO message a node receives is "new". In Storing mode, a DAO message is "new" if it satisfies any of these criteria for a contained Target: 1. it has a newer Path Sequence number, 2. it has additional Path Control bits, or
3. it is a No-Path DAO message that removes the last Downward route
to a prefix.
A node that receives a DAO message from its sub-DODAG MAY suppress
scheduling a DAO message transmission if that DAO message is not new.
9.3. DAO Base Rules
1. If a node sends a DAO message with newer or different information
than the prior DAO message transmission, it MUST increment the
DAOSequence field by at least one. A DAO message transmission
that is identical to the prior DAO message transmission MAY
increment the DAOSequence field.
2. The RPLInstanceID and DODAGID fields of a DAO message MUST be the
same value as the members of the node's parent set and the DIOs
it transmits.
3. A node MAY set the 'K' flag in a unicast DAO message to solicit a
unicast DAO-ACK in response in order to confirm the attempt.
4. A node receiving a unicast DAO message with the 'K' flag set
SHOULD respond with a DAO-ACK. A node receiving a DAO message
without the 'K' flag set MAY respond with a DAO-ACK, especially
to report an error condition.
5. A node that sets the 'K' flag in a unicast DAO message but does
not receive a DAO-ACK in response MAY reschedule the DAO message
transmission for another attempt, up until an implementation-
specific number of retries.
6. Nodes SHOULD ignore DAOs without newer sequence numbers and MUST
NOT process them further.
Unlike the Version field of a DIO, which is incremented only by a
DODAG root and repeated unchanged by other nodes, DAOSequence values
are unique to each node. The sequence number space for unicast and
multicast DAO messages can be either the same or distinct. It is
RECOMMENDED to use the same sequence number space.
9.4. Structure of DAO Messages
DAOs follow a common structure in both storing and non-storing
networks. In the most general form, a DAO message may include
several groups of options, where each group consists of one or more
Target options followed by one or more Transit Information options.
The entire group of Transit Information options applies to the entire
group of Target options. Later sections describe further details for
each mode of operation.
1. RPL nodes MUST include one or more RPL Target options in each DAO
message they transmit. One RPL Target option MUST have a prefix
that includes the node's IPv6 address if that node needs the
DODAG to provision Downward routes to that node. The RPL Target
option MAY be immediately followed by an opaque RPL Target
Descriptor option that qualifies it.
2. When a node updates the information in a Transit Information
option for a Target option that covers one of its addresses, it
MUST increment the Path Sequence number in that Transit
Information option. The Path Sequence number MAY be incremented
occasionally to cause a refresh to the Downward routes.
3. One or more RPL Target options in a unicast DAO message MUST be
followed by one or more Transit Information options. All the
transit options apply to all the Target options that immediately
precede them.
4. Multicast DAOs MUST NOT include the DODAG Parent Address subfield
in Transit Information options.
5. A node that receives and processes a DAO message containing
information for a specific Target, and that has prior information
for that Target, MUST use the Path Sequence number in the Transit
Information option associated with that Target in order to
determine whether or not the DAO message contains updated
information per Section 7.
6. If a node receives a DAO message that does not follow the above
rules, it MUST discard the DAO message without further
processing.
In Non-Storing mode, the root builds a strict source routing header,
hop-by-hop, by recursively looking up one-hop information that ties a
Target (address or prefix) and a transit address together. In some
cases, when a child address is derived from a prefix that is owned
and advertised by a parent, that parent-child relationship may be
inferred by the root for the purpose of constructing the source
routing header. In all other cases, it is necessary to inform the
root of the transit-Target relationship from a reachable target, so
as to later enable the recursive construction of the routing header.
An address that is advertised as a Target in a DAO message MUST be
collocated in the same router, or reachable on-link by the router
that owns the address that is indicated in the associated Transit
Information. The following additional rules apply to ensure the
continuity of the end-to-end source route path:
1. The address of a parent used in the transit option MUST be taken
from a PIO from that parent with the 'R' flag set. The 'R' flag
in a PIO indicates that the prefix field actually contains the
full parent address but the child SHOULD NOT assume that the
parent address is on-link.
2. A PIO with an 'A' flag set indicates that the RPL child node may
use the prefix to autoconfigure an address. A parent that
advertises a prefix in a PIO with the 'A' flag set MUST ensure
that the address or the whole prefix in the PIO is reachable from
the root by advertising it as a DAO target. If the parent also
sets the 'L' flag indicating that the prefix is on-link, then it
MUST advertise the whole prefix as Target in a DAO message. If
the 'L' flag is cleared and the 'R' flag is set, indicating that
the parent provides its own address in the PIO, then the parent
MUST advertise that address as a DAO target.
3. An address that is advertised as Target in a DAO message MUST be
collocated in the same router or reachable on-link by the router
that owns the address that is indicated in the associated Transit
Information.
4. In order to enable an optimum compression of the routing header,
the parent SHOULD set the 'R' flag in all PIOs with the 'A' flag
set and the 'L' flag cleared, and the child SHOULD prefer to use
as transit the address of the parent that is found in the PIO
that is used to autoconfigure the address that is advertised as
Target in the DAO message.
5. A router might have targets that are not known to be on-link for
a parent, either because they are addresses located on an
alternate interface or because they belong to nodes that are
external to RPL, for instance connected hosts. In order to
inject such a Target in the RPL network, the router MUST
advertise itself as the DODAG Parent Address subfield in the
Transit Information option for that target, using an address that
is on-link for that nodes DAO parent. If the Target belongs to
an external node, then the router MUST set the External 'E' flag
in the Transit Information.
A child node that has autoconfigured an address from a parent PIO
with the 'L' flag set does not need to advertise that address as a
DAO Target since the parent ensures that the whole prefix is already
reachable from the root. However, if the 'L' flag is not set, then
it is necessary, in Non-Storing mode, for the child node to inform the root of the parent-child relationship, using a reachable address of the parent, so as to enable the recursive construction of the routing header. This is done by associating an address of the parent as transit with the address of the child as Target in a DAO message.9.5. DAO Transmission Scheduling
Because DAOs flow Upward, receiving a unicast DAO can trigger sending a unicast DAO to a DAO parent. 1. On receiving a unicast DAO message with updated information, such as containing a Transit Information option with a new Path Sequence, a node SHOULD send a DAO. It SHOULD NOT send this DAO message immediately. It SHOULD delay sending the DAO message in order to aggregate DAO information from other nodes for which it is a DAO parent. 2. A node SHOULD delay sending a DAO message with a timer (DelayDAO). Receiving a DAO message starts the DelayDAO timer. DAO messages received while the DelayDAO timer is active do not reset the timer. When the DelayDAO timer expires, the node sends a DAO. 3. When a node adds a node to its DAO parent set, it SHOULD schedule a DAO message transmission. DelayDAO's value and calculation is implementation dependent. A default value of DEFAULT_DAO_DELAY is defined in this specification.9.6. Triggering DAO Messages
Nodes can trigger their sub-DODAG to send DAO messages. Each node maintains a DAO Trigger Sequence Number (DTSN), which it communicates through DIO messages. 1. If a node hears one of its DAO parents increment its DTSN, the node MUST schedule a DAO message transmission using rules in Sections 9.3 and 9.5. 2. In Non-Storing mode, if a node hears one of its DAO parents increment its DTSN, the node MUST increment its own DTSN. In a Storing mode of operation, as part of routine routing table updates and maintenance, a storing node MAY increment DTSN in order to reliably trigger a set of DAO updates from its immediate children.
In a Storing mode of operation, it is not necessary to trigger DAO updates from the entire sub-DODAG, since that state information will propagate hop-by-hop Up the DODAG. In a Non-Storing mode of operation, a DTSN increment will also cause the immediate children of a node to increment their DTSN in turn, triggering a set of DAO updates from the entire sub-DODAG. Typically, in a Non-Storing mode of operation, only the root would independently increment the DTSN when a DAO refresh is needed but a global repair (such as by incrementing DODAGVersionNumber) is not desired. Typically, in a Non-Storing mode of operation, all non-root nodes would increment their DTSN only when their parent(s) are observed to do so. In general, a node may trigger DAO updates according to implementation-specific logic, such as based on the detection of a Downward route inconsistency or occasionally based upon an internal timer. In a storing network, selecting a proper DelayDAO for triggered DAOs can greatly reduce the number of DAOs transmitted. The trigger flows Down the DODAG; in the best case, the DAOs flow Up the DODAG such that leaves send DAOs first, with each node sending a DAO message only once. Such a scheduling could be approximated by setting DelayDAO inversely proportional to Rank. Note that this suggestion is intended as an optimization to allow efficient aggregation (it is not required for correct operation in the general case).9.7. Non-Storing Mode
In Non-Storing mode, RPL routes messages Downward using IP source routing. The following rule applies to nodes that are in Non-Storing mode. Storing mode has a separate set of rules, described in Section 9.8. 1. The DODAG Parent Address subfield of a Transit Information option MUST contain one or more addresses. All of these addresses MUST be addresses of DAO parents of the sender. 2. DAOs are sent directly to the root along a default route installed as part of the parent selection. 3. When a node removes a node from its DAO parent set, it MAY generate a new DAO message with an updated Transit Information option.
In Non-Storing mode, a node uses DAOs to report its DAO parents to the DODAG root. The DODAG root can piece together a Downward route to a node by using DAO parent sets from each node in the route. The Path Sequence information may be used to detect stale DAO information. The purpose of this per-hop route calculation is to minimize traffic when DAO parents change. If nodes reported complete source routes, then on a DAO parent change, the entire sub-DODAG would have to send new DAOs to the DODAG root. Therefore, in Non- Storing mode, a node can send a single DAO, although it might choose to send more than one DAO message to each of multiple DAO parents. Nodes pack DAOs by sending a single DAO message with multiple RPL Target options. Each RPL Target option has its own, immediately following, Transit Information options.9.8. Storing Mode
In Storing mode, RPL routes messages Downward by the IPv6 destination address. The following rules apply to nodes that are in Storing mode: 1. The DODAG Parent Address subfield of a Transmit Information option MUST be empty. 2. On receiving a unicast DAO, a node MUST compute if the DAO would change the set of prefixes that the node itself advertises. This computation SHOULD include consultation of the Path Sequence information in the Transit Information options associated with the DAO, to determine if the DAO message contains newer information that supersedes the information already stored at the node. If so, the node MUST generate a new DAO message and transmit it, following the rules in Section 9.5. Such a change includes receiving a No-Path DAO. 3. When a node generates a new DAO, it SHOULD unicast it to each of its DAO parents. It MUST NOT unicast the DAO message to nodes that are not DAO parents. 4. When a node removes a node from its DAO parent set, it SHOULD send a No-Path DAO message (Section 6.4.3) to that removed DAO parent to invalidate the existing route. 5. If messages to an advertised Downward address suffer from a forwarding error, Neighbor Unreachable Detection (NUD), or similar failure, a node MAY mark the address as unreachable and generate an appropriate No-Path DAO.
DAOs advertise to which destination addresses and prefixes a node has routes. Unlike in Non-Storing mode, these DAOs do not communicate information about the routes themselves: that information is stored within the network and is implicit from the IPv6 source address. When a storing node generates a DAO, it uses the stored state of DAOs it has received to produce a set of RPL Target options and their associated Transmit Information options. Because this information is stored within each node's routing tables, in Storing mode, DAOs are communicated directly to DAO parents, who store this information.9.9. Path Control
A DAO message from a node contains one or more Target options. Each Target option specifies either a prefix advertised by the node, a prefix of addresses reachable outside the LLN, the address of a destination in the node's sub-DODAG, or a multicast group to which a node in the sub-DODAG is listening. The Path Control field of the Transit Information option allows nodes to request or allow for multiple Downward routes. A node constructs the Path Control field of a Transit Information option as follows: 1. The bit width of the Path Control field MUST be equal to the value (PCS + 1), where PCS is specified in the control field of the DODAG Configuration option. Bits greater than or equal to the value (PCS + 1) MUST be cleared on transmission and MUST be ignored on reception. Bits below that value are considered "active" bits. 2. The node MUST logically construct groupings of its DAO parents while populating the Path Control field, where each group consists of DAO parents of equal preference. Those groups MUST then be ordered according to preference, which allows for a logical mapping of DAO parents onto Path Control subfields (see Figure 27). Groups MAY be repeated in order to extend over the entire bit width of the patch control field, but the order, including repeated groups, MUST be retained so that preference is properly communicated. 3. For a RPL Target option describing a node's own address or a prefix outside the LLN, at least one active bit of the Path Control field MUST be set. More active bits of the Path Control field MAY be set.
4. If a node receives multiple DAOs with the same RPL Target option,
it MUST bitwise-OR the Path Control fields it receives. This
aggregated bitwise-OR represents the number of Downward routes
the prefix requests.
5. When a node sends a DAO message to one of its DAO parents, it
MUST select one or more of the bits that are set active in the
subfield that is mapped to the group containing that DAO parent
from the aggregated Path Control field. A given bit can only be
presented as active to one parent. The DAO message it transmits
to its parent MUST have these active bits set and all other
active bits cleared.
6. For the RPL Target option and DAOSequence number, the DAOs a node
sends to different DAO parents MUST have disjoint sets of active
Path Control bits. A node MUST NOT set the same active bit on
DAOs to two different DAO parents.
7. Path Control bits SHOULD be allocated according to the preference
mapping of DAO parents onto Path Control subfields, such that the
active Path Control bits, or groupings of bits, that belong to a
particular Path Control subfield are allocated to DAO parents
within the group that was mapped to that subfield.
8. In a Non-Storing mode of operation, a node MAY pass DAOs through
without performing any further processing on the Path Control
field.
9. A node MUST NOT unicast a DAO message that has no active bits in
the Path Control field set. It is possible that, for a given
Target option, a node does not have enough aggregate Path Control
bits to send a DAO message containing that Target to each of its
DAO parents, in which case those least preferred DAO Parents may
not get a DAO message for that Target.
The Path Control field allows a node to bound how many Downward
routes will be generated to it. It sets a number of bits in the Path
Control field equal to the maximum number of Downward routes it
prefers. At most, each bit is sent to one DAO parent; clusters of
bits can be sent to a single DAO parent for it to divide among its
own DAO parents.
A node that provisions a DAO route for a Target that has an
associated Path Control field SHOULD use the content of that Path
Control field in order to determine an order of preference among
multiple alternative DAO routes for that Target. The Path Control
field assignment is derived from preference (of the DAO parents), as
determined on the basis of this node's best knowledge of the "end-to-
end" aggregated metrics in the Downward direction as per the Objective Function. In Non-Storing mode the root can determine the Downward route by aggregating the information from each received DAO, which includes the Path Control indications of preferred DAO parents.9.9.1. Path Control Example
Suppose that there is an LLN operating in Storing mode that contains a Node N with four parents, P1, P2, P3, and P4. Let N have three children, C1, C2, and C3 in its sub-DODAG. Let PCS be 7, such that there will be 8 active bits in the Path Control field: 11111111b. Consider the following example: The Path Control field is split into four subfields, PC1 (11000000b), PC2 (00110000b), PC3 (00001100b), and PC4 (00000011b), such that those four subfields represent four different levels of preference per Figure 27. The implementation at Node N, in this example, groups {P1, P2} to be of equal preference to each other and the most preferred group overall. {P3} is less preferred to {P1, P2}, and more preferred to {P4}. Let Node N then perform its Path Control mapping such that: {P1, P2} -> PC1 (11000000b) in the Path Control field {P3} -> PC2 (00110000b) in the Path Control field {P4} -> PC3 (00001100b) in the Path Control field {P4} -> PC4 (00000011b) in the Path Control field Note that the implementation repeated {P4} in order to get complete coverage of the Path Control field. 1. Let C1 send a DAO containing a Target T with a Path Control 10000000b. Node N stores an entry associating 10000000b with the Path Control field for C1 and Target T. 2. Let C2 send a DAO containing a Target T with a Path Control 00010000b. Node N stores an entry associating 00010000b with the Path Control field for C1 and Target T. 3. Let C3 send a DAO containing a Target T with a Path Control 00001100b. Node N stores an entry associating 00001100b with the Path Control field for C1 and Target T. 4. At some later time, Node N generates a DAO for Target T. Node N will construct an aggregate Path Control field by ORing together the contribution from each of its children that have given a DAO for Target T. Thus, the aggregate Path Control field has the active bits set as: 10011100b.
5. Node N then distributes the aggregate Path Control bits among
its parents P1, P2, P3, and P4 in order to prepare the DAO
messages.
6. P1 and P2 are eligible to receive active bits from the most
preferred subfield (11000000b). Those bits are 10000000b in the
aggregate Path Control field. Node N must set the bit to one of
the two parents only. In this case, Node P1 is allocated the
bit and gets the Path Control field 10000000b for its DAO.
There are no bits left to allocate to Node P2; thus, Node P2
would have a Path Control field of 00000000b and a DAO cannot be
generated to Node P2 since there are no active bits.
7. The second-most preferred subfield (00110000b) has the active
bits 00010000b. Node N has mapped P3 to this subfield. Node N
may allocates the active bit to P3, constructing a DAO for P3
containing Target T with a Path Control of 00010000b.
8. The third-most preferred subfield (00001100b) has the active
bits 00001100b. Node N has mapped P4 to this subfield. Node N
may allocate both bits to P4, constructing a DAO for P4
containing Target T with a Path Control of 00001100b.
9. The least preferred subfield (00000011b) has no active bits.
Had there been active bits, those bits would have been added to
the Path Control field of the DAO constructed for P4.
10. The process of populating the DAO messages destined for P1, P2,
P3, P4 with other targets (other than T) proceeds according to
the aggregate Path Control fields collected for those targets.
9.10. Multicast Destination Advertisement Messages
A special case of DAO operation, distinct from unicast DAO operation,
is multicast DAO operation that may be used to populate '1-hop'
routing table entries.
1. A node MAY multicast a DAO message to the link-local scope all-
RPL-nodes multicast address.
2. A multicast DAO message MUST be used only to advertise
information about the node itself, i.e., prefixes directly
connected to or owned by the node, such as a multicast group that
the node is subscribed to or a global address owned by the node.
3. A multicast DAO message MUST NOT be used to relay connectivity
information learned (e.g., through unicast DAO) from another
node.
4. A node MUST NOT perform any other DAO-related processing on a
received multicast DAO message; in particular, a node MUST NOT
perform the actions of a DAO parent upon receipt of a multicast
DAO.
o The multicast DAO may be used to enable direct P2P communication,
without needing the DODAG to relay the packets.
(page 90 continued on part 5)
