draft-ietf-p2psip-self-tuning-09.txt   draft-ietf-p2psip-self-tuning-10.txt 
P2PSIP Working Group J. Maenpaa P2PSIP Working Group J. Maenpaa
Internet-Draft G. Camarillo Internet-Draft G. Camarillo
Intended status: Standards Track Ericsson Intended status: Standards Track Ericsson
Expires: February 11, 2014 August 10, 2013 Expires: August 6, 2014 February 2, 2014
Self-tuning Distributed Hash Table (DHT) for REsource LOcation And Self-tuning Distributed Hash Table (DHT) for REsource LOcation And
Discovery (RELOAD) Discovery (RELOAD)
draft-ietf-p2psip-self-tuning-09.txt draft-ietf-p2psip-self-tuning-10.txt
Abstract Abstract
REsource LOcation And Discovery (RELOAD) is a peer-to-peer (P2P) REsource LOcation And Discovery (RELOAD) is a peer-to-peer (P2P)
signaling protocol that provides an overlay network service. Peers signaling protocol that provides an overlay network service. Peers
in a RELOAD overlay network collectively run an overlay algorithm to in a RELOAD overlay network collectively run an overlay algorithm to
organize the overlay, and to store and retrieve data. This document organize the overlay, and to store and retrieve data. This document
describes how the default topology plugin of RELOAD can be extended describes how the default topology plugin of RELOAD can be extended
to support self-tuning, that is, to adapt to changing operating to support self-tuning, that is, to adapt to changing operating
conditions such as churn and network size. conditions such as churn and network size.
skipping to change at page 1, line 37 skipping to change at page 1, line 37
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on February 11, 2014. This Internet-Draft will expire on August 6, 2014.
Copyright Notice Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Introduction to Stabilization in DHTs . . . . . . . . . . . . 5 3. Introduction to Stabilization in DHTs . . . . . . . . . . . . 5
3.1. Reactive vs. Periodic Stabilization . . . . . . . . . . . 5 3.1. Reactive vs. Periodic Stabilization . . . . . . . . . . . 5
3.2. Configuring Periodic Stabilization . . . . . . . . . . . 6 3.2. Configuring Periodic Stabilization . . . . . . . . . . . 6
3.3. Adaptive Stabilization . . . . . . . . . . . . . . . . . 7 3.3. Adaptive Stabilization . . . . . . . . . . . . . . . . . 7
4. Introduction to Chord . . . . . . . . . . . . . . . . . . . . 7 4. Introduction to Chord . . . . . . . . . . . . . . . . . . . . 8
5. Extending Chord-reload to Support Self-tuning . . . . . . . . 9 5. Extending Chord-reload to Support Self-tuning . . . . . . . . 9
5.1. Update Requests . . . . . . . . . . . . . . . . . . . . . 9 5.1. Update Requests . . . . . . . . . . . . . . . . . . . . . 10
5.2. Neighbor Stabilization . . . . . . . . . . . . . . . . . 10 5.2. Neighbor Stabilization . . . . . . . . . . . . . . . . . 10
5.3. Finger Stabilization . . . . . . . . . . . . . . . . . . 11 5.3. Finger Stabilization . . . . . . . . . . . . . . . . . . 11
5.4. Adjusting Finger Table Size . . . . . . . . . . . . . . . 11 5.4. Adjusting Finger Table Size . . . . . . . . . . . . . . . 11
5.5. Detecting Partitioning . . . . . . . . . . . . . . . . . 11 5.5. Detecting Partitioning . . . . . . . . . . . . . . . . . 11
5.6. Leaving the Overlay . . . . . . . . . . . . . . . . . . . 11 5.6. Leaving the Overlay . . . . . . . . . . . . . . . . . . . 12
6. Self-tuning Chord Parameters . . . . . . . . . . . . . . . . 12 6. Self-tuning Chord Parameters . . . . . . . . . . . . . . . . 12
6.1. Estimating Overlay Size . . . . . . . . . . . . . . . . . 12 6.1. Estimating Overlay Size . . . . . . . . . . . . . . . . . 12
6.2. Determining Routing Table Size . . . . . . . . . . . . . 13 6.2. Determining Routing Table Size . . . . . . . . . . . . . 13
6.3. Estimating Failure Rate . . . . . . . . . . . . . . . . . 13 6.3. Estimating Failure Rate . . . . . . . . . . . . . . . . . 13
6.3.1. Detecting Failures . . . . . . . . . . . . . . . . . 14 6.3.1. Detecting Failures . . . . . . . . . . . . . . . . . 14
6.4. Estimating Join Rate . . . . . . . . . . . . . . . . . . 15 6.4. Estimating Join Rate . . . . . . . . . . . . . . . . . . 15
6.5. Estimate Sharing . . . . . . . . . . . . . . . . . . . . 15 6.5. Estimate Sharing . . . . . . . . . . . . . . . . . . . . 15
6.6. Calculating the Stabilization Interval . . . . . . . . . 16 6.6. Calculating the Stabilization Interval . . . . . . . . . 16
7. Overlay Configuration Document Extension . . . . . . . . . . 17 7. Overlay Configuration Document Extension . . . . . . . . . . 17
8. Security Considerations . . . . . . . . . . . . . . . . . . . 17 8. Security Considerations . . . . . . . . . . . . . . . . . . . 18
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
9.1. Message Extensions . . . . . . . . . . . . . . . . . . . 18 9.1. Message Extensions . . . . . . . . . . . . . . . . . . . 18
10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 18 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 18
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 18 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
11.1. Normative References . . . . . . . . . . . . . . . . . . 19 11.1. Normative References . . . . . . . . . . . . . . . . . . 19
11.2. Informative References . . . . . . . . . . . . . . . . . 19 11.2. Informative References . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 21
1. Introduction 1. Introduction
REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a
peer-to-peer signaling protocol that can be used to maintain an peer-to-peer signaling protocol that can be used to maintain an
overlay network, and to store data in and retrieve data from the overlay network, and to store data in and retrieve data from the
overlay. For interoperability reasons, RELOAD specifies one overlay overlay. For interoperability reasons, RELOAD specifies one overlay
skipping to change at page 13, line 5 skipping to change at page 13, line 5
from the numBitsInNodeId-bit identifier space, the average distance from the numBitsInNodeId-bit identifier space, the average distance
between peer identifiers in the successor set is (2^numBitsInNodeId)/ between peer identifiers in the successor set is (2^numBitsInNodeId)/
N. N.
To estimate the overlay network size, a peer MUST compute the average To estimate the overlay network size, a peer MUST compute the average
inter-peer distance d between the successive peers starting from the inter-peer distance d between the successive peers starting from the
most distant predecessor and ending to the most distant successor in most distant predecessor and ending to the most distant successor in
the successor list. The estimated network size MUST be calculated the successor list. The estimated network size MUST be calculated
as: as:
2^numBitsInNodeId 2^numBitsInNodeId
N = ------------------- N = -------------------
d d
This estimate has been found to be accurate within 15% of the real This estimate has been found to be accurate within 15% of the real
network size [ghinita2006]. Of course, the size of the neighborhood network size [ghinita2006]. Of course, the size of the neighborhood
set affects the accuracy of the estimate. set affects the accuracy of the estimate.
During the join process, a joining peer fills its routing table by During the join process, a joining peer fills its routing table by
sending a series of Ping and Attach requests, as specified in RELOAD sending a series of Ping and Attach requests, as specified in RELOAD
base [I-D.ietf-p2psip-base]. Thus, a joining peer immediately has base [I-D.ietf-p2psip-base]. Thus, a joining peer immediately has
enough information at its disposal to calculate an estimate of the enough information at its disposal to calculate an estimate of the
network size. network size.
skipping to change at page 13, line 48 skipping to change at page 13, line 48
to a Poisson process with rate L and leave according to a Poisson to a Poisson process with rate L and leave according to a Poisson
process with rate parameter U [mahajan2003]. The value of U can be process with rate parameter U [mahajan2003]. The value of U can be
estimated using peer failures in the finger table and neighborhood estimated using peer failures in the finger table and neighborhood
set [mahajan2003]. If peers fail with rate U, a peer with M unique set [mahajan2003]. If peers fail with rate U, a peer with M unique
peer identifiers in its routing table should observe K failures in peer identifiers in its routing table should observe K failures in
time K/(M*U). Every peer in the overlay MUST maintain a history of time K/(M*U). Every peer in the overlay MUST maintain a history of
the last K failures. The current time MUST be inserted into the the last K failures. The current time MUST be inserted into the
history when the peer joins the overlay. The estimate of U MUST be history when the peer joins the overlay. The estimate of U MUST be
calculated as: calculated as:
k k
U = --------, U = --------,
M * Tk M * Tk
where M is the number of unique peer identifiers in the routing where M is the number of unique peer identifiers in the routing
table, Tk is the time between the first and the last failure in the table, Tk is the time between the first and the last failure in the
history, and k is the number of failures in the history. If k is history, and k is the number of failures in the history. If k is
smaller than K, the estimate MUST be computed as if there was a smaller than K, the estimate MUST be computed as if there was a
failure at the current time. It has been shown that an estimate failure at the current time. It has been shown that an estimate
calculated in a similar manner is accurate within 17% of the real calculated in a similar manner is accurate within 17% of the real
value of U [ghinita2006]. value of U [ghinita2006].
The size of the failure history K affects the accuracy of the The size of the failure history K affects the accuracy of the
skipping to change at page 15, line 15 skipping to change at page 15, line 15
6.4. Estimating Join Rate 6.4. Estimating Join Rate
Reference [ghinita2006] proposes that a peer can estimate the join Reference [ghinita2006] proposes that a peer can estimate the join
rate based on the uptime of the peers in its routing table. An rate based on the uptime of the peers in its routing table. An
increase in peer join rate will be reflected by a decrease in the increase in peer join rate will be reflected by a decrease in the
average age of peers in the routing table. Thus, each peer MUST average age of peers in the routing table. Thus, each peer MUST
maintain an array of the ages of the peers in its routing table maintain an array of the ages of the peers in its routing table
sorted in increasing order. Using this information, an estimate of sorted in increasing order. Using this information, an estimate of
the global peer join rate L MUST be calculated as: the global peer join rate L MUST be calculated as:
N N
L = ---------------, L = ---------------,
Ages[rsize/2] Ages[rsize/2]
where Ages is an array containing the ages of the peers in the where Ages is an array containing the ages of the peers in the
routing table sorted in increasing order and rsize is the size of the routing table sorted in increasing order and rsize is the size of the
routing table. It has been shown that the estimate obtained by using routing table. It has been shown that the estimate obtained by using
this method is accurate within 22% of the real join rate this method is accurate within 22% of the real join rate
[ghinita2006]. Of course, the size of the routing table affects the [ghinita2006]. Of course, the size of the routing table affects the
accuracy. accuracy.
In order for this mechanism to work, peers need to exchange In order for this mechanism to work, peers need to exchange
information about the time they have been present in the overlay. information about the time they have been present in the overlay.
skipping to change at page 16, line 13 skipping to change at page 16, line 13
contain a SelfTuningData structure: contain a SelfTuningData structure:
struct { struct {
uint32 network_size; uint32 network_size;
uint32 join_rate; uint32 join_rate;
uint32 leave_rate; uint32 leave_rate;
} SelfTuningData; } SelfTuningData;
The contents of the SelfTuningData structure are as follows: The contents of the SelfTuningData structure are as follows:
network_size
The latest network size estimate calculated by the sender. The latest network size estimate calculated by the sender.
join_rate
The latest join rate estimate calculated by the sender. The latest join rate estimate calculated by the sender.
leave_rate
The latest leave rate estimate calculated by the sender. The latest leave rate estimate calculated by the sender.
The join and leave rates are expressed as joins or failures per 24 The join and leave rates are expressed as joins or failures per 24
hours. As an example, if the global join rate estimate a peer has hours. As an example, if the global join rate estimate a peer has
calculated is 0.123 peers/s, it would include in the join_rate field calculated is 0.123 peers/s, it would include in the join_rate field
the ceiling of the value 10627.2 (24*60*60*0.123 = 10627.2), that is, the ceiling of the value 10627.2 (24*60*60*0.123 = 10627.2), that is,
the value 10628. the value 10628.
The 'type' field of the MessageExtension structure MUST be set to The 'type' field of the MessageExtension structure MUST be set to
contain the value 'self_tuning_data'. The 'critical' field of the contain the value 'self_tuning_data'. The 'critical' field of the
skipping to change at page 16, line 43 skipping to change at page 17, line 7
data set containing its own estimate and the received estimates. data set containing its own estimate and the received estimates.
6.6. Calculating the Stabilization Interval 6.6. Calculating the Stabilization Interval
According to [liben-nowell2002], a Chord network in a ring-like state According to [liben-nowell2002], a Chord network in a ring-like state
remains in a ring-like state as long as peers send Omega(log2(N))^2 remains in a ring-like state as long as peers send Omega(log2(N))^2
messages before N new peers join or N/2 peers fail. We can use the messages before N new peers join or N/2 peers fail. We can use the
estimate of peer failure rate, U, to calculate the time Tf in which N estimate of peer failure rate, U, to calculate the time Tf in which N
/2 peers fail: /2 peers fail:
1 1
Tf = ------ Tf = ------
2*U 2*U
Based on this estimate, a stabilization interval Tstab-1 MUST be Based on this estimate, a stabilization interval Tstab-1 MUST be
calculated as: calculated as:
Tf Tf
Tstab-1 = ----------- Tstab-1 = -----------
log2^2(N) log2^2(N)
On the other hand, the estimated join rate L can be used to calculate On the other hand, the estimated join rate L can be used to calculate
the time in which N new peers join the overlay. Based on the the time in which N new peers join the overlay. Based on the
estimate of L, a stabilization interval Tstab-2 MUST be calculated estimate of L, a stabilization interval Tstab-2 MUST be calculated
as: as:
N N
Tstab-2 = --------------- Tstab-2 = ---------------
L * log2^2(N) L * log2^2(N)
Finally, the actual stabilization interval Tstab that MUST be used Finally, the actual stabilization interval Tstab that MUST be used
can be obtained by taking the minimum of Tstab-1 and Tstab-2. can be obtained by taking the minimum of Tstab-1 and Tstab-2.
The results obtained in [maenpaa2009] indicate that making the The results obtained in [maenpaa2009] indicate that making the
stabilization interval too small has the effect of making the overlay stabilization interval too small has the effect of making the overlay
less stable (e.g., in terms of detected loops and path failures). less stable (e.g., in terms of detected loops and path failures).
Thus, a lower limit should be used for the stabilization period. Thus, a lower limit should be used for the stabilization period.
Based on the results in [maenpaa2009], a lower limit of 15s is Based on the results in [maenpaa2009], a lower limit of 15s is
RECOMMENDED, since using a stabilization period smaller than this RECOMMENDED, since using a stabilization period smaller than this
skipping to change at page 19, line 4 skipping to change at page 19, line 6
Note to RFC Editor: please replace AAAA with the RFC number for this Note to RFC Editor: please replace AAAA with the RFC number for this
specification. specification.
10. Acknowledgments 10. Acknowledgments
The authors would like to thank Jani Hautakorpi for his contributions The authors would like to thank Jani Hautakorpi for his contributions
to the document. The authors would also like to thank Carlos to the document. The authors would also like to thank Carlos
Bernardos for his comments on the document. Bernardos for his comments on the document.
11. References 11. References
11.1. Normative References 11.1. Normative References
[I-D.ietf-p2psip-base] [I-D.ietf-p2psip-base]
Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and
H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) H. Schulzrinne, "REsource LOcation And Discovery (RELOAD)
Base Protocol", draft-ietf-p2psip-base-26 (work in Base Protocol", draft-ietf-p2psip-base-26 (work in
progress), February 2013. progress), February 2013.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels ", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5245] Rosenberg, J., "Interactive Connectivity Establishment [RFC5245] Rosenberg, J., "Interactive Connectivity Establishment
(ICE): A Protocol for Network Address Translator (NAT) (ICE): A Protocol for Network Address Translator (NAT)
Traversal for Offer/Answer Protocols", RFC 5245, April Traversal for Offer/Answer Protocols", RFC 5245, April
2010. 2010.
[RFC5389] Rosenberg, J., Mahy, R., Matthews, P., and D. Wing, [RFC5389] Rosenberg, J., Mahy, R., Matthews, P., and D. Wing,
"Session Traversal Utilities for NAT (STUN)", RFC 5389, "Session Traversal Utilities for NAT (STUN)", RFC 5389,
October 2008. October 2008.
 End of changes. 20 change blocks. 
28 lines changed or deleted 35 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/