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 |