Internet Engineering Task Force (IETF) P. Levis
Request for Comments: 6206 Stanford University
Category: Standards Track T. Clausen
ISSN: 2070-1721 LIX, Ecole Polytechnique
J. Hui
Arch Rock Corporation
O. Gnawali
Stanford University
J. Ko
Johns Hopkins University
March 2011
Internet Engineering Task Force (IETF) P. Levis
Request for Comments: 6206 Stanford University
Category: Standards Track T. Clausen
ISSN: 2070-1721 LIX, Ecole Polytechnique
J. Hui
Arch Rock Corporation
O. Gnawali
Stanford University
J. Ko
Johns Hopkins University
March 2011
The Trickle Algorithm
涓流算法
Abstract
摘要
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 allow Trickle's communication rate to scale logarithmically with density. This document describes the Trickle algorithm and considerations in its use.
涓流算法允许有损共享介质（例如，低功耗和有损网络）中的节点以高度健壮、节能、简单和可扩展的方式交换信息。通过动态调整传输窗口，涓流可以按照链路层传输时间的规模传播新信息，而在信息不变的情况下，每小时仅发送几条消息。简单的抑制机制和传输点选择允许涓流的通信速率与密度成对数比例。本文档描述了涓流算法及其使用注意事项。
Status of This Memo
关于下段备忘
This is an Internet Standards Track document.
这是一份互联网标准跟踪文件。
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 5741.
本文件是互联网工程任务组（IETF）的产品。它代表了IETF社区的共识。它已经接受了公众审查，并已被互联网工程指导小组（IESG）批准出版。有关互联网标准的更多信息，请参见RFC 5741第2节。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6206.
有关本文件当前状态、任何勘误表以及如何提供反馈的信息，请访问http://www.rfc-editor.org/info/rfc6206.
Copyright Notice
版权公告
Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.
版权所有（c）2011 IETF信托基金和确定为文件作者的人员。版权所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
本文件受BCP 78和IETF信托有关IETF文件的法律规定的约束(http://trustee.ietf.org/license-info)自本文件出版之日起生效。请仔细阅读这些文件，因为它们描述了您对本文件的权利和限制。从本文件中提取的代码组件必须包括信托法律条款第4.e节中所述的简化BSD许可证文本，并提供简化BSD许可证中所述的无担保。
Table of Contents
目录
1. Introduction ....................................................2
2. Terminology .....................................................3
3. Trickle Algorithm Overview ......................................3
4. Trickle Algorithm ...............................................5
4.1. Parameters and Variables ...................................5
4.2. Algorithm Description ......................................5
5. Using Trickle ...................................................6
6. Operational Considerations ......................................7
6.1. Mismatched Redundancy Constants ............................7
6.2. Mismatched Imin ............................................7
6.3. Mismatched Imax ............................................8
6.4. Mismatched Definitions .....................................8
6.5. Specifying the Constant k ..................................8
6.6. Relationship between k and Imin ............................8
6.7. Tweaks and Improvements to Trickle .........................9
6.8. Uses of Trickle ............................................9
7. Acknowledgements ...............................................10
8. Security Considerations ........................................10
9. References .....................................................11
9.1. Normative References ......................................11
9.2. Informative References ....................................11
1. Introduction ....................................................2
2. Terminology .....................................................3
3. Trickle Algorithm Overview ......................................3
4. Trickle Algorithm ...............................................5
4.1. Parameters and Variables ...................................5
4.2. Algorithm Description ......................................5
5. Using Trickle ...................................................6
6. Operational Considerations ......................................7
6.1. Mismatched Redundancy Constants ............................7
6.2. Mismatched Imin ............................................7
6.3. Mismatched Imax ............................................8
6.4. Mismatched Definitions .....................................8
6.5. Specifying the Constant k ..................................8
6.6. Relationship between k and Imin ............................8
6.7. Tweaks and Improvements to Trickle .........................9
6.8. Uses of Trickle ............................................9
7. Acknowledgements ...............................................10
8. Security Considerations ........................................10
9. References .....................................................11
9.1. Normative References ......................................11
9.2. Informative References ....................................11
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].
用数据包淹没网络时，该算法控制发送速率，使每个节点都能听到少量的数据包，刚好能够保持一致。此外，通过仅依赖本地通信（例如，广播或本地多播），涓流处理网络重新填充；对网络瞬变、损耗和断开具有鲁棒性；易于实现；只需要很少的状态。当前的实现使用4-11字节的RAM，并且是50-200行C代码[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 a 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 6.8 presents a few examples of how the algorithm can be used.
尽管Trickle最初设计用于重新编程协议（其中数据是正在更新的程序的代码），但经验表明，它是一种强大的机制，可应用于广泛的协议设计问题，包括控制流量定时、多播传播和路由发现。这种灵活性源于能够在个案基础上定义什么构成“协议”或“不一致”；第6.8节给出了如何使用该算法的几个示例。
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 regarding Trickle's performance or behavior, nor does it explain the algorithm's design in detail: interested readers should refer to [Levis04] and [Levis08].
本文档描述了涓流算法，并提供了使用指南。它还说明了使用涓流的协议规范的要求。本文档未提供有关涓流性能或行为的结果，也未详细说明算法的设计：感兴趣的读者应参考[Levis04]和[Levis08]。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].
本文件中的关键词“必须”、“不得”、“必需”、“应”、“不应”、“建议”、“不建议”、“可”和“可选”应按照RFC 2119[RFC2119]中的说明进行解释。
Additionally, this document introduces the following terminology:
此外，本文件还介绍了以下术语：
Trickle communication rate: the sum of the number of messages sent or received by the Trickle algorithm in an interval.
涓流通信速率：涓流算法在一段时间间隔内发送或接收的消息数之和。
Trickle transmission rate: the sum of the number of messages sent by the Trickle algorithm in an interval.
涓流传输速率：涓流算法在一段时间间隔内发送的消息数之和。
Trickle's basic primitive is simple: every so often, a node transmits data unless it hears a few other transmissions whose data suggest its own transmission is redundant. Examples of such data include routing state, software update versions, and the last heard multicast packet. This primitive allows Trickle to scale to thousand-fold variations in network density, quickly propagate updates, distribute transmission
涓流的基本原理很简单：节点每隔一段时间就会传输数据，除非它听到一些其他传输，而这些传输的数据表明其自身的传输是冗余的。此类数据的示例包括路由状态、软件更新版本和最后听到的多播数据包。该原语允许涓流扩展到网络密度的千倍变化，快速传播更新，分发传输
load evenly, be robust to transient disconnections, handle network re-populations, and impose a very low maintenance overhead: one example use, routing beacons in the Collection Tree Protocol (CTP) [Gnawali09], requires sending on the order of a few packets per hour, yet CTP can respond to topology changes in milliseconds.
负载均匀，对瞬时断开具有鲁棒性，处理网络重新填充，并施加非常低的维护开销：例如，使用收集树协议（CTP）[Gnawali09]中的路由信标时，需要每小时发送几个数据包，但CTP可以在毫秒内响应拓扑变化。
Trickle sends all messages to a local communication address. The exact address used can depend on the underlying IP protocol as well as how the higher-layer protocol uses Trickle. In IPv6, for example, it can be the link-local multicast address or another local multicast address, while in IPv4 it can be the broadcast address (255.255.255.255).
涓流将所有消息发送到本地通信地址。使用的确切地址可能取决于底层IP协议以及高层协议如何使用涓流。例如，在IPv6中，它可以是链路本地多播地址或另一个本地多播地址，而在IPv4中，它可以是广播地址（255.255.255.255）。
There are two possible results to a Trickle message: either every node that hears the message finds that the message data is consistent with its own state, or a recipient detects an inconsistency. Detection can be the result of either an out-of-date node hearing something new, or an updated node hearing something old. As long as every node communicates somehow -- either receives or transmits -- some node will detect the need for an update.
涓流消息有两种可能的结果：要么是听到消息的每个节点发现消息数据与其自身状态一致，要么是接收者检测到不一致。检测可能是过时节点听到新消息或更新节点听到旧消息的结果。只要每个节点以某种方式进行通信（接收或发送），一些节点就会检测到需要更新。
For example, consider a simple case where "up to date" is defined by version numbers (e.g., network configuration). If node A transmits that it has version V, but B has version V+1, then B knows that A needs an update. Similarly, if B transmits that it has version V+1, A knows that it needs an update. If B broadcasts or multicasts updates, then all of its neighbors can receive them without having to advertise their need. Some of these recipients might not have even heard A's transmission. In this example, it does not matter who first transmits -- A or B; the inconsistency will be detected in either case.
例如，考虑一个简单的情况，其中“最新的”是由版本号（例如，网络配置）定义的。如果节点A传输它有版本V，但B有版本V+1，那么B知道A需要更新。类似地，如果B传输它有版本V+1，A知道它需要更新。如果B广播或多播更新，那么它的所有邻居都可以接收它们，而无需公布它们的需要。其中一些接收者甚至可能没有听到A的传输。在这个例子中，谁先传输并不重要——A或B；在任何一种情况下都会检测到不一致性。
The fact that Trickle communication can be either transmission or reception enables the Trickle algorithm to operate in sparse as well as dense networks. A single, disconnected node must transmit at the Trickle communication rate. In a lossless, single-hop network of size n, the Trickle communication rate at each node equals the sum of the Trickle transmission rates across all nodes. 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 the utilization of a given broadcast domain (e.g., radio channel over space, shared medium) will not increase. This is an important property in wireless networks and other shared media, where the channel is a valuable shared resource. Additionally, reducing transmissions in dense networks conserves system energy.
涓流通信可以是传输也可以是接收，这一事实使得涓流算法能够在稀疏网络和密集网络中运行。单个断开连接的节点必须以涓流通信速率进行传输。在大小为n的无损单跳网络中，每个节点的涓流通信速率等于所有节点的涓流传输速率之和。涓流算法在这种情况下平衡负载，因为每个节点的涓流传输速率是涓流通信速率的1/n。稀疏网络要求每个节点有更多的传输，但给定广播域（例如，空间上的无线信道、共享媒体）的利用率不会增加。这是无线网络和其他共享媒体中的一个重要属性，其中信道是一种宝贵的共享资源。此外，减少密集网络中的传输可以节省系统能量。
This section describes the Trickle algorithm.
本节介绍涓流算法。
A Trickle timer runs for a defined interval and has three configuration parameters: the minimum interval size Imin, the maximum interval size Imax, and a redundancy constant k:
涓流计时器按定义的间隔运行，并具有三个配置参数：最小间隔大小Imin、最大间隔大小Imax和冗余常数k：
o The minimum interval size, Imin, is defined in units of time (e.g., milliseconds, seconds). For example, a protocol might define the minimum interval as 100 milliseconds.
o 最小间隔大小Imin以时间单位（例如毫秒、秒）定义。例如，协议可能将最小间隔定义为100毫秒。
o The maximum interval size, Imax, is described as a number of doublings of the minimum interval size (the base-2 log(max/min)). For example, a protocol might define Imax as 16. If the minimum interval is 100 ms, then the amount of time specified by Imax is 100 ms * 65,536, i.e., 6,553.6 seconds or approximately 109 minutes.
o 最大间隔大小Imax被描述为最小间隔大小（base-2 log（max/min））的倍数。例如，协议可能将Imax定义为16。如果最小间隔为100 ms，则Imax指定的时间量为100 ms*65536，即6553.6秒或约109分钟。
o The redundancy constant, k, is a natural number (an integer greater than zero).
o 冗余常数k是一个自然数（大于零的整数）。
In addition to these three parameters, Trickle maintains three variables:
除这三个参数外，涓流还保持三个变量：
o I, the current interval size,
o 一、 当前间隔大小，
o t, a time within the current interval, and
o t、 当前间隔内的时间，以及
o c, a counter.
o c、 柜台。
The Trickle algorithm has six rules:
涓流算法有六条规则：
1. When the algorithm starts execution, it sets I to a value in the range of [Imin, Imax] -- that is, greater than or equal to Imin and less than or equal to Imax. The algorithm then begins the first interval.
1. 当算法开始执行时，它将I设置为[Imin，Imax]范围内的值，即大于或等于Imin，小于或等于Imax。然后，算法开始第一个间隔。
2. When an interval begins, Trickle resets c to 0 and sets t to a random point in the interval, taken from the range [I/2, I), that is, values greater than or equal to I/2 and less than I. The interval ends at I.
2. 当间隔开始时，涓流将c重置为0，并将t设置为间隔中的一个随机点，取自范围[I/2，I]，即大于或等于I/2且小于I的值。间隔在I处结束。
3. Whenever Trickle hears a transmission that is "consistent", it increments the counter c.
3. 每当涓流听到“一致”的传输信号时，它就会增加计数器c。
4. At time t, Trickle transmits if and only if the counter c is less than the redundancy constant k.
4. 在时间t，当且仅当计数器c小于冗余常数k时，涓流传输。
5. When the interval I expires, Trickle doubles the interval length. If this new interval length would be longer than the time specified by Imax, Trickle sets the interval length I to be the time specified by Imax.
5. 当间隔I到期时，涓流将使间隔长度加倍。如果此新间隔长度将长于Imax指定的时间，则涓流将间隔长度I设置为Imax指定的时间。
6. If Trickle hears a transmission that is "inconsistent" and I is greater than Imin, it resets the Trickle timer. To reset the timer, Trickle sets I to Imin and starts a new interval as in step 2. If I is equal to Imin when Trickle hears an "inconsistent" transmission, Trickle does nothing. Trickle can also reset its timer in response to external "events".
6. 如果涓流听到“不一致”的传输，并且I大于Imin，则重置涓流计时器。要重置计时器，涓流将I设置为Imin，并开始一个新的间隔，如步骤2所示。当涓流听到一个“不一致”的传输时，如果I等于Imin，涓流什么也不做。涓流还可以根据外部“事件”重置其计时器。
The terms "consistent", "inconsistent", and "events" are in quotes because their meaning depends on how a protocol uses Trickle.
术语“一致”、“不一致”和“事件”在引号中，因为它们的含义取决于协议如何使用涓流。
The only time the Trickle algorithm transmits is at step 4 of the above algorithm. This means there is an inherent delay between detecting an inconsistency (shrinking I to Imin) and responding to that inconsistency (transmitting at time t in the new interval). This is intentional. Immediately responding to detecting an inconsistency can cause a broadcast storm, where many nodes respond at once and in a synchronized fashion. By making responses follow the Trickle algorithm (with the minimal interval size), a protocol can benefit from Trickle's suppression mechanism and scale across a huge range of node densities.
涓流算法的唯一传输时间是在上述算法的步骤4。这意味着在检测不一致性（将I缩小为Imin）和响应该不一致性（在新间隔的时间t处传输）之间存在固有的延迟。这是故意的。立即响应检测不一致性可能会导致广播风暴，其中许多节点会立即以同步的方式响应。通过使响应遵循Trickle算法（具有最小的间隔大小），协议可以受益于Trickle的抑制机制，并可在巨大的节点密度范围内扩展。
A protocol specification that uses Trickle MUST specify:
使用涓流的协议规范必须指定：
o Default values for Imin, Imax, and k. Because link layers can vary widely in their properties, the default value of Imin SHOULD be specified in terms of the worst-case latency of a link-layer transmission. For example, a specification should say "the default value of Imin is 4 times the worst-case link-layer latency" and should not say "the default value of Imin is 500 milliseconds". Worst-case latency is approximately the time until the first link-layer transmission of the frame, assuming an idle channel (does not include backoff, virtual carrier sense, etc.).
o Imin、Imax和k的默认值。由于链路层的属性可能有很大差异，因此应根据链路层传输的最坏情况延迟来指定Imin的默认值。例如，规范应该说“Imin的默认值是最坏情况下链路层延迟的4倍”，而不应该说“Imin的默认值是500毫秒”。最坏情况下的延迟大约是帧的第一链路层传输之前的时间，假设为空闲信道（不包括退避、虚拟载波检测等）。
o What constitutes a "consistent" transmission.
o 什么构成“一致”传输。
o What constitutes an "inconsistent" transmission.
o 构成“不一致”传输的内容。
o What "events", if any -- besides inconsistent transmissions -- reset the Trickle timer.
o 除了不一致的传输之外，还有什么“事件”（如果有）重置涓流计时器。
o What information a node transmits in Trickle messages.
o 节点在涓流消息中传输的信息。
o What actions outside the algorithm the protocol takes, if any, when it detects an inconsistency.
o 当协议检测到不一致性时，它在算法之外采取了什么行动（如果有的话）。
It is RECOMMENDED that a protocol that uses Trickle include mechanisms to inform nodes of configuration parameters at runtime. However, it is not always possible to do so. In the cases where different nodes have different configuration parameters, Trickle may have unintended behaviors. This section outlines some of those behaviors and operational considerations as educational exercises.
建议使用涓流的协议包括在运行时通知节点配置参数的机制。然而，并非总是能够做到这一点。在不同节点具有不同配置参数的情况下，涓流可能具有意外行为。本节概述了作为教育练习的一些行为和操作注意事项。
If nodes do not agree on the redundancy constant k, then nodes with higher values of k will transmit more often than nodes with lower values of k. In some cases, this increased load can be independent of the density. For example, consider a network where all nodes but one have k=1, and this one node has k=2. The different node can end up transmitting on every interval: it is maintaining a Trickle communication rate of 2 with only itself. Hence, the danger of mismatched k values is uneven transmission load that can deplete the energy of some nodes in a low-power network.
如果节点不同意冗余常数k，则k值较高的节点比k值较低的节点传输的频率更高。在某些情况下，增加的荷载可能与密度无关。例如，考虑一个网络，其中一个节点只有一个k＝1，并且这个节点具有k＝2。不同的节点可以在每个间隔上进行传输：它只与自身保持2的涓流通信速率。因此，k值不匹配的危险是传输负载不均匀，这会耗尽低功率网络中某些节点的能量。
If nodes do not agree on Imin, then some nodes, on hearing inconsistent messages, will transmit sooner than others. These faster nodes will have their intervals grow to a size similar to that of the slower nodes within a single slow interval time, but in that period may suppress the slower nodes. However, such suppression will end after the first slow interval, when the nodes generally agree on the interval size. Hence, mismatched Imin values are usually not a significant concern. Note that mismatched Imin values and matching Imax doubling constants will lead to mismatched maximum interval lengths.
如果节点在Imin上不一致，那么一些节点在听到不一致的消息时，将比其他节点传输得更快。这些较快的节点将在单个较慢的间隔时间内使其间隔增长到与较慢的节点相似的大小，但在该时间段内可能会抑制较慢的节点。然而，当节点通常同意间隔大小时，这种抑制将在第一个慢间隔之后结束。因此，不匹配的Imin值通常不是一个重要问题。请注意，不匹配的Imin值和匹配的Imax倍增常数将导致不匹配的最大间隔长度。
If nodes do not agree on Imax, then this can cause long-term problems with transmission load. Nodes with small Imax values will transmit faster, suppressing those with larger Imax values. The nodes with larger Imax values, always suppressed, will never transmit. In the base case, when the network is consistent, this can cause long-term inequities in energy cost.
如果节点在Imax上不一致，则可能导致传输负载的长期问题。具有较小Imax值的节点将传输得更快，从而抑制具有较大Imax值的节点。Imax值较大的节点（始终被抑制）将永远不会传输。在基本情况下，当网络一致时，这可能会导致能源成本的长期不平等。
If nodes do not agree on what constitutes a consistent or inconsistent transmission, then Trickle may fail to operate properly. For example, if a receiver thinks a transmission is consistent, but the transmitter (if in the receiver's situation) would have thought it inconsistent, then the receiver will not respond properly and inform the transmitter. This can lead the network to not reach a consistent state. For this reason, unlike the configuration constants k, Imin, and Imax, consistency definitions MUST be clearly stated in the protocol and SHOULD NOT be configured at runtime.
如果节点对一致或不一致传输的构成不一致，则涓流可能无法正常运行。例如，如果接收器认为传输是一致的，但发射器（如果在接收器的情况下）会认为传输是不一致的，那么接收器将不会正确响应并通知发射器。这可能导致网络无法达到一致状态。因此，与配置常量k、Imin和Imax不同，一致性定义必须在协议中明确说明，并且不应在运行时进行配置。
There are some edge cases where a protocol may wish to use Trickle with its suppression disabled (k is set to infinity). In general, this approach is highly dangerous and it is NOT RECOMMENDED. Disabling suppression means that every node will always send on every interval; this can lead to congestion in dense networks. This approach is especially dangerous if many nodes reset their intervals at the same time. In general, it is much more desirable to set k to a high value (e.g., 5 or 10) than infinity. Typical values for k are 1-5: these achieve a good balance between redundancy and low cost [Levis08].
在某些边缘情况下，协议可能希望在禁用抑制的情况下使用涓流（k设置为无穷大）。一般来说，这种方法非常危险，不推荐使用。禁用抑制意味着每个节点将始终在每个间隔上发送；这可能导致密集网络中的拥塞。如果多个节点同时重置其间隔，这种方法尤其危险。一般来说，将k设置为高值（例如，5或10）比无穷大更可取。k的典型值为1-5：这些值在冗余和低成本之间实现了良好的平衡[Levis08]。
Nevertheless, there are situations where a protocol may wish to turn off Trickle suppression. Because k is a natural number (Section 4.1), k=0 has no useful meaning. If a protocol allows k to be dynamically configured, a value of 0 remains unused. For ease of debugging and packet inspection, having the parameter describe k-1 rather than k can be confusing. Instead, it is RECOMMENDED that protocols that require turning off suppression reserve k=0 to mean k=infinity.
然而，在某些情况下，协议可能希望关闭涓流抑制。因为k是一个自然数（第4.1节），所以k=0没有任何有用的意义。如果协议允许动态配置k，则值0保持未使用状态。为了便于调试和数据包检查，让参数描述k-1而不是k可能会令人困惑。相反，建议要求关闭抑制储备k=0的协议表示k=无穷大。
Finally, a protocol SHOULD set k and Imin such that Imin is at least two to three times as long as it takes to transmit k packets. Otherwise, if more than k nodes reset their intervals to Imin, the
最后，协议应该设置k和Imin，使得Imin至少是传输k个数据包所需时间的两到三倍。否则，如果超过k个节点将其间隔重置为Imin，则
resulting communication will lead to congestion and significant packet loss. Experimental results have shown that packet losses from congestion reduce Trickle's efficiency [Levis04].
由此产生的通信将导致拥塞和严重的数据包丢失。实验结果表明，拥塞导致的数据包丢失会降低涓流的效率[Levis04]。
Trickle is based on a small number of simple, tightly integrated mechanisms that are highly robust to challenging network environments. In our experiences using Trickle, attempts to tweak its behavior are typically not worth the cost. As written, the algorithm is already highly efficient: further reductions in transmissions or response time come at the cost of failures in edge cases. Based on our experiences, we urge protocol designers to suppress the instinct to tweak or improve Trickle without a great deal of experimental evidence that the change does not violate its assumptions and break the algorithm in edge cases.
涓流基于少量简单、紧密集成的机制，这些机制对具有挑战性的网络环境非常健壮。在我们使用涓流的经验中，试图调整其行为通常是不值得的。如前所述，该算法已经非常高效：传输或响应时间的进一步减少是以边缘情况下的故障为代价的。根据我们的经验，我们敦促协议设计者抑制调整或改进涓流的本能，而无需大量实验证据证明这种变化不会违反其假设，并在边缘情况下破坏算法。
With this warning in mind, Trickle is far from perfect. For example, Trickle suppression typically leads sparser nodes to transmit more than denser ones; it is far from the optimal computation of a minimum cover. However, in dynamic network environments such as wireless and low-power, lossy networks, the coordination needed to compute the optimal set of transmissions is typically much greater than the benefits it provides. One of the benefits of Trickle is that it is so simple to implement and requires so little state yet operates so efficiently. Efforts to improve it should be weighed against the cost of increased complexity.
考虑到这一警告，涓涓细流远非完美。例如，涓流抑制通常会导致稀疏节点比密集节点传输更多信息；这远远不是最小覆盖的最优计算。然而，在动态网络环境中，如无线和低功耗、有损网络，计算最佳传输集所需的协调通常比它提供的好处大得多。涓流的好处之一是，它的实现非常简单，所需的状态非常少，但运行效率却非常高。改进it的努力应该与增加复杂性的成本相权衡。
The Trickle algorithm has been used in a variety of protocols, in operational as well as academic settings. Giving a brief overview of some of these uses provides useful examples of how and when it can be used. These examples should not be considered exhaustive.
涓流算法已在各种协议中使用，包括在操作和学术环境中。简要概述其中的一些用途，提供了如何以及何时使用它的有用示例。这些例子不应被视为详尽无遗。
Reliable flooding/dissemination: A protocol uses Trickle to periodically advertise the most recent data it has received, typically through a version number. An inconsistency occurs when a node hears a newer version number or receives new data. A consistency occurs when a node hears an older or equal version number. When hearing an older version number, rather than reset its own Trickle timer, the node sends an update. Nodes with old version numbers that receive the update will then reset their own timers, leading to fast propagation of the new data. Examples of this use include multicast [Hui08a], network configuration [Lin08] [Dang09], and installing new application programs [Hui04] [Levis04].
可靠的泛洪/传播：协议使用涓流定期公布其收到的最新数据，通常通过版本号。当节点听到较新的版本号或接收到新数据时，会发生不一致。当节点听到较旧或相同的版本号时，会发生一致性。当听到较旧的版本号时，节点会发送更新，而不是重置自己的涓流计时器。接收更新的具有旧版本号的节点随后将重置其自己的计时器，从而导致新数据的快速传播。这种使用的示例包括多播[Hui08a]、网络配置[Lin08][Dang09]和安装新的应用程序[Hui04][Levis04]。
Routing control traffic: A protocol uses Trickle to control when it sends beacons that contain routing state. An inconsistency occurs when the routing topology changes in a way that could lead to loops or significant stretch: examples include when the routing layer detects a routing loop or when a node's routing cost changes significantly. Consistency occurs when the routing topology is operating well and is delivering packets successfully. Using the Trickle algorithm in this way allows a routing protocol to react very quickly to problems (Imin is small) but send very few beacons when the topology is stable. Examples of this use include the IPv6 routing protocol for low-power and lossy networks (RPL) [RPL], CTP [Gnawali09], and some current commercial IPv6 routing layers [Hui08b].
路由控制流量：协议使用涓流控制何时发送包含路由状态的信标。当路由拓扑以可能导致循环或显著拉伸的方式更改时，会发生不一致：例如，当路由层检测到路由循环时，或者当节点的路由成本显著更改时。当路由拓扑运行良好并成功传递数据包时，就会出现一致性。以这种方式使用涓流算法允许路由协议对问题做出非常快速的反应（Imin很小），但在拓扑稳定时发送很少的信标。这种使用的示例包括用于低功耗和有损网络的IPv6路由协议（RPL）[RPL]、CTP[Gnawali09]和一些当前的商用IPv6路由层[Hui08b]。
The authors would like to acknowledge the guidance and input provided by the ROLL chairs, David Culler and JP Vasseur.
作者希望感谢滚动椅、David Culler和JP Vasseur提供的指导和意见。
The authors would also like to acknowledge the helpful comments of Yoav Ben-Yehezkel, Alexandru Petrescu, and Ulrich Herberg, which greatly improved the document.
作者还要感谢Yoav Ben Yehezkel、Alexandru Petrescu和Ulrich Herberg的有益评论，这些评论极大地改进了文档。
As it is an algorithm, Trickle itself does not have any specific security considerations. However, two security concerns can arise when Trickle is used in a protocol. The first is that an adversary can force nodes to send many more packets than needed by forcing Trickle timer resets. In low-power networks, this increase in traffic can harm system lifetime. The second concern is that an adversary can prevent nodes from reaching consistency.
由于它是一种算法，Trickle本身没有任何特定的安全考虑。然而，在协议中使用涓流时，可能会出现两个安全问题。首先，对手可以通过强制涓流计时器重置，迫使节点发送比需要多得多的数据包。在低功率网络中，通信量的增加会影响系统寿命。第二个问题是对手可能会阻止节点达到一致性。
Protocols can prevent adversarial Trickle resets by carefully selecting what can cause a reset and protecting these events and messages with proper security mechanisms. For example, if a node can reset nearby Trickle timers by sending a certain packet, this packet should be authenticated such that an adversary cannot forge one.
协议可以通过仔细选择导致重置的原因并使用适当的安全机制保护这些事件和消息，从而防止对抗性涓流重置。例如，如果一个节点可以通过发送某个数据包来重置附近的涓流计时器，那么应该对该数据包进行身份验证，以便对手无法伪造该数据包。
An adversary can possibly prevent nodes from reaching consistency by suppressing transmissions with "consistent" messages. For example, imagine node A detects an inconsistency and resets its Trickle timer. If an adversary can prevent A from sending messages that inform nearby nodes of the inconsistency in order to repair it, then A may remain inconsistent indefinitely. Depending on the security model of the network, authenticated messages or a transitive notion of consistency can prevent this problem. For example, let us suppose an adversary wishes to suppress A from notifying neighbors of an
敌方可能通过使用“一致”消息抑制传输来阻止节点达到一致性。例如，假设节点A检测到不一致并重置其涓流计时器。如果对手可以阻止A发送通知附近节点不一致性的消息以修复不一致性，则A可能会无限期地保持不一致。根据网络的安全模型，经过身份验证的消息或一致性的可传递概念可以防止此问题。例如，让我们假设一个对手希望阻止A通知邻居一个
inconsistency. To do so, it must send messages that are consistent with A. These messages are by definition inconsistent with those of A's neighbors. Correspondingly, an adversary cannot simultaneously prevent A from notifying neighbors and not notify the neighbors itself (recall that Trickle operates on shared, broadcast media). Note that this means Trickle should filter unicast messages.
反复无常为此，它必须发送与A一致的消息。根据定义，这些消息与A的邻居的消息不一致。相应地，对手不能同时阻止A通知邻居而不通知邻居本身（回想一下，涓流是在共享广播媒体上运行的）。注意，这意味着Trickle应该过滤单播消息。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2119]Bradner，S.，“RFC中用于表示需求水平的关键词”，BCP 14，RFC 2119，1997年3月。
[Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code Consistency Maintenance Protocol for Multi-hop Wireless Networks", Wireless Sensor Networks: 6th European Conference Proceedings EWSN 2009 Cork, February 2009, <http://portal.acm.org/citation.cfm?id=1506781>.
[Dang09]Dang，T.，Bulusu，N.，Feng，W.，和S.Park，“DHV：多跳无线网络的代码一致性维护协议”，无线传感器网络：第六届欧洲会议记录EWSN 2009，科克，2009年2月<http://portal.acm.org/citation.cfm?id=1506781>.
[Gnawali09] Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P. Levis, "Collection Tree Protocol", Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, SenSys 2009, November 2009, <http://portal.acm.org/citation.cfm?id=1644038.1644040>.
[Gnawali，O.，Fonseca，R.，Jamieson，K.，Moss，D.，和P.Levis，“收集树协议”，第七届ACM嵌入式网络传感器系统会议记录，SenSys 2009，2009年11月<http://portal.acm.org/citation.cfm?id=1644038.1644040>.
[Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data dissemination protocol for network programming at scale", Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems, SenSys 2004, November 2004, <http://portal.acm.org/citation.cfm?id=1031506>.
[Hui04]Hui，J.和D.Culler，“大规模网络编程数据传播协议的动态行为”，第二届ACM嵌入式网络传感器系统会议论文集，SenSys 2004，2004年11月<http://portal.acm.org/citation.cfm?id=1031506>.
[Hui08a] Hui, J., "An Extended Internet Architecture for Low-Power Wireless Networks - Design and Implementation", UC Berkeley Technical Report EECS-2008-116, September 2008, <http://www.eecs.berkeley.edu/Pubs/>.
[Hui08a]Hui，J.，“低功率无线网络的扩展互联网架构-设计和实施”，加州大学伯克利分校技术报告EECS-2008-116，2008年9月<http://www.eecs.berkeley.edu/Pubs/>.
[Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for wireless sensor networks", Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems, SenSys 2008, November 2008, <http://portal.acm.org/citation.cfm?id=1460412.1460415>.
[Hui08b]Hui，J.和D.Culler，“无线传感器网络的IP是死的，IP是长寿的”，第六届ACM嵌入式网络传感器系统会议记录，SenSys 2008，2008年11月<http://portal.acm.org/citation.cfm?id=1460412.1460415>.
[Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker, "Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks", Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation, NSDI 2004, March 2004, <http://portal.acm.org/citation.cfm?id=1251177>.
[Levis04]Levis，P.，Patel，N.，Culler，D.，和S.Shenker，“涓流：无线传感器网络中代码传播和维护的自我调节算法”，第一届USENIX/ACM网络化系统设计和实现研讨会论文集，NSDI 2004，2004年3月<http://portal.acm.org/citation.cfm?id=1251177>.
[Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. Woo, "The Emergence of a Networking Primitive in Wireless Sensor Networks", Communications of the ACM, Vol. 51 No. 7, July 2008, <http://portal.acm.org/citation.cfm?id=1364804>.
[Levis08]Levis，P.，Brewer，E.，Culler，D.，Gay，D.，Madden，S.，Patel，N.，Polastre，J.，Shenker，S.，Szewczyk，R.，和A.Woo，“无线传感器网络中网络原语的出现”，《ACM通讯》，第51卷第7期，2008年7月<http://portal.acm.org/citation.cfm?id=1364804>.
[Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination with DIP", Proceedings of the 7th international conference on Information processing in sensor networks, IPSN 2008, April 2008, <http://portal.acm.org/citation.cfm?id=1371607.1372753>.
[Lin08]Lin，K.和P.Levis，“利用DIP进行数据发现和传播”，第七届传感器网络信息处理国际会议记录，IPSN 2008，2008年4月<http://portal.acm.org/citation.cfm?id=1371607.1372753>.
[RPL] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and JP. Vasseur, "RPL: IPv6 Routing Protocol for Low power and Lossy Networks", Work in Progress, March 2011.
[RPL]温特，T.，Ed.，苏伯特，P.，Ed.，勃兰特，A.，克劳森，T.，许，J.，凯尔西，R.，莱维斯，P.，皮斯特，K.，斯特鲁克，R.，和JP。Vasseur，“RPL：低功耗和有损网络的IPv6路由协议”，正在进行的工作，2011年3月。
Authors' Addresses
作者地址
Philip Levis Stanford University 358 Gates Hall Stanford, CA 94305 USA
Philip Levis斯坦福大学358 Gates Hall斯坦福，加利福尼亚州94305美国
Phone: +1 650 725 9064
EMail: pal@cs.stanford.edu
Phone: +1 650 725 9064
EMail: pal@cs.stanford.edu
Thomas Heide Clausen LIX, Ecole Polytechnique
托马斯·海德·克劳森·利克斯，理工学院
Phone: +33 6 6058 9349
EMail: T.Clausen@computer.org
Phone: +33 6 6058 9349
EMail: T.Clausen@computer.org
Jonathan Hui Arch Rock Corporation 501 2nd St., Suite 410 San Francisco, CA 94107 USA
乔纳森回族摇滚公司501第二街，套房410旧金山，CA 94107美国
EMail: jhui@archrock.com
EMail: jhui@archrock.com
Omprakash Gnawali Stanford University S255 Clark Center, 318 Campus Drive Stanford, CA 94305 USA
Omprakash Gnawali斯坦福大学S255克拉克中心，美国加利福尼亚州斯坦福大学校园大道318号，邮编94305
Phone: +1 650 725 6086
EMail: gnawali@cs.stanford.edu
Phone: +1 650 725 6086
EMail: gnawali@cs.stanford.edu
JeongGil Ko Johns Hopkins University 3400 N. Charles St., 224 New Engineering Building Baltimore, MD 21218 USA
美国马里兰州巴尔的摩市北查尔斯街3400号新工程大楼224号约翰霍普金斯大学
Phone: +1 410 516 4312
EMail: jgko@cs.jhu.edu
Phone: +1 410 516 4312
EMail: jgko@cs.jhu.edu