Trickle library
Contents
Introduction
In this tutorial you will get to see what a trickle timer is and what the trickle library file contains. We will also see how we can modify the basic function parameters here according to our needs. The trickle algorithm as stated in the RFC allows nodes in a lossy shared medium to exchange information in a highly robust, energy efficient, simple and scalable manner. The Trickle library contains the functions used to implement the trickle algorithm. Trickle algorithm forms the base on which the trickle timer runs. The trickle timer on the other hand contains the details of the functions which are used in the trickle library. The trickle algorithm is used to check if whether there is any change in the information present in the system. When such a change is detected, sufficient measures are taken to ensure that the inconsistency is resolved.
Objective
The main objective of this tutorial is to explore what a trickle library contains, the algorithm on which the library is based and how a protocol uses this library.
What you will learn
You will get to learn how the code for trickle timer is implemented based on the trickle algorithm, what functions are used in the trickle library to support this algorithm. How the timer interval is set and the parameters can be modified to suit our applications needs.
Description of the trickle algorithm
There are 3 parameters in the trickle algorithm. IMIN, IMAX and k, where IMIN is the min interval size, IMAX is the number of doublings of IMIN and k is the redundancy constant. There are 3 variables I which defines the current interval size, t which states the current time in the interval range, and c which is a counter variable.
Working of the algorithm
Before starting the timer the IMIN value is set from the range [I/2, I]. The counter variable (c) helps keep track of the condition of the system whether it’s inconsistent or consistent. If it’s consistent the counter is incremented, else its reset. This c value must always be less than k (which is called the redundant constant). The trickle is reset to IMIN when the timer expires else it is doubled. Care must be taken to check if the new current interval falls within the range above. The nodes can even be made to suppress the inconsistency when required. This is not recommended but for few applications we might need to disable the suppression by setting k = 0.
The flowchart shown below describes briefly the working of the trickle algorithm.
Usage
Usage: Trickle timers are used in various applications. Most applications may need to periodically check if a node has new information. This is done with the help of a version number. If an inconsistency is detected it means the node does not have new information and needs to update its information. An example protocol which uses trickle timer is the RPL protocol. RPL has DIO and DAO messages which it uses to send and receive messages. The DIO message originates from the sink while the DAO originates from the nodes. This trickle timer helps keep track of the messages sent by the sink when it tells the nodes “I am the sink”. In RPL the DIO’s are sent out periodically and the time gap is increased after every transmission. This is done with the help of a trickle timer.
Code Building Blocks
static struct trickle_timer tt ;
#define IMIN 16 /* ticks */
#define IMAX 10 /* doublings */
#define REDUNDANCY_CONST 2
#define NEW_TOKEN_INTERVAL 10 * CLOCK_SECOND
#define NEW_TOKEN_PROB 2
Here static struct trickle_timer tt; is a pointer to the trickle timer structure which hold various fields related to the working of the trickle algorithm. IMIN here is the minimum interval possible for I to take and the k value is set to 2. Each token is generated with an interval given by the NEW_TOKEN_INTERVAL and with probability 0.5. These values can be changed according to our needs.
There are different timers defined in contiki which is explained in detail in the link -> Timers For communication purpose, a port is defined and is given the number 30001.
PROCESS_THREAD(trickle_protocol_process, ev, data)
{
PROCESS_BEGIN();
PRINTF("Trickle protocol started\n");
uip_create_linklocal_allnodes_mcast(&ipaddr); /* Store for later */
trickle_conn = udp_new(NULL, UIP_HTONS(TRICKLE_PROTO_PORT), NULL);
udp_bind(trickle_conn, UIP_HTONS(TRICKLE_PROTO_PORT));
PRINTF("Connection: local/remote port %u/%u\n",
UIP_HTONS(trickle_conn->lport), UIP_HTONS(trickle_conn->rport));
token = 0;
trickle_timer_config(&tt, IMIN, IMAX, REDUNDANCY_CONST);
trickle_timer_set(&tt, trickle_tx, &tt);
etimer_set(&et, NEW_TOKEN_INTERVAL);
The code above shows how a new thread is created and a local port is opened for communication purpose. The socket is made and port number is bound to it. The initial value of token is set to 0. In the function trickle_timer_config (&tt, IMIN, IMAX, REDUNDANCY_CONST); the respective fields are populated by calling the functions. The timer is started by calling trickle_timer_set(&tt, trickle_tx, &tt);
else if(etimer_expired(&et)) {
if((random_rand() % NEW_TOKEN_PROB) == 0) {
token++;
trickle_timer_reset_event(&tt);
}
etimer_set(&et, NEW_TOKEN_INTERVAL);
The etimer is used to generate inconsistencies periodically. This helps us to make sure the system is in proper working condition. An event handler is specified, to make sure proper handling of inconsistencies takes place. Periodically an inconsistency is triggered by the etimer depending on the interval specified above.
if(ev == tcpip_event) {
tcpip_handler();
}
When the handler is called the function the control goes to the tcpip_handler function defined by, static void tcpip_handler(void) We can use LED’s to help us observe when transmission is taking place. In the handler a check is made to see if a transmission is consistent or not. If a node has new token then an inconsistency is triggered and the token is updated by resetting the timer. A callback is triggered when the timer reaches the specified time. The trickle library provides for this callback. The trickle library depends on the trickle timer along with other timers such as etimer, stimer, ctimer and rtimer. The trickle timer is defined in the trickle-timer.c file which is located in core -> lib -> trickle-timer.c.
In the inconsistent state the function -> void trickle_timer_inconsistency (struct trickle_timer *tt); will call the library and ask it to reset the timer based on the kind on inconsistency. In the consistent state the counter is incremented which is given by the function, void trickle_timer_consistency (struct trickle_timer *tt)
All the functions for setting the parameter values are defined here in the trickle-timer.c. The trickle library forms the base which hold the main functions and function calls are made from here.
Applications where trickle timers are useful
Since trickle library implements the trickle algorithm, this library functions are used by protocols to solve problems such as
- Controlling the traffic timing
- route discovery and
- Multicast propagation.
Debug
After making the desired changes we need to make sure that the timers work without errors. To debug we need to go to the folder containing the file: cd contiki2.7/examples/trickle-library Once inside the folder,type the following on the terminal.
make TARGET=sky
This command will create an executable file with .sky extension.
References
[1] https://tools.ietf.org/html/draft-ietf-roll-trickle-08
[2] http://anrg.usc.edu/contiki/index.php/Timers
[3] http://www.bth.se/fou/cuppsats.nsf/all/418758357c3441b8c1257aca002d2932/$file/BTH2012Hazrat.pdf
[4] http://www.tinyos.net/tinyos-2.x/doc/nesdoc/micaz/ihtml/tos.lib.net.TrickleTimer.html
