Tech-invite3GPPspaceIETF RFCsSIP
9190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 6550

RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks

Pages: 157
Proposed Standard
Errata
Updated by:  90089010
Part 2 of 6 – Pages 13 to 30
First   Prev   Next

Top   ToC   RFC6550 - Page 13   prevText

3. Protocol Overview

The aim of this section is to describe RPL in the spirit of [RFC4101]. Protocol details can be found in further sections.

3.1. Topologies

This section describes the basic RPL topologies that may be formed, and the rules by which these are constructed, i.e., the rules governing DODAG formation.

3.1.1. Constructing Topologies

LLNs, such as Radio Networks, do not typically have predefined topologies, for example, those imposed by point-to-point wires, so RPL has to discover links and then select peers sparingly. In many cases, because Layer 2 ranges overlap only partially, RPL forms non-transitive / Non-Broadcast Multi-Access (NBMA) network topologies upon which it computes routes. RPL routes are optimized for traffic to or from one or more roots that act as sinks for the topology. As a result, RPL organizes a topology as a Directed Acyclic Graph (DAG) that is partitioned into
Top   ToC   RFC6550 - Page 14
   one or more Destination Oriented DAGs (DODAGs), one DODAG per sink.
   If the DAG has multiple roots, then it is expected that the roots are
   federated by a common backbone, such as a transit link.

3.1.2. RPL Identifiers

RPL uses four values to identify and maintain a topology: o The first is a RPLInstanceID. A RPLInstanceID identifies a set of one or more Destination Oriented DAGs (DODAGs). A network may have multiple RPLInstanceIDs, each of which defines an independent set of DODAGs, which may be optimized for different Objective Functions (OFs) and/or applications. The set of DODAGs identified by a RPLInstanceID is called a RPL Instance. All DODAGs in the same RPL Instance use the same OF. o The second is a DODAGID. The scope of a DODAGID is a RPL Instance. The combination of RPLInstanceID and DODAGID uniquely identifies a single DODAG in the network. A RPL Instance may have multiple DODAGs, each of which has an unique DODAGID. o The third is a DODAGVersionNumber. The scope of a DODAGVersionNumber is a DODAG. A DODAG is sometimes reconstructed from the DODAG root, by incrementing the DODAGVersionNumber. The combination of RPLInstanceID, DODAGID, and DODAGVersionNumber uniquely identifies a DODAG Version. o The fourth is Rank. The scope of Rank is a DODAG Version. Rank establishes a partial order over a DODAG Version, defining individual node positions with respect to the DODAG root.

3.1.3. Instances, DODAGs, and DODAG Versions

A RPL Instance contains one or more DODAG roots. A RPL Instance may provide routes to certain destination prefixes, reachable via the DODAG roots or alternate paths within the DODAG. These roots may operate independently, or they may coordinate over a network that is not necessarily as constrained as an LLN. A RPL Instance may comprise: o a single DODAG with a single root * For example, a DODAG optimized to minimize latency rooted at a single centralized lighting controller in a Home Automation application.
Top   ToC   RFC6550 - Page 15
   o  multiple uncoordinated DODAGs with independent roots (differing
      DODAGIDs)

      *  For example, multiple data collection points in an urban data
         collection application that do not have suitable connectivity
         to coordinate with each other or that use the formation of
         multiple DODAGs as a means to dynamically and autonomously
         partition the network.

   o  a single DODAG with a virtual root that coordinates LLN sinks
      (with the same DODAGID) over a backbone network.

      *  For example, multiple border routers operating with a reliable
         transit link, e.g., in support of an IPv6 Low-Power Wireless
         Personal Area Network (6LoWPAN) application, that are capable
         of acting as logically equivalent interfaces to the sink of the
         same DODAG.

   o  a combination of the above as suited to some application scenario.

   Each RPL packet is associated with a particular RPLInstanceID (see
   Section 11.2) and, therefore, RPL Instance (Section 5).  The
   provisioning or automated discovery of a mapping between a
   RPLInstanceID and a type or service of application traffic is out of
   scope for this specification (to be defined in future companion
   specifications).

   Figure 1 depicts an example of a RPL Instance comprising three DODAGs
   with DODAG roots R1, R2, and R3.  Each of these DODAG roots
   advertises the same RPLInstanceID.  The lines depict connectivity
   between parents and children.

   Figure 2 depicts how a DODAGVersionNumber increment leads to a new
   DODAG Version.  This depiction illustrates a DODAGVersionNumber
   increment that results in a different DODAG topology.  Note that a
   new DODAG Version does not always imply a different DODAG topology.
   To accommodate certain topology changes requires a new DODAG Version,
   as described later in this specification.

   In the following examples, please note that tree-like structures are
   depicted for simplicity, although the DODAG structure allows for each
   node to have multiple parents when the connectivity supports it.
Top   ToC   RFC6550 - Page 16
     +----------------------------------------------------------------+
     |                                                                |
     | +--------------+                                               |
     | |              |                                               |
     | |     (R1)     |            (R2)                   (R3)        |
     | |     /  \     |            /| \                  / |  \       |
     | |    /    \    |           / |  \                /  |   \      |
     | |  (A)    (B)  |         (C) |  (D)     ...    (F) (G)  (H)    |
     | |  /|\     |\  |         /   | / |\             |\  |    |     |
     | | : : :    : : |        :   (E)  : :            :  `:    :     |
     | |              |            / \                                |
     | +--------------+           :   :                               |
     |      DODAG                                                     |
     |                                                                |
     +----------------------------------------------------------------+
                                RPL Instance

                          Figure 1: RPL Instance

            +----------------+                +----------------+
            |                |                |                |
            |      (R1)      |                |      (R1)      |
            |      /  \      |                |      /         |
            |     /    \     |                |     /          |
            |   (A)    (B)   |         \      |   (A)          |
            |   /|\   / |\   |    ------\     |   /|\          |
            |  : : (C)  : :  |           \    |  : : (C)       |
            |                |           /    |        \       |
            |                |    ------/     |         \      |
            |                |         /      |         (B)    |
            |                |                |          |\    |
            |                |                |          : :   |
            |                |                |                |
            +----------------+                +----------------+
                Version N                        Version N+1

                          Figure 2: DODAG Version

3.2. Upward Routes and DODAG Construction

RPL provisions routes Up towards DODAG roots, forming a DODAG optimized according to an Objective Function (OF). RPL nodes construct and maintain these DODAGs through DODAG Information Object (DIO) messages.
Top   ToC   RFC6550 - Page 17

3.2.1. Objective Function (OF)

The Objective Function (OF) defines how RPL nodes select and optimize routes within a RPL Instance. The OF is identified by an Objective Code Point (OCP) within the DIO Configuration option. An OF defines how nodes translate one or more metrics and constraints, which are themselves defined in [RFC6551], into a value called Rank, which approximates the node's distance from a DODAG root. An OF also defines how nodes select parents. Further details may be found in Section 14, [RFC6551], [RFC6552], and related companion specifications.

3.2.2. DODAG Repair

A DODAG root institutes a global repair operation by incrementing the DODAGVersionNumber. This initiates a new DODAG Version. Nodes in the new DODAG Version can choose a new position whose Rank is not constrained by their Rank within the old DODAG Version. RPL also supports mechanisms that may be used for local repair within the DODAG Version. The DIO message specifies the necessary parameters as configured from and controlled by policy at the DODAG root.

3.2.3. Security

RPL supports message confidentiality and integrity. It is designed such that link-layer mechanisms can be used when available and appropriate; yet, in their absence, RPL can use its own mechanisms. RPL has three basic security modes. In the first, called "unsecured", RPL control messages are sent without any additional security mechanisms. Unsecured mode does not imply that the RPL network is unsecure: it could be using other present security primitives (e.g., link-layer security) to meet application security requirements. In the second, called "preinstalled", nodes joining a RPL Instance have preinstalled keys that enable them to process and generate secured RPL messages. The third mode is called "authenticated". In authenticated mode, nodes have preinstalled keys as in preinstalled mode, but the preinstalled key may only be used to join a RPL Instance as a leaf. Joining an authenticated RPL Instance as a router requires obtaining a key from an authentication authority. The process by which this key is obtained is out of scope for this specification. Note that this specification alone does not provide sufficient detail for a RPL
Top   ToC   RFC6550 - Page 18
   implementation to securely operate in authenticated mode.  For a RPL
   implementation to operate securely in authenticated mode, it is
   necessary for a future companion specification to detail the
   mechanisms by which a node obtains/requests the authentication
   material (e.g., key, certificate) and to determine from where that
   material should be obtained.  See also Section 10.3.

3.2.4. Grounded and Floating DODAGs

DODAGs can be grounded or floating: the DODAG root advertises which is the case. A grounded DODAG offers connectivity to hosts that are required for satisfying the application-defined goal. A floating DODAG is not expected to satisfy the goal; in most cases, it only provides routes to nodes within the DODAG. Floating DODAGs may be used, for example, to preserve interconnectivity during repair.

3.2.5. Local DODAGs

RPL nodes can optimize routes to a destination within an LLN by forming a Local DODAG whose DODAG root is the desired destination. Unlike global DAGs, which can consist of multiple DODAGs, local DAGs have one and only one DODAG and therefore one DODAG root. Local DODAGs can be constructed on demand.

3.2.6. Administrative Preference

An implementation/deployment may specify that some DODAG roots should be used over others through an administrative preference. Administrative preference offers a way to control traffic and engineer DODAG formation in order to better support application requirements or needs.

3.2.7. Data-Path Validation and Loop Detection

The low-power and lossy nature of LLNs motivates RPL's use of on- demand loop detection using data packets. Because data traffic can be infrequent, maintaining a routing topology that is constantly up to date with the physical topology can waste energy. Typical LLNs exhibit variations in physical connectivity that are transient and innocuous to traffic, but that would be costly to track closely from the control plane. Transient and infrequent changes in connectivity need not be addressed by RPL until there is data to send. This aspect of RPL's design draws from existing, highly used LLN protocols as well as extensive experimental and deployment evidence on its efficacy.
Top   ToC   RFC6550 - Page 19
   The RPL Packet Information that is transported with data packets
   includes the Rank of the transmitter.  An inconsistency between the
   routing decision for a packet (Upward or Downward) and the Rank
   relationship between the two nodes indicates a possible loop.  On
   receiving such a packet, a node institutes a local repair operation.

   For example, if a node receives a packet flagged as moving in the
   Upward direction, and if that packet records that the transmitter is
   of a lower (lesser) Rank than the receiving node, then the receiving
   node is able to conclude that the packet has not progressed in the
   Upward direction and that the DODAG is inconsistent.

3.2.8. Distributed Algorithm Operation

A high-level overview of the distributed algorithm, which constructs the DODAG, is as follows: o Some nodes are configured to be DODAG roots, with associated DODAG configurations. o Nodes advertise their presence, affiliation with a DODAG, routing cost, and related metrics by sending link-local multicast DIO messages to all-RPL-nodes. o Nodes listen for DIOs and use their information to join a new DODAG (thus, selecting DODAG parents), or to maintain an existing DODAG, according to the specified Objective Function and Rank of their neighbors. o Nodes provision routing table entries, for the destinations specified by the DIO message, via their DODAG parents in the DODAG Version. Nodes that decide to join a DODAG can provision one or more DODAG parents as the next hop for the default route and a number of other external routes for the associated instance.

3.3. Downward Routes and Destination Advertisement

RPL uses Destination Advertisement Object (DAO) messages to establish Downward routes. DAO messages are an optional feature for applications that require point-to-multipoint (P2MP) or point-to- point (P2P) traffic. RPL supports two modes of Downward traffic: Storing (fully stateful) or Non-Storing (fully source routed); see Section 9. Any given RPL Instance is either storing or non-storing. In both cases, P2P packets travel Up toward a DODAG root then Down to the final destination (unless the destination is on the Upward route). In the Non-Storing case, the packet will travel all the way to a DODAG root before traveling Down. In the Storing case, the
Top   ToC   RFC6550 - Page 20
   packet may be directed Down towards the destination by a common
   ancestor of the source and the destination prior to reaching a DODAG
   root.

   As of the writing of this specification, no implementation is
   expected to support both Storing and Non-Storing modes of operation.
   Most implementations are expected to support either no Downward
   routes, Non-Storing mode only, or Storing mode only.  Other modes of
   operation, such as a hybrid mix of Storing and Non-Storing mode, are
   out of scope for this specification and may be described in other
   companion specifications.

   This specification describes a basic mode of operation in support of
   P2P traffic.  Note that more optimized P2P solutions may be described
   in companion specifications.

3.4. Local DODAGs Route Discovery

Optionally, a RPL network can support on-demand discovery of DODAGs to specific destinations within an LLN. Such Local DODAGs behave slightly differently than Global DODAGs: they are uniquely defined by the combination of DODAGID and RPLInstanceID. The RPLInstanceID denotes whether a DODAG is a Local DODAG.

3.5. Rank Properties

The Rank of a node is a scalar representation of the location of that node within a DODAG Version. The Rank is used to avoid and detect loops and, as such, must demonstrate certain properties. The exact calculation of the Rank is left to the Objective Function. Even though the specific computation of the Rank is left to the Objective Function, the Rank must implement generic properties regardless of the Objective Function. In particular, the Rank of the nodes must monotonically decrease as the DODAG Version is followed towards the DODAG destination. In that regard, the Rank can be considered a scalar representation of the location or radius of a node within a DODAG Version. The details of how the Objective Function computes Rank are out of scope for this specification, although that computation may depend, for example, on parents, link metrics, node metrics, and the node configuration and policies. See Section 14 for more information. The Rank is not a path cost, although its value can be derived from and influenced by path metrics. The Rank has properties of its own that are not necessarily those of all metrics:
Top   ToC   RFC6550 - Page 21
   Type: The Rank is an abstract numeric value.

   Function: The Rank is the expression of a relative position within a
         DODAG Version with regard to neighbors, and it is not
         necessarily a good indication or a proper expression of a
         distance or a path cost to the root.

   Stability: The stability of the Rank determines the stability of the
         routing topology.  Some dampening or filtering is RECOMMENDED
         to keep the topology stable; thus, the Rank does not
         necessarily change as fast as some link or node metrics would.
         A new DODAG Version would be a good opportunity to reconcile
         the discrepancies that might form over time between metrics and
         Ranks within a DODAG Version.

   Properties: The Rank is incremented in a strictly monotonic fashion,
         and it can be used to validate a progression from or towards
         the root.  A metric, like bandwidth or jitter, does not
         necessarily exhibit this property.

   Abstract: The Rank does not have a physical unit, but rather a range
         of increment per hop, where the assignment of each increment is
         to be determined by the Objective Function.

   The Rank value feeds into DODAG parent selection, according to the
   RPL loop-avoidance strategy.  Once a parent has been added, and a
   Rank value for the node within the DODAG has been advertised, the
   node's further options with regard to DODAG parent selection and
   movement within the DODAG are restricted in favor of loop avoidance.

3.5.1. Rank Comparison (DAGRank())

Rank may be thought of as a fixed-point number, where the position of the radix point between the integer part and the fractional part is determined by MinHopRankIncrease. MinHopRankIncrease is the minimum increase in Rank between a node and any of its DODAG parents. A DODAG root provisions MinHopRankIncrease. MinHopRankIncrease creates a trade-off between hop cost precision and the maximum number of hops a network can support. A very large MinHopRankIncrease, for example, allows precise characterization of a given hop's effect on Rank but cannot support many hops. When an Objective Function computes Rank, the Objective Function operates on the entire (i.e., 16-bit) Rank quantity. When Rank is compared, e.g., for determination of parent relationships or loop detection, the integer portion of the Rank is to be used. The
Top   ToC   RFC6550 - Page 22
   integer portion of the Rank is computed by the DAGRank() macro as
   follows, where floor(x) is the function that evaluates to the
   greatest integer less than or equal to x:

              DAGRank(rank) = floor(rank/MinHopRankIncrease)

   For example, if a 16-bit Rank quantity is decimal 27, and the
   MinHopRankIncrease is decimal 16, then DAGRank(27) = floor(1.6875) =
   1.  The integer part of the Rank is 1 and the fractional part is
   11/16.

   Following the conventions in this document, using the macro
   DAGRank(node) may be interpreted as DAGRank(node.rank), where
   node.rank is the Rank value as maintained by the node.

   A Node A has a Rank less than the Rank of a Node B if DAGRank(A) is
   less than DAGRank(B).

   A Node A has a Rank equal to the Rank of a Node B if DAGRank(A) is
   equal to DAGRank(B).

   A Node A has a Rank greater than the Rank of a Node B if DAGRank(A)
   is greater than DAGRank(B).

3.5.2. Rank Relationships

Rank computations maintain the following properties for any nodes M and N that are neighbors in the LLN: DAGRank(M) is less than DAGRank(N): In this case, the position of M is closer to the DODAG root than the position of N. Node M may safely be a DODAG parent for Node N without risk of creating a loop. Further, for a Node N, all parents in the DODAG parent set must be of a Rank less than DAGRank(N). In other words, the Rank presented by a Node N MUST be greater than that presented by any of its parents. DAGRank(M) equals DAGRank(N): In this case, the positions of M and N within the DODAG and with respect to the DODAG root are similar or identical. Routing through a node with equal Rank may cause a routing loop (i.e., if that node chooses to route through a node with equal Rank as well).
Top   ToC   RFC6550 - Page 23
   DAGRank(M) is greater than DAGRank(N):

      In this case, the position of M is farther from the DODAG root
      than the position of N.  Further, Node M may in fact be in the
      sub-DODAG of Node N.  If Node N selects Node M as DODAG parent,
      there is a risk of creating a loop.

   As an example, the Rank could be computed in such a way so as to
   closely track ETX (expected transmission count, a fairly common
   routing metric used in LLN and defined in [RFC6551]) when the metric
   that an Objective Function minimizes is ETX, or latency, or in a more
   complicated way as appropriate to the Objective Function being used
   within the DODAG.

3.6. Routing Metrics and Constraints Used by RPL

Routing metrics are used by routing protocols to compute shortest paths. Interior Gateway Protocols (IGPs) such as IS-IS ([RFC5120]) and OSPF ([RFC4915]) use static link metrics. Such link metrics can simply reflect the bandwidth or can also be computed according to a polynomial function of several metrics defining different link characteristics. Some routing protocols support more than one metric: in the vast majority of the cases, one metric is used per (sub-)topology. Less often, a second metric may be used as a tiebreaker in the presence of Equal Cost Multiple Paths (ECMPs). The optimization of multiple metrics is known as an NP-complete problem and is sometimes supported by some centralized path computation engine. In contrast, LLNs do require the support of both static and dynamic metrics. Furthermore, both link and node metrics are required. In the case of RPL, it is virtually impossible to define one metric, or even a composite metric, that will satisfy all use cases. In addition, RPL supports constraint-based routing where constraints may be applied to both link and nodes. If a link or a node does not satisfy a required constraint, it is "pruned" from the candidate neighbor set, thus leading to a constrained shortest path. An Objective Function specifies the objectives used to compute the (constrained) path. Furthermore, nodes are configured to support a set of metrics and constraints and select their parents in the DODAG according to the metrics and constraints advertised in the DIO messages. Upstream and Downstream metrics may be merged or advertised separately depending on the OF and the metrics. When they are advertised separately, it may happen that the set of DIO parents
Top   ToC   RFC6550 - Page 24
   is different from the set of DAO parents (a DAO parent is a node to
   which unicast DAO messages are sent).  Yet, all are DODAG parents
   with regard to the rules for Rank computation.

   The Objective Function is decoupled from the routing metrics and
   constraints used by RPL.  Whereas the OF dictates rules such as DODAG
   parent selection, load balancing, and so on, the set of metrics
   and/or constraints used, and thus those that determine the preferred
   path, are based on the information carried within the DAG container
   option in DIO messages.

   The set of supported link/node constraints and metrics is specified
   in [RFC6551].

   Example 1: Shortest path: path offering the shortest end-to-end
              delay.

   Example 2: Shortest Constrained path: the path that does not traverse
              any battery-operated node and that optimizes the path
              reliability.

3.7. Loop Avoidance

RPL tries to avoid creating loops when undergoing topology changes and includes Rank-based data-path validation mechanisms for detecting loops when they do occur (see Section 11 for more details). In practice, this means that RPL guarantees neither loop-free path selection nor tight delay convergence times, but it can detect and repair a loop as soon as it is used. RPL uses this loop detection to ensure that packets make forward progress within the DODAG Version and trigger repairs when necessary.

3.7.1. Greediness and Instability

A node is greedy if it attempts to move deeper (increase Rank) in the DODAG Version in order to increase the size of the parent set or improve some other metric. Once a node has joined a DODAG Version, RPL disallows certain behaviors, including greediness, in order to prevent resulting instabilities in the DODAG Version. Suppose a node is willing to receive and process a DIO message from a node in its own sub-DODAG and, in general, a node deeper than itself. In this case, a possibility exists that a feedback loop is created, wherein two or more nodes continue to try and move in the DODAG Version while attempting to optimize against each other. In some cases, this will result in instability. It is for this reason that RPL limits the cases where a node may process DIO messages from deeper nodes to some form of local repair. This approach creates an
Top   ToC   RFC6550 - Page 25
   "event horizon", whereby a node cannot be influenced beyond some
   limit into an instability by the action of nodes that may be in its
   own sub-DODAG.

3.7.1.1. Example: Greedy Parent Selection and Instability
(A) (A) (A) |\ |\ |\ | `-----. | `-----. | `-----. | \ | \ | \ (B) (C) (B) \ | (C) \ | | / `-----. | | .-----' \| |/ (C) (B) -1- -2- -3- Figure 3: Greedy DODAG Parent Selection Figure 3 depicts a DODAG in three different configurations. A usable link between (B) and (C) exists in all three configurations. In Figure 3-1, Node (A) is a DODAG parent for Nodes (B) and (C). In Figure 3-2, Node (A) is a DODAG parent for Nodes (B) and (C), and Node (B) is also a DODAG parent for Node (C). In Figure 3-3, Node (A) is a DODAG parent for Nodes (B) and (C), and Node (C) is also a DODAG parent for Node (B). If a RPL node is too greedy, in that it attempts to optimize for an additional number of parents beyond its most preferred parents, then an instability can result. Consider the DODAG illustrated in Figure 3-1. In this example, Nodes (B) and (C) may most prefer Node (A) as a DODAG parent, but we will consider the case when they are operating under the greedy condition that will try to optimize for two parents. o Let Figure 3-1 be the initial condition. o Suppose Node (C) first is able to leave the DODAG and rejoin at a lower Rank, taking both Nodes (A) and (B) as DODAG parents as depicted in Figure 3-2. Now Node (C) is deeper than both Nodes (A) and (B), and Node (C) is satisfied to have two DODAG parents. o Suppose Node (B), in its greediness, is willing to receive and process a DIO message from Node (C) (against the rules of RPL), and then Node (B) leaves the DODAG and rejoins at a lower Rank,
Top   ToC   RFC6550 - Page 26
      taking both Nodes (A) and (C) as DODAG parents.  Now Node (B) is
      deeper than both Nodes (A) and (C) and is satisfied with two DAG
      parents.

   o  Then, Node (C), because it is also greedy, will leave and rejoin
      deeper, to again get two parents and have a lower Rank then both
      of them.

   o  Next, Node (B) will again leave and rejoin deeper, to again get
      two parents.

   o  Again, Node (C) leaves and rejoins deeper.

   o  The process will repeat, and the DODAG will oscillate between
      Figure 3-2 and Figure 3-3 until the nodes count to infinity and
      restart the cycle again.

   o  This cycle can be averted through mechanisms in RPL:

      *  Nodes (B) and (C) stay at a Rank sufficient to attach to their
         most preferred parent (A) and don't go for any deeper (worse)
         alternate parents (Nodes are not greedy).

      *  Nodes (B) and (C) do not process DIO messages from nodes deeper
         than themselves (because such nodes are possibly in their own
         sub-DODAGs).

   These mechanisms are further described in Section 8.2.2.4.

3.7.2. DODAG Loops

A DODAG loop may occur when a node detaches from the DODAG and reattaches to a device in its prior sub-DODAG. In particular, this may happen when DIO messages are missed. Strict use of the DODAGVersionNumber can eliminate this type of loop, but this type of loop may possibly be encountered when using some local repair mechanisms. For example, consider the local repair mechanism that allows a node to detach from the DODAG, advertise a Rank of INFINITE_RANK (in order to poison its routes / inform its sub-DODAG), and then reattach to the DODAG. In some of these cases, the node may reattach to its own prior-sub-DODAG, causing a DODAG loop, because the poisoning may fail if the INFINITE_RANK advertisements are lost in the LLN environment. (In this case, the Rank-based data-path validation mechanisms would eventually detect and trigger correction of the loop).
Top   ToC   RFC6550 - Page 27

3.7.3. DAO Loops

A DAO loop may occur when the parent has a route installed upon receiving and processing a DAO message from a child, but the child has subsequently cleaned up the related DAO state. This loop happens when a No-Path (a DAO message that invalidates a previously announced prefix, see Section 6.4.3) was missed and persists until all state has been cleaned up. RPL includes an optional mechanism to acknowledge DAO messages, which may mitigate the impact of a single DAO message being missed. RPL includes loop detection mechanisms that mitigate the impact of DAO loops and trigger their repair. (See Section 11.2.2.3.)

4. Traffic Flows Supported by RPL

RPL supports three basic traffic flows: multipoint-to-point (MP2P), point-to-multipoint (P2MP), and point-to-point (P2P).

4.1. Multipoint-to-Point Traffic

Multipoint-to-point (MP2P) is a dominant traffic flow in many LLN applications ([RFC5867], [RFC5826], [RFC5673], and [RFC5548]). The destinations of MP2P flows are designated nodes that have some application significance, such as providing connectivity to the larger Internet or core private IP network. RPL supports MP2P traffic by allowing MP2P destinations to be reached via DODAG roots.

4.2. Point-to-Multipoint Traffic

Point-to-multipoint (P2MP) is a traffic pattern required by several LLN applications ([RFC5867], [RFC5826], [RFC5673], and [RFC5548]). RPL supports P2MP traffic by using a destination advertisement mechanism that provisions Down routes toward destinations (prefixes, addresses, or multicast groups), and away from roots. Destination advertisements can update routing tables as the underlying DODAG topology changes.

4.3. Point-to-Point Traffic

RPL DODAGs provide a basic structure for point-to-point (P2P) traffic. For a RPL network to support P2P traffic, a root must be able to route packets to a destination. Nodes within the network may also have routing tables to destinations. A packet flows towards a root until it reaches an ancestor that has a known route to the destination. As pointed out later in this document, in the most constrained case (when nodes cannot store routes), that common ancestor may be the DODAG root. In other cases, it may be a node closer to both the source and destination.
Top   ToC   RFC6550 - Page 28
   RPL also supports the case where a P2P destination is a 'one-hop'
   neighbor.

   RPL neither specifies nor precludes additional mechanisms for
   computing and installing potentially more optimal routes to support
   arbitrary P2P traffic.

5. RPL Instance

Within a given LLN, there may be multiple, logically independent RPL Instances. A RPL node may belong to multiple RPL Instances, and it may act as a router in some and as a leaf in others. This document describes how a single instance behaves. There are two types of RPL Instances: Local and Global. RPL divides the RPLInstanceID space between Global and Local instances to allow for both coordinated and unilateral allocation of RPLInstanceIDs. Global RPL Instances are coordinated, have one or more DODAGs, and are typically long-lived. Local RPL Instances are always a single DODAG whose singular root owns the corresponding DODAGID and allocates the local RPLInstanceID in a unilateral manner. Local RPL Instances can be used, for example, for constructing DODAGs in support of a future on-demand routing solution. The mode of operation of Local RPL Instances is out of scope for this specification and may be described in other companion specifications. The definition and provisioning of RPL Instances are out of scope for this specification. Guidelines may be application and implementation specific, and they are expected to be elaborated in future companion specifications. Those operations are expected to be such that data packets coming from the outside of the RPL network can unambiguously be associated to at least one RPL Instance and be safely routed over any instance that would match the packet. Control and data packets within RPL network are tagged to unambiguously identify of which RPL Instance they are a part. Every RPL control message has a RPLInstanceID field. Some RPL control messages, when referring to a local RPLInstanceID as defined below, may also include a DODAGID. Data packets that flow within the RPL network expose the RPLInstanceID as part of the RPL Packet Information that RPL requires, as further described in Section 11.2. For data packets coming from outside the RPL network, the ingress router determines the RPLInstanceID and places it into the resulting packet that it injects into the RPL network.
Top   ToC   RFC6550 - Page 29

5.1. RPL Instance ID

A global RPLInstanceID MUST be unique to the whole LLN. Mechanisms for allocating and provisioning global RPLInstanceID are out of scope for this specification. There can be up to 128 Global instance in the whole network. Local instances are always used in conjunction with a DODAGID (which is either given explicitly or implicitly in some cases), and up 64 Local instances per DODAGID can be supported. Local instances are allocated and managed by the node that owns the DODAGID, without any explicit coordination with other nodes, as further detailed below. A global RPLInstanceID is encoded in a RPLInstanceID field as follows: 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ |0| ID | Global RPLInstanceID in 0..127 +-+-+-+-+-+-+-+-+ Figure 4: RPLInstanceID Field Format for Global Instances A local RPLInstanceID is autoconfigured by the node that owns the DODAGID and it MUST be unique for that DODAGID. The DODAGID used to configure the local RPLInstanceID MUST be a reachable IPv6 address of the node, and it MUST be used as an endpoint of all communications within that Local instance. A local RPLInstanceID is encoded in a RPLInstanceID field as follows: 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ |1|D| ID | Local RPLInstanceID in 0..63 +-+-+-+-+-+-+-+-+ Figure 5: RPLInstanceID Field Format for Local Instances The 'D' flag in a local RPLInstanceID is always set to 0 in RPL control messages. It is used in data packets to indicate whether the DODAGID is the source or the destination of the packet. If the 'D' flag is set to 1, then the destination address of the IPv6 packet MUST be the DODAGID. If the 'D' flag is cleared, then the source address of the IPv6 packet MUST be the DODAGID. For example, consider a Node A that is the DODAG root of a Local RPL Instance, and has allocated a local RPLInstanceID. By definition, all traffic traversing that Local RPL Instance will either originate or terminate at Node A. In this case, the DODAGID will be the
Top   ToC   RFC6550 - Page 30
   reachable IPv6 address of Node A.  All traffic will contain the
   address of Node A, and thus the DODAGID, in either the source or
   destination address.  Thus, the local RPLInstanceID may indicate that
   the DODAGID is equivalent to either the source address or the
   destination address by setting the 'D' flag appropriately.



(page 30 continued on part 3)

Next Section