Debian Codegraph @

rfc7363.html

raw
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&nbsp;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 &amp; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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="&quot;Key words for use in RFCs to Indicate Requirement Levels&quot;">RFC2119</a>].
152
153 This document uses terminology and definitions from the RELOAD base
154 specification [<a href="./rfc6940" title="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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&lt;=P&lt;=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 &amp; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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="&quot;A Scalable Content-Addressable Network&quot;">CAN</a>], Chord
266 [<a href="#ref-Chord" title="&quot;Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications&quot;">Chord</a>], Pastry [<a href="#ref-Pastry" title="&quot;Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems&quot;">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 &amp; 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 &amp; 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="&quot;Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications&quot;">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="&quot;Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications&quot;">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="&quot;Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications&quot;">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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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="&quot;Comparing the Performance of Distributed Hash Tables Under Churn&quot;">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 &amp; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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 &amp; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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="&quot;Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/Answer Protocols&quot;">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="&quot;Session Traversal Utilities for NAT (STUN)&quot;">RFC5389</a>] for keepalives.
747 STUN keepalives take the form of STUN Binding Indication
748 transactions. As specified in ICE [<a href="./rfc5245" title="&quot;Interactive Connectivity Establishment (ICE): A Protocol for Network Address Translator (NAT) Traversal for Offer/Answer Protocols&quot;">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 &amp; 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 &amp; 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 &amp; 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 &amp; 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 &amp;= element self-tuning:number-of-peers-to-probe {
958 xsd:unsignedInt }?
959
960 This namespace is added into the &lt;mandatory-extension&gt; 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="&quot;REsource LOcation And Discovery (RELOAD) Base Protocol&quot;">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 &amp; 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="&quot;The IETF XML Registry&quot;">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 &amp; 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 &amp; 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 &amp; 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 &amp; Camarillo Standards Track [Page 22]
1229 </pre>