| 1 |
<pre>Internet Engineering Task Force (IETF) J. Maenpaa |
| 2 |
Request for Comments: 7363 G. Camarillo |
| 3 |
Category: Standards Track Ericsson |
| 4 |
ISSN: 2070-1721 September 2014 |
| 5 |
|
| 6 |
|
| 7 |
<span class="h1">Self-Tuning Distributed Hash Table (DHT)</span> |
| 8 |
<span class="h1">for REsource LOcation And Discovery (RELOAD)</span> |
| 9 |
|
| 10 |
Abstract |
| 11 |
|
| 12 |
REsource LOcation And Discovery (RELOAD) is a peer-to-peer (P2P) |
| 13 |
signaling protocol that provides an overlay network service. Peers |
| 14 |
in a RELOAD overlay network collectively run an overlay algorithm to |
| 15 |
organize the overlay and to store and retrieve data. This document |
| 16 |
describes how the default topology plugin of RELOAD can be extended |
| 17 |
to support self-tuning, that is, to adapt to changing operating |
| 18 |
conditions such as churn and network size. |
| 19 |
|
| 20 |
Status of This Memo |
| 21 |
|
| 22 |
This is an Internet Standards Track document. |
| 23 |
|
| 24 |
This document is a product of the Internet Engineering Task Force |
| 25 |
(IETF). It represents the consensus of the IETF community. It has |
| 26 |
received public review and has been approved for publication by the |
| 27 |
Internet Engineering Steering Group (IESG). Further information on |
| 28 |
Internet Standards is available in <a href="./rfc5741#section-2">Section 2 of RFC 5741</a>. |
| 29 |
|
| 30 |
Information about the current status of this document, any errata, |
| 31 |
and how to provide feedback on it may be obtained at |
| 32 |
<a href="http://www.rfc-editor.org/info/rfc7363">http://www.rfc-editor.org/info/rfc7363</a>. |
| 33 |
|
| 34 |
Copyright Notice |
| 35 |
|
| 36 |
Copyright (c) 2014 IETF Trust and the persons identified as the |
| 37 |
document authors. All rights reserved. |
| 38 |
|
| 39 |
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal |
| 40 |
Provisions Relating to IETF Documents |
| 41 |
(<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of |
| 42 |
publication of this document. Please review these documents |
| 43 |
carefully, as they describe your rights and restrictions with respect |
| 44 |
to this document. Code Components extracted from this document must |
| 45 |
include Simplified BSD License text as described in Section 4.e of |
| 46 |
the Trust Legal Provisions and are provided without warranty as |
| 47 |
described in the Simplified BSD License. |
| 48 |
|
| 49 |
|
| 50 |
|
| 51 |
|
| 52 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 1]</span></pre> |
| 53 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span> |
| 54 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 55 |
|
| 56 |
|
| 57 |
Table of Contents |
| 58 |
|
| 59 |
<a href="#section-1">1</a>. Introduction ....................................................<a href="#page-2">2</a> |
| 60 |
<a href="#section-2">2</a>. Terminology .....................................................<a href="#page-3">3</a> |
| 61 |
<a href="#section-3">3</a>. Introduction to Stabilization in DHTs ...........................<a href="#page-5">5</a> |
| 62 |
<a href="#section-3.1">3.1</a>. Reactive versus Periodic Stabilization .....................<a href="#page-5">5</a> |
| 63 |
<a href="#section-3.2">3.2</a>. Configuring Periodic Stabilization .........................<a href="#page-6">6</a> |
| 64 |
<a href="#section-3.3">3.3</a>. Adaptive Stabilization .....................................<a href="#page-7">7</a> |
| 65 |
<a href="#section-4">4</a>. Introduction to Chord ...........................................<a href="#page-7">7</a> |
| 66 |
<a href="#section-5">5</a>. Extending Chord-Reload to Support Self-Tuning ...................<a href="#page-9">9</a> |
| 67 |
<a href="#section-5.1">5.1</a>. Update Requests ............................................<a href="#page-9">9</a> |
| 68 |
<a href="#section-5.2">5.2</a>. Neighbor Stabilization ....................................<a href="#page-10">10</a> |
| 69 |
<a href="#section-5.3">5.3</a>. Finger Stabilization ......................................<a href="#page-11">11</a> |
| 70 |
<a href="#section-5.4">5.4</a>. Adjusting Finger Table Size ...............................<a href="#page-11">11</a> |
| 71 |
<a href="#section-5.5">5.5</a>. Detecting Partitioning ....................................<a href="#page-11">11</a> |
| 72 |
<a href="#section-5.6">5.6</a>. Leaving the Overlay .......................................<a href="#page-11">11</a> |
| 73 |
<a href="#section-6">6</a>. Self-Tuning Chord Parameters ...................................<a href="#page-12">12</a> |
| 74 |
<a href="#section-6.1">6.1</a>. Estimating Overlay Size ...................................<a href="#page-12">12</a> |
| 75 |
<a href="#section-6.2">6.2</a>. Determining Routing Table Size ............................<a href="#page-13">13</a> |
| 76 |
<a href="#section-6.3">6.3</a>. Estimating Failure Rate ...................................<a href="#page-13">13</a> |
| 77 |
<a href="#section-6.3.1">6.3.1</a>. Detecting Failures .................................<a href="#page-14">14</a> |
| 78 |
<a href="#section-6.4">6.4</a>. Estimating Join Rate ......................................<a href="#page-14">14</a> |
| 79 |
<a href="#section-6.5">6.5</a>. Estimate Sharing ..........................................<a href="#page-15">15</a> |
| 80 |
<a href="#section-6.6">6.6</a>. Calculating the Stabilization Interval ....................<a href="#page-17">17</a> |
| 81 |
<a href="#section-7">7</a>. Overlay Configuration Document Extension .......................<a href="#page-17">17</a> |
| 82 |
<a href="#section-8">8</a>. Security Considerations ........................................<a href="#page-18">18</a> |
| 83 |
<a href="#section-9">9</a>. IANA Considerations ............................................<a href="#page-18">18</a> |
| 84 |
<a href="#section-9.1">9.1</a>. Message Extensions ........................................<a href="#page-18">18</a> |
| 85 |
<a href="#section-9.2">9.2</a>. New Overlay Algorithm Type ................................<a href="#page-19">19</a> |
| 86 |
<a href="#section-9.3">9.3</a>. A New IETF XML Registry ...................................<a href="#page-19">19</a> |
| 87 |
<a href="#section-10">10</a>. Acknowledgments ...............................................<a href="#page-19">19</a> |
| 88 |
<a href="#section-11">11</a>. References ....................................................<a href="#page-19">19</a> |
| 89 |
<a href="#section-11.1">11.1</a>. Normative References .....................................<a href="#page-19">19</a> |
| 90 |
<a href="#section-11.2">11.2</a>. Informative References ...................................<a href="#page-20">20</a> |
| 91 |
|
| 92 |
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span> |
| 93 |
|
| 94 |
REsource LOcation And Discovery (RELOAD) [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>] is a peer-to-peer |
| 95 |
signaling protocol that can be used to maintain an overlay network |
| 96 |
and to store data in and retrieve data from the overlay. For |
| 97 |
interoperability reasons, RELOAD specifies one overlay algorithm, |
| 98 |
called "chord-reload", that is mandatory to implement. This document |
| 99 |
extends the chord-reload algorithm by introducing self-tuning |
| 100 |
behavior. |
| 101 |
|
| 102 |
DHT-based overlay networks are self-organizing, scalable, and |
| 103 |
reliable. However, these features come at a cost: peers in the |
| 104 |
overlay network need to consume network bandwidth to maintain routing |
| 105 |
|
| 106 |
|
| 107 |
|
| 108 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 2]</span></pre> |
| 109 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span> |
| 110 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 111 |
|
| 112 |
|
| 113 |
state. Most DHTs use a periodic stabilization routine to counter the |
| 114 |
undesirable effects of churn on routing. To configure the parameters |
| 115 |
of a DHT, some characteristics such as churn rate and network size |
| 116 |
need to be known in advance. These characteristics are then used to |
| 117 |
configure the DHT in a static fashion by using fixed values for |
| 118 |
parameters such as the size of the successor set, size of the routing |
| 119 |
table, and rate of maintenance messages. The problem with this |
| 120 |
approach is that it is not possible to achieve a low failure rate and |
| 121 |
a low communication overhead by using fixed parameters. Instead, a |
| 122 |
better approach is to allow the system to take into account the |
| 123 |
evolution of network conditions and adapt to them. |
| 124 |
|
| 125 |
This document extends the mandatory-to-implement chord-reload |
| 126 |
algorithm by making it self-tuning. The use of the self-tuning |
| 127 |
feature is optional. However, when used, it needs to be supported by |
| 128 |
all peers in the RELOAD overlay network. The fact that a RELOAD |
| 129 |
overlay uses the self-tuning feature is indicated in the RELOAD |
| 130 |
overlay configuration document using the CHORD-SELF-TUNING algorithm |
| 131 |
name specified in <a href="#section-9.2">Section 9.2</a> in the topology-plugin element. Two |
| 132 |
main advantages of self-tuning are that users no longer need to tune |
| 133 |
every DHT parameter correctly for a given operating environment and |
| 134 |
that the system adapts to changing operating conditions. |
| 135 |
|
| 136 |
The remainder of this document is structured as follows: <a href="#section-2">Section 2</a> |
| 137 |
provides definitions of terms used in this document. <a href="#section-3">Section 3</a> |
| 138 |
discusses alternative approaches to stabilization operations in DHTs, |
| 139 |
including reactive stabilization, periodic stabilization, and |
| 140 |
adaptive stabilization. <a href="#section-4">Section 4</a> gives an introduction to the Chord |
| 141 |
DHT algorithm. <a href="#section-5">Section 5</a> describes how this document extends the |
| 142 |
stabilization routine of the chord-reload algorithm. <a href="#section-6">Section 6</a> |
| 143 |
describes how the stabilization rate and routing table size are |
| 144 |
calculated in an adaptive fashion. |
| 145 |
|
| 146 |
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Terminology</span> |
| 147 |
|
| 148 |
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", |
| 149 |
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and |
| 150 |
"OPTIONAL" in this document are to be interpreted as described in |
| 151 |
[<a href="./rfc2119" title=""Key words for use in RFCs to Indicate Requirement Levels"">RFC2119</a>]. |
| 152 |
|
| 153 |
This document uses terminology and definitions from the RELOAD base |
| 154 |
specification [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>]. |
| 155 |
|
| 156 |
numBitsInNodeId: Specifies the number of bits in a RELOAD Node-ID. |
| 157 |
|
| 158 |
DHT: Distributed Hash Tables are a class of decentralized |
| 159 |
distributed systems that provide a lookup service similar to a |
| 160 |
regular hash table. Given a key, any peer participating in the |
| 161 |
|
| 162 |
|
| 163 |
|
| 164 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 3]</span></pre> |
| 165 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span> |
| 166 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 167 |
|
| 168 |
|
| 169 |
system can retrieve the value associated with that key. The |
| 170 |
responsibility for maintaining the mapping from keys to values is |
| 171 |
distributed among the peers. |
| 172 |
|
| 173 |
Chord Ring: The Chord DHT uses ring topology and orders identifiers |
| 174 |
on an identifier circle of size 2^numBitsInNodeId. This |
| 175 |
identifier circle is called the Chord ring. On the Chord ring, |
| 176 |
the responsibility for a key k is assigned to the node whose |
| 177 |
identifier equals to or immediately follows k. |
| 178 |
|
| 179 |
Finger Table: A data structure with up to (but typically less than) |
| 180 |
numBitsInNodeId entries maintained by each peer in a Chord-based |
| 181 |
overlay. The ith entry in the finger table of peer n contains the |
| 182 |
identity of the first peer that succeeds n by at least |
| 183 |
2^(numBitsInNodeId-i) on the Chord ring. This peer is called the |
| 184 |
ith finger of peer n. As an example, the first entry in the |
| 185 |
finger table of peer n contains a peer halfway around the Chord |
| 186 |
ring from peer n. The purpose of the finger table is to |
| 187 |
accelerate lookups. |
| 188 |
|
| 189 |
n.id: In this document, this abbreviation is used to refer to the |
| 190 |
Node-ID of peer n. |
| 191 |
|
| 192 |
O(g(n)): Informally, saying that some equation f(n) = O(g(n)) means |
| 193 |
that f(n) is less than some constant multiple of g(n). For the |
| 194 |
formal definition, please refer to [<a href="#ref-Weiss1998">Weiss1998</a>]. |
| 195 |
|
| 196 |
Omega(g(n)): Informally, saying that some equation f(n) = |
| 197 |
Omega(g(n)) means that f(n) is more than some constant multiple of |
| 198 |
g(n). For the formal definition, please refer to [<a href="#ref-Weiss1998">Weiss1998</a>]. |
| 199 |
|
| 200 |
Percentile: The Pth (0<=P<=100) percentile of N values arranged in |
| 201 |
ascending order is obtained by first calculating the (ordinal) |
| 202 |
rank n=(P/100)*N, rounding the result to the nearest integer and |
| 203 |
then taking the value corresponding to that rank. |
| 204 |
|
| 205 |
Predecessor List: A data structure containing the first r |
| 206 |
predecessors of a peer on the Chord ring. |
| 207 |
|
| 208 |
Successor List: A data structure containing the first r successors |
| 209 |
of a peer on the Chord ring. |
| 210 |
|
| 211 |
Neighborhood Set: A term used to refer to the set of peers included |
| 212 |
in the successor and predecessor lists of a given peer. |
| 213 |
|
| 214 |
|
| 215 |
|
| 216 |
|
| 217 |
|
| 218 |
|
| 219 |
|
| 220 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 4]</span></pre> |
| 221 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span> |
| 222 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 223 |
|
| 224 |
|
| 225 |
Routing Table: Contents of a given peer's routing table include the |
| 226 |
set of peers that the peer can use to route overlay messages. The |
| 227 |
routing table is made up of the finger table, successor list, and |
| 228 |
predecessor list. |
| 229 |
|
| 230 |
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Introduction to Stabilization in DHTs</span> |
| 231 |
|
| 232 |
DHTs use stabilization routines to counter the undesirable effects of |
| 233 |
churn on routing. The purpose of stabilization is to keep the |
| 234 |
routing information of each peer in the overlay consistent with the |
| 235 |
constantly changing overlay topology. There are two alternative |
| 236 |
approaches to stabilization: periodic and reactive [<a href="#ref-Rhea2004">Rhea2004</a>]. |
| 237 |
Periodic stabilization can either use a fixed stabilization rate or |
| 238 |
calculate the stabilization rate in an adaptive fashion. |
| 239 |
|
| 240 |
<span class="h3"><a class="selflink" id="section-3.1" href="#section-3.1">3.1</a>. Reactive versus Periodic Stabilization</span> |
| 241 |
|
| 242 |
In reactive stabilization, a peer reacts to the loss of a peer in its |
| 243 |
neighborhood set or to the appearance of a new peer that should be |
| 244 |
added to its neighborhood set by sending a copy of its neighbor table |
| 245 |
to all peers in the neighborhood set. Periodic recovery, in |
| 246 |
contrast, takes place independently of changes in the neighborhood |
| 247 |
set. In periodic recovery, a peer periodically shares its |
| 248 |
neighborhood set with each or a subset of the members of that set. |
| 249 |
|
| 250 |
The chord-reload algorithm [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>] supports both reactive and |
| 251 |
periodic stabilization. It has been shown in [<a href="#ref-Rhea2004">Rhea2004</a>] that |
| 252 |
reactive stabilization works well for small neighborhood sets (i.e., |
| 253 |
small overlays) and moderate churn. However, in large-scale (e.g., |
| 254 |
1000 peers or more [<a href="#ref-Rhea2004">Rhea2004</a>]) or high-churn overlays, reactive |
| 255 |
stabilization runs the risk of creating a positive feedback cycle, |
| 256 |
which can eventually result in congestion collapse. In [<a href="#ref-Rhea2004">Rhea2004</a>], |
| 257 |
it is shown that a 1000-peer overlay under churn uses significantly |
| 258 |
less bandwidth and has lower latencies when periodic stabilization is |
| 259 |
used than when reactive stabilization is used. Although in the |
| 260 |
experiments carried out in [<a href="#ref-Rhea2004">Rhea2004</a>], reactive stabilization |
| 261 |
performed well when there was no churn, its bandwidth use was |
| 262 |
observed to jump dramatically under churn. At higher churn rates and |
| 263 |
larger scale overlays, periodic stabilization uses less bandwidth and |
| 264 |
the resulting lower contention for the network leads to lower |
| 265 |
latencies. For this reason, most DHTs, such as CAN [<a href="#ref-CAN" title=""A Scalable Content-Addressable Network"">CAN</a>], Chord |
| 266 |
[<a href="#ref-Chord" title=""Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"">Chord</a>], Pastry [<a href="#ref-Pastry" title=""Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems"">Pastry</a>], and Bamboo [<a href="#ref-Rhea2004">Rhea2004</a>], use periodic |
| 267 |
stabilization [<a href="#ref-Ghinita2006">Ghinita2006</a>]. As an example, the first version of |
| 268 |
Bamboo used reactive stabilization, which caused Bamboo to suffer |
| 269 |
from degradation in performance under churn. To fix this problem, |
| 270 |
Bamboo was modified to use periodic stabilization. |
| 271 |
|
| 272 |
|
| 273 |
|
| 274 |
|
| 275 |
|
| 276 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 5]</span></pre> |
| 277 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span> |
| 278 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 279 |
|
| 280 |
|
| 281 |
In Chord, periodic stabilization is typically done both for |
| 282 |
successors and fingers. An alternative strategy is analyzed in |
| 283 |
[<a href="#ref-Krishnamurthy2008">Krishnamurthy2008</a>]. In this strategy, called the "correction-on- |
| 284 |
change maintenance strategy", a peer periodically stabilizes its |
| 285 |
successors but does not do so for its fingers. Instead, finger |
| 286 |
pointers are stabilized in a reactive fashion. The results obtained |
| 287 |
in [<a href="#ref-Krishnamurthy2008">Krishnamurthy2008</a>] imply that although the correction-on-change |
| 288 |
strategy works well when churn is low, periodic stabilization |
| 289 |
outperforms the correction-on-change strategy when churn is high. |
| 290 |
|
| 291 |
<span class="h3"><a class="selflink" id="section-3.2" href="#section-3.2">3.2</a>. Configuring Periodic Stabilization</span> |
| 292 |
|
| 293 |
When periodic stabilization is used, one faces the problem of |
| 294 |
selecting an appropriate execution rate for the stabilization |
| 295 |
procedure. If the execution rate of periodic stabilization is high, |
| 296 |
changes in the system can be quickly detected, but at the |
| 297 |
disadvantage of increased communication overhead. Alternatively, if |
| 298 |
the stabilization rate is low and the churn rate is high, routing |
| 299 |
tables become inaccurate and DHT performance deteriorates. Thus, the |
| 300 |
problem is setting the parameters so that the overlay achieves the |
| 301 |
desired reliability and performance even in challenging conditions, |
| 302 |
such as under heavy churn. This naturally results in high cost |
| 303 |
during periods when the churn level is lower than expected, or |
| 304 |
alternatively, poor performance or even network partitioning in worse |
| 305 |
than expected conditions. |
| 306 |
|
| 307 |
In addition to selecting an appropriate stabilization interval, |
| 308 |
regardless of whether or not periodic stabilization is used, an |
| 309 |
appropriate size needs to be selected for the neighborhood set and |
| 310 |
for the finger table. |
| 311 |
|
| 312 |
The current approach is to configure overlays statically. This works |
| 313 |
in situations where perfect information about the future is |
| 314 |
available. In situations where the operating conditions of the |
| 315 |
network are known in advance and remain static throughout the |
| 316 |
lifetime of the system, it is possible to choose fixed optimal values |
| 317 |
for parameters such as stabilization rate, neighborhood set size and |
| 318 |
routing table size. However, if the operating conditions (e.g., the |
| 319 |
size of the overlay and its churn rate) do not remain static but |
| 320 |
evolve with time, it is not possible to achieve both a low lookup |
| 321 |
failure rate and a low communication overhead by using fixed |
| 322 |
parameters [<a href="#ref-Ghinita2006">Ghinita2006</a>]. |
| 323 |
|
| 324 |
As an example, to configure the Chord DHT algorithm, one needs to |
| 325 |
select values for the following parameters: size of successor list, |
| 326 |
stabilization interval, and size of the finger table. To select an |
| 327 |
appropriate value for the stabilization interval, one needs to know |
| 328 |
the expected churn rate and overlay size. According to |
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 6]</span></pre> |
| 333 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span> |
| 334 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 335 |
|
| 336 |
|
| 337 |
[<a href="#ref-Liben-Nowell2002">Liben-Nowell2002</a>], a Chord network in a ring-like state remains in a |
| 338 |
ring-like state as long as peers send Omega(square(log(N))) messages |
| 339 |
before N new peers join or N/2 peers fail. Thus, in a 500-peer |
| 340 |
overlay churning at a rate such that one peer joins and one peer |
| 341 |
leaves the network every 30 seconds, an appropriate stabilization |
| 342 |
interval would be on the order of 93 s. According to [<a href="#ref-Chord" title=""Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"">Chord</a>], the |
| 343 |
size of the successor list and finger table should be on the order of |
| 344 |
log(N). Already a successor list of a modest size (e.g., log2(N) or |
| 345 |
2*log2(N), which is the successor list size used in [<a href="#ref-Chord" title=""Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"">Chord</a>]) makes it |
| 346 |
very unlikely that a peer will lose all of its successors, which |
| 347 |
would cause the Chord ring to become disconnected. Thus, in a |
| 348 |
500-peer network each peer should maintain on the order of nine |
| 349 |
successors and fingers. However, if the churn rate doubles and the |
| 350 |
network size remains unchanged, the stabilization rate should double |
| 351 |
as well. That is, the appropriate maintenance interval would now be |
| 352 |
on the order of 46 s. On the other hand, if the churn rate becomes, |
| 353 |
e.g., six-fold and the size of the network grows to 2000 peers, on |
| 354 |
the order of 11 fingers and successors should be maintained and the |
| 355 |
stabilization interval should be on the order of 42 s. If one |
| 356 |
continued using the old values, this could result in inaccurate |
| 357 |
routing tables, network partitioning, and deteriorating performance. |
| 358 |
|
| 359 |
<span class="h3"><a class="selflink" id="section-3.3" href="#section-3.3">3.3</a>. Adaptive Stabilization</span> |
| 360 |
|
| 361 |
A self-tuning DHT takes into consideration the continuous evolution |
| 362 |
of network conditions and adapts to them. In a self-tuning DHT, each |
| 363 |
peer collects statistical data about the network and dynamically |
| 364 |
adjusts its stabilization rate, neighborhood set size, and finger |
| 365 |
table size based on the analysis of the data [<a href="#ref-Ghinita2006">Ghinita2006</a>]. |
| 366 |
Reference [<a href="#ref-Mahajan2003">Mahajan2003</a>] shows that by using self-tuning, it is |
| 367 |
possible to achieve high reliability and performance even in adverse |
| 368 |
conditions with low maintenance cost. Adaptive stabilization has |
| 369 |
been shown to outperform periodic stabilization in terms of both |
| 370 |
lookup failures and communication overhead [<a href="#ref-Ghinita2006">Ghinita2006</a>]. |
| 371 |
|
| 372 |
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Introduction to Chord</span> |
| 373 |
|
| 374 |
Chord [<a href="#ref-Chord" title=""Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"">Chord</a>] is a structured P2P algorithm that uses consistent |
| 375 |
hashing to build a DHT out of several independent peers. Consistent |
| 376 |
hashing assigns each peer and resource a fixed-length identifier. |
| 377 |
Peers use SHA-1 as the base hash function to generate the |
| 378 |
identifiers. As specified in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], the length of |
| 379 |
the identifiers is numBitsInNodeId=128 bits. The identifiers are |
| 380 |
ordered on an identifier circle of size 2^numBitsInNodeId. On the |
| 381 |
identifier circle, key k is assigned to the first peer whose |
| 382 |
identifier equals or follows the identifier of k in the identifier |
| 383 |
space. The identifier circle is called the Chord ring. |
| 384 |
|
| 385 |
|
| 386 |
|
| 387 |
|
| 388 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 7]</span></pre> |
| 389 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span> |
| 390 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 391 |
|
| 392 |
|
| 393 |
Different DHTs differ significantly in performance when bandwidth is |
| 394 |
limited. It has been shown that when compared to other DHTs, the |
| 395 |
advantages of Chord include that it uses bandwidth efficiently and |
| 396 |
can achieve low lookup latencies at little cost [<a href="#ref-Li2004" title=""Comparing the Performance of Distributed Hash Tables Under Churn"">Li2004</a>]. |
| 397 |
|
| 398 |
A simple lookup mechanism could be implemented on a Chord ring by |
| 399 |
requiring each peer to only know how to contact its current successor |
| 400 |
on the identifier circle. Queries for a given identifier could then |
| 401 |
be passed around the circle via the successor pointers until they |
| 402 |
encounter the first peer whose identifier is equal to or larger than |
| 403 |
the desired identifier. Such a lookup scheme uses a number of |
| 404 |
messages that grows linearly with the number of peers. To reduce the |
| 405 |
cost of lookups, Chord maintains also additional routing information; |
| 406 |
each peer n maintains a data structure with up to numBitsInNodeId |
| 407 |
entries, called the finger table. The first entry in the finger |
| 408 |
table of peer n contains the peer halfway around the ring from peer |
| 409 |
n. The second entry contains the peer that is 1/4th of the way |
| 410 |
around, the third entry the peer that is 1/8th of the way around, |
| 411 |
etc. In other words, the ith entry in the finger table at peer n |
| 412 |
contains the identity of the first peer s that succeeds n by at least |
| 413 |
2^(numBitsInNodeId-i) on the Chord ring. This peer is called the ith |
| 414 |
finger of peer n. The interval between two consecutive fingers is |
| 415 |
called a finger interval. The ith finger interval of peer n covers |
| 416 |
the range [n.id + 2^(numBitsInNodeId-i), n.id + 2^(numBitsInNodeId- |
| 417 |
i+1)) on the Chord ring. In an N-peer network, each peer maintains |
| 418 |
information about O(log(N)) other peers in its finger table. As an |
| 419 |
example, if N=100000, it is sufficient to maintain 17 fingers. |
| 420 |
|
| 421 |
Chord needs all peers' successor pointers to be up to date in order |
| 422 |
to ensure that lookups produce correct results as the set of |
| 423 |
participating peers changes. To achieve this, peers run a |
| 424 |
stabilization protocol periodically in the background. The |
| 425 |
stabilization protocol of the original Chord algorithm uses two |
| 426 |
operations: successor stabilization and finger stabilization. |
| 427 |
However, the Chord algorithm of RELOAD base defines two additional |
| 428 |
stabilization components, as will be discussed below. |
| 429 |
|
| 430 |
To increase robustness in the event of peer failures, each Chord peer |
| 431 |
maintains a successor list of size r, containing the peer's first r |
| 432 |
successors. The benefit of successor lists is that if each peer |
| 433 |
fails independently with probability p, the probability that all r |
| 434 |
successors fail simultaneously is only p^r. |
| 435 |
|
| 436 |
The original Chord algorithm maintains only a single predecessor |
| 437 |
pointer. However, multiple predecessor pointers (i.e., a predecessor |
| 438 |
list) can be maintained to speed up recovery from predecessor |
| 439 |
failures. The routing table of a peer consists of the successor |
| 440 |
list, finger table, and predecessor list. |
| 441 |
|
| 442 |
|
| 443 |
|
| 444 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 8]</span></pre> |
| 445 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span> |
| 446 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 447 |
|
| 448 |
|
| 449 |
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Extending Chord-Reload to Support Self-Tuning</span> |
| 450 |
|
| 451 |
This section describes how the mandatory-to-implement chord-reload |
| 452 |
algorithm defined in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>] can be extended to support |
| 453 |
self-tuning. |
| 454 |
|
| 455 |
The chord-reload algorithm supports both reactive and periodic |
| 456 |
recovery strategies. When the self-tuning mechanisms defined in this |
| 457 |
document are used, the periodic recovery strategy is used. Further, |
| 458 |
chord-reload specifies that at least three predecessors and three |
| 459 |
successors need to be maintained. When the self-tuning mechanisms |
| 460 |
are used, the appropriate sizes of the successor list and predecessor |
| 461 |
list are determined in an adaptive fashion based on the estimated |
| 462 |
network size, as will be described in <a href="#section-6">Section 6</a>. |
| 463 |
|
| 464 |
As specified in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], each peer maintains a |
| 465 |
stabilization timer. When the stabilization timer fires, the peer |
| 466 |
restarts the timer and carries out the overlay stabilization routine. |
| 467 |
Overlay stabilization has four components in chord-reload: |
| 468 |
|
| 469 |
1. Update the neighbor table. We refer to this as "neighbor |
| 470 |
stabilization". |
| 471 |
|
| 472 |
2. Refreshing the finger table. We refer to this as "finger |
| 473 |
stabilization". |
| 474 |
|
| 475 |
3. Adjusting finger table size. |
| 476 |
|
| 477 |
4. Detecting partitioning. We refer to this as "strong |
| 478 |
stabilization". |
| 479 |
|
| 480 |
As specified in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], a peer sends periodic messages |
| 481 |
as part of the neighbor stabilization, finger stabilization, and |
| 482 |
strong stabilization routines. In neighbor stabilization, a peer |
| 483 |
periodically sends an Update request to every peer in its connection |
| 484 |
table. The default time is every ten minutes. In finger |
| 485 |
stabilization, a peer periodically searches for new peers to include |
| 486 |
in its finger table. This time defaults to one hour. This document |
| 487 |
specifies how the neighbor stabilization and finger stabilization |
| 488 |
intervals can be determined in an adaptive fashion based on the |
| 489 |
operating conditions of the overlay. The subsections below describe |
| 490 |
how this document extends the four components of stabilization. |
| 491 |
|
| 492 |
<span class="h3"><a class="selflink" id="section-5.1" href="#section-5.1">5.1</a>. Update Requests</span> |
| 493 |
|
| 494 |
As described in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], the neighbor and finger |
| 495 |
stabilization procedures are implemented using Update requests. |
| 496 |
RELOAD base defines three types of Update requests: 'peer_ready', |
| 497 |
|
| 498 |
|
| 499 |
|
| 500 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 9]</span></pre> |
| 501 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span> |
| 502 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 503 |
|
| 504 |
|
| 505 |
'neighbors', and 'full'. Regardless of the type, all Update requests |
| 506 |
include an 'uptime' field. The self-tuning extensions require |
| 507 |
information on the uptimes of peers in the routing table. The sender |
| 508 |
of an Update request includes its current uptime (in seconds) in the |
| 509 |
'uptime' field. Regardless of the type, all Update requests MUST |
| 510 |
include an 'uptime' field. |
| 511 |
|
| 512 |
When self-tuning is used, each peer decides independently the |
| 513 |
appropriate size for the successor list, predecessor list, and finger |
| 514 |
table. Thus, the 'predecessors', 'successors', and 'fingers' fields |
| 515 |
included in RELOAD Update requests are of variable length. As |
| 516 |
specified in RELOAD [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], variable-length fields are on the wire |
| 517 |
preceded by length bytes. In the case of the successor list, |
| 518 |
predecessor list, and finger table, there are two length bytes |
| 519 |
(allowing lengths up to 2^16-1). The number of NodeId structures |
| 520 |
included in each field can be calculated based on the length bytes |
| 521 |
since the size of a single NodeId structure is 16 bytes. If a peer |
| 522 |
receives more entries than fit into its successor list, predecessor |
| 523 |
list, or finger table, the peer MUST ignore the extra entries. A |
| 524 |
peer may also receive less entries than it currently has in its own |
| 525 |
data structure. In that case, it uses the received entries to update |
| 526 |
only a subset of the entries in its data structure. As an example, a |
| 527 |
peer that has a successor list of size 8 may receive a successor list |
| 528 |
of size 4 from its immediate successor. In that case, the received |
| 529 |
successor list can only be used to update the first few successors on |
| 530 |
the peer's successor list. The rest of the successors will remain |
| 531 |
intact. |
| 532 |
|
| 533 |
<span class="h3"><a class="selflink" id="section-5.2" href="#section-5.2">5.2</a>. Neighbor Stabilization</span> |
| 534 |
|
| 535 |
In the neighbor stabilization operation of chord-reload, a peer |
| 536 |
periodically sends an Update request to every peer in its connection |
| 537 |
table. In a small, low-churn overlay, the amount of traffic this |
| 538 |
process generates is typically acceptable. However, in a large-scale |
| 539 |
overlay churning at a moderate or high churn rate, the traffic load |
| 540 |
may no longer be acceptable since the size of the connection table is |
| 541 |
large and the stabilization interval relatively short. The self- |
| 542 |
tuning mechanisms described in this document are especially designed |
| 543 |
for overlays of the latter type. Therefore, when the self-tuning |
| 544 |
mechanisms are used, each peer only sends a periodic Update request |
| 545 |
to its first predecessor and first successor on the Chord ring; it |
| 546 |
MUST NOT send Update requests to others. |
| 547 |
|
| 548 |
The neighbor stabilization routine is executed when the stabilization |
| 549 |
timer fires. To begin the neighbor stabilization routine, a peer |
| 550 |
sends an Update request to its first successor and its first |
| 551 |
predecessor. The type of the Update request MUST be 'neighbors'. |
| 552 |
The Update request includes the successor and predecessor lists of |
| 553 |
|
| 554 |
|
| 555 |
|
| 556 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 10]</span></pre> |
| 557 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span> |
| 558 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 559 |
|
| 560 |
|
| 561 |
the sender. If a peer receiving such an Update request learns from |
| 562 |
the predecessor and successor lists included in the request that new |
| 563 |
peers can be included in its neighborhood set, it sends Attach |
| 564 |
requests to the new peers. |
| 565 |
|
| 566 |
After a new peer has been added to the predecessor or successor list, |
| 567 |
an Update request of type 'peer_ready' is sent to the new peer. This |
| 568 |
allows the new peer to insert the sender into its neighborhood set. |
| 569 |
|
| 570 |
<span class="h3"><a class="selflink" id="section-5.3" href="#section-5.3">5.3</a>. Finger Stabilization</span> |
| 571 |
|
| 572 |
Chord-reload specifies two alternative methods for searching for new |
| 573 |
peers to the finger table. Both of the alternatives can be used with |
| 574 |
the self-tuning extensions defined in this document. |
| 575 |
|
| 576 |
Immediately after a new peer has been added to the finger table, a |
| 577 |
Probe request is sent to the new peer to fetch its uptime. The |
| 578 |
'requested_info' field of the Probe request MUST be set to contain |
| 579 |
the ProbeInformationType 'uptime' defined in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>]. |
| 580 |
|
| 581 |
<span class="h3"><a class="selflink" id="section-5.4" href="#section-5.4">5.4</a>. Adjusting Finger Table Size</span> |
| 582 |
|
| 583 |
The chord-reload algorithm defines how a peer can make sure that the |
| 584 |
finger table is appropriately sized to allow for efficient routing. |
| 585 |
Since the self-tuning mechanisms specified in this document produce a |
| 586 |
network size estimate, this estimate can be directly used to |
| 587 |
calculate the optimal size for the finger table. This mechanism is |
| 588 |
used instead of the one specified by chord-reload. A peer uses the |
| 589 |
network size estimate to determine whether it needs to adjust the |
| 590 |
size of its finger table each time when the stabilization timer |
| 591 |
fires. The way this is done is explained in <a href="#section-6.2">Section 6.2</a>. |
| 592 |
|
| 593 |
<span class="h3"><a class="selflink" id="section-5.5" href="#section-5.5">5.5</a>. Detecting Partitioning</span> |
| 594 |
|
| 595 |
This document does not require any changes to the mechanism chord- |
| 596 |
reload uses to detect network partitioning. |
| 597 |
|
| 598 |
<span class="h3"><a class="selflink" id="section-5.6" href="#section-5.6">5.6</a>. Leaving the Overlay</span> |
| 599 |
|
| 600 |
As specified in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], a leaving peer SHOULD send a |
| 601 |
Leave request to all members of its neighbor table prior to leaving |
| 602 |
the overlay. The 'overlay_specific_data' field MUST contain the |
| 603 |
ChordLeaveData structure. The Leave requests that are sent to |
| 604 |
successors contain the predecessor list of the leaving peer. The |
| 605 |
Leave requests that are sent to the predecessors contain the |
| 606 |
successor list of the leaving peer. If a given successor can |
| 607 |
identify better predecessors (that is, predecessors that are closer |
| 608 |
to it on the Chord ring than its existing predecessors) than are |
| 609 |
|
| 610 |
|
| 611 |
|
| 612 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 11]</span></pre> |
| 613 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span> |
| 614 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 615 |
|
| 616 |
|
| 617 |
already included in its predecessor lists by investigating the |
| 618 |
predecessor list it receives from the leaving peer, it sends Attach |
| 619 |
requests to them. Similarly, if a given predecessor identifies |
| 620 |
better successors by investigating the successor list it receives |
| 621 |
from the leaving peer, it sends Attach requests to them. |
| 622 |
|
| 623 |
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Self-Tuning Chord Parameters</span> |
| 624 |
|
| 625 |
This section specifies how to determine an appropriate stabilization |
| 626 |
rate and routing table size in an adaptive fashion. The proposed |
| 627 |
mechanism is based on [<a href="#ref-Mahajan2003">Mahajan2003</a>], [<a href="#ref-Liben-Nowell2002">Liben-Nowell2002</a>], and |
| 628 |
[<a href="#ref-Ghinita2006">Ghinita2006</a>]. To calculate an appropriate stabilization rate, the |
| 629 |
values of three parameters must be estimated: overlay size N, failure |
| 630 |
rate U, and join rate L. To calculate an appropriate routing table |
| 631 |
size, the estimated network size N can be used. Peers in the overlay |
| 632 |
MUST recalculate the values of the parameters to self-tune the chord- |
| 633 |
reload algorithm at the end of each stabilization period before |
| 634 |
restarting the stabilization timer. |
| 635 |
|
| 636 |
<span class="h3"><a class="selflink" id="section-6.1" href="#section-6.1">6.1</a>. Estimating Overlay Size</span> |
| 637 |
|
| 638 |
Techniques for estimating the size of an overlay network have been |
| 639 |
proposed, for instance, in [<a href="#ref-Mahajan2003">Mahajan2003</a>], [<a href="#ref-Horowitz2003">Horowitz2003</a>], |
| 640 |
[<a href="#ref-Kostoulas2005">Kostoulas2005</a>], [<a href="#ref-Binzenhofer2006">Binzenhofer2006</a>], and [<a href="#ref-Ghinita2006">Ghinita2006</a>]. In Chord, the |
| 641 |
density of peer identifiers in the neighborhood set can be used to |
| 642 |
produce an estimate of the size of the overlay, N [<a href="#ref-Mahajan2003">Mahajan2003</a>]. |
| 643 |
Since peer identifiers are picked randomly with uniform probability |
| 644 |
from the numBitsInNodeId-bit identifier space, the average distance |
| 645 |
between peer identifiers in the successor set is |
| 646 |
(2^numBitsInNodeId)/N. |
| 647 |
|
| 648 |
To estimate the overlay network size, a peer computes the average |
| 649 |
inter-peer distance d between the successive peers starting from the |
| 650 |
most distant predecessor and ending to the most distant successor in |
| 651 |
the successor list. The estimated network size is calculated as: |
| 652 |
|
| 653 |
2^numBitsInNodeId |
| 654 |
N = ------------------- |
| 655 |
d |
| 656 |
|
| 657 |
This estimate has been found to be accurate within 15% of the real |
| 658 |
network size [<a href="#ref-Ghinita2006">Ghinita2006</a>]. Of course, the size of the neighborhood |
| 659 |
set affects the accuracy of the estimate. |
| 660 |
|
| 661 |
|
| 662 |
|
| 663 |
|
| 664 |
|
| 665 |
|
| 666 |
|
| 667 |
|
| 668 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 12]</span></pre> |
| 669 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span> |
| 670 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 671 |
|
| 672 |
|
| 673 |
During the join process, a joining peer fills its routing table by |
| 674 |
sending a series of Ping and Attach requests, as specified in RELOAD |
| 675 |
base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>]. Thus, a joining peer immediately has enough |
| 676 |
information at its disposal to calculate an estimate of the network |
| 677 |
size. |
| 678 |
|
| 679 |
<span class="h3"><a class="selflink" id="section-6.2" href="#section-6.2">6.2</a>. Determining Routing Table Size</span> |
| 680 |
|
| 681 |
As specified in RELOAD base [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>], the finger table must contain |
| 682 |
at least 16 entries. When the self-tuning mechanisms are used, the |
| 683 |
size of the finger table MUST be set to max(ceiling(log2(N)), 16) |
| 684 |
using the estimated network size N. |
| 685 |
|
| 686 |
The size of the successor list MUST be set to a maximum of |
| 687 |
ceiling(log2(N)). An implementation can place a lower limit on the |
| 688 |
size of the successor list. As an example, the implementation might |
| 689 |
require the size of the successor list to be always at least three. |
| 690 |
|
| 691 |
The size of the predecessor list MUST be set to ceiling(log2(N)). |
| 692 |
|
| 693 |
<span class="h3"><a class="selflink" id="section-6.3" href="#section-6.3">6.3</a>. Estimating Failure Rate</span> |
| 694 |
|
| 695 |
A typical approach is to assume that peers join the overlay according |
| 696 |
to a Poisson process with rate L and leave according to a Poisson |
| 697 |
process with rate parameter U [<a href="#ref-Mahajan2003">Mahajan2003</a>]. The value of U can be |
| 698 |
estimated using peer failures in the finger table and neighborhood |
| 699 |
set [<a href="#ref-Mahajan2003">Mahajan2003</a>]. If peers fail with rate U, a peer with M unique |
| 700 |
peer identifiers in its routing table should observe K failures in |
| 701 |
time K/(M*U). Every peer in the overlay maintains a history of the |
| 702 |
last K failures. The current time is inserted into the history when |
| 703 |
the peer joins the overlay. The estimate of U is calculated as: |
| 704 |
|
| 705 |
k |
| 706 |
U = --------, |
| 707 |
M * Tk |
| 708 |
|
| 709 |
where M is the number of unique peer identifiers in the routing |
| 710 |
table, Tk is the time between the first and the last failure in the |
| 711 |
history, and k is the number of failures in the history. If k is |
| 712 |
smaller than K, the estimate is computed as if there was a failure at |
| 713 |
the current time. It has been shown that an estimate calculated in a |
| 714 |
similar manner is accurate within 17% of the real value of U |
| 715 |
[<a href="#ref-Ghinita2006">Ghinita2006</a>]. |
| 716 |
|
| 717 |
The size of the failure history K affects the accuracy of the |
| 718 |
estimate of U. One can increase the accuracy by increasing K. |
| 719 |
However, this has the side effect of decreasing responsiveness to |
| 720 |
changes in the failure rate. On the other hand, a small history size |
| 721 |
|
| 722 |
|
| 723 |
|
| 724 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 13]</span></pre> |
| 725 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span> |
| 726 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 727 |
|
| 728 |
|
| 729 |
may cause a peer to overreact each time a new failure occurs. In |
| 730 |
[<a href="#ref-Ghinita2006">Ghinita2006</a>], K is set to 25% of the routing table size. Use of |
| 731 |
this value is RECOMMENDED. |
| 732 |
|
| 733 |
<span class="h4"><a class="selflink" id="section-6.3.1" href="#section-6.3.1">6.3.1</a>. Detecting Failures</span> |
| 734 |
|
| 735 |
A new failure is inserted to the failure history in the following |
| 736 |
cases: |
| 737 |
|
| 738 |
1. A Leave request is received from a neighbor. |
| 739 |
|
| 740 |
2. A peer fails to reply to a Ping request sent in the situation |
| 741 |
explained below. If no packets have been received on a |
| 742 |
connection during the past 2*Tr seconds (where Tr is the |
| 743 |
inactivity timer defined by Interactive Connectivity |
| 744 |
Establishment (ICE) [<a href="./rfc5245" title=""Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/Answer Protocols"">RFC5245</a>]), a RELOAD Ping request MUST be |
| 745 |
sent to the remote peer. RELOAD mandates the use of Session |
| 746 |
Traversal Utilities for NAT (STUN) [<a href="./rfc5389" title=""Session Traversal Utilities for NAT (STUN)"">RFC5389</a>] for keepalives. |
| 747 |
STUN keepalives take the form of STUN Binding Indication |
| 748 |
transactions. As specified in ICE [<a href="./rfc5245" title=""Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/Answer Protocols"">RFC5245</a>], a peer sends a STUN |
| 749 |
Binding Indication if there has been no packet sent on a |
| 750 |
connection for Tr seconds. Tr is configurable and has a default |
| 751 |
of 15 seconds. Although STUN Binding Indications do not generate |
| 752 |
a response, the fact that a peer has failed can be learned from |
| 753 |
the lack of packets (Binding Indications or application protocol |
| 754 |
packets) received from the peer. If the remote peer fails to |
| 755 |
reply to the Ping request, the sender should consider the remote |
| 756 |
peer to have failed. |
| 757 |
|
| 758 |
As an alternative to relying on STUN keepalives to detect peer |
| 759 |
failure, a peer could send additional, frequent RELOAD messages to |
| 760 |
every peer in its connection table. These messages could be Update |
| 761 |
requests, in which case they would serve two purposes: detecting peer |
| 762 |
failure and stabilization. However, as the cost of this approach can |
| 763 |
be very high in terms of bandwidth consumption and traffic load, |
| 764 |
especially in large-scale overlays experiencing churn, its use is NOT |
| 765 |
RECOMMENDED. |
| 766 |
|
| 767 |
<span class="h3"><a class="selflink" id="section-6.4" href="#section-6.4">6.4</a>. Estimating Join Rate</span> |
| 768 |
|
| 769 |
Reference [<a href="#ref-Ghinita2006">Ghinita2006</a>] proposes that a peer can estimate the join |
| 770 |
rate based on the uptime of the peers in its routing table. An |
| 771 |
increase in peer join rate will be reflected by a decrease in the |
| 772 |
average age of peers in the routing table. Thus, each peer |
| 773 |
maintained an array of the ages of the peers in its routing table |
| 774 |
sorted in increasing order. Using this information, an estimate of |
| 775 |
the global peer join rate L is calculated as: |
| 776 |
|
| 777 |
|
| 778 |
|
| 779 |
|
| 780 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 14]</span></pre> |
| 781 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span> |
| 782 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 783 |
|
| 784 |
|
| 785 |
N |
| 786 |
L = ----------------------, |
| 787 |
Ages[floor(rsize/2)] |
| 788 |
|
| 789 |
where Ages is an array containing the ages of the peers in the |
| 790 |
routing table sorted in increasing order and rsize is the size of the |
| 791 |
routing table. It has been shown that the estimate obtained by using |
| 792 |
this method is accurate within 22% of the real join rate |
| 793 |
[<a href="#ref-Ghinita2006">Ghinita2006</a>]. Of course, the size of the routing table affects the |
| 794 |
accuracy. |
| 795 |
|
| 796 |
In order for this mechanism to work, peers need to exchange |
| 797 |
information about the time they have been present in the overlay. |
| 798 |
Peers receive the uptimes of their successors and predecessors during |
| 799 |
the stabilization operations since all Update requests carry uptime |
| 800 |
values. A joining peer learns the uptime of the admitting peer since |
| 801 |
it receives an Update from the admitting peer during the join |
| 802 |
procedure. Peers learn the uptimes of new fingers since they can |
| 803 |
fetch the uptime using a Probe request after having attached to the |
| 804 |
new finger. |
| 805 |
|
| 806 |
<span class="h3"><a class="selflink" id="section-6.5" href="#section-6.5">6.5</a>. Estimate Sharing</span> |
| 807 |
|
| 808 |
To improve the accuracy of network size, join rate, and leave rate |
| 809 |
estimates, peers share their estimates. When the stabilization timer |
| 810 |
fires, a peer selects number-of-peers-to-probe random peers from its |
| 811 |
finger table and send each of them a Probe request. The targets of |
| 812 |
Probe requests are selected from the finger table rather than from |
| 813 |
the neighbor table since neighbors are likely to make similar errors |
| 814 |
when calculating their estimates. The number-of-peers-to-probe is a |
| 815 |
new element in the overlay configuration document. It is defined in |
| 816 |
<a href="#section-7">Section 7</a>. Both the Probe request and the answer returned by the |
| 817 |
target peer MUST contain a new message extension whose |
| 818 |
MessageExtensionType is 'self_tuning_data'. This extension type is |
| 819 |
defined in <a href="#section-9.1">Section 9.1</a>. The 'extension_contents' field of the |
| 820 |
MessageExtension structure MUST contain a SelfTuningData structure: |
| 821 |
|
| 822 |
struct { |
| 823 |
uint32 network_size; |
| 824 |
uint32 join_rate; |
| 825 |
uint32 leave_rate; |
| 826 |
} SelfTuningData; |
| 827 |
|
| 828 |
|
| 829 |
|
| 830 |
|
| 831 |
|
| 832 |
|
| 833 |
|
| 834 |
|
| 835 |
|
| 836 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 15]</span></pre> |
| 837 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span> |
| 838 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 839 |
|
| 840 |
|
| 841 |
The contents of the SelfTuningData structure are as follows: |
| 842 |
|
| 843 |
network_size |
| 844 |
|
| 845 |
The latest network size estimate calculated by the sender. |
| 846 |
|
| 847 |
join_rate |
| 848 |
|
| 849 |
The latest join rate estimate calculated by the sender. |
| 850 |
|
| 851 |
leave_rate |
| 852 |
|
| 853 |
The latest leave rate estimate calculated by the sender. |
| 854 |
|
| 855 |
The join and leave rates are expressed as joins or failures per 24 |
| 856 |
hours. As an example, if the global join rate estimate a peer has |
| 857 |
calculated is 0.123 peers/s, it would include in the 'join_rate' |
| 858 |
field the ceiling of the value 10627.2 (24*60*60*0.123 = 10627.2), |
| 859 |
that is, the value 10628. |
| 860 |
|
| 861 |
The 'type' field of the MessageExtension structure MUST be set to |
| 862 |
contain the value 'self_tuning_data'. The 'critical' field of the |
| 863 |
structure MUST be set to False. |
| 864 |
|
| 865 |
A peer stores all estimates it receives in Probe requests and answers |
| 866 |
during a stabilization interval. When the stabilization timer fires, |
| 867 |
the peer calculates the estimates to be used during the next |
| 868 |
stabilization interval by taking the 75th percentile (i.e., third |
| 869 |
quartile) of a data set containing its own estimate and the received |
| 870 |
estimates. |
| 871 |
|
| 872 |
The default value for number-of-peers-to-probe is 4. This default |
| 873 |
value is recommended to allow a peer to receive a sufficiently large |
| 874 |
set of estimates from other peers. With a value of 4, a peer |
| 875 |
receives four estimates in Probe answers. On the average, each peer |
| 876 |
also receives four Probe requests each carrying an estimate. Thus, |
| 877 |
on the average, each peer has nine estimates (including its own) that |
| 878 |
it can use at the end of the stabilization interval. A value smaller |
| 879 |
than 4 is NOT RECOMMENDED to keep the number of received estimates |
| 880 |
high enough. As an example, if the value were 2, there would be |
| 881 |
peers in the overlay that would only receive two estimates during a |
| 882 |
stabilization interval. Such peers would only have three estimates |
| 883 |
available at the end of the interval, which may not be reliable |
| 884 |
enough since even a single exceptionally high or low estimate can |
| 885 |
have a large impact. |
| 886 |
|
| 887 |
|
| 888 |
|
| 889 |
|
| 890 |
|
| 891 |
|
| 892 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 16]</span></pre> |
| 893 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span> |
| 894 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 895 |
|
| 896 |
|
| 897 |
<span class="h3"><a class="selflink" id="section-6.6" href="#section-6.6">6.6</a>. Calculating the Stabilization Interval</span> |
| 898 |
|
| 899 |
According to [<a href="#ref-Liben-Nowell2002">Liben-Nowell2002</a>], a Chord network in a ring-like state |
| 900 |
remains in a ring-like state as long as peers send |
| 901 |
Omega(square(log(N))) messages before N new peers join or N/2 peers |
| 902 |
fail. We can use the estimate of peer failure rate, U, to calculate |
| 903 |
the time Tf in which N/2 peers fail: |
| 904 |
|
| 905 |
1 |
| 906 |
Tf = ------ |
| 907 |
2*U |
| 908 |
|
| 909 |
Based on this estimate, a stabilization interval Tstab-1 is |
| 910 |
calculated as: |
| 911 |
|
| 912 |
Tf |
| 913 |
Tstab-1 = ----------------- |
| 914 |
square(log2(N)) |
| 915 |
|
| 916 |
On the other hand, the estimated join rate L can be used to calculate |
| 917 |
the time in which N new peers join the overlay. Based on the |
| 918 |
estimate of L, a stabilization interval Tstab-2 is calculated as: |
| 919 |
|
| 920 |
N |
| 921 |
Tstab-2 = --------------------- |
| 922 |
L * square(log2(N)) |
| 923 |
|
| 924 |
Finally, the actual stabilization interval Tstab that is used can be |
| 925 |
obtained by taking the minimum of Tstab-1 and Tstab-2. |
| 926 |
|
| 927 |
The results obtained in [<a href="#ref-Maenpaa2009">Maenpaa2009</a>] indicate that making the |
| 928 |
stabilization interval too small has the effect of making the overlay |
| 929 |
less stable (e.g., in terms of detected loops and path failures). |
| 930 |
Thus, a lower limit should be used for the stabilization period. |
| 931 |
Based on the results in [<a href="#ref-Maenpaa2009">Maenpaa2009</a>], a lower limit of 15 s is |
| 932 |
RECOMMENDED, since using a stabilization period smaller than this |
| 933 |
will with a high probability cause too much traffic in the overlay. |
| 934 |
|
| 935 |
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Overlay Configuration Document Extension</span> |
| 936 |
|
| 937 |
This document extends the RELOAD overlay configuration document by |
| 938 |
adding one new element, "number-of-peers-to-probe", inside each |
| 939 |
"configuration" element. |
| 940 |
|
| 941 |
self-tuning:number-of-peers-to-probe: The number of fingers to which |
| 942 |
Probe requests are sent to obtain their network size, join rate, |
| 943 |
and leave rate estimates. The default value is 4. |
| 944 |
|
| 945 |
|
| 946 |
|
| 947 |
|
| 948 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 17]</span></pre> |
| 949 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span> |
| 950 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 951 |
|
| 952 |
|
| 953 |
The RELAX NG grammar for this element is: |
| 954 |
|
| 955 |
namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning" |
| 956 |
|
| 957 |
parameter &= element self-tuning:number-of-peers-to-probe { |
| 958 |
xsd:unsignedInt }? |
| 959 |
|
| 960 |
This namespace is added into the <mandatory-extension> element in the |
| 961 |
overlay configuration file. |
| 962 |
|
| 963 |
<span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>. Security Considerations</span> |
| 964 |
|
| 965 |
In the same way as malicious or compromised peers implementing the |
| 966 |
RELOAD base protocol [<a href="./rfc6940" title=""REsource LOcation And Discovery (RELOAD) Base Protocol"">RFC6940</a>] can advertise false network metrics or |
| 967 |
distribute false routing table information for instance in RELOAD |
| 968 |
Update messages, malicious peers implementing this specification may |
| 969 |
share false join rate, leave rate, and network size estimates. For |
| 970 |
such attacks, the same security concerns apply as in the RELOAD base |
| 971 |
specification. In addition, as long as the amount of malicious peers |
| 972 |
in the overlay remains modest, the statistical mechanisms applied in |
| 973 |
<a href="#section-6.5">Section 6.5</a> (i.e., the use of 75th percentiles) to process the shared |
| 974 |
estimates a peer obtains help ensure that estimates that are clearly |
| 975 |
different from (i.e., larger or smaller than) other received |
| 976 |
estimates will not significantly influence the process of adapting |
| 977 |
the stabilization interval and routing table size. However, it |
| 978 |
should be noted that if an attacker is able to impersonate a high |
| 979 |
number of other peers in the overlay in strategic locations, it may |
| 980 |
be able to send a high enough number of false estimates to a victim |
| 981 |
and therefore influence the victim's choice of a stabilization |
| 982 |
interval. |
| 983 |
|
| 984 |
<span class="h2"><a class="selflink" id="section-9" href="#section-9">9</a>. IANA Considerations</span> |
| 985 |
|
| 986 |
<span class="h3"><a class="selflink" id="section-9.1" href="#section-9.1">9.1</a>. Message Extensions</span> |
| 987 |
|
| 988 |
This document introduces one additional extension to the "RELOAD |
| 989 |
Extensions Registry": |
| 990 |
|
| 991 |
+------------------+-------+---------------+ |
| 992 |
| Extension Name | Code | Specification | |
| 993 |
+------------------+-------+---------------+ |
| 994 |
| self_tuning_data | 0x3 | <a href="./rfc7363">RFC 7363</a> | |
| 995 |
+------------------+-------+---------------+ |
| 996 |
|
| 997 |
|
| 998 |
The contents of the extension are defined in <a href="#section-6.5">Section 6.5</a>. |
| 999 |
|
| 1000 |
|
| 1001 |
|
| 1002 |
|
| 1003 |
|
| 1004 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 18]</span></pre> |
| 1005 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span> |
| 1006 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 1007 |
|
| 1008 |
|
| 1009 |
<span class="h3"><a class="selflink" id="section-9.2" href="#section-9.2">9.2</a>. New Overlay Algorithm Type</span> |
| 1010 |
|
| 1011 |
This document introduces one additional overlay algorithm type to the |
| 1012 |
"RELOAD Overlay Algorithm Types" registry: |
| 1013 |
|
| 1014 |
+-------------------+-----------+ |
| 1015 |
| Algorithm Name | Reference | |
| 1016 |
+-------------------+-----------+ |
| 1017 |
| CHORD-SELF-TUNING | <a href="./rfc7363">RFC 7363</a> | |
| 1018 |
+-------------------+-----------+ |
| 1019 |
|
| 1020 |
|
| 1021 |
<span class="h3"><a class="selflink" id="section-9.3" href="#section-9.3">9.3</a>. A New IETF XML Registry</span> |
| 1022 |
|
| 1023 |
This document registers one new URI for the self-tuning namespace in |
| 1024 |
the "ns" subregistry of the IETF XML registry defined in [<a href="./rfc3688" title=""The IETF XML Registry"">RFC3688</a>]. |
| 1025 |
|
| 1026 |
URI: urn:ietf:params:xml:ns:p2p:self-tuning |
| 1027 |
|
| 1028 |
Registrant Contact: The IESG |
| 1029 |
|
| 1030 |
XML: N/A, the requested URI is an XML namespace |
| 1031 |
|
| 1032 |
<span class="h2"><a class="selflink" id="section-10" href="#section-10">10</a>. Acknowledgments</span> |
| 1033 |
|
| 1034 |
The authors would like to thank Jani Hautakorpi for his contributions |
| 1035 |
to the document. The authors would also like to thank Carlos |
| 1036 |
Bernardos, Martin Durst, Alissa Cooper, Tobias Gondrom, and Barry |
| 1037 |
Leiba for their comments on the document. |
| 1038 |
|
| 1039 |
<span class="h2"><a class="selflink" id="section-11" href="#section-11">11</a>. References</span> |
| 1040 |
|
| 1041 |
<span class="h3"><a class="selflink" id="section-11.1" href="#section-11.1">11.1</a>. Normative References</span> |
| 1042 |
|
| 1043 |
[<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate |
| 1044 |
Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>, March 1997. |
| 1045 |
|
| 1046 |
[<a id="ref-RFC5245">RFC5245</a>] Rosenberg, J., "Interactive Connectivity Establishment |
| 1047 |
(ICE): A Protocol for Network Address Translator (NAT) |
| 1048 |
Traversal for Offer/Answer Protocols", <a href="./rfc5245">RFC 5245</a>, April |
| 1049 |
2010. |
| 1050 |
|
| 1051 |
[<a id="ref-RFC5389">RFC5389</a>] Rosenberg, J., Mahy, R., Matthews, P., and D. Wing, |
| 1052 |
"Session Traversal Utilities for NAT (STUN)", <a href="./rfc5389">RFC 5389</a>, |
| 1053 |
October 2008. |
| 1054 |
|
| 1055 |
|
| 1056 |
|
| 1057 |
|
| 1058 |
|
| 1059 |
|
| 1060 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 19]</span></pre> |
| 1061 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span> |
| 1062 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 1063 |
|
| 1064 |
|
| 1065 |
[<a id="ref-RFC6940">RFC6940</a>] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and |
| 1066 |
H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) |
| 1067 |
Base Protocol", <a href="./rfc6940">RFC 6940</a>, January 2014. |
| 1068 |
|
| 1069 |
<span class="h3"><a class="selflink" id="section-11.2" href="#section-11.2">11.2</a>. Informative References</span> |
| 1070 |
|
| 1071 |
[<a id="ref-Binzenhofer2006">Binzenhofer2006</a>] |
| 1072 |
Binzenhofer, A., Kunzmann, G., and R. Henjes, "A Scalable |
| 1073 |
Algorithm to Monitor Chord-Based P2P Systems at Runtime", |
| 1074 |
In Proceedings of the 20th IEEE International Parallel and |
| 1075 |
Distributed Processing Symposium (IPDPS), pp. 1-8, April |
| 1076 |
2006. |
| 1077 |
|
| 1078 |
[<a id="ref-CAN">CAN</a>] Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S. |
| 1079 |
Schenker, "A Scalable Content-Addressable Network", In |
| 1080 |
Proceedings of the 2001 Conference on Applications, |
| 1081 |
Technologies, Architectures and Protocols for Computer |
| 1082 |
Communications, pp. 161-172, August 2001. |
| 1083 |
|
| 1084 |
[<a id="ref-Chord">Chord</a>] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., |
| 1085 |
Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A |
| 1086 |
Scalable Peer-to-peer Lookup Service for Internet |
| 1087 |
Applications", IEEE/ACM Transactions on Networking, Volume |
| 1088 |
11, Issue 1, pp. 17-32, February 2003. |
| 1089 |
|
| 1090 |
[<a id="ref-Ghinita2006">Ghinita2006</a>] |
| 1091 |
Ghinita, G. and Y. Teo, "An Adaptive Stabilization |
| 1092 |
Framework for Distributed Hash Tables", In Proceedings of |
| 1093 |
the 20th IEEE International Parallel and Distributed |
| 1094 |
Processing Symposium (IPDPS), pp. 29-38, April 2006. |
| 1095 |
|
| 1096 |
[<a id="ref-Horowitz2003">Horowitz2003</a>] |
| 1097 |
Horowitz, K. and D. Malkhi, "Estimating Network Size from |
| 1098 |
Local Information", Information Processing Letters, Volume |
| 1099 |
88, Issue 5, pp. 237-243, December 2003. |
| 1100 |
|
| 1101 |
[<a id="ref-Kostoulas2005">Kostoulas2005</a>] |
| 1102 |
Kostoulas, D., Psaltoulis, D., Gupta, I., Birman, K., and |
| 1103 |
A. Demers, "Decentralized Schemes for Size Estimation in |
| 1104 |
Large and Dynamic Groups", In Proceedings of the 4th IEEE |
| 1105 |
International Symposium on Network Computing and |
| 1106 |
Applications, pp. 41-48, July 2005. |
| 1107 |
|
| 1108 |
|
| 1109 |
|
| 1110 |
|
| 1111 |
|
| 1112 |
|
| 1113 |
|
| 1114 |
|
| 1115 |
|
| 1116 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 20]</span></pre> |
| 1117 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span> |
| 1118 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 1119 |
|
| 1120 |
|
| 1121 |
[<a id="ref-Krishnamurthy2008">Krishnamurthy2008</a>] |
| 1122 |
Krishnamurthy, S., El-Ansary, S., Aurell, E., and S. |
| 1123 |
Haridi, "Comparing Maintenance Strategies for Overlays", |
| 1124 |
In Proceedings of the 16th Euromicro Conference on |
| 1125 |
Parallel, Distributed and Network-Based Processing, pp. |
| 1126 |
473-482, February 2008. |
| 1127 |
|
| 1128 |
[<a id="ref-Li2004">Li2004</a>] Li, J., Strinbling, J., Gil, T., Morris, R., and M. |
| 1129 |
Kaashoek, "Comparing the Performance of Distributed Hash |
| 1130 |
Tables Under Churn", Peer-to-Peer Systems III, Volume 3279 |
| 1131 |
of Lecture Notes in Computer Science, Springer, pp. 87-99, |
| 1132 |
February 2005. |
| 1133 |
|
| 1134 |
[<a id="ref-Liben-Nowell2002">Liben-Nowell2002</a>] |
| 1135 |
Liben-Nowell, D., Balakrishnan, H., and D. Karger, |
| 1136 |
"Observations on the Dynamic Evolution of Peer-to-Peer |
| 1137 |
Networks", In Proceedings of the 1st International |
| 1138 |
Workshop on Peer-to-Peer Systems (IPTPS), pp. 22-33, March |
| 1139 |
2002. |
| 1140 |
|
| 1141 |
[<a id="ref-Maenpaa2009">Maenpaa2009</a>] |
| 1142 |
Maenpaa, J. and G. Camarillo, "A Study on Maintenance |
| 1143 |
Operations in a Chord-Based Peer-to-Peer Session |
| 1144 |
Initiation Protocol Overlay Network", In Proceedings of |
| 1145 |
the 23rd IEEE International Parallel and Distributed |
| 1146 |
Processing Symposium (IPDPS), pp. 1-9, May 2009. |
| 1147 |
|
| 1148 |
[<a id="ref-Mahajan2003">Mahajan2003</a>] |
| 1149 |
Mahajan, R., Castro, M., and A. Rowstron, "Controlling the |
| 1150 |
Cost of Reliability in Peer-to-Peer Overlays", In |
| 1151 |
Proceedings of the 2nd International Workshop on Peer-to- |
| 1152 |
Peer Systems (IPTPS), pp. 21-32, February 2003. |
| 1153 |
|
| 1154 |
[<a id="ref-Pastry">Pastry</a>] Rowstron, A. and P. Druschel, "Pastry: Scalable, |
| 1155 |
Decentralized Object Location and Routing for Large-Scale |
| 1156 |
Peer-to-Peer Systems", In Proceedings of the IFIP/ACM |
| 1157 |
International Conference on Distributed Systems Platforms, |
| 1158 |
pp. 329-350, November 2001. |
| 1159 |
|
| 1160 |
[<a id="ref-RFC3688">RFC3688</a>] Mealling, M., "The IETF XML Registry", <a href="https://www.rfc-editor.org/bcp/bcp81">BCP 81</a>, <a href="./rfc3688">RFC 3688</a>, |
| 1161 |
January 2004. |
| 1162 |
|
| 1163 |
[<a id="ref-Rhea2004">Rhea2004</a>] |
| 1164 |
Rhea, S., Geels, D., Roscoe, T., and J. Kubiatowicz, |
| 1165 |
"Handling Churn in a DHT", In Proceedings of the USENIX |
| 1166 |
Annual Technical Conference, pp. 127-140, June 2004. |
| 1167 |
|
| 1168 |
|
| 1169 |
|
| 1170 |
|
| 1171 |
|
| 1172 |
<span class="grey">Maenpaa & Camarillo Standards Track [Page 21]</span></pre> |
| 1173 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span> |
| 1174 |
<span class="grey"><a href="./rfc7363">RFC 7363</a> Self-Tuning DHT for RELOAD September 2014</span> |
| 1175 |
|
| 1176 |
|
| 1177 |
[<a id="ref-Weiss1998">Weiss1998</a>] |
| 1178 |
Weiss, M., "Data Structures and Algorithm Analysis in |
| 1179 |
C++", Addison-Wesley Longman Publishing Co., Inc., 2nd |
| 1180 |
Edition, ISBN 0201361221, 1998. |
| 1181 |
|
| 1182 |
Authors' Addresses |
| 1183 |
|
| 1184 |
Jouni Maenpaa |
| 1185 |
Ericsson |
| 1186 |
Hirsalantie 11 |
| 1187 |
Jorvas 02420 |
| 1188 |
Finland |
| 1189 |
|
| 1190 |
EMail: [email protected] |
| 1191 |
|
| 1192 |
|
| 1193 |
Gonzalo Camarillo |
| 1194 |
Ericsson |
| 1195 |
Hirsalantie 11 |
| 1196 |
Jorvas 02420 |
| 1197 |
Finland |
| 1198 |
|
| 1199 |
EMail: [email protected] |
| 1200 |
|
| 1201 |
|
| 1202 |
|
| 1203 |
|
| 1204 |
|
| 1205 |
|
| 1206 |
|
| 1207 |
|
| 1208 |
|
| 1209 |
|
| 1210 |
|
| 1211 |
|
| 1212 |
|
| 1213 |
|
| 1214 |
|
| 1215 |
|
| 1216 |
|
| 1217 |
|
| 1218 |
|
| 1219 |
|
| 1220 |
|
| 1221 |
|
| 1222 |
|
| 1223 |
|
| 1224 |
|
| 1225 |
|
| 1226 |
|
| 1227 |
|
| 1228 |
Maenpaa & Camarillo Standards Track [Page 22] |
| 1229 |
</pre> |