## 3 RPL Overview
### Trickle Algorithm  
As mentioned in Section 3.1, RPL uses the Trickle algorithm to schedule and transmit DIO messages in a network [25]. Therefore, Trickle plays a key role in the convergence of a RPL network. Trickle is a density-aware local multicast communication mechanism that is based on a consistency model. According to this model, a network is in a consistent state when it does not suffer changes and therefore DIO messages are consistent with prior DIO messages transmitted. In this case, nodes slow their DIO message rate exponentially. However, when a node detects an inconsistency, it increases its DIO message transmission rate to resolve the inconsistency quickly. On the other hand, Trickle supports a message suppression mechanism that aims at minimizing the DIO message redundancy in a network. A detailed presentation of the Trickle algorithm is provided next.  
Trickle divides time into non-identical intervals. In each interval, every node attempts to send one DIO message. Trickle rules determine whether the transmission will be allowed or not. The Trickle algorithm operates based on a set of parameters, variables and rules, which are reviewed next.  
There are three parameters that configure the Trickle algorithm:  
* The minimum interval size, \(I_{min}\).
* The maximum interval size, \(I_{max}\).
* The redundancy constant, \(k\).  
In addition, the Trickle algorithm uses three variables that track the current status of the algorithm. These variables are: the current interval size, \(I\), the tentative transmission time within the current interval, \(t\), and the number of messages heard within the current interval, \(c\).  
The operation of Trickle is based on the following steps:  
1. Initially, Trickle sets \(I\) to a value in the range \([I_{min},I_{max}]\).
2. At the beginning of each interval, Trickle resets \(c\) to 0 and sets \(t\) to a random point within the range \([I\)/2,\(I\)).
3. Whenever Trickle hears a transmission that is consistent, it increments its own counter \(c\).
4. At time \(t\), Trickle performs the transmission if, and only if, its counter \(c\) is smaller than the redundancy constant, \(k\); otherwise, the transmission is suppressed.
5. Whenever the interval \(I\) expires, Trickle doubles the interval length (if the new interval length is greater than \(I_{max}\), the new interval length is set to \(I_{max}\)). Then, the algorithm goes back to execute step 2.
6. If Trickle hears a transmission that is inconsistent, it must reset \(I\), set this variable to \(I_{min}\), start a new interval and execute step 2.  
The three main parameters of the Trickle algorithm, \(I_{min}\), \(I_{max}\) and \(k\), are set by the DODAG root. The values for these parameters are encapsulated in the DIO messages sent by the root. Hence, these parameter values are learnt by the root neighbors upon DIO reception, and are included in the DIO messages sent by these neighbors. The same process happens for the rest of nodes that join the DODAG, and thus the parameter values originally announced by the root are propagated to the whole DODAG. In order to keep a low network convergence time, \(I_{min}\) is commonly used as the value for the first interval [28].