Skip to main content

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 "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.

  • Let Figure 3-1 be the initial condition.

  • 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.

  • 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, 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.

  • 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.

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

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

  • 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.

  • 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.

Last updated on