[要約] RFC 7363は、RELOADプロトコルのための自己調整型分散ハッシュテーブル（DHT）に関する要約です。このRFCの目的は、RELOADネットワーク内のリソースの位置と検出を効率的に行うためのDHTの設計と動作を提案することです。
Internet Engineering Task Force (IETF) J. Maenpaa
Request for Comments: 7363 G. Camarillo
Category: Standards Track Ericsson
ISSN: 2070-1721 September 2014
Self-Tuning Distributed Hash Table (DHT) for REsource LOcation And Discovery (RELOAD)
リソースの検索と発見（RELOAD）を再利用するための自己調整分散ハッシュテーブル（DHT）
Abstract
概要
REsource LOcation And Discovery (RELOAD) is a peer-to-peer (P2P) signaling protocol that provides an overlay network service. Peers in a RELOAD overlay network collectively run an overlay algorithm to organize the overlay and to store and retrieve data. This document describes how the default topology plugin of RELOAD can be extended to support self-tuning, that is, to adapt to changing operating conditions such as churn and network size.
RElocation LOcation And Discovery（RELOAD）は、オーバーレイネットワークサービスを提供するピアツーピア（P2P）シグナリングプロトコルです。 RELOADオーバーレイネットワークのピアは、オーバーレイアルゴリズムを集合的に実行して、オーバーレイを整理し、データを格納および取得します。このドキュメントでは、RELOADのデフォルトトポロジプラグインを拡張してセルフチューニングをサポートする方法、つまりチャーンやネットワークサイズなどの変化する動作条件に適応する方法について説明します。
Status of This Memo
本文書の状態
This is an Internet Standards Track document.
これはInternet Standards Trackドキュメントです。
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（Internet Engineering Task Force）の製品です。これは、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/rfc7363.
このドキュメントの現在のステータス、エラータ、およびフィードバックの提供方法に関する情報は、http：//www.rfc-editor.org/info/rfc7363で入手できます。
Copyright Notice
著作権表示
Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved.
Copyright（c）2014 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文書に関するIETFトラストの法的規定（http://trustee.ietf.org/license-info）の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関するあなたの権利と制限を説明しているため、注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、Trust Legal Provisionsのセクション4.eに記載されているSimplified BSD Licenseテキストが含まれている必要があり、Simplified BSD Licenseに記載されているように保証なしで提供されます。
Table of Contents
目次
1. Introduction ....................................................2
2. Terminology .....................................................3
3. Introduction to Stabilization in DHTs ...........................5
3.1. Reactive versus Periodic Stabilization .....................5
3.2. Configuring Periodic Stabilization .........................6
3.3. Adaptive Stabilization .....................................7
4. Introduction to Chord ...........................................7
5. Extending Chord-Reload to Support Self-Tuning ...................9
5.1. Update Requests ............................................9
5.2. Neighbor Stabilization ....................................10
5.3. Finger Stabilization ......................................11
5.4. Adjusting Finger Table Size ...............................11
5.5. Detecting Partitioning ....................................11
5.6. Leaving the Overlay .......................................11
6. Self-Tuning Chord Parameters ...................................12
6.1. Estimating Overlay Size ...................................12
6.2. Determining Routing Table Size ............................13
6.3. Estimating Failure Rate ...................................13
6.3.1. Detecting Failures .................................14
6.4. Estimating Join Rate ......................................14
6.5. Estimate Sharing ..........................................15
6.6. Calculating the Stabilization Interval ....................17
7. Overlay Configuration Document Extension .......................17
8. Security Considerations ........................................18
9. IANA Considerations ............................................18
9.1. Message Extensions ........................................18
9.2. New Overlay Algorithm Type ................................19
9.3. A New IETF XML Registry ...................................19
10. Acknowledgments ...............................................19
11. References ....................................................19
11.1. Normative References .....................................19
11.2. Informative References ...................................20
REsource LOcation And Discovery (RELOAD) [RFC6940] is a peer-to-peer signaling protocol that can be used to maintain an overlay network and to store data in and retrieve data from the overlay. For interoperability reasons, RELOAD specifies one overlay algorithm, called "chord-reload", that is mandatory to implement. This document extends the chord-reload algorithm by introducing self-tuning behavior.
REsource LOcation And Discovery（RELOAD）[RFC6940]は、オーバーレイネットワークを維持し、オーバーレイにデータを保存したり、オーバーレイからデータを取得したりするために使用できるピアツーピアシグナリングプロトコルです。相互運用性の理由から、RELOADは「chord-reload」と呼ばれる1つのオーバーレイアルゴリズムを指定します。これは、実装する必要があります。このドキュメントでは、セルフチューニング動作を導入することにより、コード再読み込みアルゴリズムを拡張しています。
DHT-based overlay networks are self-organizing, scalable, and reliable. However, these features come at a cost: peers in the overlay network need to consume network bandwidth to maintain routing state. Most DHTs use a periodic stabilization routine to counter the undesirable effects of churn on routing. To configure the parameters of a DHT, some characteristics such as churn rate and network size need to be known in advance. These characteristics are then used to configure the DHT in a static fashion by using fixed values for parameters such as the size of the successor set, size of the routing table, and rate of maintenance messages. The problem with this approach is that it is not possible to achieve a low failure rate and a low communication overhead by using fixed parameters. Instead, a better approach is to allow the system to take into account the evolution of network conditions and adapt to them.
DHTベースのオーバーレイネットワークは、自己組織化、スケーラブル、および信頼性があります。ただし、これらの機能にはコストがかかります。オーバーレイネットワークのピアは、ルーティング状態を維持するためにネットワーク帯域幅を消費する必要があります。ほとんどのDHTは、定期的な安定化ルーチンを使用して、ルーティングに対するチャーンの望ましくない影響に対抗します。 DHTのパラメーターを構成するには、解約率やネットワークサイズなどのいくつかの特性を事前に把握しておく必要があります。次に、これらの特性を使用して、後続セットのサイズ、ルーティングテーブルのサイズ、メンテナンスメッセージのレートなどのパラメータに固定値を使用することにより、DHTを静的に構成します。このアプローチの問題は、固定パラメーターを使用して低い故障率と低い通信オーバーヘッドを達成することができないことです。代わりに、より良いアプローチは、システムがネットワーク状態の変化を考慮に入れ、それらに適応できるようにすることです。
This document extends the mandatory-to-implement chord-reload algorithm by making it self-tuning. The use of the self-tuning feature is optional. However, when used, it needs to be supported by all peers in the RELOAD overlay network. The fact that a RELOAD overlay uses the self-tuning feature is indicated in the RELOAD overlay configuration document using the CHORD-SELF-TUNING algorithm name specified in Section 9.2 in the topology-plugin element. Two main advantages of self-tuning are that users no longer need to tune every DHT parameter correctly for a given operating environment and that the system adapts to changing operating conditions.
このドキュメントでは、必須のコードリロードアルゴリズムをセルフチューニングにすることでコードリロードアルゴリズムを拡張しています。セルフチューニング機能の使用はオプションです。ただし、使用する場合は、RELOADオーバーレイネットワークのすべてのピアでサポートする必要があります。 RELOADオーバーレイがセルフチューニング機能を使用するという事実は、トポロジープラグイン要素のセクション9.2で指定されたCHORD-SELF-TUNINGアルゴリズム名を使用したRELOADオーバーレイ構成ドキュメントに示されています。セルフチューニングの2つの主な利点は、ユーザーが特定の動作環境ですべてのDHTパラメータを正しくチューニングする必要がなくなり、システムが変化する動作条件に適応することです。
The remainder of this document is structured as follows: Section 2 provides definitions of terms used in this document. Section 3 discusses alternative approaches to stabilization operations in DHTs, including reactive stabilization, periodic stabilization, and adaptive stabilization. Section 4 gives an introduction to the Chord DHT algorithm. Section 5 describes how this document extends the stabilization routine of the chord-reload algorithm. Section 6 describes how the stabilization rate and routing table size are calculated in an adaptive fashion.
このドキュメントの残りの部分は、次のように構成されています。セクション2では、このドキュメントで使用される用語の定義を示します。セクション3では、DHTでの安定化操作の代替アプローチについて説明します。これには、リアクティブ安定化、定期的安定化、および適応安定化が含まれます。セクション4では、コードDHTアルゴリズムの概要を説明します。セクション5では、このドキュメントがコード再ロードアルゴリズムの安定化ルーチンを拡張する方法について説明します。セクション6では、安定化率とルーティングテーブルのサイズを適応的に計算する方法について説明します。
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 [RFC2119].
キーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「NOT RECOMMENDED」、「MAY」、「OPTIONALこの文書の "は、[RFC2119]で説明されているように解釈されます。
This document uses terminology and definitions from the RELOAD base specification [RFC6940].
このドキュメントでは、RELOAD基本仕様[RFC6940]の用語と定義を使用しています。
numBitsInNodeId: Specifies the number of bits in a RELOAD Node-ID.
numBitsInNodeId：RELOADノードIDのビット数を指定します。
DHT: Distributed Hash Tables are a class of decentralized distributed systems that provide a lookup service similar to a regular hash table. Given a key, any peer participating in the system can retrieve the value associated with that key. The responsibility for maintaining the mapping from keys to values is distributed among the peers.
DHT：分散ハッシュテーブルは、通常のハッシュテーブルと同様のルックアップサービスを提供する分散分散システムのクラスです。キーを指定すると、システムに参加しているすべてのピアが、そのキーに関連付けられている値を取得できます。キーから値へのマッピングを維持する責任は、ピア間で分散されます。
Chord Ring: The Chord DHT uses ring topology and orders identifiers on an identifier circle of size 2^numBitsInNodeId. This identifier circle is called the Chord ring. On the Chord ring, the responsibility for a key k is assigned to the node whose identifier equals to or immediately follows k.
コードリング：コードDHTはリングトポロジを使用し、サイズが2 ^ numBitsInNodeIdの識別子円に識別子を並べます。この識別子円はコードリングと呼ばれます。コードリングでは、キーkの責任は、識別子がkに等しいか、直後にあるノードに割り当てられます。
Finger Table: A data structure with up to (but typically less than) numBitsInNodeId entries maintained by each peer in a Chord-based overlay. The ith entry in the finger table of peer n contains the identity of the first peer that succeeds n by at least 2^(numBitsInNodeId-i) on the Chord ring. This peer is called the ith finger of peer n. As an example, the first entry in the finger table of peer n contains a peer halfway around the Chord ring from peer n. The purpose of the finger table is to accelerate lookups.
Finger Table：Chordベースのオーバーレイの各ピアによって維持されるnumBitsInNodeIdエントリ（通常はそれより少ない）までのデータ構造。ピアnのfingerテーブルのi番目のエントリには、コードリングでnの後に少なくとも2 ^（numBitsInNodeId-i）だけ成功した最初のピアのIDが含まれています。このピアは、ピアnのi番目のフィンガーと呼ばれます。例として、ピアnのfingerテーブルの最初のエントリには、ピアnからのコードリングの途中にピアが含まれています。 fingerテーブルの目的は、検索を高速化することです。
n.id: In this document, this abbreviation is used to refer to the Node-ID of peer n.
n.id：このドキュメントでは、この省略形はピアnのノードIDを参照するために使用されます。
O(g(n)): Informally, saying that some equation f(n) = O(g(n)) means that f(n) is less than some constant multiple of g(n). For the formal definition, please refer to [Weiss1998].
O（g（n））：非公式に、いくつかの方程式f（n）= O（g（n））は、f（n）がg（n）の定数倍より小さいことを意味します。正式な定義については、[Weiss1998]を参照してください。
Omega(g(n)): Informally, saying that some equation f(n) = Omega(g(n)) means that f(n) is more than some constant multiple of g(n). For the formal definition, please refer to [Weiss1998].
Omega（g（n））：非公式に、ある式f（n）= Omega（g（n））は、f（n）がg（n）の定数倍よりも大きいことを意味します。正式な定義については、[Weiss1998]を参照してください。
Percentile: The Pth (0<=P<=100) percentile of N values arranged in ascending order is obtained by first calculating the (ordinal) rank n=(P/100)*N, rounding the result to the nearest integer and then taking the value corresponding to that rank.
パーセンタイル：昇順で配置されたN個の値のPth（0 <= P <= 100）パーセンタイルは、最初に（序数）ランクn =（P / 100）* Nを計算し、結果を最も近い整数に丸め、次にそのランクに対応する値を取ります。
Predecessor List: A data structure containing the first r predecessors of a peer on the Chord ring.
先行リスト：コードリング上のピアの最初のr個の先行を含むデータ構造。
Successor List: A data structure containing the first r successors of a peer on the Chord ring.
サクセサリスト：コードリング上のピアの最初のrサクセサを含むデータ構造。
Neighborhood Set: A term used to refer to the set of peers included in the successor and predecessor lists of a given peer.
Neighborhood Set：特定のピアの後続および先行リストに含まれるピアのセットを指すために使用される用語。
Routing Table: Contents of a given peer's routing table include the set of peers that the peer can use to route overlay messages. The routing table is made up of the finger table, successor list, and predecessor list.
ルーティングテーブル：特定のピアのルーティングテーブルの内容には、ピアがオーバーレイメッセージのルーティングに使用できるピアのセットが含まれます。ルーティングテーブルは、fingerテーブル、後続リスト、および先行リストで構成されています。
DHTs use stabilization routines to counter the undesirable effects of churn on routing. The purpose of stabilization is to keep the routing information of each peer in the overlay consistent with the constantly changing overlay topology. There are two alternative approaches to stabilization: periodic and reactive [Rhea2004]. Periodic stabilization can either use a fixed stabilization rate or calculate the stabilization rate in an adaptive fashion.
DHTは、安定化ルーチンを使用して、ルーティングに対するチャーンの望ましくない影響に対抗します。安定化の目的は、オーバーレイの各ピアのルーティング情報を、絶えず変化するオーバーレイトポロジーと一致させることです。安定化には2つの代替アプローチがあります：周期的およびリアクティブ[Rhea2004]。定期的な安定化では、固定安定化率を使用するか、適応方式で安定化率を計算できます。
In reactive stabilization, a peer reacts to the loss of a peer in its neighborhood set or to the appearance of a new peer that should be added to its neighborhood set by sending a copy of its neighbor table to all peers in the neighborhood set. Periodic recovery, in contrast, takes place independently of changes in the neighborhood set. In periodic recovery, a peer periodically shares its neighborhood set with each or a subset of the members of that set.
リアクティブ安定化では、ピアは、ネイバーセットのピアの損失、またはネイバーテーブルのコピーをネイバーセットのすべてのピアに送信することにより、ネイバーセットに追加する必要のある新しいピアの出現に反応します。対照的に、定期的な回復は、近隣セットの変化とは無関係に行われます。定期的な回復では、ピアは近隣セットをそのセットのメンバーのそれぞれまたはサブセットと定期的に共有します。
The chord-reload algorithm [RFC6940] supports both reactive and periodic stabilization. It has been shown in [Rhea2004] that reactive stabilization works well for small neighborhood sets (i.e., small overlays) and moderate churn. However, in large-scale (e.g., 1000 peers or more [Rhea2004]) or high-churn overlays, reactive stabilization runs the risk of creating a positive feedback cycle, which can eventually result in congestion collapse. In [Rhea2004], it is shown that a 1000-peer overlay under churn uses significantly less bandwidth and has lower latencies when periodic stabilization is used than when reactive stabilization is used. Although in the experiments carried out in [Rhea2004], reactive stabilization performed well when there was no churn, its bandwidth use was observed to jump dramatically under churn. At higher churn rates and larger scale overlays, periodic stabilization uses less bandwidth and the resulting lower contention for the network leads to lower latencies. For this reason, most DHTs, such as CAN [CAN], Chord [Chord], Pastry [Pastry], and Bamboo [Rhea2004], use periodic stabilization [Ghinita2006]. As an example, the first version of Bamboo used reactive stabilization, which caused Bamboo to suffer from degradation in performance under churn. To fix this problem, Bamboo was modified to use periodic stabilization.
和音リロードアルゴリズム[RFC6940]は、リアクティブと定期的な安定化の両方をサポートしています。 [Rhea2004]では、小さな近傍セット（つまり、小さなオーバーレイ）と中程度のチャーンで反応安定化がうまく機能することが示されています。ただし、大規模なオーバーレイ（例：1000ピア以上[Rhea2004]）またはチャーンの多いオーバーレイでは、リアクティブな安定化により正のフィードバックサイクルが発生するリスクが生じ、最終的には輻輳の崩壊を引き起こす可能性があります。 [Rhea2004]では、チャーン下の1000ピアオーバーレイの帯域幅が大幅に減少し、反応型安定化を使用した場合よりも定期的安定化を使用した場合の方が遅延が少ないことが示されています。 [Rhea2004]で実施された実験では、チャーンがないときに反応安定化がうまく機能しましたが、その帯域幅の使用はチャーンの下で劇的にジャンプすることが観察されました。チャーン率が高く、オーバーレイが大規模な場合、定期的な安定化では使用する帯域幅が少なくなり、その結果、ネットワークの競合が減少するため、待機時間が短くなります。このため、CAN [CAN]、Chord [Chord]、Pastry [Pastry]、Bamboo [Rhea2004]などのほとんどのDHTは、定期的な安定化[Ghinita2006]を使用しています。一例として、Bambooの最初のバージョンは反応安定化を使用していたため、チャーン時にBambooのパフォーマンスが低下しました。この問題を修正するために、Bambooは定期的な安定化を使用するように変更されました。
In Chord, periodic stabilization is typically done both for successors and fingers. An alternative strategy is analyzed in [Krishnamurthy2008]. In this strategy, called the "correction-on-change maintenance strategy", a peer periodically stabilizes its successors but does not do so for its fingers. Instead, finger pointers are stabilized in a reactive fashion. The results obtained in [Krishnamurthy2008] imply that although the correction-on-change strategy works well when churn is low, periodic stabilization outperforms the correction-on-change strategy when churn is high.
コードでは、定期的な安定化は通常、後継者と指の両方に対して行われます。 [Krishnamurthy2008]では、代替戦略が分析されています。 「変更時の修正メンテナンス戦略」と呼ばれるこの戦略では、ピアは後継者を定期的に安定させますが、指に対しては行いません。代わりに、指のポインターは反応的に安定します。 [Krishnamurthy2008]で得られた結果は、チャーンが低い場合は変更時修正戦略が適切に機能しますが、チャーンが高い場合は定期的な安定化が変更時修正戦略よりも優れていることを意味します。
When periodic stabilization is used, one faces the problem of selecting an appropriate execution rate for the stabilization procedure. If the execution rate of periodic stabilization is high, changes in the system can be quickly detected, but at the disadvantage of increased communication overhead. Alternatively, if the stabilization rate is low and the churn rate is high, routing tables become inaccurate and DHT performance deteriorates. Thus, the problem is setting the parameters so that the overlay achieves the desired reliability and performance even in challenging conditions, such as under heavy churn. This naturally results in high cost during periods when the churn level is lower than expected, or alternatively, poor performance or even network partitioning in worse than expected conditions.
定期的な安定化を使用する場合、安定化手順に適切な実行レートを選択するという問題に直面します。定期的な安定化の実行率が高いと、システムの変化をすばやく検出できますが、通信オーバーヘッドが大きくなるというデメリットがあります。または、安定化率が低く、解約率が高い場合、ルーティングテーブルが不正確になり、DHTのパフォーマンスが低下します。したがって、問題は、過大なチャーンなどの厳しい条件でもオーバーレイが望ましい信頼性とパフォーマンスを実現するようにパラメーターを設定することです。これは当然、チャーンレベルが予想よりも低い期間に高コストになるか、パフォーマンスが低下したり、予想よりも悪い状況でネットワークのパーティション分割が発生したりします。
In addition to selecting an appropriate stabilization interval, regardless of whether or not periodic stabilization is used, an appropriate size needs to be selected for the neighborhood set and for the finger table.
適切な安定化間隔を選択することに加えて、定期的な安定化を使用するかどうかに関係なく、近傍セットとフィンガーテーブルに適切なサイズを選択する必要があります。
The current approach is to configure overlays statically. This works in situations where perfect information about the future is available. In situations where the operating conditions of the network are known in advance and remain static throughout the lifetime of the system, it is possible to choose fixed optimal values for parameters such as stabilization rate, neighborhood set size and routing table size. However, if the operating conditions (e.g., the size of the overlay and its churn rate) do not remain static but evolve with time, it is not possible to achieve both a low lookup failure rate and a low communication overhead by using fixed parameters [Ghinita2006].
現在のアプローチは、静的にオーバーレイを構成することです。これは、将来についての完全な情報が利用可能な状況で機能します。ネットワークの動作条件が事前にわかっており、システムのライフタイム全体を通じて静的である状況では、安定化率、近隣セットのサイズ、ルーティングテーブルのサイズなどのパラメーターに固定の最適値を選択できます。ただし、動作条件（たとえば、オーバーレイのサイズとそのチャーン率）が静的なままではなく、時間とともに変化する場合、固定パラメーターを使用して低いルックアップ失敗率と低い通信オーバーヘッドの両方を実現することはできません[ Ghinita2006]。
As an example, to configure the Chord DHT algorithm, one needs to select values for the following parameters: size of successor list, stabilization interval, and size of the finger table. To select an appropriate value for the stabilization interval, one needs to know the expected churn rate and overlay size. According to
例として、Chord DHTアルゴリズムを構成するには、次のパラメーターの値を選択する必要があります：サクセサーリストのサイズ、安定化間隔、およびフィンガーテーブルのサイズ。安定化間隔に適切な値を選択するには、予想されるチャーン率とオーバーレイサイズを知る必要があります。による
[Liben-Nowell2002], a Chord network in a ring-like state remains in a ring-like state as long as peers send Omega(square(log(N))) messages before N new peers join or N/2 peers fail. Thus, in a 500-peer overlay churning at a rate such that one peer joins and one peer leaves the network every 30 seconds, an appropriate stabilization interval would be on the order of 93 s. According to [Chord], the size of the successor list and finger table should be on the order of log(N). Already a successor list of a modest size (e.g., log2(N) or 2*log2(N), which is the successor list size used in [Chord]) makes it very unlikely that a peer will lose all of its successors, which would cause the Chord ring to become disconnected. Thus, in a 500-peer network each peer should maintain on the order of nine successors and fingers. However, if the churn rate doubles and the network size remains unchanged, the stabilization rate should double as well. That is, the appropriate maintenance interval would now be on the order of 46 s. On the other hand, if the churn rate becomes, e.g., six-fold and the size of the network grows to 2000 peers, on the order of 11 fingers and successors should be maintained and the stabilization interval should be on the order of 42 s. If one continued using the old values, this could result in inaccurate routing tables, network partitioning, and deteriorating performance.
[Liben-Nowell2002]、リングのような状態のChordネットワークは、ピアがOmega（square（log（N）））メッセージを送信してからN個の新しいピアが参加するか、N / 2個のピアが失敗するまで、リングのような状態のままです。したがって、1つのピアがネットワークに参加し、1つのピアが30秒ごとにネットワークを離れるような速度で500ピアのオーバーレイチャーニングでは、適切な安定化間隔は約93秒です。 [Chord]によると、サクセサリストとフィンガーテーブルのサイズはlog（N）のオーダーである必要があります。すでに適度なサイズのサクセサリスト（たとえば、[Chord]で使用されるサクセサリストサイズであるlog2（N）または2 * log2（N））により、ピアがサクセサのすべてを失うことはほとんどありません。コードリングが切断されます。したがって、500ピアネットワークでは、各ピアは9つのサクセサとフィンガーのオーダーを維持する必要があります。ただし、解約率が2倍になり、ネットワークサイズが変わらない場合、安定化率も2倍になるはずです。つまり、適切なメンテナンス間隔は46秒程度になります。一方、解約率が、たとえば6倍になり、ネットワークのサイズが2000ピアに拡大した場合、11の指と後続ノードのオーダーが維持され、安定化間隔は42秒のオーダーである必要があります。 。古い値を使い続けると、ルーティングテーブルが不正確になり、ネットワークが分割され、パフォーマンスが低下する可能性があります。
A self-tuning DHT takes into consideration the continuous evolution of network conditions and adapts to them. In a self-tuning DHT, each peer collects statistical data about the network and dynamically adjusts its stabilization rate, neighborhood set size, and finger table size based on the analysis of the data [Ghinita2006]. Reference [Mahajan2003] shows that by using self-tuning, it is possible to achieve high reliability and performance even in adverse conditions with low maintenance cost. Adaptive stabilization has been shown to outperform periodic stabilization in terms of both lookup failures and communication overhead [Ghinita2006].
セルフチューニングDHTは、ネットワーク状態の継続的な変化を考慮し、それらに適応します。セルフチューニングDHTでは、各ピアがネットワークに関する統計データを収集し、データの分析に基づいて、安定化率、近隣セットのサイズ、およびフィンガーテーブルのサイズを動的に調整します[Ghinita2006]。参考文献[Mahajan2003]は、セルフチューニングを使用することにより、低いメンテナンスコストで悪条件でも高い信頼性とパフォーマンスを実現できることを示しています。適応安定化は、ルックアップの失敗と通信オーバーヘッドの両方に関して、定期的な安定化よりも優れていることが示されています[Ghinita2006]。
Chord [Chord] is a structured P2P algorithm that uses consistent hashing to build a DHT out of several independent peers. Consistent hashing assigns each peer and resource a fixed-length identifier. Peers use SHA-1 as the base hash function to generate the identifiers. As specified in RELOAD base [RFC6940], the length of the identifiers is numBitsInNodeId=128 bits. The identifiers are ordered on an identifier circle of size 2^numBitsInNodeId. On the identifier circle, key k is assigned to the first peer whose identifier equals or follows the identifier of k in the identifier space. The identifier circle is called the Chord ring.
Chord [Chord]は、一貫したハッシュを使用して、複数の独立したピアからDHTを構築する構造化P2Pアルゴリズムです。一貫性のあるハッシュにより、各ピアとリソースに固定長の識別子が割り当てられます。ピアは、識別子を生成するための基本ハッシュ関数としてSHA-1を使用します。 RELOADベース[RFC6940]で指定されているように、識別子の長さはnumBitsInNodeId = 128ビットです。識別子は、サイズ2 ^ numBitsInNodeIdの識別子円で並べられます。識別子サークルでは、鍵kは、識別子空間でkの識別子と等しいか、それに続く識別子を持つ最初のピアに割り当てられます。識別子円はコードリングと呼ばれます。
Different DHTs differ significantly in performance when bandwidth is limited. It has been shown that when compared to other DHTs, the advantages of Chord include that it uses bandwidth efficiently and can achieve low lookup latencies at little cost [Li2004].
帯域幅が制限されている場合、DHTによってパフォーマンスが大きく異なります。他のDHTと比較した場合、Chordの利点には、帯域幅を効率的に使用し、少ないコストで低いルックアップレイテンシを実現できることが含まれています[Li2004]。
A simple lookup mechanism could be implemented on a Chord ring by requiring each peer to only know how to contact its current successor on the identifier circle. Queries for a given identifier could then be passed around the circle via the successor pointers until they encounter the first peer whose identifier is equal to or larger than the desired identifier. Such a lookup scheme uses a number of messages that grows linearly with the number of peers. To reduce the cost of lookups, Chord maintains also additional routing information; each peer n maintains a data structure with up to numBitsInNodeId entries, called the finger table. The first entry in the finger table of peer n contains the peer halfway around the ring from peer n. The second entry contains the peer that is 1/4th of the way around, the third entry the peer that is 1/8th of the way around, etc. In other words, the ith entry in the finger table at peer n contains the identity of the first peer s that succeeds n by at least 2^(numBitsInNodeId-i) on the Chord ring. This peer is called the ith finger of peer n. The interval between two consecutive fingers is called a finger interval. The ith finger interval of peer n covers the range [n.id + 2^(numBitsInNodeId-i), n.id + 2^(numBitsInNodeId-i+1)) on the Chord ring. In an N-peer network, each peer maintains information about O(log(N)) other peers in its finger table. As an example, if N=100000, it is sufficient to maintain 17 fingers.
単純なルックアップメカニズムをコードリングに実装するには、IDサークルで現在の後続ノードに連絡する方法のみを各ピアに知ってもらう必要があります。次に、特定の識別子のクエリは、その識別子が目的の識別子以上の最初のピアに遭遇するまで、後続ポインタを介してサークル内を渡されます。このような検索スキームは、ピアの数に比例して増加するメッセージの数を使用します。ルックアップのコストを削減するために、Chordは追加のルーティング情報も保持します。各ピアnは、フィンガーテーブルと呼ばれるnumBitsInNodeIdエントリまでのデータ構造を維持します。ピアnのfingerテーブルの最初のエントリには、ピアnからのリングの途中のピアが含まれています。 2番目のエントリには、経路の1/4のピアが含まれ、3番目のエントリには、経路の1/8のピアなどが含まれます。つまり、ピアnのfingerテーブルのi番目のエントリにはIDが含まれます。 Chordリング上で少なくとも2 ^（numBitsInNodeId-i）だけnに続く最初のピアsの。このピアは、ピアnのi番目のフィンガーと呼ばれます。連続する2本の指の間隔を指間隔と呼びます。ピアnのi番目の指の間隔は、コードリングの範囲[n.id + 2 ^（numBitsInNodeId-i）、n.id + 2 ^（numBitsInNodeId-i + 1））をカバーします。 Nピアネットワークでは、各ピアは他のピアO（log（N））に関する情報をフィンガーテーブルに保持します。例として、N = 100000の場合、17本の指を維持するだけで十分です。
Chord needs all peers' successor pointers to be up to date in order to ensure that lookups produce correct results as the set of participating peers changes. To achieve this, peers run a stabilization protocol periodically in the background. The stabilization protocol of the original Chord algorithm uses two operations: successor stabilization and finger stabilization. However, the Chord algorithm of RELOAD base defines two additional stabilization components, as will be discussed below.
Chordは、参加するピアのセットが変更されたときにルックアップが正しい結果を生成することを保証するために、すべてのピアのサクセサーポインターを最新にする必要があります。これを実現するために、ピアはバックグラウンドで定期的に安定化プロトコルを実行します。オリジナルのコードアルゴリズムの安定化プロトコルは、後続の安定化と指の安定化の2つの操作を使用します。ただし、RELOADベースのコードアルゴリズムは、以下で説明するように、2つの追加の安定化コンポーネントを定義します。
To increase robustness in the event of peer failures, each Chord peer maintains a successor list of size r, containing the peer's first r successors. The benefit of successor lists is that if each peer fails independently with probability p, the probability that all r successors fail simultaneously is only p^r.
ピアに障害が発生した場合の堅牢性を高めるために、各Chordピアは、ピアの最初のr個の後続ノードを含む、サイズrの後続リストを維持します。サクセサリストの利点は、各ピアが確率pで独立して失敗した場合、すべてのrサクセサが同時に失敗する確率はp ^ rだけであることです。
The original Chord algorithm maintains only a single predecessor pointer. However, multiple predecessor pointers (i.e., a predecessor list) can be maintained to speed up recovery from predecessor failures. The routing table of a peer consists of the successor list, finger table, and predecessor list.
オリジナルのChordアルゴリズムは、単一の先行ポインターのみを維持します。ただし、複数の先行ポインター（つまり、先行リスト）を維持して、先行障害からのリカバリーを高速化できます。ピアのルーティングテーブルは、後続リスト、フィンガーテーブル、および先行リストで構成されています。
This section describes how the mandatory-to-implement chord-reload algorithm defined in RELOAD base [RFC6940] can be extended to support self-tuning.
このセクションでは、RELOADベース[RFC6940]で定義されているコードコードの再読み込みの必須アルゴリズムを拡張して、セルフチューニングをサポートする方法について説明します。
The chord-reload algorithm supports both reactive and periodic recovery strategies. When the self-tuning mechanisms defined in this document are used, the periodic recovery strategy is used. Further, chord-reload specifies that at least three predecessors and three successors need to be maintained. When the self-tuning mechanisms are used, the appropriate sizes of the successor list and predecessor list are determined in an adaptive fashion based on the estimated network size, as will be described in Section 6.
コード再ロードアルゴリズムは、リアクティブおよび定期的なリカバリ戦略の両方をサポートしています。このドキュメントで定義されているセルフチューニングメカニズムを使用する場合は、定期的なリカバリ戦略が使用されます。さらに、chord-reloadは、少なくとも3つの前任者と3つの後継者を維持する必要があることを指定しています。セルフチューニングメカニズムを使用する場合、セクション6で説明するように、後続リストと先行リストの適切なサイズは、推定ネットワークサイズに基づいて適応的に決定されます。
As specified in RELOAD base [RFC6940], each peer maintains a stabilization timer. When the stabilization timer fires, the peer restarts the timer and carries out the overlay stabilization routine. Overlay stabilization has four components in chord-reload:
RELOADベース[RFC6940]で指定されているように、各ピアは安定化タイマーを維持します。安定化タイマーが起動すると、ピアはタイマーを再起動し、オーバーレイ安定化ルーチンを実行します。オーバーレイの安定化には、コードのリロードに4つのコンポーネントがあります。
1. Update the neighbor table. We refer to this as "neighbor stabilization".
1. ネイバーテーブルを更新します。これを「近傍安定化」と呼びます。
2. Refreshing the finger table. We refer to this as "finger stabilization".
2. 指先をリフレッシュ。これを「指の安定化」と呼びます。
3. Adjusting finger table size.
3. フィンガーテーブルのサイズを調整しています。
4. Detecting partitioning. We refer to this as "strong stabilization".
4. パーティション分割を検出しています。これを「強力な安定化」と呼びます。
As specified in RELOAD base [RFC6940], a peer sends periodic messages as part of the neighbor stabilization, finger stabilization, and strong stabilization routines. In neighbor stabilization, a peer periodically sends an Update request to every peer in its connection table. The default time is every ten minutes. In finger stabilization, a peer periodically searches for new peers to include in its finger table. This time defaults to one hour. This document specifies how the neighbor stabilization and finger stabilization intervals can be determined in an adaptive fashion based on the operating conditions of the overlay. The subsections below describe how this document extends the four components of stabilization.
RELOADベース[RFC6940]で指定されているように、ピアはネイバーの安定化、指の安定化、および強力な安定化ルーチンの一部として定期的なメッセージを送信します。ネイバー安定化では、ピアは接続テーブル内のすべてのピアに定期的に更新要求を送信します。デフォルトの時間は10分ごとです。フィンガー安定化では、ピアは定期的に新しいピアを検索して、フィンガーテーブルに含めます。この時間のデフォルトは1時間です。このドキュメントでは、オーバーレイの動作条件に基づいて、近隣の安定化間隔と指の安定化間隔を適応的に決定する方法を指定します。以下のサブセクションでは、このドキュメントが安定化の4つのコンポーネントをどのように拡張するかについて説明します。
As described in RELOAD base [RFC6940], the neighbor and finger stabilization procedures are implemented using Update requests. RELOAD base defines three types of Update requests: 'peer_ready',
RELOADベース[RFC6940]で説明されているように、ネイバーとフィンガーの安定化手順は、更新リクエストを使用して実装されます。 RELOADベースは、3つのタイプの更新要求を定義します。「peer_ready」、
'neighbors', and 'full'. Regardless of the type, all Update requests include an 'uptime' field. The self-tuning extensions require information on the uptimes of peers in the routing table. The sender of an Update request includes its current uptime (in seconds) in the 'uptime' field. Regardless of the type, all Update requests MUST include an 'uptime' field.
'neighbors'、および 'full'。タイプに関係なく、すべての更新リクエストには「稼働時間」フィールドが含まれます。セルフチューニング拡張には、ルーティングテーブル内のピアの稼働時間に関する情報が必要です。更新リクエストの送信者は、現在の稼働時間（秒単位）を「稼働時間」フィールドに含めます。タイプに関係なく、すべての更新リクエストには「uptime」フィールドを含める必要があります。
When self-tuning is used, each peer decides independently the appropriate size for the successor list, predecessor list, and finger table. Thus, the 'predecessors', 'successors', and 'fingers' fields included in RELOAD Update requests are of variable length. As specified in RELOAD [RFC6940], variable-length fields are on the wire preceded by length bytes. In the case of the successor list, predecessor list, and finger table, there are two length bytes (allowing lengths up to 2^16-1). The number of NodeId structures included in each field can be calculated based on the length bytes since the size of a single NodeId structure is 16 bytes. If a peer receives more entries than fit into its successor list, predecessor list, or finger table, the peer MUST ignore the extra entries. A peer may also receive less entries than it currently has in its own data structure. In that case, it uses the received entries to update only a subset of the entries in its data structure. As an example, a peer that has a successor list of size 8 may receive a successor list of size 4 from its immediate successor. In that case, the received successor list can only be used to update the first few successors on the peer's successor list. The rest of the successors will remain intact.
セルフチューニングを使用する場合、各ピアは、後続リスト、先行リスト、およびフィンガーテーブルの適切なサイズを個別に決定します。したがって、RELOAD Updateリクエストに含まれる「predecessors」、「successors」、および「fingers」フィールドは可変長です。 RELOAD [RFC6940]で指定されているように、可変長フィールドは、長さバイトが先行するネットワーク上にあります。後続リスト、先行リスト、およびフィンガーテーブルの場合、2バイトの長さがあります（最大長は2 ^ 16-1です）。単一のNodeId構造体のサイズは16バイトであるため、各フィールドに含まれるNodeId構造体の数は長さバイトに基づいて計算できます。ピアが後続リスト、先行リスト、またはフィンガーテーブルに収まるよりも多くのエントリを受信する場合、ピアは余分なエントリを無視する必要があります。ピアは、それ自体のデータ構造で現在持っているよりも少ないエントリを受け取ることもあります。その場合、受信したエントリを使用して、データ構造内のエントリのサブセットのみを更新します。例として、サイズ8のサクセサリストを持つピアは、その直後のサクセサからサイズ4のサクセサリストを受信する場合があります。その場合、受信したサクセサリストは、ピアのサクセサリストの最初のいくつかのサクセサを更新するためにのみ使用できます。残りの後継者はそのまま残ります。
In the neighbor stabilization operation of chord-reload, a peer periodically sends an Update request to every peer in its connection table. In a small, low-churn overlay, the amount of traffic this process generates is typically acceptable. However, in a large-scale overlay churning at a moderate or high churn rate, the traffic load may no longer be acceptable since the size of the connection table is large and the stabilization interval relatively short. The self-tuning mechanisms described in this document are especially designed for overlays of the latter type. Therefore, when the self-tuning mechanisms are used, each peer only sends a periodic Update request to its first predecessor and first successor on the Chord ring; it MUST NOT send Update requests to others.
コードリロードのネイバー安定化操作では、ピアは接続テーブル内のすべてのピアに定期的に更新要求を送信します。小さなチャーンの少ないオーバーレイでは、このプロセスが生成するトラフィックの量は通常、許容範囲です。ただし、中程度または高いチャーン率での大規模なオーバーレイチャーニングでは、接続テーブルのサイズが大きく、安定化間隔が比較的短いため、トラフィック負荷が許容できなくなる可能性があります。このドキュメントで説明するセルフチューニングメカニズムは、特に後者のタイプのオーバーレイ用に設計されています。したがって、セルフチューニングメカニズムが使用されている場合、各ピアは定期的な更新要求を、コードリングの最初の先行ノードと最初の後続ノードにのみ送信します。他のユーザーに更新リクエストを送信してはなりません。
The neighbor stabilization routine is executed when the stabilization timer fires. To begin the neighbor stabilization routine, a peer sends an Update request to its first successor and its first predecessor. The type of the Update request MUST be 'neighbors'. The Update request includes the successor and predecessor lists of the sender. If a peer receiving such an Update request learns from the predecessor and successor lists included in the request that new peers can be included in its neighborhood set, it sends Attach requests to the new peers.
近傍安定化ルーチンは、安定化タイマーが作動したときに実行されます。ネイバー安定化ルーチンを開始するには、ピアが最初の後続ノードと最初の先行ノードに更新要求を送信します。更新リクエストのタイプは「ネイバー」である必要があります。更新リクエストには、送信者の後続リストと先行リストが含まれています。このような更新要求を受信するピアが、要求に含まれる先行リストと後続リストから、新しいピアを近隣セットに含めることができることを学習した場合、接続要求を新しいピアに送信します。
After a new peer has been added to the predecessor or successor list, an Update request of type 'peer_ready' is sent to the new peer. This allows the new peer to insert the sender into its neighborhood set.
新しいピアが先行リストまたは後続リストに追加された後、タイプ「peer_ready」の更新要求が新しいピアに送信されます。これにより、新しいピアは送信者を近隣セットに挿入できます。
Chord-reload specifies two alternative methods for searching for new peers to the finger table. Both of the alternatives can be used with the self-tuning extensions defined in this document.
Chord-reloadは、fingerテーブルの新しいピアを検索するための2つの代替方法を指定します。このドキュメントで定義されているセルフチューニング拡張機能では、どちらの方法も使用できます。
Immediately after a new peer has been added to the finger table, a Probe request is sent to the new peer to fetch its uptime. The 'requested_info' field of the Probe request MUST be set to contain the ProbeInformationType 'uptime' defined in RELOAD base [RFC6940].
新しいピアがfingerテーブルに追加された直後に、プローブ要求が新しいピアに送信され、稼働時間を取得します。プローブ要求の「requested_info」フィールドは、RELOADベース[RFC6940]で定義されているProbeInformationType「uptime」を含むように設定する必要があります。
The chord-reload algorithm defines how a peer can make sure that the finger table is appropriately sized to allow for efficient routing. Since the self-tuning mechanisms specified in this document produce a network size estimate, this estimate can be directly used to calculate the optimal size for the finger table. This mechanism is used instead of the one specified by chord-reload. A peer uses the network size estimate to determine whether it needs to adjust the size of its finger table each time when the stabilization timer fires. The way this is done is explained in Section 6.2.
コードリロードアルゴリズムは、ピアがフィンガーテーブルのサイズを適切に設定して、効率的なルーティングを可能にする方法を定義します。このドキュメントで指定されているセルフチューニングメカニズムはネットワークサイズの推定値を生成するため、この推定値を直接使用して、フィンガーテーブルの最適なサイズを計算できます。このメカニズムは、chord-reloadで指定されたメカニズムの代わりに使用されます。ピアは、ネットワークサイズの見積もりを使用して、安定化タイマーが起動するたびにフィンガーテーブルのサイズを調整する必要があるかどうかを判断します。これを行う方法については、セクション6.2で説明します。
This document does not require any changes to the mechanism chord-reload uses to detect network partitioning.
このドキュメントでは、chord-reloadがネットワークのパーティション分割を検出するために使用するメカニズムを変更する必要はありません。
As specified in RELOAD base [RFC6940], a leaving peer SHOULD send a Leave request to all members of its neighbor table prior to leaving the overlay. The 'overlay_specific_data' field MUST contain the ChordLeaveData structure. The Leave requests that are sent to successors contain the predecessor list of the leaving peer. The Leave requests that are sent to the predecessors contain the successor list of the leaving peer. If a given successor can identify better predecessors (that is, predecessors that are closer to it on the Chord ring than its existing predecessors) than are already included in its predecessor lists by investigating the predecessor list it receives from the leaving peer, it sends Attach requests to them. Similarly, if a given predecessor identifies better successors by investigating the successor list it receives from the leaving peer, it sends Attach requests to them.
RELOADベース[RFC6940]で指定されているように、離脱ピアは、オーバーレイを離脱する前に、ネイバーテーブルのすべてのメンバーに離脱リクエストを送信する必要があります（SHOULD）。 「overlay_specific_data」フィールドには、ChordLeaveData構造が含まれている必要があります。後続ノードに送信されるLeave要求には、離脱するピアの先行リストが含まれています。先行ノードに送信されるLeave要求には、離脱するピアの後続リストが含まれています。特定のサクセサが、離脱するピアから受信するプレデクサリストを調査することにより、そのプレデクサリストに既に含まれているものよりも優れたプレデクサ（つまり、既存のプレデセサよりもコードリング上でより近いプレデクサ）を識別できる場合、アタッチを送信します。それらへの要求。同様に、特定の先行ノードが、退出するピアから受信した後続リストを調査して、より優れた後続ノードを特定した場合、接続リクエストをそれらに送信します。
This section specifies how to determine an appropriate stabilization rate and routing table size in an adaptive fashion. The proposed mechanism is based on [Mahajan2003], [Liben-Nowell2002], and [Ghinita2006]. To calculate an appropriate stabilization rate, the values of three parameters must be estimated: overlay size N, failure rate U, and join rate L. To calculate an appropriate routing table size, the estimated network size N can be used. Peers in the overlay MUST recalculate the values of the parameters to self-tune the chord-reload algorithm at the end of each stabilization period before restarting the stabilization timer.
このセクションでは、適切な安定化率とルーティングテーブルのサイズを適応的に決定する方法を指定します。提案されたメカニズムは、[Mahajan2003]、[Liben-Nowell2002]、および[Ghinita2006]に基づいています。適切な安定化率を計算するには、オーバーレイサイズN、障害率U、および結合率Lの3つのパラメーターの値を推定する必要があります。適切なルーティングテーブルサイズを計算するには、推定ネットワークサイズNを使用できます。オーバーレイのピアは、安定化タイマーを再開する前に、各安定化期間の終わりにコード再ロードアルゴリズムを自動調整するために、パラメーターの値を再計算する必要があります。
Techniques for estimating the size of an overlay network have been proposed, for instance, in [Mahajan2003], [Horowitz2003], [Kostoulas2005], [Binzenhofer2006], and [Ghinita2006]. In Chord, the density of peer identifiers in the neighborhood set can be used to produce an estimate of the size of the overlay, N [Mahajan2003]. Since peer identifiers are picked randomly with uniform probability from the numBitsInNodeId-bit identifier space, the average distance between peer identifiers in the successor set is (2^numBitsInNodeId)/N.
オーバーレイネットワークのサイズを推定する手法は、たとえば[Mahajan2003]、[Horowitz2003]、[Kostoulas2005]、[Binzenhofer2006]、および[Ghinita2006]で提案されています。 Chordでは、近傍セット内のピア識別子の密度を使用して、オーバーレイのサイズNの推定値を生成できます[Mahajan2003]。ピア識別子はnumBitsInNodeIdビット識別子空間からランダムな確率でランダムに選択されるため、後続セット内のピア識別子間の平均距離は（2 ^ numBitsInNodeId）/ Nです。
To estimate the overlay network size, a peer computes the average inter-peer distance d between the successive peers starting from the most distant predecessor and ending to the most distant successor in the successor list. The estimated network size is calculated as:
オーバーレイネットワークのサイズを推定するために、ピアは、最も遠い先行ノードから始まり、後続リストの最も遠い後続ノードまで、連続するピア間の平均ピア間距離dを計算します。推定ネットワークサイズは次のように計算されます。
2^numBitsInNodeId
N = -------------------
d
This estimate has been found to be accurate within 15% of the real network size [Ghinita2006]. Of course, the size of the neighborhood set affects the accuracy of the estimate.
この推定値は、実際のネットワークサイズの15％以内で正確であることがわかっています[Ghinita2006]。もちろん、近傍セットのサイズは推定の精度に影響します。
During the join process, a joining peer fills its routing table by sending a series of Ping and Attach requests, as specified in RELOAD base [RFC6940]. Thus, a joining peer immediately has enough information at its disposal to calculate an estimate of the network size.
結合プロセス中に、結合するピアは、RELOADベース[RFC6940]で指定されているように、一連のPingおよびAttach要求を送信することによってルーティングテーブルを埋めます。したがって、参加ピアは、ネットワークサイズの推定値を計算するのに十分な情報をすぐに利用できます。
As specified in RELOAD base [RFC6940], the finger table must contain at least 16 entries. When the self-tuning mechanisms are used, the size of the finger table MUST be set to max(ceiling(log2(N)), 16) using the estimated network size N.
RELOADベース[RFC6940]で指定されているように、fingerテーブルには少なくとも16のエントリが含まれている必要があります。セルフチューニングメカニズムを使用する場合、フィンガーテーブルのサイズは、推定ネットワークサイズNを使用してmax（ceiling（log2（N））、16）に設定する必要があります。
The size of the successor list MUST be set to a maximum of ceiling(log2(N)). An implementation can place a lower limit on the size of the successor list. As an example, the implementation might require the size of the successor list to be always at least three.
後継者リストのサイズは、上限の上限（log2（N））に設定する必要があります。実装では、後続リストのサイズに下限を設定できます。例として、実装では、後続リストのサイズを常に少なくとも3にする必要がある場合があります。
The size of the predecessor list MUST be set to ceiling(log2(N)).
先行リストのサイズは、ceiling（log2（N））に設定する必要があります。
A typical approach is to assume that peers join the overlay according to a Poisson process with rate L and leave according to a Poisson process with rate parameter U [Mahajan2003]. The value of U can be estimated using peer failures in the finger table and neighborhood set [Mahajan2003]. If peers fail with rate U, a peer with M unique peer identifiers in its routing table should observe K failures in time K/(M*U). Every peer in the overlay maintains a history of the last K failures. The current time is inserted into the history when the peer joins the overlay. The estimate of U is calculated as:
典型的なアプローチは、ピアがレートLのポアソンプロセスに従ってオーバーレイに参加し、レートパラメータU [Mahajan2003]を持つポアソンプロセスに従って去ると想定することです。 Uの値は、フィンガーテーブルと近傍セットのピア障害を使用して推定できます[Mahajan2003]。ピアがレートUで失敗する場合、ルーティングテーブルにM個の一意のピア識別子を持つピアは、時間K /（M * U）でK回の失敗を観察する必要があります。オーバーレイのすべてのピアは、最後のK回の失敗の履歴を保持しています。ピアがオーバーレイに参加すると、現在の時刻が履歴に挿入されます。 Uの推定値は次のように計算されます。
k
U = --------,
M * Tk
where M is the number of unique peer identifiers in the routing table, Tk is the time between the first and the last failure in the history, and k is the number of failures in the history. If k is smaller than K, the estimate is computed as if there was a failure at the current time. It has been shown that an estimate calculated in a similar manner is accurate within 17% of the real value of U [Ghinita2006].
ここで、Mはルーティングテーブル内の一意のピア識別子の数、Tkは履歴内の最初と最後の障害の間の時間、kは履歴内の障害の数です。 kがKより小さい場合、推定値は現在の時点で障害があったかのように計算されます。同様の方法で計算された推定値は、Uの実際の値の17％以内で正確であることが示されています[Ghinita2006]。
The size of the failure history K affects the accuracy of the estimate of U. One can increase the accuracy by increasing K. However, this has the side effect of decreasing responsiveness to changes in the failure rate. On the other hand, a small history size may cause a peer to overreact each time a new failure occurs. In [Ghinita2006], K is set to 25% of the routing table size. Use of this value is RECOMMENDED.
故障履歴Kのサイズは、Uの推定の精度に影響を与えます。Kを増やすことで精度を上げることができます。ただし、これには、故障率の変化に対する応答性が低下するという副作用があります。一方、履歴サイズが小さいと、新しい障害が発生するたびにピアが過剰に反応する可能性があります。 [Ghinita2006]では、Kはルーティングテーブルサイズの25％に設定されています。この値の使用は推奨されています。
A new failure is inserted to the failure history in the following cases:
以下の場合、新しい障害が障害履歴に挿入されます。
1. A Leave request is received from a neighbor.
1. ネイバーから脱退要求を受信しました。
2. A peer fails to reply to a Ping request sent in the situation explained below. If no packets have been received on a connection during the past 2*Tr seconds (where Tr is the inactivity timer defined by Interactive Connectivity Establishment (ICE) [RFC5245]), a RELOAD Ping request MUST be sent to the remote peer. RELOAD mandates the use of Session Traversal Utilities for NAT (STUN) [RFC5389] for keepalives. STUN keepalives take the form of STUN Binding Indication transactions. As specified in ICE [RFC5245], a peer sends a STUN Binding Indication if there has been no packet sent on a connection for Tr seconds. Tr is configurable and has a default of 15 seconds. Although STUN Binding Indications do not generate a response, the fact that a peer has failed can be learned from the lack of packets (Binding Indications or application protocol packets) received from the peer. If the remote peer fails to reply to the Ping request, the sender should consider the remote peer to have failed.
2. ピアは、以下で説明する状況で送信されたPing要求に応答できません。過去2 * Tr秒（TrはInteractive Connectivity Establishment（ICE）[RFC5245]で定義された非アクティブタイマー）の間にパケットが接続で受信されなかった場合、RELOAD Ping要求をリモートピアに送信する必要があります。 RELOADは、キープアライブのためのNAT（STUN）[RFC5389]のセッショントラバーサルユーティリティの使用を義務付けています。 STUNキープアライブは、STUNバインディング表示トランザクションの形式をとります。 ICE [RFC5245]で指定されているように、接続でTr秒間パケットが送信されなかった場合、ピアはSTUNバインディング表示を送信します。 Trは構成可能で、デフォルトは15秒です。 STUN Binding Indicationsは応答を生成しませんが、ピアから受信したパケット（Binding Indicationsまたはアプリケーションプロトコルパケット）の欠如から、ピアが失敗したという事実を知ることができます。リモートピアがPing要求への応答に失敗した場合、送信者はリモートピアが失敗したと見なす必要があります。
As an alternative to relying on STUN keepalives to detect peer failure, a peer could send additional, frequent RELOAD messages to every peer in its connection table. These messages could be Update requests, in which case they would serve two purposes: detecting peer failure and stabilization. However, as the cost of this approach can be very high in terms of bandwidth consumption and traffic load, especially in large-scale overlays experiencing churn, its use is NOT RECOMMENDED.
ピアの障害を検出するためにSTUNキープアライブに依存する代わりに、ピアは接続テーブル内のすべてのピアに追加の頻繁なRELOADメッセージを送信できます。これらのメッセージは更新要求である可能性があり、その場合、ピアの障害の検出と安定化の2つの目的を果たします。ただし、このアプローチのコストは、帯域幅の消費とトラフィック負荷の点で非常に高くなる可能性があるため、特にチャーンが発生している大規模なオーバーレイでは、その使用は推奨されません。
Reference [Ghinita2006] proposes that a peer can estimate the join rate based on the uptime of the peers in its routing table. An increase in peer join rate will be reflected by a decrease in the average age of peers in the routing table. Thus, each peer maintained an array of the ages of the peers in its routing table sorted in increasing order. Using this information, an estimate of the global peer join rate L is calculated as:
参考資料[Ghinita2006]は、ピアがルーティングテーブルのピアの稼働時間に基づいて参加率を推定できることを提案しています。ピア結合率の増加は、ルーティングテーブル内のピアの平均経過時間の減少に反映されます。したがって、各ピアは、ルーティングテーブル内のピアの経過時間の配列を、昇順でソートして維持していました。この情報を使用して、グローバルピアの参加率Lの推定値は次のように計算されます。
N
L = ----------------------,
Ages[floor(rsize/2)]
where Ages is an array containing the ages of the peers in the routing table sorted in increasing order and rsize is the size of the routing table. It has been shown that the estimate obtained by using this method is accurate within 22% of the real join rate [Ghinita2006]. Of course, the size of the routing table affects the accuracy.
ここで、Agesは、ルーティングテーブル内のピアの経過時間を昇順で並べた配列で、rsizeはルーティングテーブルのサイズです。この方法を使用して得られた推定値は、実際の結合率の22％以内で正確であることが示されています[Ghinita2006]。もちろん、ルーティングテーブルのサイズは精度に影響します。
In order for this mechanism to work, peers need to exchange information about the time they have been present in the overlay. Peers receive the uptimes of their successors and predecessors during the stabilization operations since all Update requests carry uptime values. A joining peer learns the uptime of the admitting peer since it receives an Update from the admitting peer during the join procedure. Peers learn the uptimes of new fingers since they can fetch the uptime using a Probe request after having attached to the new finger.
このメカニズムが機能するためには、ピアがオーバーレイに存在していた時間に関する情報を交換する必要があります。すべての更新リクエストには稼働時間の値が含まれているため、安定化操作中にピアは後続ノードと先行ノードの稼働時間を受け取ります。参加ピアは、参加手順中に承認ピアから更新を受信するため、承認ピアの稼働時間を学習します。ピアは、新しいフィンガーに接続した後、Probeリクエストを使用して稼働時間を取得できるため、新しいフィンガーの稼働時間を学習します。
To improve the accuracy of network size, join rate, and leave rate estimates, peers share their estimates. When the stabilization timer fires, a peer selects number-of-peers-to-probe random peers from its finger table and send each of them a Probe request. The targets of Probe requests are selected from the finger table rather than from the neighbor table since neighbors are likely to make similar errors when calculating their estimates. The number-of-peers-to-probe is a new element in the overlay configuration document. It is defined in Section 7. Both the Probe request and the answer returned by the target peer MUST contain a new message extension whose MessageExtensionType is 'self_tuning_data'. This extension type is defined in Section 9.1. The 'extension_contents' field of the MessageExtension structure MUST contain a SelfTuningData structure:
ネットワークサイズ、参加率、および脱退率の見積もりの精度を向上させるために、ピアはそれぞれの見積もりを共有します。安定化タイマーが作動すると、ピアは、フィンガーテーブルからプローブするピアの数のランダムピアを選択し、それぞれにプローブ要求を送信します。ネイバーは推定値を計算するときに同様のエラーを起こす可能性が高いため、プローブリクエストのターゲットはネイバーテーブルからではなくフィンガーテーブルから選択されます。 number-of-peers-to-probeは、オーバーレイ設定ドキュメントの新しい要素です。セクション7で定義されています。ターゲットピアによって返されるプローブ要求と応答の両方に、MessageExtensionTypeが 'self_tuning_data'である新しいメッセージ拡張が含まれている必要があります。この拡張タイプはセクション9.1で定義されています。 MessageExtension構造の「extension_contents」フィールドには、SelfTuningData構造が含まれている必要があります。
struct {
uint32 network_size;
uint32 join_rate;
uint32 leave_rate;
} SelfTuningData;
The contents of the SelfTuningData structure are as follows:
SelfTuningData構造の内容は次のとおりです。
network_size
network_size
The latest network size estimate calculated by the sender.
送信者が計算した最新のネットワークサイズの見積もり。
join_rate
join_rate
The latest join rate estimate calculated by the sender.
送信者が計算した最新の参加率の見積もり。
leave_rate
leave_rate
The latest leave rate estimate calculated by the sender.
送信者が計算した最新の休暇率の見積もり。
The join and leave rates are expressed as joins or failures per 24 hours. As an example, if the global join rate estimate a peer has calculated is 0.123 peers/s, it would include in the 'join_rate' field the ceiling of the value 10627.2 (24*60*60*0.123 = 10627.2), that is, the value 10628.
参加率と離脱率は、24時間あたりの参加または失敗として表されます。例として、ピアが計算したグローバル参加率の推定値が0.123ピア/秒の場合、「join_rate」フィールドに値10627.2の上限が含まれます（24 * 60 * 60 * 0.123 = 10627.2）。つまり、値10628。
The 'type' field of the MessageExtension structure MUST be set to contain the value 'self_tuning_data'. The 'critical' field of the structure MUST be set to False.
MessageExtension構造体の「type」フィールドは、値「self_tuning_data」を含むように設定する必要があります。構造の 'critical'フィールドはFalseに設定する必要があります。
A peer stores all estimates it receives in Probe requests and answers during a stabilization interval. When the stabilization timer fires, the peer calculates the estimates to be used during the next stabilization interval by taking the 75th percentile (i.e., third quartile) of a data set containing its own estimate and the received estimates.
ピアは、安定化間隔中に受信したすべての推定値をプローブ要求と応答に格納します。安定化タイマーが作動すると、ピアは、自身の推定値と受信した推定値を含むデータセットの75パーセンタイル（つまり、第3四分位数）を取得することにより、次の安定化間隔中に使用される推定値を計算します。
The default value for number-of-peers-to-probe is 4. This default value is recommended to allow a peer to receive a sufficiently large set of estimates from other peers. With a value of 4, a peer receives four estimates in Probe answers. On the average, each peer also receives four Probe requests each carrying an estimate. Thus, on the average, each peer has nine estimates (including its own) that it can use at the end of the stabilization interval. A value smaller than 4 is NOT RECOMMENDED to keep the number of received estimates high enough. As an example, if the value were 2, there would be peers in the overlay that would only receive two estimates during a stabilization interval. Such peers would only have three estimates available at the end of the interval, which may not be reliable enough since even a single exceptionally high or low estimate can have a large impact.
number-of-peers-to-probeのデフォルト値は4です。このデフォルト値は、ピアが他のピアから十分に大きな推定セットを受信できるようにするために推奨されています。値が4の場合、ピアはプローブ応答で4つの見積もりを受け取ります。平均して、各ピアは4つのプローブ要求も受信し、それぞれが推定値を伝達します。したがって、平均して、各ピアには、安定化間隔の最後に使用できる9つの推定値（自身のものを含む）があります。受け取った推定値の数を十分に高く保つために、4より小さい値は推奨されません。例として、値が2の場合、安定化間隔中に2つの推定のみを受信するピアがオーバーレイに存在します。そのようなピアは、間隔の終わりに3つの推定しか利用できません。単一の非常に高いまたは低い推定でも大きな影響を与える可能性があるため、十分に信頼できない場合があります。
According to [Liben-Nowell2002], a Chord network in a ring-like state remains in a ring-like state as long as peers send Omega(square(log(N))) messages before N new peers join or N/2 peers fail. We can use the estimate of peer failure rate, U, to calculate the time Tf in which N/2 peers fail:
[Liben-Nowell2002]によれば、N個の新しいピアが参加するかN / 2ピアになる前にピアがOmega（square（log（N）））メッセージを送信する限り、リング状のChordネットワークはリング状の状態のままです。不合格。ピアの故障率Uの推定値を使用して、N / 2のピアが故障する時間Tfを計算できます。
1
Tf = ------
2*U
Based on this estimate, a stabilization interval Tstab-1 is calculated as:
この推定に基づいて、安定化間隔Tstab-1は次のように計算されます。
Tf
Tstab-1 = -----------------
square(log2(N))
On the other hand, the estimated join rate L can be used to calculate the time in which N new peers join the overlay. Based on the estimate of L, a stabilization interval Tstab-2 is calculated as:
一方、推定参加率Lは、N個の新しいピアがオーバーレイに参加する時間を計算するために使用できます。 Lの推定に基づいて、安定化間隔Tstab-2は次のように計算されます。
N
Tstab-2 = ---------------------
L * square(log2(N))
Finally, the actual stabilization interval Tstab that is used can be obtained by taking the minimum of Tstab-1 and Tstab-2.
最後に、使用される実際の安定化間隔Tstabは、Tstab-1とTstab-2の最小値を取ることで取得できます。
The results obtained in [Maenpaa2009] indicate that making the stabilization interval too small has the effect of making the overlay less stable (e.g., in terms of detected loops and path failures). Thus, a lower limit should be used for the stabilization period. Based on the results in [Maenpaa2009], a lower limit of 15 s is RECOMMENDED, since using a stabilization period smaller than this will with a high probability cause too much traffic in the overlay.
[Maenpaa2009]で得られた結果は、安定化間隔を小さくしすぎると、オーバーレイの安定性が低下することを示しています（たとえば、検出されたループとパスの障害に関して）。したがって、安定化期間には下限を使用する必要があります。 [Maenpaa2009]の結果に基づいて、15秒の下限をお勧めします。これよりも短い安定化期間を使用すると、高い確率でオーバーレイのトラフィックが多すぎるためです。
This document extends the RELOAD overlay configuration document by adding one new element, "number-of-peers-to-probe", inside each "configuration" element.
このドキュメントは、RELOADオーバーレイ設定ドキュメントを拡張して、各「設定」要素内に「number-of-peers-to-probe」という1つの新しい要素を追加します。
self-tuning:number-of-peers-to-probe: The number of fingers to which Probe requests are sent to obtain their network size, join rate, and leave rate estimates. The default value is 4.
self-tuning：number-of-peers-to-probe：ネットワークサイズ、参加率、および脱退率の見積もりを取得するためにプローブ要求が送信されるフィンガーの数。デフォルト値は4です。
The RELAX NG grammar for this element is:
この要素のRELAX NG文法は次のとおりです。
namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning"
parameter &= element self-tuning:number-of-peers-to-probe {
xsd:unsignedInt }?
This namespace is added into the <mandatory-extension> element in the overlay configuration file.
この名前空間は、オーバーレイ構成ファイルの<mandatory-extension>要素に追加されます。
In the same way as malicious or compromised peers implementing the RELOAD base protocol [RFC6940] can advertise false network metrics or distribute false routing table information for instance in RELOAD Update messages, malicious peers implementing this specification may share false join rate, leave rate, and network size estimates. For such attacks, the same security concerns apply as in the RELOAD base specification. In addition, as long as the amount of malicious peers in the overlay remains modest, the statistical mechanisms applied in Section 6.5 (i.e., the use of 75th percentiles) to process the shared estimates a peer obtains help ensure that estimates that are clearly different from (i.e., larger or smaller than) other received estimates will not significantly influence the process of adapting the stabilization interval and routing table size. However, it should be noted that if an attacker is able to impersonate a high number of other peers in the overlay in strategic locations, it may be able to send a high enough number of false estimates to a victim and therefore influence the victim's choice of a stabilization interval.
RELOAD基本プロトコル[RFC6940]を実装する悪意のあるまたは侵害されたピアが、誤ったネットワークメトリックをアドバタイズしたり、たとえばRELOAD Updateメッセージで誤ったルーティングテーブル情報を配布したりするのと同様に、この仕様を実装した悪意のあるピアは、誤った参加率、脱退率、ネットワークサイズの見積もり。このような攻撃については、RELOAD基本仕様と同じセキュリティ上の懸念が適用されます。さらに、オーバーレイ内の悪意のあるピアの量が適度である限り、ピアが取得する共有推定値を処理するためにセクション6.5で適用される統計メカニズム（つまり、75パーセンタイルの使用）は、 （つまり、他の推定値よりも大きいまたは小さい）は、安定化間隔とルーティングテーブルのサイズを適応させるプロセスに大きな影響を与えません。ただし、攻撃者が戦略的な場所のオーバーレイで他の多数のピアを偽装できる場合、被害者に十分な数の誤った推定値を送信できるため、被害者の選択に影響を与える可能性があることに注意してください安定化間隔。
This document introduces one additional extension to the "RELOAD Extensions Registry":
このドキュメントでは、「RELOAD Extensions Registry」に追加の拡張機能を1つ紹介します。
+------------------+-------+---------------+
| Extension Name | Code | Specification |
+------------------+-------+---------------+
| self_tuning_data | 0x3 | RFC 7363 |
+------------------+-------+---------------+
The contents of the extension are defined in Section 6.5.
拡張の内容はセクション6.5で定義されています。
This document introduces one additional overlay algorithm type to the "RELOAD Overlay Algorithm Types" registry:
このドキュメントでは、「RELOADオーバーレイアルゴリズムタイプ」レジストリに1つの追加のオーバーレイアルゴリズムタイプを紹介しています。
+-------------------+-----------+
| Algorithm Name | Reference |
+-------------------+-----------+
| CHORD-SELF-TUNING | RFC 7363 |
+-------------------+-----------+
This document registers one new URI for the self-tuning namespace in the "ns" subregistry of the IETF XML registry defined in [RFC3688].
このドキュメントでは、[RFC3688]で定義されているIETF XMLレジストリの「ns」サブレジストリに、セルフチューニング名前空間の新しいURIを1つ登録しています。
URI: urn:ietf:params:xml:ns:p2p:self-tuning
Registrant Contact: The IESG
登録者の連絡先：IESG
XML: N/A, the requested URI is an XML namespace
XML：N / A、リクエストされたURIはXML名前空間です
The authors would like to thank Jani Hautakorpi for his contributions to the document. The authors would also like to thank Carlos Bernardos, Martin Durst, Alissa Cooper, Tobias Gondrom, and Barry Leiba for their comments on the document.
著者は文書への彼の貢献のためにJani Hautakorpiに感謝したいと思います。この文書に関するコメントを提供してくれたCarlos Bernardos、Martin Durst、Alissa Cooper、Tobias Gondrom、Barry Leibaにも感謝します。
[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月。
[RFC5245] Rosenberg, J., "Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/Answer Protocols", RFC 5245, April 2010.
[RFC5245] Rosenberg、J。、「Interactive Connectivity Establishment（ICE）：A Protocol for Network Address Translator（NAT）Traversal for Offer / Answer Protocols」、RFC 5245、2010年4月。
[RFC5389] Rosenberg, J., Mahy, R., Matthews, P., and D. Wing, "Session Traversal Utilities for NAT (STUN)", RFC 5389, October 2008.
[RFC5389] Rosenberg、J.、Mahy、R.、Matthews、P。、およびD. Wing、「NAT用セッショントラバーサルユーティリティ（STUN）」、RFC 5389、2008年10月。
[RFC6940] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) Base Protocol", RFC 6940, January 2014.
[RFC6940] Jennings、C.、Lowekamp、B.、Rescorla、E.、Baset、S。、およびH. Schulzrinne、「REsource LOcation And Discovery（RELOAD）Base Protocol」、RFC 6940、2014年1月。
[Binzenhofer2006] Binzenhofer, A., Kunzmann, G., and R. Henjes, "A Scalable Algorithm to Monitor Chord-Based P2P Systems at Runtime", In Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1-8, April 2006.
[Binzenhofer2006] Binzenhofer、A.、Kunzmann、G。、およびR. Henjes、「実行時にコードベースのP2Pシステムを監視するスケーラブルなアルゴリズム」、第20回IEEE国際並列および分散処理シンポジウム（IPDPS）議事録、pp 。2006年4月1〜8日。
[CAN] Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S. Schenker, "A Scalable Content-Addressable Network", In Proceedings of the 2001 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications, pp. 161-172, August 2001.
[CAN] Ratnasamy、S.、Francis、P.、Handley、M.、Karp、R.、and S. Schenker、 "A Scalable Content-Addressable Network"、Proceedings of the 2001 Conference on Applications、Technologies、Architectures andコンピュータ通信のプロトコル、pp。161-172、2001年8月。
[Chord] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", IEEE/ACM Transactions on Networking, Volume 11, Issue 1, pp. 17-32, February 2003.
[コード] Stoica、I.、Morris、R.、Liben-Nowell、D.、Karger、D.、Kaashoek、M.、Dabek、F。、およびH. Balakrishnan、「コード：スケーラブルなピアツーピアインターネットアプリケーションのルックアップサービス」、IEEE / ACM Transactions on Networking、Volume 11、Issue 1、17-32ページ、2003年2月。
[Ghinita2006] Ghinita, G. and Y. Teo, "An Adaptive Stabilization Framework for Distributed Hash Tables", In Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 29-38, April 2006.
[Ghinita2006] Ghinita、G。およびY. Teo、「分散ハッシュテーブルの適応安定化フレームワーク」、第20回IEEE国際並列および分散処理シンポジウム（IPDPS）の議事録、pp。29-38、2006年4月。
[Horowitz2003] Horowitz, K. and D. Malkhi, "Estimating Network Size from Local Information", Information Processing Letters, Volume 88, Issue 5, pp. 237-243, December 2003.
[Horowitz2003] Horowitz、K.およびD. Malkhi、「ローカル情報からのネットワークサイズの推定」、情報処理レター、88巻、5号、237-243ページ、2003年12月。
[Kostoulas2005] Kostoulas, D., Psaltoulis, D., Gupta, I., Birman, K., and A. Demers, "Decentralized Schemes for Size Estimation in Large and Dynamic Groups", In Proceedings of the 4th IEEE International Symposium on Network Computing and Applications, pp. 41-48, July 2005.
[Kostoulas2005] Kostoulas、D.、Psaltoulis、D.、Gupta、I.、Birman、K。、およびA. Demers、「大規模で動的なグループにおけるサイズ推定のための分散型スキーム」、第4回IEEE国際シンポジウムの議事録ネットワークコンピューティングとアプリケーション、pp。41-48、2005年7月。
[Krishnamurthy2008] Krishnamurthy, S., El-Ansary, S., Aurell, E., and S. Haridi, "Comparing Maintenance Strategies for Overlays", In Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing, pp. 473-482, February 2008.
[Krishnamurthy2008] Krishnamurthy、S.、El-Ansary、S.、Aurell、E.、and S. Haridi、 "Comparing Maintenance Strategies for Overlays"、Proceedings in the 16th Euromicro Conference on Parallel、Distributed and Network-Based Processing、 pp.473-482、2008年2月。
[Li2004] Li, J., Strinbling, J., Gil, T., Morris, R., and M. Kaashoek, "Comparing the Performance of Distributed Hash Tables Under Churn", Peer-to-Peer Systems III, Volume 3279 of Lecture Notes in Computer Science, Springer, pp. 87-99, February 2005.
[Li2004] Li、J.、Strinbling、J.、Gil、T.、Morris、R.、and M. Kaashoek、 "Comparing Performance of Distributed Hash Tables under Churn"、Peer-to-Peer Systems III、Volume 3279コンピュータサイエンスの講義ノート、Springer、pp.87-99、2005年2月。
[Liben-Nowell2002] Liben-Nowell, D., Balakrishnan, H., and D. Karger, "Observations on the Dynamic Evolution of Peer-to-Peer Networks", In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), pp. 22-33, March 2002.
[Liben-Nowell2002] Liben-Nowell、D.、Balakrishnan、H.、and D. Karger、 "Observations of the Dynamic Evolution of Peer-to-Peer Networks"、Proceedings in the 1st International Workshop on Peer-to-Peerシステム（IPTPS）、22-33ページ、2002年3月。
[Maenpaa2009] Maenpaa, J. and G. Camarillo, "A Study on Maintenance Operations in a Chord-Based Peer-to-Peer Session Initiation Protocol Overlay Network", In Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1-9, May 2009.
[Maenpaa2009] Maenpaa、J。およびG. Camarillo、「コードベースのピアツーピアセッション開始プロトコルオーバーレイネットワークにおけるメンテナンス操作に関する研究」、第23回IEEE国際並列および分散処理シンポジウム（IPDPS）のプロシーディングス、pp。1-9、2009年5月。
[Mahajan2003] Mahajan, R., Castro, M., and A. Rowstron, "Controlling the Cost of Reliability in Peer-to-Peer Overlays", In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS), pp. 21-32, February 2003.
[Mahajan2003] Mahajan、R.、Castro、M。、およびA. Rowstron、「ピアツーピアオーバーレイの信頼性のコストの制御」、ピアツーピアシステムに関する第2回国際ワークショップ（IPTPS）の議事録、pp。21-32、2003年2月。
[Pastry] Rowstron, A. and P. Druschel, "Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems", In Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms, pp. 329-350, November 2001.
[Pastry] Rowstron、A。およびP. Druschel、「Pastry：大規模なピアツーピアシステムのためのスケーラブルな分散オブジェクトの場所とルーティング」、分散システムプラットフォームに関するIFIP / ACM国際会議の議事録、pp。 329-350、2001年11月。
[RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, January 2004.
[RFC3688] Mealling M。、「The IETF XML Registry」、BCP 81、RFC 3688、2004年1月。
[Rhea2004] Rhea, S., Geels, D., Roscoe, T., and J. Kubiatowicz, "Handling Churn in a DHT", In Proceedings of the USENIX Annual Technical Conference, pp. 127-140, June 2004.
[Rhea2004] Rhea、S.、Geels、D.、Roscoe、T。、およびJ. Kubiatowicz、「DHTにおけるチャーンの処理」、USENIX年次技術会議の議事録、pp。127-140、2004年6月。
[Weiss1998] Weiss, M., "Data Structures and Algorithm Analysis in C++", Addison-Wesley Longman Publishing Co., Inc., 2nd Edition, ISBN 0201361221, 1998.
[Weiss1998] Weiss、M。、「C ++でのデータ構造とアルゴリズム分析」、Addison-Wesley Longman Publishing Co.、Inc.、第2版、ISBN 0201361221、1998年。
Authors' Addresses
著者のアドレス
Jouni Maenpaa Ericsson Hirsalantie 11 Jorvas 02420 Finland
Jouni Maenpaa Ericsson Hirsalantie 11 Jorvas 02420フィンランド
EMail: Jouni.Maenpaa@ericsson.com
Gonzalo Camarillo Ericsson Hirsalantie 11 Jorvas 02420 Finland
Gonzalo Camarillo Ericsson Hirsalantie 11 Jorvas 02420フィンランド
EMail: Gonzalo.Camarillo@ericsson.com