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ドキュメント（http://trustee.ietf.org/license-info）に関連IETFトラストの法律の規定に従うものとします。彼らは、この文書に関してあなたの権利と制限を説明するように、慎重にこれらの文書を確認してください。コードコンポーネントは、トラスト法規定のセクションで説明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
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].
トリクルアルゴリズムは、ノードが送信するガイド下層の一貫性モデルとプリミティブ密度対応ローカル通信を確立します。ノードのデータは、その隣人に同意しない場合、そのノードは、（例えば、ミリ秒単位で）矛盾を解決するために迅速に伝達します。ノードが一致した場合、彼らは、ノードが非常にまれにしかパケットを送信するように、指数関数的にその通信速度を遅く（例えば、時速数パケット）。代わりに、パケットでネットワークを洪水の、アルゴリズムはので、各ノードは、ちょうど十分な一貫性のある滞在し、パケットの小さなトリクルを聞い送信レートを制御します。また、ローカル通信（例えば、ブロードキャストまたはローカルマルチキャスト）にのみ依存することにより、トリクルは、ネットワーク再集団を扱います。はかなさ、損失、および切断をネットワークに堅牢です。実装が簡単です。そして、非常に少ない状態が必要です。現在の実装は、[Levis08] Cコードの50~200行をRAMの4-11バイトを使用しています。
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.
トリクルが最初に（データが更新されたプログラムのコードである）再プログラミングプロトコルのために設計されたが、経験は、制御トラフィックのタイミングを含むプロトコル設計問題の広い範囲に適用することができる強力な機構であることが示されている、マルチキャスト伝播、およびルート発見。この柔軟性は、「契約」または「矛盾」を構成するもの、ケースバイケースで、定義することができることに起因します。セクション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].
キーワード "MUST"、 "MUST NOT"、 "REQUIRED"、 "SHALL"、 "SHOULD"、 "ないもの"、 "推奨" "ない（SHOULD NOT）"、 "MAY"、 "推奨NOT"、および「OPTIONAL 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プロトコルに依存することができます。 IPv4のそれがブロードキャストアドレス（255.255.255.255）ことができるがIPv6では、例えば、それは、リンクローカルマルチキャストアドレス、または他のローカルマルチキャストアドレスとすることができます。
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.
トリクルメッセージには2つの可能な結果があります。いずれかのメッセージを聞くすべてのノードは、メッセージデータが自身の状態と一致している、または受信者が矛盾を検出することを見つけました。検出は、期限切れの新しい何かを聞いたノード、または古い何かを聞い更新ノードのいずれかの結果であり得ます。限り、すべてのノードが何らかの形で通信するよう - 受信または送信のいずれか - いくつかのノードは、更新の必要性を検出します。
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.
例えば、「最新」バージョン番号（例えば、ネットワーク構成）によって定義される単純な場合を考えます。それは、バージョンVを有するが、Bは、バージョンV + 1を有していることをノードAに送信する場合、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:
トリクルタイマーが定義された間隔で実行され、3つの設定パラメータを有する：最小間隔寸法値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.
最小間隔サイズ、IminをO、時間（例えば、ミリ秒、秒）の単位で定義されています。例えば、プロトコルは、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.
最大間隔サイズ、値Imax O、最小間隔寸法（底2対数（最大/最小））の倍加の数として記載されています。最小間隔は100ミリ秒である場合、例えば、プロトコルは、次に値Imaxで指定された時間が100ms * 65,536、即ち、6,553.6秒または約109分であり、16として値Imaxを定義するかもしれません。
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:
これら三つのパラメータに加えて、トリクル3つの変数を維持します。
o I, the current interval size,
O I、現在の間隔の大きさ、
o t, a time within the current interval, and
O T、現在の間隔内の時間、および
o c, a counter.
O、C、カウンター。
The Trickle algorithm has six rules:
トリクルアルゴリズムは、6つのルールがあります。
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.
つまり、以上値Iminに等しく、以下からImaxに等しい - アルゴリズムが実行を開始すると1には、[Iminを、Imaxを]の範囲内の値にIを設定します。このアルゴリズムは、最初のインターバルを開始します。
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は、トリクルを0にCをリセットし、範囲から採取された間隔でランダム点、[I / 2、I）、即ち、I / 2未満以上の値にTを設定しますI.間隔はI.で終了します
3. Whenever Trickle hears a transmission that is "consistent", it increments the counter c.
トリクルが「一致」であり、送信を聞くたびに、カウンタCをインクリメント3。
4. At time t, Trickle transmits if and only if the counter c is less than the redundancy constant k.
時刻tにおける4、トリクルがあれば送信し、カウンタ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.私の期限が切れる間隔は、トリクルはインターバル長を倍増する場合。この新しい間隔の長さは、アイマックスで指定された時間よりも長くなる場合は、トリクルは、私はアイマックスで指定された時間であることを間隔の長さを設定します。
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.トリクルは「矛盾」であると私はIminをより大きく、送信を聞く場合は、トリクルタイマーをリセットします。タイマーをリセットするには、トリクルをIminにIを設定し、トリクルは「矛盾」の送信を聞いたとき、私はIminのに等しい場合には、ステップ2のように新しい間隔を開始し、トリクルは何もしません。トリクルは、外部の「イベント」に応答して、そのタイマーをリセットすることができます。
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です。これは、（新たな間隔で時刻tに送信する）（値IminにIを収縮）矛盾を検出し、その矛盾への応答との間の固有の遅延が存在することを意味します。これは意図的なものです。すぐに矛盾を検出することに応答して、多くのノードが一度と同期して対応ブロードキャストストームを引き起こす可能性があります。 （最小の間隔寸法を有する）トリクルアルゴリズムに従って応答することにより、プロトコルは、ノード密度の大きな範囲にわたってトリクルの抑制機構と規模から利益を得ることができます。
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.).
Iminを、アイマックス、およびkのOのデフォルト値。リンク層は、その特性が大きく異なる可能性があるため、値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の低い値を持つノードより送信します。いくつかのケースでは、この増加した負荷は、密度に依存しないことができます。例えば、全てのノードが、1つは、K = 1を有するネットワークを考えると、この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の値を持つノードは、常に抑制し、送信することはありません。ネットワークが一貫している場合、基本ケースでは、これはエネルギーコストの長期的な不平等を引き起こす可能性があります。
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を、およびアイマックスとは異なり、一貫性の定義は明確にプロトコルに記載しなければならないと、実行時に設定しないでください。
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は無限大に設定されている）、その抑制に無効でトリクルを使用したいかもしれないいくつかのエッジ場合があります。一般的に、このアプローチは非常に危険であり、それは推奨されません。抑制を無効にすると、すべてのノードが常にすべての間隔で送信することを意味します。これは、密なネットワークの輻輳につながることができます。多くのノードが同時に彼らの間隔をリセットする場合は、このアプローチは特に危険です。一般的に、それは無限大よりも高い値（例えば、5又は10）にKを設定するために、はるかに望ましいです。 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 resulting communication will lead to congestion and significant packet loss. Experimental results have shown that packet losses from congestion reduce Trickle's efficiency [Levis04].
最後に、プロトコルは、値Iminがあれば、それがk個のパケットを送信するのにかかるように、少なくとも2倍から3倍であるようなkおよび値Iminを設定する必要があります。 k個以上のノードが値Iminにそれらの間隔をリセットするとそうでない場合、得られた通信が混雑し、有意なパケット損失につながります。実験結果は、輻輳からのパケット損失がトリクルの効率[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.
念頭に置いて、この警告では、トリクルは完璧にはほど遠いです。例えば、トリクル抑制は、典型的には、より高密度のものより多くを送信するためにまばらノードを導きます。それが最低限のカバーの最適な計算から遠いです。しかしながら、そのような無線および低電力損失の多いネットワークのような動的なネットワーク環境では、送信の最適なセットを計算するために必要な調整は、典型的にははるかに大きいことが提供利点よりも長いです。トリクルの利点の一つは、実現するのは簡単ですので、効率的に動作はまだので、少し様子を必要とすることです。それを改善する努力は複雑化のコストと比較検討されなければなりません。
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のは小さい）が、トポロジーが安定しているときに、非常に少数のビーコンを送信することができます。この使用の例は、[Hui08b】低電力およびロッシーネットワークのIPv6ルーティングプロトコル（RPL）[RPL]、CTP [Gnawali09]、およびいくつかの現在市販されているIPv6ルーティング層を含みます。
The authors would like to acknowledge the guidance and input provided by the ROLL chairs, David Culler and JP Vasseur.
著者は、ROLLの椅子、デイヴィッド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.
著者らはまた、大幅に文書を改善ヨアフベン・Yehezkel、アレクサンドル・ペトレスク、とウルリッヒ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.
それはアルゴリズムであるため、トリクル自体は、任意の特定のセキュリティ上の考慮事項はありません。トリクルは、プロトコルで使用されている場合しかし、2つのセキュリティ上の問題が発生する可能性があります。最初は敵がトリクルタイマーリセットを強制することにより、必要以上の多くのパケットを送信するためにノードを強制することができるということです。低電力ネットワークでは、トラフィックの増加は、システムの寿命に悪影響を与えることができます。第二の懸念は、敵対者が一貫性に到達するノードを防止することができるということです。
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.
プロトコルは慎重にリセットを引き起こすことができるものを選択し、適切なセキュリティメカニズムと、これらのイベントやメッセージを保護することにより敵対トリクルリセットを防ぐことができます。ノードが特定のパケットを送信することによって、近くトリクルタイマーをリセットすることができた場合、このパケットは、敵対者が1つを偽造できないように認証されなければなりません。
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 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を抑制したいと仮定しましょう。そのためには、これらのメッセージは、Aの隣人のものと矛盾定義であるA.と一致しているメッセージを送信する必要があります。これに対応して、敵対者は同時に近隣自体（トリクルがオン動作することをリコール共有、放送メディア）を通知する通知ネイバーからAを防止しないことはできません。これはトリクルは、ユニキャストメッセージをフィルタリングするべきであることを意味することに注意してください。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2119]ブラドナーの、S.、 "要件レベルを示すためにRFCsにおける使用のためのキーワード"、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]ダン、T.、Bulusu、N.、風水、W.、およびS.パーク、「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>.
[Gnawali09] Gnawali、O.、フォンセカ、R.、ジェイミソン、K.、モス、D.、およびP.リーバイス、 "コレクション・ツリー・プロトコル"、組込みネットワークセンサシステム、SENSYS 2009年11月第7回ACM会議議事録2009年、<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]ホイ、J.およびD. Culler、「規模のネットワークプログラミングのためのデータ配布プロトコルの動的挙動」、<HTTP組み込みネットワークセンサシステム、SENSYS 2004、2004年11月、第2回ACM会議の議事録：/ /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]ホイ、J.、「低消費電力ワイヤレスネットワークの拡張、インターネットアーキテクチャ - 設計と実装」、UCバークレーテクニカルレポートEECS-2008から116、2008年9月、<http://www.eecs.berkeley.edu /パブ/>。
[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]ホイ、J.とD. Cullerは、 "IPは、無線センサネットワークのために死んだ、長く生きてIPである" 組込みネットワークセンサシステム第6回ACM会議、SENSYS 2008、2008年11月の議事録、<のhttp：//ポータル.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】リーバイス、P.、パテル、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】リーバイス、P.、ブリューワー、E.、Culler、D.、ゲイ、D.、マッデン、S.、パテル、N.、Polastre、J.、Shenker、S.、Szewczyk、R.、およびA 。ウー、「無線センサネットワークにおける原始ネットワーキングの出現」、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]林、K.およびP.リーバイス、「データディスカバリーおよびDIPと普及」、センサネットワークにおける情報の処理第7回国際会議の議事録、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.、エド。、Thubert、P.、エド。、ブラント、A.、Clausenの、T.、ホイ、J.、ケルシー、R.、リーバイス、P.、ピスター教授、K.、Struik 、R.、およびJP。 Vasseur、「RPL：低消費電力とロッシーネットワークのためのIPv6ルーティングプロトコル」、進歩、2011年3月に作業。
Authors' Addresses
著者のアドレス
Philip Levis Stanford University 358 Gates Hall Stanford, CA 94305 USA
フィリップ・リーバイススタンフォード大学358ゲイツホールスタンフォード、CA 94305 USA
Phone: +1 650 725 9064 EMail: pal@cs.stanford.edu
電話：+1 650 725 9064 Eメール：pal@cs.stanford.edu
Thomas Heide Clausen LIX, Ecole Polytechnique
トーマス・ハイデクラウゼンLIX、エコールポリテクニック
Phone: +33 6 6058 9349 EMail: T.Clausen@computer.org
電話：+33 6 6058 9349 Eメール：T.Clausen@computer.org
Jonathan Hui Arch Rock Corporation 501 2nd St., Suite 410 San Francisco, CA 94107 USA
ジョナサン・ホイアーチロック株式会社501第二聖、スイート410サンフランシスコ、CA 94107 USA
EMail: jhui@archrock.com
メールアドレス：jhui@archrock.com
Omprakash Gnawali Stanford University S255 Clark Center, 318 Campus Drive Stanford, CA 94305 USA
Omprakash Gnawaliスタンフォード大学S255クラークセンター、318キャンパスドライブ、スタンフォード、CA 94305 USA
Phone: +1 650 725 6086 EMail: gnawali@cs.stanford.edu
電話：+1 650 725 6086 Eメール：gnawali@cs.stanford.edu
JeongGil Ko Johns Hopkins University 3400 N. Charles St., 224 New Engineering Building Baltimore, MD 21218 USA
JeongGilコジョンズ・ホプキンス大学3400 N.チャールズセント、224新しいエンジニアリングビルボルチモア、MD 21218 USA
Phone: +1 410 516 4312 EMail: jgko@cs.jhu.edu
電話：+1 410 516 4312 Eメール：jgko@cs.jhu.edu