[要約] RFC 7374は、RELOADプロトコルのためのサービスディスカバリの使用方法を定義しています。その目的は、リソースの場所と発見を容易にすることです。
Internet Engineering Task Force (IETF) J. Maenpaa
Request for Comments: 7374 G. Camarillo
Category: Standards Track Ericsson
ISSN: 2070-1721 October 2014
Service Discovery Usage for REsource LOcation And Discovery (RELOAD)
リソースの検索と検出を再利用するためのサービス検出の使用法（RELOAD）
Abstract
概要
REsource LOcation And Discovery (RELOAD) does not define a generic service discovery mechanism as a part of the base protocol (RFC 6940). This document defines how the Recursive Distributed Rendezvous (ReDiR) service discovery mechanism can be applied to RELOAD overlays to provide a generic service discovery mechanism.
LOcation And Discovery（RELOAD）の再ソースは、基本プロトコル（RFC 6940）の一部として一般的なサービス検出メカニズムを定義していません。このドキュメントでは、Recursive Distributed Rendezvous（ReDiR）サービス検出メカニズムを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/rfc7374.
このドキュメントの現在のステータス、エラータ、およびフィードバックの提供方法に関する情報は、http：//www.rfc-editor.org/info/rfc7374で入手できます。
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 ....................................................3
2. Terminology .....................................................4
3. Introduction to ReDiR ...........................................5
4. Using ReDiR in a RELOAD Overlay Instance ........................8
4.1. Data Structure .............................................8
4.2. Selecting the Starting Level ...............................9
4.3. Service Provider Registration ..............................9
4.4. Refreshing Registrations ..................................10
4.5. Service Lookups ...........................................11
4.6. Removing Registrations ....................................13
5. Access Control Rules ...........................................13
6. REDIR Kind Definition ..........................................13
7. Examples .......................................................14
7.1. Service Registration ......................................14
7.2. Service Lookup ............................................16
8. Overlay Configuration Document Extension .......................16
9. Security Considerations ........................................17
10. IANA Considerations ...........................................17
10.1. Access Control Policies ..................................17
10.2. A New IETF XML Registry ..................................17
10.3. Data Kind-ID .............................................18
10.4. RELOAD Services Registry .................................18
11. References ....................................................19
11.1. Normative References .....................................19
11.2. Informative Reference ....................................19
Acknowledgments ...................................................19
Authors' Addresses ................................................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. Although RELOAD defines a service discovery mechanism specific to Traversal Using Relays around Network Address Translation (TURN), it does not define a generic service discovery mechanism as a part of the base protocol. This document defines how the Recursive Distributed Rendezvous (ReDiR) service discovery mechanism specified in [Redir] can be applied to RELOAD overlays.
REsource LOcation And Discovery（RELOAD）[RFC6940]は、オーバーレイネットワークを維持し、オーバーレイにデータを保存したり、オーバーレイからデータを取得したりするために使用できるピアツーピアシグナリングプロトコルです。 RELOADは、ネットワークアドレス変換（TURN）のリレーを使用したトラバーサルに固有のサービス検出メカニズムを定義しますが、基本プロトコルの一部として一般的なサービス検出メカニズムを定義しません。このドキュメントでは、[Redir]で指定された再帰分散ランデブー（ReDiR）サービス検出メカニズムをRELOADオーバーレイに適用する方法を定義します。
In a peer-to-peer (P2P) overlay network such as a RELOAD Overlay Instance, the peers forming the overlay share their resources in order to provide the service the system has been designed to provide. The peers in the overlay both provide services to other peers and request services from other peers. Examples of possible services peers in a RELOAD Overlay Instance can offer to each other include a TURN relay service, a voice mail service, a gateway location service, and a transcoding service. Typically, only a small subset of the peers participating in the system are providers of a given service. A peer that wishes to use a particular service faces the problem of finding peers that are providing that service from the Overlay Instance.
RELOADオーバーレイインスタンスなどのピアツーピア（P2P）オーバーレイネットワークでは、オーバーレイを形成するピアは、システムが提供するように設計されたサービスを提供するためにリソースを共有します。オーバーレイのピアは、他のピアにサービスを提供し、他のピアにサービスを要求します。 RELOADオーバーレイインスタンスのピアが互いに提供できるサービスの例には、TURNリレーサービス、ボイスメールサービス、ゲートウェイロケーションサービス、トランスコーディングサービスなどがあります。通常、システムに参加しているピアの小さなサブセットのみが、特定のサービスのプロバイダーです。特定のサービスを使用したいピアは、オーバーレイインスタンスからそのサービスを提供しているピアを見つけるという問題に直面しています。
A naive way to perform service discovery is to store the Node-IDs of all nodes providing a particular service under a well-known key k. The limitation of this approach is that it scales linearly with the number of nodes that provide the service. The problem is two-fold: the node n that is responsible for service s identified by key k may end up storing a large number of Node-IDs and, most importantly, may also become overloaded since all service lookup requests for service s will need to be answered by node n. An efficient service discovery mechanism does not overload the nodes storing pointers to service providers. In addition, the mechanism must ensure that the load associated with providing a given service is distributed evenly among the nodes providing the service.
サービス検出を実行する素朴な方法は、既知のキーkの下で特定のサービスを提供するすべてのノードのノードIDを格納することです。このアプローチの制限は、サービスを提供するノードの数に比例してスケーリングすることです。問題は2つあります。キーkによって識別されるサービスsを担当するノードnは、大量のノードIDを格納することになり、最も重要なのは、サービスsのすべてのサービスルックアップ要求が必要になるため、過負荷になることです。ノードnによって応答されます。効率的なサービス検出メカニズムは、サービスプロバイダーへのポインターを格納するノードに過負荷をかけません。さらに、このメカニズムでは、特定のサービスの提供に関連する負荷が、サービスを提供するノード間で均等に分散されるようにする必要があります。
It should be noted that a simple service discovery mechanism such as the one mentioned in the previous paragraph might be an appropriate solution in a very small overlay network consisting of perhaps tens of nodes. The ReDiR-based service discovery mechanism described in this document is suitable for use even in overlay networks where the number of end users that may make service discovery requests can be very high (e.g., tens of thousands of nodes or even higher) and where a large fraction of the peers (e.g., on the order of one out of ten or more) can offer the service.
前の段落で述べたような単純なサービス検出メカニズムは、おそらく数十のノードで構成される非常に小さなオーバーレイネットワークでは適切なソリューションになる可能性があることに注意してください。このドキュメントで説明するReDiRベースのサービスディスカバリメカニズムは、サービスディスカバリリクエストを作成する可能性のあるエンドユーザーの数が非常に多くなる可能性がある（たとえば、数万ノードまたはそれ以上）オーバーレイネットワークでの使用にも適しています。ピアの大部分（たとえば、10分の1以上）がサービスを提供できます。
ReDiR implements service discovery by building a tree structure of the service providers that provide a particular service. The tree structure is stored into the RELOAD Overlay Instance using RELOAD Store and Fetch requests. Each service provided in the Overlay Instance has its own tree. The nodes in a ReDiR tree contain pointers to service providers. During service discovery, a peer wishing to use a given service fetches ReDiR tree nodes one-by-one from the RELOAD Overlay Instance until it finds a service provider responsible for its Node-ID. It has been proved that ReDiR can find a service provider using only a constant number of Fetch operations [Redir].
ReDiRは、特定のサービスを提供するサービスプロバイダーのツリー構造を構築することにより、サービスディスカバリを実装します。ツリー構造は、RELOADストアおよびフェッチ要求を使用してRELOADオーバーレイインスタンスに格納されます。オーバーレイインスタンスで提供される各サービスには、独自のツリーがあります。 ReDiRツリーのノードには、サービスプロバイダーへのポインターが含まれています。サービスの検出中に、特定のサービスを使用したいピアは、ノードIDを担当するサービスプロバイダーが見つかるまで、RELOADオーバーレイインスタンスからReDiRツリーノードを1つずつフェッチします。 ReDiRが一定数のフェッチ操作のみを使用してサービスプロバイダーを見つけることができることが証明されています[Redir]。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].
このドキュメントのキーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「MAY」、および「OPTIONAL」は、 RFC 2119 [RFC2119]で説明されているように解釈されます。
DHT: Distributed Hash Tables (DHTs) 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：分散ハッシュテーブル（DHT）は、通常のハッシュテーブルと同様のルックアップサービスを提供する分散分散システムのクラスです。キーを指定すると、システムに参加しているすべてのピアが、そのキーに関連付けられている値を取得できます。キーから値へのマッピングを維持する責任は、ピア間で分散されます。
H(x): Refers to a hash function (e.g., SHA-1 [RFC3174]) calculated over the value x.
H（x）：値xに対して計算されたハッシュ関数（SHA-1 [RFC3174]など）を指します。
H(x,y,z): Refers to a hash function calculated over a concatenated string consisting of x, y, and z, where x, y, and z can be both strings and integers. The network byte order is used.
H（x、y、z）：x、y、zで構成される連結文字列に対して計算されたハッシュ関数を指します。x、y、zは文字列と整数の両方にすることができます。ネットワークのバイト順が使用されます。
I(lvl,k): An interval at level lvl in the ReDiR tree that encloses key k. As an example, I(5,10) refers to an interval at level 5 in the ReDiR tree within whose range key 10 falls.
I（lvl、k）：キーkを囲むReDiRツリーのレベルlvlの間隔。例として、I（5,10）は、範囲キー10が含まれるReDiRツリーのレベル5の間隔を指します。
n.id: Refers to the RELOAD Node-ID of node n.
n.id：ノードnのRELOADノードIDを参照します。
Namespace: An arbitrary identifier that identifies a service provided in the RELOAD Overlay Instance. Examples of potential namespaces include 'voice-mail' and 'turn-server'. The namespace is a UTF-8-encoded [RFC3629] text string.
名前空間：RELOADオーバーレイインスタンスで提供されるサービスを識別する任意の識別子。潜在的な名前空間の例には、「ボイスメール」や「ターンサーバー」などがあります。名前空間は、UTF-8でエンコードされた[RFC3629]テキスト文字列です。
numBitsInNodeId: Refers to the number of bits in a RELOAD Node-ID. This value is used in the equations for calculating the ranges of intervals that ReDiR tree nodes are responsible for.
numBitsInNodeId：RELOADノードIDのビット数を参照します。この値は、式で、ReDiRツリーノードが担当する間隔の範囲を計算するために使用されます。
ReDiR tree: A tree structure of the nodes that provide a particular service. The nodes embed the ReDiR tree into the RELOAD Overlay Instance using RELOAD Store and Fetch requests. Each tree node in the ReDiR tree belongs to some level in the tree. The root node of the ReDiR tree is located at level 0 of the ReDiR tree. The child nodes of the root node are located at level 1. The children of the tree nodes at level 1 are located at level 2, and so forth. The ReDiR tree has a branching factor b. At every level lvl in the ReDiR tree, there is room for a maximum of b^lvl tree nodes. Each tree node in the ReDiR tree is uniquely identified by a pair (lvl,j), where lvl is a level in the ReDiR tree and j is the position of the tree node (from the left) at that level.
ReDiRツリー：特定のサービスを提供するノードのツリー構造。ノードは、RELOADストアおよびフェッチ要求を使用して、ReDiRツリーをRELOADオーバーレイインスタンスに埋め込みます。 ReDiRツリーの各ツリーノードは、ツリーのあるレベルに属しています。 ReDiRツリーのルートノードは、ReDiRツリーのレベル0にあります。ルートノードの子ノードはレベル1にあります。レベル1のツリーノードの子はレベル2にあり、以下同様に続きます。 ReDiRツリーには、分岐係数bがあります。 ReDiRツリーのすべてのレベルlvlには、最大b ^ lvlツリーノードのスペースがあります。 ReDiRツリー内の各ツリーノードは、ペア（lvl、j）によって一意に識別されます。ここで、lvlはReDiRツリー内のレベルであり、jはそのレベルでのツリーノードの位置（左から）です。
Successor: The successor of identifier k in namespace ns is the node belonging to the namespace ns whose identifier most immediately follows the identifier k.
後継：名前空間nsの識別子kの後継は、名前空間nsに属するノードで、識別子kの直後に識別子が続きます。
Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new functionality from the RELOAD base protocol [RFC6940]. This is possible since ReDiR interacts with the RELOAD Overlay Instance by simply storing and fetching data, that is, using RELOAD Store and Fetch requests. ReDiR creates a tree structure of the service providers of a particular service and stores it into the RELOAD Overlay Instance using the Store and Fetch requests. ReDiR service lookups require a logarithmic number of Fetch operations. Further, if information from past service lookups is used to determine the optimal level in the ReDiR tree from which to start new service lookups, an average service lookup can typically finish after a constant number of Fetch operations, assuming that Node-IDs are distributed uniformly at random.
再帰的分散ランデブー（ReDiR）[Redir]は、RELOADベースプロトコル[RFC6940]の新機能を必要としません。これは、ReDiRがRELOADオーバーレイインスタンスとやり取りするのは、データを格納およびフェッチするだけで、つまりRELOAD StoreおよびFetchリクエストを使用するためです。 ReDiRは、特定のサービスのサービスプロバイダーのツリー構造を作成し、StoreおよびFetchリクエストを使用してそれをRELOADオーバーレイインスタンスに格納します。 ReDiRサービスの検索には、対数のFetch操作が必要です。さらに、過去のサービスルックアップからの情報を使用して、新しいサービスルックアップを開始するReDiRツリーの最適レベルを決定する場合、ノードIDが均一に分散されていると仮定して、平均的なサービスルックアップは通常、一定数のフェッチ操作の後に終了します。無作為に。
In ReDiR, each service provided in the overlay is identified by an identifier, called the namespace. All service providers of a given service store their information under the namespace of that service. Peers wishing to use a service perform lookups within the namespace of the service. The result of a ReDiR lookup for an identifier k in namespace ns is a RedirServiceProvider structure (see Section 4.1) of a service provider that belongs to ns and whose Node-ID is the closest successor of identifier k in the namespace.
ReDiRでは、オーバーレイで提供される各サービスは、名前空間と呼ばれる識別子によって識別されます。特定のサービスのすべてのサービスプロバイダーは、そのサービスの名前空間の下に情報を格納します。サービスを使用したいピアは、サービスの名前空間内で検索を実行します。名前空間ns内の識別子kのReDiRルックアップの結果は、nsに属し、ノードIDが名前空間内の識別子kの最も近い後続であるサービスプロバイダーのRedirServiceProvider構造（セクション4.1を参照）です。
Each tree node in the ReDiR tree contains a dictionary of RedirServiceProvider entries of peers providing a particular service. Each tree node in the ReDiR tree also belongs to some level in the tree. The root node of the ReDiR tree is located at level 0. The child nodes of the root node are located at level 1 of the ReDiR tree. The children of the tree nodes at level 1 are located at level 2, and so forth. The ReDiR tree has a branching factor, whose value is determined by a new element in the RELOAD overlay configuration document, called branching-factor. The RELOAD overlay configuration document is defined in the RELOAD base protocol [RFC6940]. At every level lvl in the ReDiR tree, there is room for a maximum of branching-factor^lvl tree nodes. As an example, in a tree whose branching-factor is 2, the second level can contain up to four tree nodes (note that a given level may contain less than the maximum number of tree nodes since empty tree nodes are not stored). Each tree node in the ReDiR tree is uniquely identified by a pair (lvl,j), where lvl is a level in the ReDiR tree and j is the position of the tree node (from the left) at that level. As an example, the pair (2,3) identifies the third tree node from the left at level 2.
ReDiRツリーの各ツリーノードには、特定のサービスを提供するピアのRedirServiceProviderエントリのディクショナリが含まれています。 ReDiRツリー内の各ツリーノードも、ツリー内のあるレベルに属しています。 ReDiRツリーのルートノードはレベル0にあります。ルートノードの子ノードはReDiRツリーのレベル1にあります。レベル1のツリーノードの子は、レベル2に配置されます。 ReDiRツリーには分岐係数があり、その値はRELOADオーバーレイ構成文書内の新しい要素である、branching-factorと呼ばれます。 RELOADオーバーレイ構成文書は、RELOAD基本プロトコル[RFC6940]で定義されています。 ReDiRツリーのすべてのレベルlvlには、最大のbranching-factor ^ lvlツリーノードの余地があります。例として、branching-factorが2であるツリーでは、2番目のレベルに最大4つのツリーノードを含めることができます（空のツリーノードは格納されないため、特定のレベルに含まれるツリーノードの最大数より少ない場合があります）。 ReDiRツリー内の各ツリーノードは、ペア（lvl、j）によって一意に識別されます。ここで、lvlはReDiRツリー内のレベルであり、jはそのレベルでのツリーノード（左から）の位置です。例として、ペア（2,3）はレベル2で左から3番目のツリーノードを識別します。
The ReDiR tree is stored into the RELOAD Overlay Instance tree node by tree node, by storing the values of tree node (level,j) under a key created by taking a hash over the concatenation of the namespace, level, and j, that is, as H(namespace,level,j). As an example, the root of the tree for a voice mail service is stored at H("voice-mail",0,0). Each node (level,j) in the ReDiR tree contains b intervals of the DHT's identifier space as follows:
ReDiRツリーは、ツリーノードごとにRELOADオーバーレイインスタンスツリーノードに格納されます。名前空間、レベル、およびjの連結に対するハッシュを取得することによって作成されたキーの下にツリーノード（レベル、j）の値を格納します。 、H（namespace、level、j）として。例として、ボイスメールサービスのツリーのルートはH（ "voice-mail"、0,0）に格納されます。 ReDiRツリーの各ノード（レベル、j）には、DHTの識別子空間のb間隔が次のように含まれています。
[2^numBitsInNodeId*b^(-level)*(j+(b'/b)), 2^numBitsInNodeId*b^(-level)*(j+((b'+1)/b))), for 0<=b'<b,
[2 ^ numBitsInNodeId * b ^（-level）*（j +（b '/ b））、2 ^ numBitsInNodeId * b ^（-level）*（j +（（b' + 1）/ b）））、0の場合<= b '<b、
where b is the branching-factor and b' refers to the number of an interval within the ReDiR tree node j.
ここで、bは分岐係数であり、b 'はReDiRツリーノードj内の間隔の数を指します。
Figure 1 shows an example of a ReDiR tree whose branching factor is 2. In the figure, the size of the identifier space of the overlay is 16. Each tree node in the ReDiR tree is shown as two horizontal lines separated by a vertical bar ('|') in the middle. The horizontal lines represent the two intervals each node is responsible for. At level 0, there is only one node, (0,0), responsible for two intervals that together cover the entire identifier space of the RELOAD Overlay Instance. At level 1, there are two nodes, (1,0) and (1,1), each of which is responsible for half of the identifier space of the RELOAD Overlay Instance. At level 2, there are four nodes. Each of them owns one fourth of the identifier space. At level 3, there are eight nodes, each of which is responsible for one eighth of the identifier space.
図1は、分岐係数が2のReDiRツリーの例を示しています。図では、オーバーレイの識別子スペースのサイズは16です。ReDiRツリーの各ツリーノードは、垂直バー（ '|'）中央。水平線は、各ノードが担当する2つの間隔を表しています。レベル0では、RELOADオーバーレイインスタンスの識別子空間全体をカバーする2つの間隔を担当するノード（0,0）が1つだけあります。レベル1では、（1,0）と（1,1）の2つのノードがあり、それぞれがRELOADオーバーレイインスタンスの識別子空間の半分を担当します。レベル2では、4つのノードがあります。それらのそれぞれは、識別子スペースの4分の1を所有しています。レベル3では、8つのノードがあり、それぞれがIDスペースの8分の1を占めます。
Level 0 __________________|__________________
| |
Level 1 ________|________ ________|________
| | | |
Level 2 ___|___ ___|___ ___|___ ___|___
| | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 1: ReDiR Tree
図1：ReDiRツリー
Figure 2 illustrates how tree nodes are numbered in the ReDiR tree at levels 0-2.
図2は、ReDiRツリーでレベル0〜2のツリーノードに番号が付けられる方法を示しています。
Level 0 ________________(0,0)________________
| |
Level 1 ______(1,0)______ ______(1,1)______
| | | |
Level 2 _(2,0)_ _(2,1)_ _(2,2)_ _(2,3)_
| | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 2: ReDiR Tree Nodes
図2：ReDiRツリーノード
Figure 3 illustrates how intervals are assigned to tree nodes in the ReDiR tree at levels 0 and 1. As an example, the single tree node (0,0) at level 0 is divided into two intervals, each of which covers half of the identifier space of the overlay. These two intervals are [0,7] and [8,15].
図3は、レベル0と1でReDiRツリーのツリーノードに間隔がどのように割り当てられるかを示しています。例として、レベル0の単一のツリーノード（0,0）は2つの間隔に分割され、それぞれが識別子の半分をカバーしていますオーバーレイのスペース。これらの2つの間隔は[0,7]と[8,15]です。
Level 0 ______[0,7]_______|_______[8,15]_____
| |
Level 1 _[0,3]__|__[4,7]_ _[8,11]_|_[12,15]
| | | |
Level 2 ___|___ ___|___ ___|___ ___|___
| | | | | | | |
Level 3 _|_ _|_ _|_ _|_ _|_ _|_ _|_ _|_
Figure 3: Intervals in ReDiR Tree
図3：ReDiRツリーの間隔
Note that all of the examples above are simplified. In a real ReDiR tree, the default ReDiR branching factor is 10, meaning that each tree node is split into 10 intervals and that each tree node has 10 children. In such a tree, level 1 contains 10 nodes and 100 intervals. Level 2 contains 100 nodes and 1000 intervals, level 3 1000 nodes and 10000 intervals, etc. Further, the size of the identifier space of a real RELOAD Overlay Instance is at the minimum 2^128.
上記の例はすべて簡略化されていることに注意してください。実際のReDiRツリーでは、デフォルトのReDiR分岐係数は10です。これは、各ツリーノードが10の間隔に分割され、各ツリーノードに10の子があることを意味します。このようなツリーでは、レベル1には10個のノードと100個の間隔が含まれています。レベル2には、100ノードと1000間隔、レベル3 1000ノードと10000間隔などが含まれます。さらに、実際のRELOADオーバーレイインスタンスの識別子スペースのサイズは、最小で2 ^ 128です。
ReDiR tree nodes are stored using the dictionary data model defined in the RELOAD base protocol [RFC6940]. The data stored is a RedirServiceProvider Resource Record:
ReDiRツリーノードは、RELOADベースプロトコル[RFC6940]で定義されたディクショナリデータモデルを使用して保存されます。保存されるデータはRedirServiceProviderリソースレコードです。
enum { none(0), (255) }
RedirServiceProviderExtType;
struct {
RedirServiceProviderExtType type;
Destination destination_list<0..2^16-1>;
opaque namespace<0..2^16-1>;
uint16 level;
uint16 node;
uint16 length;
select (type) {
/* This type may be extended */
} extension;
} RedirServiceProvider;
} RedirServiceProvider;
The contents of the RedirServiceProvider Resource Record are as follows:
RedirServiceProviderリソースレコードの内容は次のとおりです。
type
タイプ
The type of an extension to the RedirServiceProvider Resource Record. Unknown types are allowed.
RedirServiceProviderリソースレコードへの拡張のタイプ。不明なタイプが許可されています。
destination_list
destination_list
A list of IDs through which a message is to be routed to reach the service provider. The destination list consists of a sequence of Destination values. The contents of the Destination structure are as defined in the RELOAD base protocol [RFC6940].
メッセージがサービスプロバイダーに到達するためにルーティングされるIDのリスト。宛先リストは、一連の宛先値で構成されています。 Destination構造の内容は、RELOAD基本プロトコル[RFC6940]で定義されています。
namespace
名前空間
An opaque UTF-8-encoded string containing the namespace.
名前空間を含む不透明なUTF-8でエンコードされた文字列。
level
レベル
The level in the ReDiR tree.
ReDiRツリーのレベル。
node
ので
The position of the node storing this RedirServiceProvider record at the current level in the ReDiR tree.
ReDiRツリーの現在のレベルでこのRedirServiceProviderレコードを格納するノードの位置。
length
長さ
The length of the rest of the Resource Record.
リソースレコードの残りの長さ。
extension
拡張
An extension value. The RedirServiceProvider Resource Record can be extended to include, for instance, information specific to the service or service provider.
拡張値。 RedirServiceProviderリソースレコードを拡張して、たとえば、サービスまたはサービスプロバイダーに固有の情報を含めることができます。
Before registering as a service provider or performing a service lookup, a peer needs to determine the starting level Lstart for the registration or lookup operation in the ReDiR tree. It is RECOMMENDED that Lstart is set to 2. This recommendation is based on the findings in [Redir], which indicate that this starting level results in good performance. In subsequent registrations, Lstart MAY, as an optimization, be set to the lowest level at which a registration operation has last completed.
ピアは、サービスプロバイダーとして登録する前、またはサービスルックアップを実行する前に、ReDiRツリーでの登録またはルックアップ操作の開始レベルLstartを決定する必要があります。 Lstartを2に設定することをお勧めします。この推奨事項は、[Redir]の調査結果に基づいています。これは、この開始レベルが良好なパフォーマンスをもたらすことを示しています。後続の登録では、Lstartは、最適化として、登録操作が最後に完了した最低レベルに設定される場合があります。
In the case of subsequent service lookups, nodes MAY, as an optimization, record the levels at which the last 16 service lookups completed and take Lstart to be the mode of those depths (mode, in statistics, is the value that appears most often in a set of data).
後続のサービスルックアップの場合、ノードは、最適化として、最後の16のサービスルックアップが完了したレベルを記録し、Lstartをそれらの深度のモードにすることができます（統計では、モードは最も頻繁に表示される値です）データのセット）。
A node MUST use the following procedure to register as a service provider in the RELOAD Overlay Instance:
ノードは次の手順を使用して、RELOADオーバーレイインスタンスにサービスプロバイダーとして登録する必要があります。
1. A node n with Node-ID n.id wishing to register as a service provider starts from a starting level Lstart (see Section 4.2 for the details on selecting the starting level). Therefore, node n sets the current level to level=Lstart.
1. サービスプロバイダーとして登録するノードID n.idのノードnは、開始レベルLstartから開始します（開始レベルの選択の詳細については、セクション4.2を参照してください）。したがって、ノードnは現在のレベルをlevel = Lstartに設定します。
2. Node n MUST send a RELOAD Fetch request to fetch the contents of the tree node responsible for I(level,n.id). An interval I(l,k) is the interval at level l in the ReDiR tree that includes key k. The fetch MUST be a wildcard fetch.
2. ノードnはRELOAD Fetchリクエストを送信して、I（level、n.id）を担当するツリーノードのコンテンツをフェッチする必要があります。間隔I（l、k）は、キーkを含むReDiRツリーのレベルlの間隔です。フェッチはワイルドカードフェッチでなければなりません。
3. Node n MUST send a RELOAD Store request to add its RedirServiceProvider entry to the dictionary stored in the tree node responsible for I(level,n.id). Note that node n always stores its RedirServiceProvider entry, regardless of the contents of the dictionary.
3. ノードnは、RELOADストア要求を送信して、I（level、n.id）を担当するツリーノードに格納されているディクショナリにRedirServiceProviderエントリを追加する必要があります。ノードnは、辞書の内容に関係なく、常にRedirServiceProviderエントリを格納することに注意してください。
4. If node n's Node-ID (n.id) is the lowest or highest Node-ID stored in the tree node responsible for I(Lstart,n.id), node n MUST reduce the current level by one (i.e., set level=level-1) and continue up the ReDiR tree towards the root level (level 0), repeating steps 2 and 3 above. Node n MUST continue in this way until it reaches either the root of the tree or a level at which n.id is not the lowest or highest Node-ID in the interval I(level,n.id).
4. ノードnのノードID（n.id）がI（Lstart、n.id）を担当するツリーノードに格納されている最小または最大のノードIDである場合、ノードnは現在のレベルを1だけ減らす必要があります（つまり、レベル=を設定します）レベル1）と、ルートレベル（レベル0）に向かってReDiRツリーを上に進み、上記のステップ2と3を繰り返します。ノードnは、ツリーのルートまたはn.idがインターバルI（level、n.id）の最小または最大のノードIDではないレベルに到達するまで、この方法で継続する必要があります。
5. Node n MUST also perform a downward walk in the ReDiR tree, during which it goes through the tree nodes responsible for intervals I(Lstart,n.id), I(Lstart+1,n.id), I(Lstart+2,n.id), etc. At each step, node n MUST fetch the responsible tree node and store its RedirServiceProvider record in that tree node if n.id is the lowest or highest Node-ID in its interval. Node n MUST end this downward walk as soon as it reaches a level l at which it is the only service provider in its interval I(l,n.id).
5. ノードnは、ReDiRツリーで下向きのウォークも実行する必要があります。その間、ノードIは、間隔I（Lstart、n.id）、I（Lstart + 1、n.id）、I（Lstart + 2、 n.id）など。各ステップで、ノードnは、責任のあるツリーノードをフェッチして、そのノードのRedirServiceProviderレコードをそのツリーノードに格納する必要があります（n.idがその間隔で最小または最大のノードIDの場合）。ノードnは、インターバルI（l、n.id）で唯一のサービスプロバイダーであるレベルlに到達するとすぐに、この下降ウォークを終了する必要があります。
Note that above, when we refer to 'the tree node responsible for I(l,k)', we mean the entire tree node (that is, all the intervals within the tree node) responsible for interval I(l,k). In contrast, I(l,k) refers to a specific interval within a tree node.
上記の「I（l、k）を担当するツリーノード」とは、区間I（l、k）を担当するツリーノード全体（つまり、ツリーノード内のすべての区間）を意味します。対照的に、I（l、k）はツリーノード内の特定の間隔を指します。
All state in the ReDiR tree is soft. Therefore, a service provider needs to periodically repeat the registration process to refresh its RedirServiceProvider Resource Record. If a record expires, it MUST be dropped from the dictionary by the peer storing the tree node. Deciding an appropriate lifetime for the RedirServiceProvider Resource Records is up to each service provider. However, a default value of 10 minutes is RECOMMENDED as this is a good trade-off between keeping the amount of ReDiR traffic in the overlay at a reasonable level and ensuring that stale information is removed quickly enough. Every service provider MUST repeat the entire registration process periodically until it leaves the RELOAD Overlay Instance. The service provider SHOULD initiate each refresh process slightly earlier (e.g., when 90% of the refresh interval has passed) than the expiry time of the Resource Record.
ReDiRツリーのすべての状態はソフトです。したがって、サービスプロバイダーは、登録プロセスを定期的に繰り返して、RedirServiceProviderリソースレコードを更新する必要があります。レコードの有効期限が切れた場合は、ツリーノードを格納しているピアが辞書から削除する必要があります。 RedirServiceProviderリソースレコードの適切なライフタイムの決定は、各サービスプロバイダーに任されています。ただし、デフォルト値の10分は推奨されます。これは、オーバーレイのReDiRトラフィックの量を妥当なレベルに維持することと、古くなった情報を十分に迅速に削除することを保証することの間の適切なトレードオフであるためです。すべてのサービスプロバイダーは、RELOADオーバーレイインスタンスを終了するまで、登録プロセス全体を定期的に繰り返す必要があります。サービスプロバイダーは、リソースレコードの有効期限よりも少し早く（たとえば、更新間隔の90％が経過したとき）各更新プロセスを開始する必要があります（SHOULD）。
Note that no new mechanisms are needed to keep track of the remaining lifetime of RedirServiceProvider records. The 'storage_time' and 'lifetime' fields of RELOAD's StoredData structure can be used for this purpose in the usual way.
RedirServiceProviderレコードの残りのライフタイムを追跡するために新しいメカニズムは必要ないことに注意してください。 RELOADのStoredData構造の「storage_time」および「lifetime」フィールドは、通常の方法でこの目的に使用できます。
The purpose of a service lookup for identifier k in namespace ns is to find the node that is a part of ns and whose identifier most immediately follows (i.e., is the closest successor of) the identifier k.
名前空間nsの識別子kのサービスルックアップの目的は、nsの一部であり、識別子kの直後に続く（つまり、最も近い後続ノードである）ノードを見つけることです。
A service lookup operation resembles the service registration operation described in Section 4.3. Service lookups start from a given starting level level=Lstart in the ReDiR tree (see Section 4.2 for the details on selecting the starting level). At each step, a node n wishing to discover a service provider MUST fetch the tree node responsible for the interval I(level,n.id) that encloses the search key n.id at the current level using a RELOAD Fetch request. Having fetched the tree node, node n MUST determine the next action to carry out as follows:
サービス検索操作は、セクション4.3で説明されているサービス登録操作に似ています。サービス検索は、ReDiRツリーの特定の開始レベルlevel = Lstartから開始します（開始レベルの選択の詳細については、セクション4.2を参照してください）。各ステップで、サービスプロバイダーを検出するノードnは、RELOAD Fetch要求を使用して、現在のレベルで検索キーn.idを囲む間隔I（level、n.id）を担当するツリーノードをフェッチする必要があります。ツリーノードをフェッチしたら、ノードnは次のアクションを実行するように決定する必要があります。
Condition 1
条件1
If there is no successor of node n present in the just-fetched ReDiR tree node (note: within the entire tree node and not only within the current interval) responsible for I(level,n.id), then the successor of node n must be present in a larger segment of the identifier space (i.e., further up in the ReDiR tree where each interval and tree node covers a larger range of the identifier space). Therefore, node n MUST reduce the current level by one to level=level-1 and carry out a new Fetch operation for the tree node responsible for n.id at that level. The fetched tree node is then analyzed and the next action determined by checking Conditions 1-3.
フェッチされたばかりのReDiRツリーノードにノードnの後続ノードが存在しない場合（注：現在の間隔内だけでなく、ツリーノード全体内）、I（level、n.id）を担当する場合、ノードnの後続ノード識別子空間のより大きなセグメントに存在する必要があります（つまり、各間隔とツリーノードがより広い範囲の識別子空間をカバーするReDiRツリーのさらに上）。したがって、ノードnは現在のレベルを1つ下げてlevel = level-1にし、そのレベルでn.idを担当するツリーノードに対して新しいフェッチ操作を実行する必要があります。次に、フェッチされたツリーノードが分析され、次のアクションが条件1〜3をチェックすることによって決定されます。
Condition 2
条件2
If n.id is neither the lowest nor the highest Node-ID within the interval (note: within the interval, not within the entire tree node) I(level,n.id), n MUST next check the tree node responsible for n.id at the next level down the tree. Thus, node n MUST increase the level by one to level=level+1 and carry out a new Fetch operation at that level. The fetched tree node is then analyzed and the next action determined by checking the conditions listed here, starting at Condition 1.
n.idが間隔内の最小ノードIDでも最大ノードIDでもない場合（注：ツリーノード全体ではなく間隔内）I（level、n.id）、nは次にnを担当するツリーノードをチェックする必要があります。ツリーの下の次のレベルの.id。したがって、ノードnはレベルを1だけ上げてlevel = level + 1にし、そのレベルで新しいフェッチ操作を実行する必要があります。次に、フェッチされたツリーノードが分析され、次のアクションは、条件1から始まる、ここにリストされた条件をチェックすることによって決定されます。
Condition 3
条件3
If neither of the conditions above holds, meaning that there is a successor s of n.id present in the just-fetched ReDiR tree node and n.id is the highest or lowest Node-ID in its interval, the service lookup has finished successfully, and s must be the closest successor of n.id in the ReDiR tree.
上記のいずれの条件も満たされない場合、つまり、フェッチされたばかりのReDiRツリーノードにn.idの後続ノードが存在し、n.idがその間隔の最大または最小のノードIDである場合、サービスのルックアップは正常に終了しています、およびsは、ReDiRツリーのn.idの最も近い後続ノードでなければなりません。
Note that above, when we refer to 'the tree node responsible for interval I(l,k)', we mean the entire tree node (that is, all the intervals within the tree node) responsible for interval I(l,k). In contrast, I(l,k) refers to a specific interval within a tree node.
上記の「間隔I（l、k）を担当するツリーノード」を参照する場合、間隔I（l、k）を担当するツリーノード全体（つまり、ツリーノード内のすべての間隔）を意味することに注意してください。 。対照的に、I（l、k）はツリーノード内の特定の間隔を指します。
Note also that there may be some cases in which no successor can be found from the ReDiR tree. An example is a situation in which all of the service providers stored in the ReDiR tree have a Node-ID smaller than identifier k. In this case, the upward walk of the service lookup will reach the root of the tree without encountering a successor. An appropriate strategy in this case is to pick one of the RedirServiceProvider entries stored in the dictionary of the root node at random.
また、ReDiRツリーから後続が見つからない場合があることに注意してください。例としては、ReDiRツリーに格納されているすべてのサービスプロバイダーのNode-IDが識別子kより小さい状況です。この場合、サービスルックアップの上方へのウォークは、後続ノードに遭遇することなくツリーのルートに到達します。この場合の適切な戦略は、ルートノードのディクショナリにランダムに格納されているRedirServiceProviderエントリの1つを選択することです。
Since RedirServiceProvider records are expiring and registrations are being refreshed periodically, there can be certain rare situations in which a service lookup may fail even if there is a valid successor present in the ReDiR tree. An example is a case in which a ReDiR tree node is fetched just after a RedirServiceProvider entry of the only successor of k present in the tree node has expired and just before a Store request that has been sent to refresh the entry reaches the peer storing the tree node. In this rather unlikely scenario, the successor that should have been present in the tree node is temporarily missing. Thus, the service lookup will fail and needs to be carried out again.
RedirServiceProviderレコードが期限切れになり、登録が定期的に更新されるため、ReDiRツリーに有効な後続が存在していても、サービスの検索が失敗するというまれな状況が発生する可能性があります。例は、ツリーノードに存在するkの唯一の後継者のRedirServiceProviderエントリが期限切れになり、エントリを更新するために送信されたStoreリクエストがピアを格納するピアに到達する直前にReDiRツリーノードがフェッチされる場合です。ツリーノード。このかなりありそうもないシナリオでは、ツリーノードに存在するはずだったサクセサが一時的に失われています。したがって、サービスの検索は失敗し、再度実行する必要があります。
To recover from the kinds of situations described above, a ReDiR implementation MAY choose to use the optimization described next. The ReDiR implementation MAY implement a local temporary cache that is maintained for the duration of a service lookup operation in a RELOAD node. The temporary cache is used to store all RedirServiceProvider entries that have been fetched during the upward and downward walks of a service lookup operation. Should it happen that a service lookup operation fails due to the downward walk reaching a level that does not contain a successor, the cache is searched for successors of the search key. If there are successors present in the cache, the closest one of them is selected as the service provider.
上記のような状況から回復するために、ReDiR実装は次に説明する最適化を使用することを選択できます。 ReDiR実装は、RELOADノードでのサービスルックアップ操作の期間中維持されるローカル一時キャッシュを実装してもよい（MAY）。一時キャッシュは、サービス検索操作の上昇および下降ウォーク中にフェッチされたすべてのRedirServiceProviderエントリを格納するために使用されます。下降ウォークが後続操作を含まないレベルに達したためにサービス検索操作が失敗した場合、キャッシュで検索キーの後続操作が検索されます。キャッシュにサクセサが存在する場合、それらのうち最も近いサクセサがサービスプロバイダとして選択されます。
Before leaving the RELOAD Overlay Instance, a service provider SHOULD remove the RedirServiceProvider records it has stored by storing exists=False values in their place, as described in [RFC6940].
[RFC6940]で説明されているように、サービスプロバイダーは、RELOADオーバーレイインスタンスを終了する前に、exist = False値をその場所に格納することで、格納したRedirServiceProviderレコードを削除する必要があります（SHOULD）。
As specified in the RELOAD base protocol [RFC6940], every Kind that is storable in an overlay must be associated with an access control policy. This policy defines whether a request from a given node to operate on a given value should succeed or fail. Usages can define any access control rules they choose, including publicly writable values.
RELOAD基本プロトコル[RFC6940]で指定されているように、オーバーレイに格納できるすべての種類は、アクセス制御ポリシーに関連付けられている必要があります。このポリシーは、特定のノードから特定の値を操作する要求が成功するか失敗するかを定義します。使用法では、パブリックに書き込み可能な値を含め、選択したアクセス制御ルールを定義できます。
ReDiR requires an access control policy that allows multiple nodes in the overlay read and write access to the ReDiR tree nodes stored in the overlay. Therefore, none of the access control policies specified in the RELOAD base protocol [RFC6940] is sufficient.
ReDiRには、オーバーレイに格納されているReDiRツリーノードへの読み取りおよび書き込みアクセスをオーバーレイ内の複数のノードに許可するアクセス制御ポリシーが必要です。したがって、RELOAD基本プロトコル[RFC6940]で指定されているアクセス制御ポリシーはどれも十分ではありません。
This document defines a new access control policy, called NODE-ID-MATCH. In this policy, a given value MUST be written and overwritten only if the request is signed with a key associated with a certificate whose Node-ID is equal to the dictionary key. In addition, provided that exists=True, the Node-ID MUST belong to one of the intervals associated with the tree node (the number of intervals each tree node has is determined by the branching-factor parameter). Finally, provided that exists=True, H(namespace,level,node), where namespace, level, and node are taken from the RedirServiceProvider structure being stored, MUST be equal to the Resource-ID for the resource. The NODE-ID-MATCH policy may only be used with dictionary types.
このドキュメントでは、NODE-ID-MATCHと呼ばれる新しいアクセス制御ポリシーを定義します。このポリシーでは、ノードIDがディクショナリキーと等しい証明書に関連付けられたキーでリクエストが署名されている場合にのみ、所定の値を書き込んで上書きする必要があります。さらに、exists = Trueの場合、Node-IDはツリーノードに関連付けられた間隔の1つに属している必要があります（各ツリーノードの間隔の数は、branching-factorパラメーターによって決定されます）。最後に、exists = True、H（namespace、level、node）が存在する場合、名前空間、レベル、およびノードは、格納されているRedirServiceProvider構造体から取得され、リソースのResource-IDと等しい必要があります。 NODE-ID-MATCHポリシーは、辞書タイプでのみ使用できます。
This section defines the REDIR Kind.
このセクションではREDIRの種類を定義します。
Name
名前
REDIR
赤
Kind-ID
種類ID
The Resource Name for the REDIR Kind-ID is created by concatenating three pieces of information: namespace, level, and node number. Namespace is an opaque UTF-8-encoded string identifying a service, such as 'turn-server'. Level is an integer specifying a level in the ReDiR tree. Node number is an integer identifying a ReDiR tree node at a specific level. The data stored is a RedirServiceProvider structure, as defined in Section 4.1.
REDIR Kind-IDのリソース名は、名前空間、レベル、ノード番号の3つの情報を連結して作成されます。名前空間は、「ターンサーバー」などのサービスを識別する不透明なUTF-8エンコードされた文字列です。 Levelは、ReDiRツリーのレベルを指定する整数です。ノード番号は、特定のレベルのReDiRツリーノードを識別する整数です。保存されるデータは、セクション4.1で定義されているRedirServiceProvider構造です。
Data Model
データ・モデル
The data model for the REDIR Kind-ID is dictionary. The dictionary key is the Node-ID of the service provider.
REDIR Kind-IDのデータモデルはディクショナリです。ディクショナリキーは、サービスプロバイダーのノードIDです。
Access Control
アクセス制御
The access control policy for the REDIR Kind is the NODE-ID-MATCH policy that was defined in Section 5.
REDIR種類のアクセス制御ポリシーは、セクション5で定義されたNODE-ID-MATCHポリシーです。
Figure 4 shows an example of a ReDiR tree containing information about four different service providers whose Node-IDs are 2, 3, 4, and 7. In the example, numBitsInNodeId=4. Initially, the ReDiR tree is empty; Figure 4 shows the state of the tree at the point when all the service providers have registered.
図4は、ノードIDが2、3、4、および7である4つの異なるサービスプロバイダーに関する情報を含むReDiRツリーの例を示しています。この例では、numBitsInNodeId = 4です。最初、ReDiRツリーは空です。図4は、すべてのサービスプロバイダーが登録された時点のツリーの状態を示しています。
Level 0 ____2_3___4_____7_|__________________
| |
Level 1 ____2_3_|_4_____7 ________|________
| | | |
Level 2 ___|2_3 4__|__7 ___|___ ___|___
| | | | | | | |
Level 3 _|_ _|3 _|_ _|_ _|_ _|_ _|_ _|_
Figure 4: Example of a ReDiR Tree
図4：ReDiRツリーの例
First, peer 2 whose Node-ID is 2 joins the namespace. Since this is the first registration peer 2 performs, peer 2 sets the starting level Lstart to 2, as was described in Section 4.2. Also, all other peers in this example will start from level 2. First, peer 2 fetches the contents of the tree node associated with interval I(2,2) from the RELOAD Overlay Instance. This tree node is the first tree node from the left at level 2 since key 2 is associated with the second interval of the first tree node. Peer 2 also stores its RedirServiceProvider record in that tree node. Since peer 2's Node-ID is the only Node-ID stored in the tree node (i.e., peer 2's Node-ID fulfills the condition in Section 4.3 that it be the numerically lowest or highest among the keys stored in the node), peer 2 continues up the tree. In fact, peer 2 continues up in the tree all the way to the root inserting its own Node-ID in all levels since the tree is empty (which means that peer 2's Node-ID always fulfills the condition that it be the numerically lowest or highest Node-ID in the interval I(level, 2) during the upward walk). As described in Section 4.3, peer 2 also walks down the tree. The downward walk peer 2 does ends at level 2 since peer 2 is the only node in its interval at that level.
まず、ノードIDが2のピア2が名前空間に参加します。これはピア2が実行する最初の登録なので、ピア2はセクション4.2で説明したように、開始レベルLstartを2に設定します。また、この例の他のすべてのピアはレベル2から開始します。最初に、ピア2は間隔I（2,2）に関連付けられたツリーノードのコンテンツをRELOADオーバーレイインスタンスからフェッチします。キー2は最初のツリーノードの2番目の間隔に関連付けられているため、このツリーノードはレベル2の左から1番目のツリーノードです。ピア2は、そのRedirServiceProviderレコードもそのツリーノードに格納します。ピア2のノードIDはツリーノードに格納されている唯一のノードIDであるため（つまり、ピア2のノードIDは、ノードに格納されているキーの中で数値的に最低または最高であるというセクション4.3の条件を満たす）、ピア2ツリーの上に続きます。実際、ピア2はツリーまで空になっているため、ルートに至るまでツリー内を進み、独自のノードIDをすべてのレベルに挿入します（つまり、ピア2のノードIDは常に数値的に最小または上昇歩行中の間隔I（レベル、2）で最高のノードID。セクション4.3で説明したように、ピア2もツリーをたどります。ピア2は、そのレベルでの間隔内の唯一のノードであるため、下降ウォークピア2はレベル2で終了します。
The next peer to join the namespace is peer 3, whose Node-ID is 3. Peer 3 starts from level 2. At that level, peer 3 stores its RedirServiceProvider entry in the same interval I(2,3) that already contains the RedirServiceProvider entry of peer 2. Interval I(2,3), that is, the interval at level 2 enclosing key 3, is associated with the right-hand-side interval of the first tree node. Since peer 3 has the numerically highest Node-ID in the tree node associated with I(2,3), peer 3 continues up the tree. Peer 3 also stores its RedirServiceProvider record at levels 1 and 0 since its Node-ID is numerically highest among the Node-IDs stored in the intervals to which its own Node-ID belongs. Peer 3 also does a downward walk that starts from level 2 (i.e., the starting level). Since peer 3 is not the only node in interval I(2,3), it continues down the tree to level 3. The downward walk ends at this level since peer 3 is the only service provider in the interval I(3,3).
名前空間に参加する次のピアはピア3であり、そのノードIDは3です。ピア3はレベル2から始まります。そのレベルでは、ピア3は、すでにRedirServiceProviderを含む同じ間隔I（2,3）にRedirServiceProviderエントリを格納します。ピア2のエントリ。インターバルI（2,3）、つまり、キー3を囲むレベル2のインターバルは、最初のツリーノードの右側のインターバルに関連付けられます。ピア3は、I（2,3）に関連付けられているツリーノードで、数値的に最大のノードIDを持っているため、ピア3はツリーを上方向に進みます。ピア3は、そのノードIDが自身のノードIDが属する間隔に格納されているノードIDの中で数値的に最も高いため、レベル1および0にそのRedirServiceProviderレコードも格納します。ピア3は、レベル2（つまり、開始レベル）から始まる下向きの歩行も行います。ピア3はインターバルI（2,3）の唯一のノードではないため、ツリーを下ってレベル3まで続きます。ピア3がインターバルI（3,3）の唯一のサービスプロバイダーであるため、下降ウォークはこのレベルで終了します。 。
The third peer to join the namespace is peer 7, whose Node-ID is 7. Like the two earlier peers, peer 7 also starts from level 2 because this is the first registration it performs. Peer 7 stores its RedirServiceProvider record at level 2. At level 1, peer 7 has the numerically highest (and lowest) Node-ID in its interval I(1,7) (because it is the only node in interval I(1,7); peers 2 and 3 are stored in the same tree node but in a different interval), and therefore, it stores its Node-ID in the tree node associated with that interval. Peer 7 also has the numerically highest Node-ID in the interval I(0,7) associated with its Node-ID at level 0. Finally, peer 7 performs a downward walk, which ends at level 2 because peer 7 is the only node in its interval at that level.
名前空間に参加する3番目のピアはピア7で、そのノードIDは7です。以前の2つのピアと同様に、ピア7もレベル2から開始します。これは、これが最初に実行する登録だからです。ピア7はそのRedirServiceProviderレコードをレベル2で保存します。レベル1では、ピア7は間隔I（1,7）で数値的に最大（および最小）のノードIDを持っています（間隔I（1,7で唯一のノードであるため） ）;ピア2とピア3は同じツリーノードに格納されますが、間隔が異なります）。したがって、そのノードIDは、その間隔に関連付けられたツリーノードに格納されます。ピア7は、レベル0のノードIDに関連付けられた間隔I（0,7）で、数値的に最も高いノードIDも持っています。最後に、ピア7は、ノード7が唯一のノードであるため、レベル2で終了する下降ウォークを実行します。そのレベルの間隔で。
The final peer to join the ReDiR tree is peer 4, whose Node-ID is 4. Peer 4 starts by storing its RedirServiceProvider record at level 2. Since it has the numerically lowest Node-ID in the tree node associated with interval I(2,4), it continues up in the tree to level 1. At level 1, peer 4 stores its record in the tree node associated with interval I(1,4) because it has the numerically lowest Node-ID in that interval. Next, peer 4 continues to the root level, at which it stores its RedirServiceProvider record and finishes the upward walk since the root level was reached. Peer 4 also does a downward walk starting from level 2. The downward walk stops at level 2 because peer 4 is the only peer in the interval I(2,4).
ReDiRツリーに参加する最後のピアはピア4であり、そのノードIDは4です。ピア4は、レベル2にRedirServiceProviderレコードを格納することから始まります。これは、インターバルI（2 、4）、それはツリー内でレベル1まで続きます。レベル1では、ピア4はその間隔で数値的に最も低いノードIDを持っているため、間隔I（1,4）に関連付けられたツリーノードにそのレコードを保存します。次に、ピア4はルートレベルに続き、そこでピアはRedirServiceProviderレコードを格納し、ルートレベルに達してから上方へのウォークを終了します。ピア4もレベル2から開始して下向きのウォークを行います。ピア4がインターバルI（2,4）の唯一のピアであるため、下向きのウォークはレベル2で停止します。
This subsection gives an example of peer 5 whose Node-ID is 5 performing a service lookup operation in the ReDiR tree shown in Figure 4. This is the first service lookup peer 5 carries out, and thus, the service lookup starts from the default starting level 2. As the first action, peer 5 fetches the tree node corresponding to the interval I(2,5) from the starting level. This interval maps to the second tree node from the left at level 2 since that tree node is responsible for the interval (third interval from left) to which Node-ID 5 falls at level 2. Having fetched the tree node, peer 5 checks its contents. First, there is a successor, peer 7, present in the tree node. Therefore, Condition 1 of Section 4.5 is false, and there is no need to perform an upward walk. Second, Node-ID 5 is the highest Node-ID in its interval, so Condition 2 of Section 4.5 is also false, and there is no need to perform a downward walk. Thus, the service lookup finishes at level 2 since Node-ID 7 is the closest successor of peer 5.
このサブセクションでは、図4に示すReDiRツリーでノードIDが5のサービスルックアップ操作を実行するピア5の例を示します。これは、ピア5が実行する最初のサービスルックアップであり、したがって、サービスルックアップはデフォルトの開始から始まります。レベル2。最初のアクションとして、ピア5は開始レベルから間隔I（2,5）に対応するツリーノードをフェッチします。この間隔は、レベル2で左から2番目のツリーノードにマップされます。これは、そのツリーノードがノードID 5がレベル2に落ちる間隔（左から3番目の間隔）を担当するためです。ピア5は、ツリーノードをフェッチすると、そのノードをチェックします。内容。まず、ツリーノードに存在する後続のピア7があります。したがって、セクション4.5の条件1は偽であり、上方向のウォークを実行する必要はありません。第2に、ノードID 5はその間隔で最も高いノードIDであるため、セクション4.5の条件2も偽であり、下降ウォークを実行する必要はありません。したがって、ノードID 7はピア5の最も近い後続ノードであるため、サービスルックアップはレベル2で終了します。
Note that the service lookup procedure would be slightly different if peer 5 used level 3 as the starting level. Peer 5 might use this starting level, for instance, if it has already carried out service lookups in the past and follows the heuristic in Section 4.2 to select the starting level. In this case, peer 5's first action is to fetch the tree node at level 3 that is responsible for I(3,5). Thus, peer 5 fetches the third tree node from the left. Since this tree node is empty, peer 5 decreases the current level by one to 2 and thus continues up in the tree. The next action peer 5 performs is identical to the single action in the previous example of fetching the node associated with I(2,5) from level 2. Thus, the service lookup finishes at level 2.
ピア5がレベル3を開始レベルとして使用した場合、サービス検索手順は少し異なることに注意してください。ピア5は、たとえば、過去にサービス検索をすでに実行していて、セクション4.2のヒューリスティックに従って開始レベルを選択する場合に、この開始レベルを使用する場合があります。この場合、ピア5の最初のアクションは、I（3,5）を担当するレベル3のツリーノードをフェッチすることです。したがって、ピア5は左から3番目のツリーノードをフェッチします。このツリーノードは空なので、ピア5は現在のレベルを1から2に減らし、ツリー内で上に進みます。ピア5が実行する次のアクションは、レベル2からI（2,5）に関連付けられたノードをフェッチする前の例の単一のアクションと同じです。したがって、サービスのルックアップはレベル2で終了します。
This document extends the RELOAD overlay configuration document defined in the RELOAD base protocol specification [RFC6940] by adding a new element, "branching-factor", inside the new "REDIR" kind element:
このドキュメントは、RELOADベースプロトコル仕様[RFC6940]で定義されているRELOADオーバーレイ構成ドキュメントを拡張し、新しい "REDIR"種類の要素内に新しい要素 "branching-factor"を追加します。
redir:branching-factor: The branching factor of the ReDiR tree. The default value is 10.
redir：branching-factor：ReDiRツリーの分岐係数。デフォルト値は10です。
The RELAX NG grammar for this element is:
この要素のRELAX NG文法は次のとおりです。
namespace redir = "urn:ietf:params:xml:ns:p2p:redir"
parameter &= element redir:branching-factor { xsd:unsignedInt }? The 'redir' namespace is added into the <mandatory-extension> element in the overlay configuration file.
パラメータ＆=要素redir：branching-factor {xsd：unsignedInt}？ 'redir'名前空間は、オーバーレイ構成ファイルの<mandatory-extension>要素に追加されます。
This document defines a new access control policy called NODE-ID-MATCH (see Section 5) whose purpose is to control which nodes in the overlay are allowed read and write access to the ReDiR tree nodes. The NODE-ID-MATCH access control policy ensures that the only node in the overlay that can store a pointer to a specific service provider in the ReDiR tree is the service provider itself. This prevents attacks where a malicious node inserts pointers to other nodes in the ReDiR tree. Further, the NODE-ID-MATCH access control policy ensures that a node can only store information in locations in the ReDiR tree where it is entitled to do so. In other words, a node can only store one RedirServiceProvider record at any given level in the ReDiR tree. This prevents an attack where a malicious node is trying to insert a high number of pointers to the ReDiR tree.
このドキュメントでは、NODE-ID-MATCH（セクション5を参照）と呼ばれる新しいアクセス制御ポリシーを定義しています。このポリシーの目的は、オーバーレイのどのノードにReDiRツリーノードへの読み取りおよび書き込みアクセスを許可するかを制御することです。 NODE-ID-MATCHアクセス制御ポリシーは、ReDiRツリー内の特定のサービスプロバイダーへのポインターを格納できるオーバーレイ内の唯一のノードがサービスプロバイダー自体であることを保証します。これにより、悪意のあるノードがReDiRツリー内の他のノードへのポインターを挿入する攻撃を防ぎます。さらに、NODE-ID-MATCHアクセス制御ポリシーは、ノードがReDiRツリー内の場所にしか情報を格納できないようにします。言い換えると、ノードはReDiRツリーの任意のレベルで1つのRedirServiceProviderレコードのみを保存できます。これにより、悪意のあるノードが多数のポインタをReDiRツリーに挿入しようとする攻撃を防ぐことができます。
When it comes to attacks such as a malicious node refusing to store a value or denying knowledge of a value it has previously accepted, such security concerns are already discussed in the RELOAD base specification [RFC6940].
悪意のあるノードが値を格納することを拒否したり、以前に受け入れた値の知識を否定したりするなどの攻撃に関しては、そのようなセキュリティの懸念はRELOAD基本仕様[RFC6940]ですでに説明されています。
This document adds a new access control policy to the "RELOAD Access Control Policies" registry:
このドキュメントは、「RELOAD Access Control Policies」レジストリに新しいアクセスコントロールポリシーを追加します。
NODE-ID-MATCH
ノードIDマッチ
This access control policy was described in Section 5.
このアクセス制御ポリシーは、セクション5で説明されています。
This document registers one new URI for the 'redir' namespace in the "IETF XML Registry" defined in [RFC3688].
このドキュメントは、[RFC3688]で定義されている「IETF XMLレジストリ」の「redir」名前空間に1つの新しいURIを登録します。
URI: urn:ietf:params:xml:ns:p2p:redir
Registrant Contact: The IESG
登録者の連絡先：IESG
XML: N/A, the requested URI is an XML namespace
XML：N / A、リクエストされたURIはXML名前空間です
This document adds one new data Kind-ID to the "RELOAD Data Kind-ID" registry:
このドキュメントは、「RELOAD Data Kind-ID」レジストリに1つの新しいデータKind-IDを追加します。
+--------------+------------+-----------+
| Kind | Kind-ID | RFC |
+--------------+------------+-----------+
| REDIR | 0x104 | [RFC7374] |
+--------------+------------+-----------+
This Kind-ID was defined in Section 6.
この種類IDはセクション6で定義されています。
IANA has created a new registry for ReDiR namespaces:
IANAはReDiR名前空間の新しいレジストリを作成しました：
Registry Name: RELOAD Services Registry
レジストリ名：RELOADサービスレジストリ
Reference: [RFC7374]
参照：[RFC7374]
Registration Procedure: Specification Required
登録手順：仕様が必要
Entries in this registry are strings denoting ReDiR namespace values. The initial contents of this registry are:
このレジストリのエントリは、ReDiR名前空間の値を示す文字列です。このレジストリの初期内容は次のとおりです。
+----------------+-----------+
| Namespace | RFC |
+----------------+-----------+
| turn-server | [RFC7374] |
+----------------+-----------+
| voice-mail | [RFC7374] |
+----------------+-----------+
The namespace 'turn-server' is used by nodes that wish to register as providers of a TURN relay service in the RELOAD overlay and by nodes that wish to discover providers of a TURN relay service from the RELOAD overlay. In the TURN server discovery use case, the ReDiR-based service discovery and registration mechanism specified in this document can be used as an alternative to the TURN server discovery mechanism specified in the RELOAD base specification [RFC6940]. The namespace 'voice-mail' is intended for a voice mail service implemented on top of a RELOAD overlay.
名前空間「turn-server」は、RELOADオーバーレイでTURNリレーサービスのプロバイダーとして登録するノードと、RELOADオーバーレイからTURNリレーサービスのプロバイダーを検出するノードで使用されます。 TURNサーバー検出のユースケースでは、このドキュメントで指定されているReDiRベースのサービス検出と登録メカニズムを、RELOAD基本仕様[RFC6940]で指定されているTURNサーバー検出メカニズムの代わりとして使用できます。名前空間「voice-mail」は、RELOADオーバーレイの上に実装されたボイスメールサービスを対象としています。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>.
[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するキーワード」、BCP 14、RFC 2119、1997年3月、<http://www.rfc-editor.org/info/rfc2119>。
[RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 (SHA1)", RFC 3174, September 2001, <http://www.rfc-editor.org/info/rfc3174>.
[RFC3174] Eastlake、D。およびP. Jones、「US Secure Hash Algorithm 1（SHA1）」、RFC 3174、2001年9月、<http://www.rfc-editor.org/info/rfc3174>。
[RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO 10646", STD 63, RFC 3629, November 2003, <http://www.rfc-editor.org/info/rfc3629>.
[RFC3629] Yergeau、F。、「UTF-8、ISO 10646の変換フォーマット」、STD 63、RFC 3629、2003年11月、<http://www.rfc-editor.org/info/rfc3629>。
[RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, January 2004, <http://www.rfc-editor.org/info/rfc3688>.
[RFC3688] Mealling、M。、「The IETF XML Registry」、BCP 81、RFC 3688、2004年1月、<http://www.rfc-editor.org/info/rfc3688>。
[RFC6940] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) Base Protocol", RFC 6940, January 2014, <http://www.rfc-editor.org/info/rfc6940>.
[RFC6940] Jennings、C.、Lowekamp、B.、Rescorla、E.、Baset、S。、およびH. Schulzrinne、「REsource LOcation And Discovery（RELOAD）Base Protocol」、RFC 6940、2014年1月、<http：/ /www.rfc-editor.org/info/rfc6940>。
[Redir] Rhea, S., Godfrey, B., Karp, B., Kubiatowicz, J., Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "OpenDHT: A Public DHT Service and Its Uses", October 2005.
[Redir] Rhea、S.、Godfrey、B.、Karp、B.、Kubiatowicz、J.、Ratnasamy、S.、Shenker、S.、Stoica、I。、およびH. Yu、「OpenDHT：A Public DHT Serviceとその用途」、2005年10月。
Acknowledgments
謝辞
The authors would like to thank Marc Petit-Huguenin, Joscha Schneider, Carlos Bernardos, Spencer Dawkins, Barry Leiba, Adrian Farrel, Alexey Melnikov, Ted Lemon, and Stephen Farrell for their comments on the document.
この文書に関するコメントを提供してくれたMarc Petit-Huguenin、Joscha Schneider、Carlos Bernardos、Spencer Dawkins、Barry Leiba、Adrian Farrel、Alexey Melnikov、Ted Lemon、Stephen Farrellに感謝します。
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