[要約] RFC 6206は、ネットワークデバイス間での情報の効率的な伝送を目指すTrickleアルゴリズムについての要約です。このRFCの目的は、ネットワークのリソースを最適化し、情報の伝送を効率化することです。
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.
Trickleアルゴリズムにより、損失のある共有媒体（低電力および損失のあるネットワークなど）のノードが、非常に堅牢でエネルギー効率の良い、シンプルで、スケーラブルな方法で情報を交換できます。送信ウィンドウを動的に調整することで、Trickleはリンク層の送信時間のスケールに関する新しい情報を広げることができ、情報が変更されない場合は1時間あたり数件のメッセージしか送信されません。単純な抑制メカニズムと伝送点の選択により、Trickleの通信率は密度で対数的にスケーリングすることができます。このドキュメントでは、その使用におけるトリクルアルゴリズムと考慮事項について説明します。
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.
このドキュメントの現在のステータス、任意のERRATA、およびそのフィードバックを提供する方法に関する情報は、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.
Copyright（c）2011 IETF Trustおよび文書著者として特定された人。全著作権所有。
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 Trustの法的規定の対象となります。この文書に関するあなたの権利と制限を説明するので、これらの文書を注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、セクション4.Eで説明されている法的規定のセクション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].
Trickleアルゴリズムは、ノードが送信されたときにガイドする根本的な一貫性モデルを使用して、密度認識ローカル通信を確立します。ノードのデータが近隣のデータと一致しない場合、ノードは迅速に通信して矛盾を解決します（たとえば、ミリ秒単位）。ノードが同意すると、通信率が指数関数的に遅くなるため、ノードはパケットを非常にまれに送信します（たとえば、1時間あたり数個のパケット）。ネットワークをパケットであふれさせる代わりに、アルゴリズムは送信レートを制御するため、各ノードはパケットの小さなトリクルを聞きます。さらに、ローカルコミュニケーション（放送やローカルマルチキャストなど）のみに依存することにより、トリクルハンドルネットワークの再入力。ネットワークのトランサンス、損失、および切断に堅牢です。実装は簡単です。そして、状態はほとんど必要ありません。現在の実装では、4〜11バイトのRAMが使用され、Cコードの50〜200ラインです[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].
このドキュメントでは、Trickleアルゴリズムについて説明し、その使用に関するガイドラインを提供します。また、Trickleを使用するプロトコル仕様の要件も述べています。このドキュメントは、Trickleのパフォーマンスや行動に関する結果を提供しません。また、アルゴリズムの設計を詳細に説明していません。興味のある読者は[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].
キーワードは「必須」、「必要」、「必須」、「shall」、「shall "、" bood "、" low "not"、 "becommended"、 "bodement"、 ""、 "、" 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.
Trickleの基本的な原始は単純です。多くの場合、ノードは、独自の伝送が冗長であることを示唆するデータをいくつか耳にしない限り、データを送信します。このようなデータの例には、ルーティング状態、ソフトウェア更新バージョン、最後に聞かれるマルチキャストパケットが含まれます。このプリミティブにより、トリクルはネットワーク密度の千倍のバリエーションにスケーリングし、更新を迅速に伝播し、伝送負荷を均等に分配し、一時的な切断に堅牢になり、ネットワークの再集団を処理し、非常に低いメンテナンスオーバーヘッドを課します。コレクションツリープロトコル（CTP）[GNAWALI09]では、1時間あたり数個のパケットの注文を送信する必要がありますが、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).
Trickleは、すべてのメッセージをローカル通信アドレスに送信します。使用される正確なアドレスは、基礎となるIPプロトコルと、高層プロトコルがトリクルを使用する方法に依存する可能性があります。たとえば、IPv6では、Link-Local Multicastアドレスまたは別のローカルマルチキャストアドレスである可能性がありますが、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.
トリクルメッセージには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.
たとえば、「最新」がバージョン番号（ネットワーク構成など）で定義される単純なケースを検討してください。ノードaがバージョンvを備えているがバージョン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/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つの構成パラメーターがあります。最小間隔サイズのイミン、最大間隔サイズ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 最小間隔サイズのイミンは、時間単位（ミリ秒、秒など）で定義されます。たとえば、プロトコルは最小間隔を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は、最小間隔サイズ（ベース2ログ（最大/分））の多くの倍増として記述されています。たとえば、プロトコルはIMAXを16として定義する場合があります。最小間隔が100ミリ秒の場合、IMAXで指定された時間は100ミリ秒 * 65,536、つまり6,553.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:
これらの3つのパラメーターに加えて、Trickleは3つの変数を維持します。
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:
Trickleアルゴリズムには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.
1. アルゴリズムが実行を開始すると、[imin、imax]の範囲の値にiを設定します。つまり、イミンよりも大きく、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. 間隔が始まると、TrickleはCにCにリセットし、範囲[I/2、I）から取られた間隔のランダムなポイントにTを設定します。つまり、I/2以下の値以下の値をIよりも少なくします。間隔はIで終わります。
3. Whenever Trickle hears a transmission that is "consistent", it increments the counter c.
3. Trickleが「一貫性」の伝送を聞くたびに、カウンター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. 間隔が期限切れになると、トリクルは間隔の長さを2倍にします。この新しい間隔の長さがIMAXで指定された時間よりも長くなる場合、Trickleは間隔の長さ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. トリクルが「一貫性がない」トランスミッションを聞き、私がイミンよりも大きい場合、それはトリクルタイマーをリセットします。タイマーをリセットするために、TrickleはIをIminに設定し、ステップ2のように新しい間隔を開始します。トリクルが「一貫性のない」伝送を聞いたときにイミンに等しい場合、Trickleは何もしません。トリクルは、外部の「イベント」に応じてタイマーをリセットすることもできます。
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.
Trickleアルゴリズムが送信されるのは、上記のアルゴリズムのステップ4にあるのです。これは、矛盾を検出する（Iを縮小する）とその矛盾（新しい間隔の時間tで送信）に応答することとの間に固有の遅延があることを意味します。これは意図的です。矛盾を検出することに直ちに応答すると、多くのノードが一度に同期して応答するブロードキャストストームを引き起こす可能性があります。応答を行うことにより、トリクルアルゴリズム（間隔サイズが最小限）に従うことにより、プロトコルはトリクルの抑制メカニズムから利益を得て、膨大な範囲のノード密度にわたってスケーリングできます。
A protocol specification that uses Trickle MUST specify:
Trickleを使用するプロトコル仕様は、指定する必要があります。
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のデフォルト値。リンクレイヤーはプロパティで大きく異なる可能性があるため、イミンのデフォルト値は、リンク層伝送の最悪の潜伏期の観点から指定する必要があります。たとえば、仕様には「イミンのデフォルト値は最悪のリンクレイヤーレイテンシの4倍である」と言う必要があり、「イミンのデフォルト値は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.
Trickleを使用するプロトコルには、メカニズムが含まれて、実行時に構成パラメーターのノードを通知することをお勧めします。ただし、そうすることは常に可能ではありません。異なるノードに異なる構成パラメーターがある場合、Trickleは意図しない動作を持つ可能性があります。このセクションでは、これらの行動と運用上の考慮事項のいくつかを教育演習として概説します。
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.
ノードがイミンに一致しない場合、一貫性のないメッセージを聞くと、一部のノードは他のノードよりも早く送信されます。これらの高速なノードは、間隔が1回の遅い間隔時間内に遅いノードのサイズと同様のサイズに成長しますが、その期間には遅いノードが抑制される場合があります。ただし、そのような抑制は、ノードが一般に間隔サイズに一致する最初の遅い間隔の後に終了します。したがって、不一致のイミン値は通常、重要な懸念ではありません。不一致のイミン値と一致する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ではなくK-1を記述することは混乱を招く可能性があります。代わりに、抑制をオフにする必要があるプロトコルは、k = 0を平均するためにk = 0を保護することをお勧めします。
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].
最後に、プロトコルはKとイミンを設定して、IminがKパケットを送信するのにかかる限り少なくとも2〜3倍になるようにする必要があります。それ以外の場合、kノード以上の場合、間隔をイミンにリセットすると、結果として生じる通信はうっ血と重大なパケット損失につながります。実験結果は、混雑によるパケット損失がトリクルの効率を低下させることを示しています[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.
Trickleは、挑戦的なネットワーク環境に対して非常に堅牢な、少数のシンプルで密接に統合されたメカニズムに基づいています。Trickleを使用した私たちの経験では、その動作を調整しようとする試みは通常、コストの価値がありません。書かれているように、アルゴリズムはすでに非常に効率的です。エッジケースでは、送信または応答時間のさらなる削減が故障の犠牲を払っています。私たちの経験に基づいて、プロトコル設計者は、変更がその仮定に違反しないという多くの実験的証拠なしに、本能を微調整または改善するように本能を抑制するように促します。
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.
この警告を念頭に置いて、Trickleは完璧とはほど遠いものです。たとえば、トリクル抑制は通常、スパースのないノードを密度の高いノードよりも伝達するようになります。最小カバーの最適な計算からはほど遠いものです。ただし、ワイヤレスや低電力の損失のあるネットワークなどの動的なネットワーク環境では、伝送の最適なセットを計算するために必要な調整は、通常、それが提供する利点よりもはるかに大きくなります。Trickleの利点の1つは、実装が非常に簡単で、状態が非常に少ないが効率的に動作する必要があることです。それを改善する努力は、複雑さの増加のコストと比較検討する必要があります。
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.
Trickleアルゴリズムは、さまざまなプロトコル、運用設定および学術環境で使用されています。これらの用途のいくつかの簡単な概要を提供すると、使用方法の有用な例が提供されます。これらの例は、網羅的と見なされるべきではありません。
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].
信頼性の高い洪水/普及：プロトコルはTrickleを使用して、通常はバージョン番号を使用して受信した最新のデータを定期的に宣伝します。ノードが新しいバージョン番号を聞いたり、新しいデータを受信したりすると、矛盾が発生します。ノードが古いバージョンまたは等しいバージョン数を聞くと、一貫性が発生します。独自のトリクルタイマーをリセットするのではなく、古いバージョン番号を聞くと、ノードは更新を送信します。更新を受信する古いバージョン番号を持つノードは、独自のタイマーをリセットし、新しいデータの速い伝播につながります。この使用の例には、マルチキャスト[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].
ルーティング制御トラフィック：プロトコルは、ルーティング状態を含むビーコンを送信するときにトリクルを使用して制御します。ルーティングトポロジがループまたは大幅なストレッチにつながる可能性のある方法で変化する場合、矛盾が発生します。例には、ルーティングレイヤーがルーティングループを検出する場合、またはノードのルーティングコストが大幅に変化する場合が含まれます。一貫性は、ルーティングトポロジがうまく動作しており、パケットを正常に配信している場合に発生します。このようにしてトリクルアルゴリズムを使用すると、ルーティングプロトコルが問題に非常に迅速に反応することができます（イミンは小さい）が、トポロジが安定している場合は非常に少ないビーコンを送信できます。この使用の例には、低電力および損失ネットワーク（RPL）[RPL]、CTP [GNAWALI09]のIPv6ルーティングプロトコル、および現在の市販のIPv6ルーティング層[HUI08B]が含まれます。
The authors would like to acknowledge the guidance and input provided by the ROLL chairs, David Culler and JP Vasseur.
著者は、ロールチェア、デビッド・カラー、JP・ヴァスザーが提供するガイダンスと入力を認めたいと考えています。
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自体には特定のセキュリティ上の考慮事項はありません。ただし、プロトコルでトリクルが使用されると、2つのセキュリティ上の懸念が生じる可能性があります。1つ目は、敵が、トリクルタイマーのリセットを強制することで必要以上に多くのパケットを送信するようにノードを強制できることです。低電力ネットワークでは、このトラフィックの増加はシステムの寿命を損なう可能性があります。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.
プロトコルは、リセットを引き起こす可能性のあるものを慎重に選択し、適切なセキュリティメカニズムでこれらのイベントやメッセージを保護することにより、敵対的なトリクルリセットを防ぐことができます。たとえば、特定のパケットを送信してノードが近くのトリクルタイマーをリセットできる場合、このパケットは敵がそれを偽造できないように認証する必要があります。
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.
敵は、「一貫した」メッセージで送信を抑制することにより、ノードが一貫性に達するのを防ぐことができます。たとえば、Imagine Node Aは矛盾を検出し、トリクルタイマーをリセットします。敵がそれを修復するために矛盾を近くのノードに通知するメッセージを送信するのを防ぐことができれば、Aは無期限に一貫性を保つことができます。ネットワークのセキュリティモデルに応じて、認証されたメッセージまたは一貫性の推移的な概念は、この問題を防ぐことができます。たとえば、敵が矛盾の隣人に通知することを抑制したいと思っていると仮定しましょう。そのためには、Aと一致するメッセージを送信する必要があります。これらのメッセージは、定義上、Aの隣人のメッセージと矛盾しています。それに対応して、敵は同時に隣人に通知することを防ぎ、隣人自体に通知しないことを防ぐことはできません（トリクルが共有された放送メディアで動作していることを思い出してください）。これは、トリクルがユニキャストメッセージをフィルタリングすることを意味することに注意してください。
[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：マルチホップワイヤレスネットワークのコード一貫性メンテナンスプロトコル」、ワイヤレスセンサーネットワーク：第6欧州会議議事録EWSN 2009 Cork、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.、Fonseca、R.、Jamieson、K.、Moss、D.、およびP. Levis、「Collection Tree Protocol」、第7回ACM埋め込みセンサーシステムに関する議事録、Sensys 2009、11月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] Hui、J。およびD. Culler、「大規模なネットワークプログラミングのためのデータ普及プロトコルの動的動作」、埋め込みネットワークセンサーシステムに関する第2回ACM会議の議事録、2004年11月、<http：/ <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。、「低電力ワイヤレスネットワークのための拡張インターネットアーキテクチャ - 設計と実装」、UC Berkeley技術レポート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 IS DEAD、Wireless Sensor NetworksのLong Live IP」、Embedded Network Sensor Systemsに関する第6回ACM会議の議事録、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] 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。ウー、「ワイヤレスセンサーネットワークにおけるネットワーキングプリミティブの出現」、ACMの通信、Vol。51 No. 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、「Data Discovery and Essemination with Dip」、センサーネットワークでの情報処理に関する第7回国際会議の議事録、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] Winter、T.、Ed。、Thubert、P.、Ed。、Brandt、A.、Clausen、T.、Hui、J.、Kelsey、R.、Levis、P.、Pister、K.、Struik、R。、およびJP。Vasseur、「RPL：低電力および損失ネットワーク向けのIPv6ルーティングプロトコル」、2011年3月、進行中の作業。
Authors' Addresses
著者のアドレス
Philip Levis Stanford University 358 Gates Hall Stanford, CA 94305 USA
フィリップレビススタンフォード大学358ゲイツホールスタンフォード、カリフォルニア94305アメリカ
Phone: +1 650 725 9064
EMail: pal@cs.stanford.edu
Thomas Heide Clausen LIX, Ecole Polytechnique
Thomas Heide Clausen Lix、Ecole Polytechnique
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
Jonathan Hui Arch Rock Corporation 501 2nd St.、Suite 410 San Francisco、CA 94107 USA
EMail: jhui@archrock.com
Omprakash Gnawali Stanford University S255 Clark Center, 318 Campus Drive Stanford, CA 94305 USA
Omprakash Gnawali Stanford University S255 Clark Center、318 Campus Drive Stanford、CA 94305 USA
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
Jeonggil Ko Johns Hopkins University 3400 N. Charles St.、224 New Engineering Building Baltimore、MD 21218 USA
Phone: +1 410 516 4312
EMail: jgko@cs.jhu.edu