Internet Engineering Task Force (IETF) J. Maenpaa
Request for Comments: 7363 G. Camarillo
Category: Standards Track Ericsson
ISSN: 2070-1721 September 2014
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)
用于资源定位和发现的自调优分布式哈希表（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.
资源定位和发现（RELOAD）是一种提供覆盖网络服务的对等（P2P）信令协议。重载覆盖网络中的对等节点共同运行覆盖算法来组织覆盖并存储和检索数据。本文档描述了如何扩展RELOAD的默认拓扑插件以支持自调整，即适应不断变化的操作条件，如客户流失和网络规模。
Status of This Memo
关于下段备忘
This is an Internet Standards Track document.
这是一份互联网标准跟踪文件。
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 5741.
本文件是互联网工程任务组（IETF）的产品。它代表了IETF社区的共识。它已经接受了公众审查，并已被互联网工程指导小组（IESG）批准出版。有关互联网标准的更多信息，请参见RFC 5741第2节。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/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.
版权所有（c）2014 IETF信托基金和确定为文件作者的人员。版权所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
本文件受BCP 78和IETF信托有关IETF文件的法律规定的约束(http://trustee.ietf.org/license-info)自本文件出版之日起生效。请仔细阅读这些文件，因为它们描述了您对本文件的权利和限制。从本文件中提取的代码组件必须包括信托法律条款第4.e节中所述的简化BSD许可证文本，并提供简化BSD许可证中所述的无担保。
Table of Contents
目录
1. Introduction ....................................................2
2. Terminology .....................................................3
3. 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
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.
资源定位和发现（RELOAD）[RFC6940]是一种对等信令协议，可用于维护覆盖网络，并在覆盖中存储数据和从覆盖中检索数据。出于互操作性的原因，RELOAD指定了一种覆盖算法，称为“chord RELOAD”，这是必须实现的。本文档通过引入自调优行为扩展了chord重载算法。
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
基于DHT的覆盖网络是自组织、可扩展和可靠的。然而，这些特性是有代价的：覆盖网络中的对等方需要消耗网络带宽来维持路由
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。这种方法的问题在于，不可能通过使用固定参数来实现低故障率和低通信开销。相反，更好的方法是允许系统考虑网络条件的演变并适应它们。
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.
本文档通过自调整扩展了强制实现chord重载算法。使用自调整功能是可选的。但是，在使用时，它需要得到重新加载覆盖网络中所有对等方的支持。重载覆盖使用自调整功能的事实在重载覆盖配置文档中使用拓扑插件元素第9.2节中指定的CHORD自调整算法名称进行了说明。自调整的两个主要优点是，用户不再需要针对给定的操作环境正确调整每个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节讨论了DHTs中稳定操作的替代方法，包括反应稳定、周期稳定和自适应稳定。第4节介绍Chord 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].
本文件中的关键词“必须”、“不得”、“必需”、“应”、“不应”、“建议”、“不建议”、“可”和“可选”应按照[RFC2119]中的说明进行解释。
This document uses terminology and definitions from the RELOAD base specification [RFC6940].
本文件使用重新加载基础规范[RFC6940]中的术语和定义。
numBitsInNodeId: Specifies the number of bits in a RELOAD Node-ID.
NumbitsinodeId：指定重新加载节点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
DHT：分布式哈希表是一类分散的分布式系统，提供类似于常规哈希表的查找服务。给定密钥后，参与
system can retrieve the value associated with that key. The responsibility for maintaining the mapping from keys to values is distributed among the peers.
系统可以检索与该键关联的值。维护从键到值的映射的责任在对等点之间分配。
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.
手指表：一种数据结构，由每个对等方在基于弦的覆盖中维护多达（但通常少于）个numBitsInNodeId条目。对等点n的finger表中的第i个条目包含在弦环上以至少2^（numBitsInNodeId-i）的方式继承n的第一个对等点的标识。这个节点称为节点n的第i个手指。例如，对等点n的finger表中的第一个条目包含一个位于对等点n的弦环中间的对等点。手指表的目的是加速查找。
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].
ω（g（n））：非正式地说，一些方程f（n）=ω（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=（P/100）*N，将结果四舍五入到最接近的整数，然后取对应于该秩的值，以升序排列的N个值的Pth（0<=P<=100）百分位。
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.
邻域集：一个术语，用于指包含在给定对等点的后续和先前列表中的对等点集。
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.
路由表：给定对等方路由表的内容包括对等方可用于路由覆盖消息的对等方集。路由表由手指表、后续列表和前置列表组成。
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使用稳定程序来应对客户流失对路由的不良影响。稳定化的目的是使覆盖中每个节点的路由信息与不断变化的覆盖拓扑保持一致。有两种可供选择的稳定方法：周期性和反应性[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]中进行的实验中，反应稳定在没有搅动的情况下表现良好，但观察到其带宽使用在搅动下急剧增加。在较高的流失率和较大规模的覆盖下，周期性稳定使用较少的带宽，由此产生的较低的网络争用导致较低的延迟。由于这个原因，大多数DHT，如罐头[CAN]、和弦[Chord]、糕点[Pastry]和竹子[Rhea2004]，都使用周期稳定[Ghinita2006]。例如，竹子的第一个版本使用了反应稳定，这导致竹子在搅拌下性能下降。为了解决这个问题，竹被修改为使用周期稳定。
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算法，需要为以下参数选择值：后续列表的大小、稳定间隔和finger表的大小。要为稳定区间选择合适的值，需要知道预期的流失率和覆盖大小。根据
[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]，只要节点在N个新节点加入或N/2个节点失败之前发送Omega（square（log（N）））消息，处于环形状态的Chord网络将保持环形状态。因此，在以每30秒一个对等方加入和一个对等方离开网络的速率搅动的500个对等方覆盖中，适当的稳定间隔大约为93秒。根据[Chord]，后续列表和finger表的大小应为log（N）的顺序。已经有一个中等大小的后继列表（例如，log2（N）或2*log2（N），这是[Chord]中使用的后继列表大小）使得对等方不太可能丢失其所有后继列表，这将导致弦环断开连接。因此，在500个对等网络中，每个对等网络应保持9个继承者和手指的顺序。但是，如果客户流失率翻倍，网络规模保持不变，那么稳定率也应该翻倍。也就是说，适当的维护间隔现在大约为46秒。另一方面，如果客户流失率变为（例如）六倍，并且网络规模增长到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]是一种结构化P2P算法，它使用一致性哈希从几个独立的对等点构建DHT。一致哈希为每个对等方和资源分配一个固定长度的标识符。对等方使用SHA-1作为基本哈希函数来生成标识符。按照RELOAD base[RFC6940]中的规定，标识符的长度为numbitInnodeId=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.
一个简单的查找机制可以通过要求每个对等方只知道如何联系标识符圆上的当前后续方而在弦环上实现。然后，对给定标识符的查询可以通过后续指针在圆中传递，直到遇到标识符等于或大于所需标识符的第一个对等方。这种查找方案使用的消息数量与对等方的数量成线性增长。为了降低查找成本，Chord还维护了额外的路由信息；每个对等节点n维护一个数据结构，其中最多有numBitsInNodeId条目，称为finger表。对等点n的手指表中的第一个条目包含位于对等点n环中间的对等点。第二个条目包含四分之一左右的对等方，第三个条目包含八分之一左右的对等方，等等。换句话说，对等方n的手指表中的第i个条目包含第一个对等方s的标识，该对等方s在和弦环上以至少2^（Numbitsinodeid-i）的速度成功n。这个节点称为节点n的第i个手指。两个连续手指之间的间隔称为手指间隔。对等点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需要所有对等点的后续指针都是最新的，以确保在参与对等点集发生更改时查找产生正确的结果。为了实现这一点，对等方在后台定期运行稳定协议。原始Chord算法的稳定协议使用两种操作：后继稳定和手指稳定。然而，重新加载基座的弦算法定义了两个额外的稳定组件，如下所述。
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 base[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算法支持反应式和周期性恢复策略。当使用本文档中定义的自调优机制时，将使用定期恢复策略。此外，chord reload指定至少需要维护三个前辈和三个后辈。当使用自调整机制时，后继列表和前置列表的适当大小根据估计的网络大小以自适应方式确定，如第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 base[RFC6940]中的规定，每个对等机都维护一个稳定计时器。当稳定定时器触发时，对等方重启定时器并执行叠加稳定例程。叠加稳定在弦杆重新加载中有四个组件：
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 base[RFC6940]中的规定，对等方定期发送消息，作为邻居稳定、手指稳定和强稳定例程的一部分。在邻居稳定中，对等方定期向其连接表中的每个对等方发送更新请求。默认时间为每十分钟一次。在手指稳定中，对等点定期搜索新的对等点以包括在其手指表中。此时间默认为一小时。本文件规定了如何根据叠加的操作条件以自适应方式确定相邻稳定和手指稳定间隔。以下各小节描述了本文件如何扩展稳定的四个组成部分。
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 base[RFC6940]中所述，使用更新请求实现邻居和手指稳定程序。RELOAD base定义了三种类型的更新请求：“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.
“邻居”和“满”。无论类型如何，所有更新请求都包含“正常运行时间”字段。自调优扩展需要路由表中对等方的正常运行时间信息。更新请求的发送方在“正常运行时间”字段中包含其当前正常运行时间（以秒为单位）。无论类型如何，所有更新请求都必须包含“正常运行时间”字段。
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[RFC6940]中的规定，可变长度字段在导线上以长度字节开头。对于后继列表、前置列表和手指表，有两个长度字节（允许最大长度为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.
在chord-reload的邻居稳定操作中，对等方定期向其连接表中的每个对等方发送更新请求。在一个小的、低流失率的覆盖中，这个过程产生的流量通常是可以接受的。然而，在中等或高搅动率的大规模覆盖搅动中，由于连接表的大小较大且稳定间隔相对较短，因此流量负载可能不再是可接受的。本文档中描述的自调整机制是专门为后一种类型的覆盖层设计的。因此，当使用自调优机制时，每个对等方仅向弦环上的其第一前导和第一后继发送周期性更新请求；它不能向其他人发送更新请求。
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表的新对等点的替代方法。这两个备选方案都可以与本文档中定义的自调优扩展一起使用。
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 base[RFC6940]中定义的ProbeInformation类型“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算法定义了对等方如何确保finger表的大小适当，以实现高效路由。由于本文档中指定的自调整机制产生网络大小估计，因此此估计可直接用于计算手指表的最佳大小。使用此机制代替和弦重新加载指定的机制。对等方使用网络大小估计值来确定是否需要在每次稳定计时器启动时调整其手指表的大小。第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
按照RELOAD base[RFC6940]中的规定，离开对等方应在离开覆盖之前向其邻居表的所有成员发送一个离开请求。“覆盖特定数据”字段必须包含ChordLeaveData结构。发送给继任者的休假请求包含离职对等者的前任列表。发送给前辈的请假请求包含离职同辈的继任者列表。如果一个给定的继承者能够识别出比现有继承者更好的继承者（即，在弦环上与其更接近的继承者）
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.
通过调查从离开的对等方收到的前置列表，它已经包含在前置列表中，并向它们发送附加请求。类似地，如果给定的前置机通过调查从离开的对等机接收到的后续机列表来识别更好的后续机，那么它会向它们发送附加请求。
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。为了计算适当的路由表大小，可以使用估计的网络大小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]、[Horowitz 2003]、[Kostoulas2005]、[Binzenhofer2006]和[Ghinita2006]中提出了估计覆盖网络大小的技术。在Chord中，邻域集中对等标识符的密度可用于产生覆盖大小的估计值N[Mahajan2003]。由于对等标识符是以统一的概率从Numbitsinodeid位标识符空间随机选取的，因此后续集合中对等标识符之间的平均距离为（2^Numbitsinodeid）/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
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.
在加入过程中，加入的对等方通过发送一系列Ping和Attach请求来填充其路由表，如RELOAD base[RFC6940]中所述。因此，加入的对等方立即拥有足够的信息来计算网络大小的估计值。
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 base[RFC6940]中的规定，finger表必须至少包含16个条目。使用自调优机制时，必须使用估计的网络大小N将finger表的大小设置为max（天花板（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））。实现可以对后续列表的大小设置较低的限制。例如，实现可能要求后续列表的大小始终至少为三个。
The size of the predecessor list MUST be set to ceiling(log2(N)).
前置列表的大小必须设置为上限（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
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
故障历史K的大小影响U估计的准确性。可以通过增加K来提高准确性。但是，这会降低对故障率变化的响应性。另一方面，历史规模较小
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.
每次发生新故障时，可能会导致对等方反应过度。在[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是交互式连接建立（ICE）[RFC5245]定义的非活动计时器），则必须向远程对等方发送重新加载Ping请求。RELOAD强制使用NAT（STUN）[RFC5389]的会话遍历实用程序进行keepalives。STUN keepalives采用STUN绑定指示事务的形式。如ICE[RFC5245]中所述，如果在Tr秒的连接上没有发送数据包，则对等方发送STUN绑定指示。Tr是可配置的，默认值为15秒。尽管STUN绑定指示不会生成响应，但可以从缺少从对等方接收的数据包（绑定指示或应用程序协议数据包）中了解对等方失败的事实。如果远程对等体无法答复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 keepalives检测对等故障的替代方法，对等机可以向其连接表中的每个对等机发送额外的、频繁的重新加载消息。这些消息可以是更新请求，在这种情况下，它们将用于两个目的：检测对等故障和稳定。但是，由于这种方法在带宽消耗和流量负载方面的成本可能非常高，特别是在遇到客户流失的大规模覆盖中，因此不建议使用这种方法。
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)]
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是一个数组，包含路由表中的对等方的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.
为了使这一机制发挥作用，对等体需要交换有关它们在覆盖中出现的时间的信息。由于所有更新请求都带有正常运行时间值，因此对等点在稳定操作期间接收其后继和前辈的正常运行时间。加入的对等方了解加入对等方的正常运行时间，因为它在加入过程中从加入对等方接收更新。对等点了解新手指的正常运行时间，因为它们可以在连接到新手指后使用探测请求获取正常运行时间。
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:
为了提高网络大小、加入速率和离开速率估计的准确性，对等方共享其估计。当稳定计时器启动时，对等方选择若干对等方从其手指表中探测随机对等方，并向每个对等方发送探测请求。探测请求的目标是从finger表而不是邻居表中选择的，因为邻居在计算其估计值时可能会犯类似的错误。要探测的对等点的数量是覆盖配置文档中的新元素。第7节对其进行了定义。目标对等方返回的探测请求和应答都必须包含一个新的消息扩展，其MessageExtensionType为“self_tuning_data”。该扩展类型在第9.1节中定义。MessageExtension结构的“extension_contents”字段必须包含自调优数据结构：
struct {
uint32 network_size;
uint32 join_rate;
uint32 leave_rate;
} SelfTuningData;
struct {
uint32 network_size;
uint32 join_rate;
uint32 leave_rate;
} SelfTuningData;
The contents of the SelfTuningData structure are as follows:
自调优数据结构的内容如下：
network_size
网络规模
The latest network size estimate calculated by the sender.
发送方计算的最新网络大小估计值。
join_rate
加入率
The latest join rate estimate calculated by the sender.
发送方计算的最新加入速率估计值。
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 peers/s，则它将在“加入速率”字段中包括值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\u tuning\u data”。结构的“临界”字段必须设置为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个百分位（即第三个四分位）来计算下一个稳定间隔期间要使用的估计值。
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.
要探测的对等节点数的默认值为4。建议使用此默认值，以允许对等方从其他对等方接收足够大的估计集。如果值为4，则对等方将收到探测答案中的四个估计值。平均而言，每个对等方还接收到四个探测请求，每个请求都带有一个估计值。因此，平均而言，每个对等体都有九个估计值（包括自己的估计值），可以在稳定区间结束时使用。不建议使用小于4的值来保持收到的估计数足够高。例如，如果值为2，则叠加中的对等点在稳定间隔期间仅接收两个估计值。在时间间隔结束时，此类同行只有三个估计值可用，这可能不够可靠，因为即使是一个非常高或非常低的估计值也可能产生很大的影响。
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
1
Tf = ------
2*U
Based on this estimate, a stabilization interval Tstab-1 is calculated as:
根据该估算，稳定区间Tstab-1计算如下：
Tf
Tstab-1 = -----------------
square(log2(N))
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))
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-1和Tstab-2中的最小值，可以获得所使用的实际稳定间隔Tstab。
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.
本文档通过在每个“配置”元素中添加一个新元素“要探测的对等节点数”，扩展了重载覆盖配置文档。
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.
自调整：要探测的对等方数：探测请求被发送到的手指数，以获取其网络大小、加入速率和离开速率估计值。默认值为4。
The RELAX NG grammar for this element is:
此元素的RELAX NG语法为：
namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning"
namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning"
parameter &= element self-tuning:number-of-peers-to-probe {
xsd:unsignedInt }?
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.
与实施重新加载基本协议[RFC6940]的恶意或受损对等方可以公布虚假网络度量或分发虚假路由表信息（例如在重新加载更新消息中）的方式相同，实施本规范的恶意对等方可以共享虚假加入率、离开率和网络大小估计。对于此类攻击，与重新加载基本规范中的安全问题相同。此外，只要覆盖中恶意对等体的数量保持适度，第6.5节中应用的统计机制（即，使用第75百分位）处理对等体获得的共享估计值有助于确保估计值明显不同于（即，大于或小于）其他收到的估计不会显著影响调整稳定间隔和路由表大小的过程。但是，应该注意的是，如果攻击者能够在战略位置模拟覆盖中的大量其他对等方，则它可能能够向受害者发送足够多的错误估计，从而影响受害者对稳定间隔的选择。
This document introduces one additional extension to the "RELOAD Extensions Registry":
本文档为“重新加载扩展注册表”引入了一个附加扩展：
+------------------+-------+---------------+
| Extension Name | Code | Specification |
+------------------+-------+---------------+
| self_tuning_data | 0x3 | RFC 7363 |
+------------------+-------+---------------+
+------------------+-------+---------------+
| 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:
本文档在“重新加载覆盖算法类型”注册表中引入了一种额外的覆盖算法类型：
+-------------------+-----------+
| Algorithm Name | Reference |
+-------------------+-----------+
| CHORD-SELF-TUNING | RFC 7363 |
+-------------------+-----------+
+-------------------+-----------+
| 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。
URI: urn:ietf:params:xml:ns:p2p:self-tuning
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对该文件的贡献。作者还要感谢卡洛斯·贝尔纳多斯、马丁·杜斯特、艾莉莎·库珀、托比亚斯·冈德罗姆和巴里·莱巴对该文件的评论。
[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.，“交互式连接建立（ICE）：提供/应答协议的网络地址转换器（NAT）遍历协议”，RFC 52452010年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，“资源定位和发现（重新加载）基本协议”，RFC 69402014年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.
[Binzenhofer 2006]Binzenhofer，A.，Kunzmann，G.，和R.Henjes，“运行时监控基于Chord的P2P系统的可伸缩算法”，发表于第20届IEEE国际并行和分布式处理研讨会（IPDPS）论文集，第1-8页，2006年4月。
[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.，和S.Schenker，“可扩展内容寻址网络”，2001年计算机通信应用、技术、架构和协议会议记录，第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.
[Chord]Stoica，I.，Morris，R.，Liben Nowell，D.，Karger，D.，Kaashoek，M.，Dabek，F.，和H.Balakrishnan，“Chord：互联网应用的可扩展对等查找服务”，IEEE/ACM网络交易，第11卷，第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]Ghinta，G.和Y.Teo，“分布式哈希表的自适应稳定框架”，载于第20届IEEE国际并行和分布式处理研讨会（IPDPS）论文集，第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.
[Horowitz 2003]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，“大型动态群体规模估算的分散方案”，载于第四届IEEE网络计算和应用国际研讨会论文集，第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.，和S.Haridi，“覆盖层维护策略的比较”，载于第16届欧洲微并行、分布式和基于网络的处理会议记录，第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.，和M.Kaashoek，“在搅动下比较分布式哈希表的性能”，点对点系统III，计算机科学课堂讲稿3279卷，Springer，第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-Nowell 2002]Liben-Nowell，D.，Balakrishnan，H.，和D.Karger，“对等网络动态演化的观察”，载于第一届对等系统国际研讨会论文集，第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，“基于Chord的对等会话发起协议覆盖网络中的维护操作研究”，载于第23届IEEE国际并行和分布式处理研讨会（IPDPS）论文集，第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.
[Mahajan 2003]Mahajan，R.，Castro，M.，和A.Rowstron，“控制点对点覆盖的可靠性成本”，载于第二届点对点系统（IPTP）国际研讨会论文集，第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分布式系统平台国际会议记录，第329-350页，2001年11月。
[RFC3688] Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688, January 2004.
[RFC3688]Mealling，M.“IETF XML注册表”，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年度技术会议记录》，第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.，第二版，ISBN 020361221998。
Authors' Addresses
作者地址
Jouni Maenpaa Ericsson Hirsalantie 11 Jorvas 02420 Finland
Jouni Maenpaa Ericsson Hirsalantie 11 Jorvas 02420芬兰
EMail: Jouni.Maenpaa@ericsson.com
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
EMail: Gonzalo.Camarillo@ericsson.com