Skip to main content

The Trickle Algorithm
RFC 6206

Revision differences

Document history

Date Rev. By Action
2017-05-16
08 (System) Changed document authors from "Thomas Clausen, Omprakash Gnawali, Jonathan Hui, JeongGil Ko" to "Thomas Clausen, Omprakash Gnawali, Jonathan Hui, JeongGil Ko, P Levis"
2015-10-14
08 (System) Notify list changed from roll-chairs@ietf.org, draft-ietf-roll-trickle@ietf.org to (None)
2012-08-22
08 (System) post-migration administrative database adjustment to the No Objection position for Stewart Bryant
2012-08-22
08 (System) post-migration administrative database adjustment to the No Objection position for Tim Polk
2012-08-22
08 (System) post-migration administrative database adjustment to the No Objection position for Lars Eggert
2011-03-31
08 Cindy Morgan State changed to RFC Published from RFC Ed Queue.
2011-03-31
08 Cindy Morgan [Note]: 'RFC 6206' added by Cindy Morgan
2011-03-29
08 (System) RFC published
2011-01-11
08 Cindy Morgan State changed to RFC Ed Queue from Approved-announcement sent.
2011-01-11
08 (System) IANA Action state changed to No IC from In Progress
2011-01-11
08 (System) IANA Action state changed to In Progress
2011-01-11
08 Amy Vezza IESG state changed to Approved-announcement sent
2011-01-11
08 Amy Vezza IESG has approved the document
2011-01-11
08 Amy Vezza Closed "Approve" ballot
2011-01-11
08 Amy Vezza State changed to Approved-announcement to be sent from IESG Evaluation - Defer::AD Followup.
2011-01-11
08 Adrian Farrel Approval announcement text changed
2011-01-11
08 Adrian Farrel Approval announcement text regenerated
2011-01-11
08 Adrian Farrel Ballot writeup text changed
2011-01-11
08 Lars Eggert [Ballot Position Update] Position for Lars Eggert has been changed to No Objection from Discuss
2011-01-10
08 Stewart Bryant [Ballot Position Update] Position for Stewart Bryant has been changed to No Objection from Discuss
2011-01-10
08 (System) Sub state has been changed to AD Follow up from New Id Needed
2011-01-10
08 (System) New version available: draft-ietf-roll-trickle-08.txt
2011-01-06
08 Cindy Morgan State changed to IESG Evaluation - Defer::Revised ID Needed from IESG Evaluation - Defer.
2011-01-06
08 Jari Arkko
[Ballot comment]
Well written specification and an interesting read. Thanks.

Looking at the other discusses, I do think that this is in the ROLL
charter. …
[Ballot comment]
Well written specification and an interesting read. Thanks.

Looking at the other discusses, I do think that this is in the ROLL
charter. Its part of the routing mechanisms.
2011-01-06
08 Jari Arkko [Ballot Position Update] New position, Yes, has been recorded by Jari Arkko
2011-01-06
08 Tim Polk [Ballot Position Update] Position for Tim Polk has been changed to No Objection from Discuss
2011-01-05
07 (System) New version available: draft-ietf-roll-trickle-07.txt
2010-12-24
08 Adrian Farrel
[Ballot comment]
Rtg Dir review from Alia Atlas says:

I have reviewed draft-ietf-roll-trickle-06.  It is one of the best drafts that I have read and …
[Ballot comment]
Rtg Dir review from Alia Atlas says:

I have reviewed draft-ietf-roll-trickle-06.  It is one of the best drafts that I have read and I do not have any substantial or even editorial comments on it.  I found the protocol as described to be clear, simple and pretty elegant.
2010-12-23
08 David Harrington Request for Telechat review by TSVDIR Completed. Reviewer: Martin Stiemerling.
2010-12-17
08 (System) Removed from agenda for telechat - 2010-12-16
2010-12-16
08 David Harrington Request for Telechat review by TSVDIR is assigned to Martin Stiemerling
2010-12-16
08 David Harrington Request for Telechat review by TSVDIR is assigned to Martin Stiemerling
2010-12-16
08 Lars Eggert State changed to IESG Evaluation - Defer from IESG Evaluation.
2010-12-16
08 Lars Eggert
[Ballot discuss]
I'm sorry for deferring this document to the next telechat. I want the TSV directorate to review it and I didn't realize this …
[Ballot discuss]
I'm sorry for deferring this document to the next telechat. I want the TSV directorate to review it and I didn't realize this in time to get the review assigned.

I'm also balloting DISCUSS. That is, because looking at the current ROLL charter, I have a hard time understanding how this document is in scope of the WG. This document does not fall under any of the work items on the charter; and it's not even what I'd consider a "routing" protocol.
2010-12-16
08 Lars Eggert [Ballot Position Update] New position, Discuss, has been recorded
2010-12-16
08 Gonzalo Camarillo [Ballot Position Update] New position, No Objection, has been recorded
2010-12-15
08 Adrian Farrel
[Ballot comment]
Rtg Dir review from Alia Atlas says:

I have reviewed draft-ietf-roll-trickle-06.  It is one of the best drafts that I have read and …
[Ballot comment]
Rtg Dir review from Alia Atlas says:

I have reviewed draft-ietf-roll-trickle-06.  It is one of the best drafts that I have read and I do not have any
substantial or even editorial comments on it.  I found the protocol as described to be clear, simple and
pretty elegant.
2010-12-15
08 Sean Turner [Ballot Position Update] New position, No Objection, has been recorded
2010-12-15
08 Tim Polk
[Ballot discuss]
This is a very nice document, but I do have a couple of issues I would like the authors to consider before
I …
[Ballot discuss]
This is a very nice document, but I do have a couple of issues I would like the authors to consider before
I move to No Objection:

The introduction implies that a participating node will attempt to communicate with
its neighbors if it notices an inconsistency in other nodes' broadcast messages
between its internal state and the state of the other nodes.  I expected to see that reflected
in Section 4.2 (Trickle Algorithm), Step 5 when the node heard an inconsistent 
transmission.  However, the text in step 5 does not state that the node transmits
anything.  As stated, the only reason that the Trickle node will transmit is if
the timer t expires before the redundancy counter is met (in step 3).

I also think that two bullets need to be added to Section 5, Using Trickle.  Perhaps
I am stating the obvious, but a protocol specification that uses Trickle needs to specify:
(1) what information is transmitted if the node transmits because of timer expiration; and
(2) what information is transmitted if the node hears information inconsistent with its
internal state.
2010-12-15
08 Tim Polk [Ballot Position Update] New position, Discuss, has been recorded
2010-12-15
08 Russ Housley [Ballot Position Update] New position, No Objection, has been recorded
2010-12-15
08 Stewart Bryant
[Ballot discuss]
"All that matters is that
  some nodes communicate with one another at some nonzero rate."

This is not right. If every node …
[Ballot discuss]
"All that matters is that
  some nodes communicate with one another at some nonzero rate."

This is not right. If every node received, nothing would get communicated. In addition I tend to think of communication as requiring some degree transmission.

I think that you mean transmits at some nonzero rate.

=======

Considering that later text says that Trickle breaks if there is a parameter mismatch, I am concerned that this text is not strict enough:

  It is RECOMMENDED that a protocol which uses Trickle includes
  mechanisms to inform nodes of configuration parameters at runtime.
  However, it is not always possible to do so. 

I am also concerned with the get out clause that allows the degradation of a MUST to a RECOMMENDATION. Surely for the cost of a few bytes the parameters can at least be announced so that other nodes can get some hint that the mismatch is occurring.
2010-12-15
08 Stewart Bryant [Ballot Position Update] New position, Discuss, has been recorded
2010-12-14
08 Ralph Droms
[Ballot comment]
Nit: 3rd para of section 3, s/their/its/

Question: is the typical value of k in the range 1-5 independent of
the density of …
[Ballot comment]
Nit: 3rd para of section 3, s/their/its/

Question: is the typical value of k in the range 1-5 independent of
the density of the network nodes, where I'm thinking of "density" as
the number of nodes that hear a given message?
2010-12-14
08 Ralph Droms [Ballot Position Update] New position, No Objection, has been recorded
2010-12-14
08 Robert Sparks
[Ballot comment]
In section 6.5 - The comment about "having the parameter describe k-1 instead of k being confusing" is confusing. I had to think …
[Ballot comment]
In section 6.5 - The comment about "having the parameter describe k-1 instead of k being confusing" is confusing. I had to think for some time to convince myself that I understood what you were trying to say. I encourage you to further explain, or rewrite the comment.

Why are you allowing different uses of trickle to give different meanings to k=0? It would seem to facilitate interoperability (and simplify implementation) if you just defined k=0 to mean turning off suppression in all cases. Individual uses of trickle can forbid setting k=0 if they don't want to allow turning off suppression.
2010-12-14
08 Robert Sparks [Ballot Position Update] New position, No Objection, has been recorded
2010-12-14
08 Ron Bonica [Ballot Position Update] New position, No Objection, has been recorded
2010-12-13
08 Peter Saint-Andre [Ballot Position Update] New position, No Objection, has been recorded
2010-12-11
08 Alexey Melnikov [Ballot Position Update] New position, No Objection, has been recorded
2010-12-07
06 (System) New version available: draft-ietf-roll-trickle-06.txt
2010-12-06
08 Adrian Farrel State changed to IESG Evaluation from Waiting for AD Go-Ahead.
2010-12-06
08 (System) State changed to Waiting for AD Go-Ahead from In Last Call.
2010-12-03
08 Adrian Farrel [Ballot Position Update] New position, Yes, has been recorded for Adrian Farrel
2010-12-03
08 Adrian Farrel Ballot has been issued
2010-12-03
08 Adrian Farrel Created "Approve" ballot
2010-12-03
08 Adrian Farrel Placed on agenda for telechat - 2010-12-16
2010-11-30
08 Samuel Weiler Request for Last Call review by SECDIR is assigned to Jeffrey Hutzelman
2010-11-30
08 Samuel Weiler Request for Last Call review by SECDIR is assigned to Jeffrey Hutzelman
2010-11-29
08 Amanda Baber We understand that this document does not require any IANA actions.
2010-11-22
08 Amy Vezza Last call sent
2010-11-22
08 Amy Vezza
State changed to In Last Call from Last Call Requested.

The following Last Call Announcement was sent out:

From: The IESG <iesg-secretary@ietf.org>
To: …
State changed to In Last Call from Last Call Requested.

The following Last Call Announcement was sent out:

From: The IESG <iesg-secretary@ietf.org>
To: IETF-Announce <ietf-announce@ietf.org>
CC: <roll@ietf.org>
Reply-To: ietf@ietf.org
Subject: Last Call: <draft-ietf-roll-trickle-05.txt> (The Trickle Algorithm) to Proposed Standard


The IESG has received a request from the Routing Over Low power and Lossy
networks WG (roll) to consider the following document:
- 'The Trickle Algorithm'
  <draft-ietf-roll-trickle-05.txt> as a Proposed Standard

The IESG plans to make a decision in the next few weeks, and solicits
final comments on this action. Please send substantive comments to the
ietf@ietf.org mailing lists by 2010-12-06. Exceptionally, comments may be
sent to iesg@ietf.org instead. In either case, please retain the
beginning of the Subject line to allow automated sorting.

The file can be obtained via
http://datatracker.ietf.org/doc/draft-ietf-roll-trickle/

IESG discussion can be tracked via
http://datatracker.ietf.org/doc/draft-ietf-roll-trickle/
2010-11-22
08 Adrian Farrel Last Call was requested
2010-11-22
08 (System) Ballot writeup text was added
2010-11-22
08 (System) Last call text was added
2010-11-22
08 (System) Ballot approval text was added
2010-11-22
08 Adrian Farrel State changed to Last Call Requested from AD Evaluation::AD Followup.
2010-11-22
08 Adrian Farrel Ballot writeup text changed
2010-11-11
08 (System) Sub state has been changed to AD Follow up from New Id Needed
2010-11-11
05 (System) New version available: draft-ietf-roll-trickle-05.txt
2010-10-21
08 Adrian Farrel State changed to AD Evaluation::Revised ID Needed from AD Evaluation by Adrian Farrel
2010-10-21
08 Adrian Farrel
AD Review: October 9th, 2010

I have performed an AD review of your draft.

Don't panic!

I review all drafts that I am responsible for …
AD Review: October 9th, 2010

I have performed an AD review of your draft.

Don't panic!

I review all drafts that I am responsible for before putting them forward
for IETF last call. The main objective is to catch nits and minor issues
that would show up during the last call or in IESG review. The intention is
to help polish your document and make sure
it is clean and shiny so that other reviewers will stick to the technical
details.

Thanks you for a really well-written and clear document. Excellent work!

On reviewing it, there are a couple of small points I think it would be
helpful to sort out to ensure complete understanding from all your readers.
I'd like to see a quick respin of the document before I issue the IETF last
call. As soon as I see a new revision posted, I'll set the ball in motion.

Of course, all of my issues are up for discussion.

Thanks for the work,
Adrian

---

idnits (http://tools.ietf.org/tools/idnits/) reports

  == You're using the IETF Trust Provisions' Section 6.b License Notice
    from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009.
    (See http://trustee.ietf.org/license-info/)

Can you fix this, plase.

---

Good that you pulled "trickle communication rate" out for attention as a
term. Could you also pull out "trickle transmission rate"?

---

In section 3

  The Trickle
  algorithm balances the load in such a scenario, as each node's
  Trickle transmission rate is 1/nth of the Trickle communication rate.
  Sparser networks require more transmissions per node, but utilization
  of the radio channel over space will not increase.

No issues with the facts.
But this is the first mention of radio channels. Up to this point we would
have been quite happy thinking of fixed-line connectivity.
Can you tweak something?

---

Section 4.1

  o  The maximum interval size is described as a number of doublings of
      the minimum interval size (the base-2 log(max/min)).  For example,
      a protocol might define the maximum interval as 16.  If the
      minimum interval is 100ms, then the maximum interval is 100ms *
      65536, 6,553.6 seconds, or approximately 109 minutes.

There is a slight discrepency in terminology here, and a little tidying that
could be done to the expression of the example.

The problem comes that you have "maximum interval sixe" as a number of
doublings, but you are also trying to state the amount of time it implies.

Can I suggest...

  o  The maximum interval size is described as a number of doublings of
      the minimum interval size (the base-2 log(max/min)).  For example,
      a protocol might define the maximum interval size as 16.  If the
      minimum interval size is 100ms, then the amount of time specified
      by the maximum interval size of 16 is
        100ms * 2^16 = 6,553.6 seconds
      or approximately 109 minutes.

A similar terminology problem shows up in 6.2

  Note that mismatched Imin values and matching
  Imax doubling constants will lead to mismatched Imax values.

Can you go through the document and decide whether Imax is the doubling
constant or the time period.

---

Section 4.2

  5.  If Trickle hears a transmission that is "inconsistent," the
      Trickle timer resets.  If I is greater than Imin, resetting a
      Trickle timer sets I to Imin and begins a new interval.  If I is
      equal to Imin, resetting a Trickle timer does nothing.  Trickle
      can also reset the timer in response to external "events."

If "resetting a Trickle timer does nothing", how can you justify the word
"reset"? Doesn't a new interval always start when the timer is
reset? Or are you saying that the timer restarts, but the counter is not
reset to zero?

---

Section 6.1

OLD
  Hence, the danger of
  mismatched k values is uneven transmission load that can deplete the
  energy of some nodes.
NEW
  Hence, the danger of
  mismatched k values is uneven transmission load that can deplete the
  energy of some nodes in a lower-power network.
END

...because there is no specific limitation to apply this to low-power
networks..

---

Section 6.5

  having the parameter describe (k-1)

Do you mean k=-1 ?

---

Section 6.6

  Finally, a protocol SHOULD set k and Imin such that Imin is at least
  two to three as long as it takes to transmit k packets.

s/three as/three times as/

---

Section 9

I am worried about this section being so empty. I don't think the algorithm
needs any security work, but I do think that you can give advice on the
security implications for protocols that use the algorithm.

For example, what would be the impact of a false positive or a false
negative? Given that impact, what precautions should a protocol that uses
Trickle take?

For example, in Section 6 you have:

  It is RECOMMENDED that a protocol which uses Trickle include
  mechanisms to inform nodes of configuration parameters at runtime.

What would happen if these mecahnisms were attacked?

In short, can you add some RECOMMENDations about what protocols that use
Trickle shold consider in their specifications.
2010-09-30
08 Adrian Farrel State changed to AD Evaluation from Publication Requested by Adrian Farrel
2010-08-23
08 Cindy Morgan
> (1.a)  Who is the Document Shepherd for this document?  Has the
>        Document Shepherd personally reviewed this version of the
>  …
> (1.a)  Who is the Document Shepherd for this document?  Has the
>        Document Shepherd personally reviewed this version of the
>        document and, in particular, does he or she believe this
>        version is ready for forwarding to the IESG for publication?

JP Vasseur is the document shepherd.
He has personally reviewed the document and believes it is ready for
forwarding to the IESG for publication.

> (1.b)  Has the document had adequate review both from key WG members
>        and from key non-WG members?  Does the Document Shepherd have
>        any concerns about the depth or breadth of the reviews that
>        have been performed?

The I-D has been discussed in details by a number of key members of the
Working group. Number of comments have been made on the mailing list
during WG Last Call and addressed in this revision.

> (1.c)  Does the Document Shepherd have concerns that the document
>        needs more review from a particular or broader perspective,
>        e.g., security, operational complexity, someone familiar with
>        AAA, internationalization or XML?

No concerns.

> (1.d)  Does the Document Shepherd have any specific concerns or
>        issues with this document that the Responsible Area Director
>        and/or the IESG should be aware of?  For example, perhaps he
>        or she is uncomfortable with certain parts of the document, or
>        has concerns whether there really is a need for it.  In any
>        event, if the WG has discussed those issues and has indicated
>        that it still wishes to advance the document, detail those
>        concerns here.  Has an IPR disclosure related to this document
>        been filed?  If so, please include a reference to the
>        disclosure and summarize the WG discussion and conclusion on
>        this issue.

The document is sound.

> (1.e)  How solid is the WG consensus behind this document?  Does it
>        represent the strong concurrence of a few individuals, with
>        others being silent, or does the WG as a whole understand and
>        agree with it?

Good consensus.

> (1.f)  Has anyone threatened an appeal or otherwise indicated extreme
>        discontent?  If so, please summarise the areas of conflict in
>        separate email messages to the Responsible Area Director.  (It
>        should be in a separate email because this questionnaire is
>        entered into the ID Tracker.)

No threats. No discontent.

> (1.g)  Has the Document Shepherd personally verified that the
>        document satisfies all ID nits?  (See
>        http://www.ietf.org/ID-Checklist.html and
>        http://tools.ietf.org/tools/idnits/).  Boilerplate checks are
>        not enough; this check needs to be thorough.  Has the document
>        met all formal review criteria it needs to, such as the MIB
>        Doctor, media type and URI type reviews?

Checks have been made. No Errors.

> (1.h)  Has the document split its references into normative and
>        informative?  Are there normative references to documents that
>        are not ready for advancement or are otherwise in an unclear
>        state?  If such normative references exist, what is the
>        strategy for their completion?  Are there normative references
>        that are downward references, as described in [RFC3967]?  If
>        so, list these downward references to support the Area
>        Director in the Last Call procedure for them [RFC3967].

References split has been done.

> (1.i)  Has the Document Shepherd verified that the document IANA
>        consideration section exists and is consistent with the body
>        of the document?  If the document specifies protocol
>        extensions, are reservations requested in appropriate IANA
>        registries?  Are the IANA registries clearly identified?  If
>        the document creates a new registry, does it define the
>        proposed initial contents of the registry and an allocation
>        procedure for future registrations?  Does it suggest a
>        reasonable name for the new registry?  See [RFC2434].  If the
>        document describes an Expert Review process has Shepherd
>        conferred with the Responsible Area Director so that the IESG
>        can appoint the needed Expert during the IESG Evaluation?

This document does not require any IANA action.

> (1.j)  Has the Document Shepherd verified that sections of the
>        document that are written in a formal language, such as XML
>        code, BNF rules, MIB definitions, etc., validate correctly in
>        an automated checker?

No such formal language is used.

> (1.k)  The IESG approval announcement includes a Document
>        Announcement Write-Up.  Please provide such a Document
>        Announcement Write-Up.  Recent examples can be found in the
>        "Action" announcements for approved documents.  The approval
>        announcement contains the following sections:
>
>        Technical Summary
>          Relevant content can frequently be found in the abstract
>          and/or introduction of the document.  If not, this may be
>          an indication that there are deficiencies in the abstract
>          or introduction.
    The Trickle algorithm allows nodes in a lossy shared medium (e.g.,
    low power and lossy networks) to exchange information in a highly
    robust, energy efficient, simple, and scalable manner.  Dynamically
    adjusting transmission windows allows Trickle to spread new
    information on the scale of link-layer transmission times while
    sending only a few messages per hour when information does not
    change.  A simple suppression mechanism and transmission point
    selection allows Trickle's communication rate to scale
    logarithmically with density.  This document describes the Trickle
    algorithm and considerations in its use.

    The Trickle algorithm establishes a density-aware local 
communication
    primitive with an underlying consistency model that guides when a
    node transmits.  When a node's data does not agree with its
    neighbors, that node communicates quickly to resolve the
    inconsistency (e.g., in milliseconds).  When nodes agree, they slow
    their communication rate exponentially, such that nodes send packets
    very infrequently (e.g., a few packets per hour).  Instead of
    flooding a network with packets, the algorithm controls the send 
rate
    so each node hears a small trickle of packets, just enough to stay
    consistent.  Furthermore, by relying only on local communication
    (e.g., broadcast or local multicast), Trickle handles network re-
    population, is robust to network transience, loss, and 
disconnection,
    is simple to implement, and requires very little state.  Current
    implementations use 4-11 bytes of RAM and are 50-200 lines of C
    code[Levis08].

    While Trickle was originally designed for reprogramming protocols
    (where the data is the code of the program being updated), 
experience
    has shown it to be a powerful mechanism that can be applied to wide
    range of protocol design problems, including control traffic timing,
    multicast propagation, and route discovery.  This flexibility stems
    from being able to define, on a case-by-case basis, what constitutes
    "agreement" or an "inconsistency;" Section Section 6.8 presents a 
few
    examples of how the algorithm can be used.

    This document describes the Trickle algorithm and provides 
guidelines
    for its use.  It also states requirements for protocol 
specifications
    that use Trickle.  This document does not provide results on
    Trickle's performance or behavior, nor does it explain the
    algorithm's design in detail: interested readers should refer to
    [Levis04] and [Levis08].

>        Working Group Summary
>          Was there anything in WG process that is worth noting?  For
>          example, was there controversy about particular points or
>          were there decisions where the consensus was particularly
>          rough?

No discontent.

>        Document Quality
>          Are there existing implementations of the protocol?  Have a
>          significant number of vendors indicated their plan to
>          implement the specification?  Are there any reviewers that
>          merit special mention as having done a thorough review,
>          e.g., one that resulted in important changes or a
>          conclusion that the document had no substantive issues?  If
>          there was a MIB Doctor, Media Type or other expert review,
>          what was its course (briefly)?  In the case of a Media Type
>          review, on what date was the request posted?

The Trickle algorithm is a true component of the RPL routing protocol, 
specified
by the ROLL WG, which has passed WG Last Call. Since RPL has been 
implemented
by more than a dozens of implementation and several interoperability 
events took
place, the trickle algorithm has also been successfully implemented 
(the reason
for documenting trickle in a separate document was that it could be 
used in other
circumstances than RPL)
2010-08-23
08 Cindy Morgan Draft added in state Publication Requested by Cindy Morgan
2010-08-23
08 Cindy Morgan Removed from agenda for telechat by Cindy Morgan
2010-08-23
08 Cindy Morgan [Note]: 'JP Vasseur (jpv@cisco.com) is the document shepherd.' added by Cindy Morgan
2010-08-19
04 (System) New version available: draft-ietf-roll-trickle-04.txt
2010-08-18
03 (System) New version available: draft-ietf-roll-trickle-03.txt
2010-07-12
02 (System) New version available: draft-ietf-roll-trickle-02.txt
2010-04-10
01 (System) New version available: draft-ietf-roll-trickle-01.txt
2010-03-23
00 (System) New version available: draft-ietf-roll-trickle-00.txt