draft-ietf-p2psip-self-tuning-08.txt   draft-ietf-p2psip-self-tuning-09.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: August 20, 2013 February 16, 2013 Expires: February 11, 2014 August 10, 2013
A 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-08.txt draft-ietf-p2psip-self-tuning-09.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.
Status of this Memo Status of This Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
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 August 20, 2013. This Internet-Draft will expire on February 11, 2014.
Copyright Notice Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the Copyright (c) 2013 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 . . . . . . . . . . . . . . . . . . . . . . . . . 3 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 . . . . . . . . . . . . . . . . . . . . 7
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 . . . . . . . . . . . . . . . . . . . . . 9
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 . . . . . . . . . . . . . . . . . . . 11
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 . . . . . . . . . . . . . . . . . . . 14 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 . . . . . . . . . . . . . . . . . . . 17
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 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 . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.1. Normative References . . . . . . . . . . . . . . . . . . . 18 11.1. Normative References . . . . . . . . . . . . . . . . . . 19
11.2. Informative References . . . . . . . . . . . . . . . . . . 18 11.2. Informative References . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 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
algorithm, called chord-reload, that is mandatory to implement. This algorithm, called chord-reload, that is mandatory to implement. This
document extends the chord-reload algorithm by introducing self- document extends the chord-reload algorithm by introducing self-
tuning behavior. tuning behavior.
DHT-based overlay networks are self-organizing, scalable and Distributed Hash Table (DHT) based overlay networks are self-
reliable. However, these features come at a cost: peers in the organizing, scalable and reliable. However, these features come at a
overlay network need to consume network bandwidth to maintain routing cost: peers in the overlay network need to consume network bandwidth
state. Most DHTs use a periodic stabilization routine to counter the to maintain routing state. Most DHTs use a periodic stabilization
undesirable effects of churn on routing. To configure the parameters routine to counter the undesirable effects of churn on routing. To
of a DHT, some characteristics such as churn rate and network size configure the parameters of a DHT, some characteristics such as churn
need to be known in advance. These characteristics are then used to rate and network size need to be known in advance. These
configure the DHT in a static fashion by using fixed values for characteristics are then used to configure the DHT in a static
parameters such as the size of the successor set, size of the routing fashion by using fixed values for parameters such as the size of the
table, and rate of maintenance messages. The problem with this successor set, size of the routing table, and rate of maintenance
approach is that it is not possible to achieve a low failure rate and messages. The problem with this approach is that it is not possible
a low communication overhead by using fixed parameters. Instead, a to achieve a low failure rate and a low communication overhead by
better approach is to allow the system to take into account the using fixed parameters. Instead, a better approach is to allow the
evolution of network conditions and adapt to them. This document system to take into account the evolution of network conditions and
extends the mandatory-to-implement chord-reload algorithm by making adapt to them. This document extends the mandatory-to-implement
it self-tuning. Two main advantages of self-tuning are that users no chord-reload algorithm by making it self-tuning. Two main advantages
longer need to tune every DHT parameter correctly for a given of self-tuning are that users no longer need to tune every DHT
operating environment and that the system adapts to changing parameter correctly for a given operating environment and that the
operating conditions. system adapts to changing operating conditions.
The remainder of this document is structured as follows: Section 2 The remainder of this document is structured as follows: Section 2
provides definitions of terms used in this document. Section 3 provides definitions of terms used in this document. Section 3
discusses alternative approaches to stabilization operations in DHTs, discusses alternative approaches to stabilization operations in DHTs,
including reactive stabilization, periodic stabilization, and including reactive stabilization, periodic stabilization, and
adaptive stabilization. Section 4 gives an introduction to the Chord adaptive stabilization. Section 4 gives an introduction to the Chord
DHT algorithm. Section 5 describes how this document extends the DHT algorithm. Section 5 describes how this document extends the
stabilization routine of the chord-reload algorithm. Section 6 stabilization routine of the chord-reload algorithm. Section 6
describes how the stabilization rate and routing table size are describes how the stabilization rate and routing table size are
calculated in an adaptive fashion. calculated in an adaptive fashion.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
document are to be interpreted as described in RFC 2119 [RFC2119]. "OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119].
This document uses the terminology and definitions from the Concepts This document uses the terminology and definitions from the Concepts
and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts] and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts]
draft. draft.
Chord Ring: The Chord DHT orders identifiers on an identifier circle numBitsInNodeId: Specifies the number of bits in a RELOAD Node-ID.
of size 2^numBitsInNodeId (numBitsInNodeId is the number of bits
in node identifiers). This identifier circle is called the Chord
ring.
DHT: Distributed Hash Tables (DHTs) are a class of decentralized DHT: Distributed Hash Tables (DHTs) are a class of decentralized
distributed systems that provide a lookup service similar to a distributed systems that provide a lookup service similar to a
hash table. Given a key, any participating peer can retrieve the regular hash table. Given a key, any peer participating in the
value associated with that key. The responsibility for system can retrieve the value associated with that key. The
maintaining the mapping from keys to values is distributed among responsibility for maintaining the mapping from keys to values is
the peers. distributed among the peers.
Finger Table: A data structure with up to numBitsInNodeId entries
maintained by each peer in a Chord-based overlay. The ith entry
in the finger table of peer n contains the identity of the first
peer that succeeds n by at least 2^(numBitsInNodeId-i) on the
Chord ring. This peer is called the ith finger of peer n. As an
example, the first entry in the finger table of peer n contains a
peer half-way around the Chord ring from peer n. The purpose of
the finger table is to accelerate lookups.
log2(N): Logarithm of N with base 2.
n.id: Peer-ID of peer n. Chord Ring: The Chord DHT uses ring topology and orders identifiers
on an identifier circle of size 2^numBitsInNodeId. This
identifier circle is called the Chord ring. On the Chord ring,
the responsibility for a key k is assigned to the node whose
identifier equals to or immediately follows k.
Neighborhood Set: Consists of successor and predecessor lists. Finger Table: A data structure with up to (but typically less than)
numBitsInNodeId entries maintained by each peer in a Chord-based
overlay. The ith entry in the finger table of peer n contains the
identity of the first peer that succeeds n by at least
2^(numBitsInNodeId-i) on the Chord ring. This peer is called the
ith finger of peer n. As an example, the first entry in the finger
table of peer n contains a peer half-way around the Chord ring
from peer n. The purpose of the finger table is to accelerate
lookups.
numBitsInNodeId: Number of bits in a Node-ID. n.id: An abbreviation that is in this document used refer to the
Node-ID of peer n.
O(g(n)): Informally, saying that some equation f(n) = O(g(n)) means O(g(n)): Informally, saying that some equation f(n) = O(g(n)) means
that f(n) is less than some constant multiple of g(n). that f(n) is less than some constant multiple of g(n).
Omega(g(n)): Informally, saying that some equation f(n) = Omega(g(n)): Informally, saying that some equation f(n) =
Omega(g(n)) means that f(n) is more than some constant multiple of Omega(g(n)) means that f(n) is more than some constant multiple of
g(n). g(n).
Predecessor List: A data structure containing the predecessors of a Predecessor List: A data structure containing the first predecessors
peer on the Chord ring. of a peer on the Chord ring.
Routing Table: The set of peers that a node can use to route overlay
messages. The routing table consists of the finger table,
successor list and predecessor list.
Successor List: A data structure containing the first r successors Successor List: A data structure containing the first r successors
of a peer on the Chord ring. of a peer on the Chord ring.
Neighborhood Set: A term used to refer to the set of peers included
in the successor and predecessor lists of a given peer.
Routing Table: Contents of a given peer's routing table include the
set of peers that the peer can use to route overlay messages. The
routing table is made up of the finger table, successor list and
predecessor list.
3. Introduction to Stabilization in DHTs 3. Introduction to Stabilization in DHTs
DHTs use stabilization routines to counter the undesirable effects of DHTs use stabilization routines to counter the undesirable effects of
churn on routing. The purpose of stabilization is to keep the churn on routing. The purpose of stabilization is to keep the
routing information of each peer in the overlay consistent with the routing information of each peer in the overlay consistent with the
constantly changing overlay topology. There are two alternative constantly changing overlay topology. There are two alternative
approaches to stabilization: periodic and reactive [rhea2004]. approaches to stabilization: periodic and reactive [rhea2004].
Periodic stabilization can either use a fixed stabilization rate or Periodic stabilization can either use a fixed stabilization rate or
calculate the stabilization rate in an adaptive fashion. calculate the stabilization rate in an adaptive fashion.
skipping to change at page 7, line 4 skipping to change at page 6, line 46
size of the overlay and its churn rate) do not remain static but size of the overlay and its churn rate) do not remain static but
evolve with time, it is not possible to achieve both a low lookup evolve with time, it is not possible to achieve both a low lookup
failure rate and a low communication overhead by using fixed failure rate and a low communication overhead by using fixed
parameters [ghinita2006]. parameters [ghinita2006].
As an example, to configure the Chord DHT algorithm, one needs to As an example, to configure the Chord DHT algorithm, one needs to
select values for the following parameters: size of successor list, select values for the following parameters: size of successor list,
stabilization interval, and size of the finger table. To select an stabilization interval, and size of the finger table. To select an
appropriate value for the stabilization interval, one needs to know appropriate value for the stabilization interval, one needs to know
the expected churn rate and overlay size. According to the expected churn rate and overlay size. According to
[liben-nowell2002], a Chord network in a ring-like state remains in a [liben-nowell2002], a Chord network in a ring-like state remains in a
ring-like state as long as peers send Omega(log2^2(N)) messages ring-like state as long as peers send Omega(log2^2(N)) messages
before N new peers join or N/2 peers fail. Thus, in a 500-peer before N new peers join or N/2 peers fail. Thus, in a 500-peer
overlay churning at a rate such that one peer joins and one peer overlay churning at a rate such that one peer joins and one peer
leaves the network every 30 seconds, an appropriate stabilization leaves the network every 30 seconds, an appropriate stabilization
interval would be on the order of 93s. According to [Chord], the interval would be on the order of 93s. According to [Chord], the size
size of the successor list and finger table should be on the order of of the successor list and finger table should be on the order of
log2(N). Having a successor list of size O(log2(N)) makes it log2(N). Having a successor list of size O(log2(N)) makes it
unlikely that a peer will lose all of its successors, which would unlikely that a peer will lose all of its successors, which would
cause the Chord ring to become disconnected. Thus, in a 500-peer cause the Chord ring to become disconnected. Thus, in a 500-peer
network each peer should maintain on the order of nine successors and network each peer should maintain on the order of nine successors and
fingers. However, if the churn rate doubles and the network size fingers. However, if the churn rate doubles and the network size
remains unchanged, the stabilization rate should double as well. remains unchanged, the stabilization rate should double as well.
That is, the appropriate maintenance interval would now be on the That is, the appropriate maintenance interval would now be on the
order of 46s. On the other hand, if the churn rate becomes e.g. six- order of 46s. On the other hand, if the churn rate becomes e.g. six-
fold and the size of the network grows to 2000 peers, on the order of fold and the size of the network grows to 2000 peers, on the order of
eleven fingers and successors should be maintained and the eleven fingers and successors should be maintained and the
stabilization interval should be on the order of 42s. If one stabilization interval should be on the order of 42s. If one
continued using the old values, this could result in inaccurate continued using the old values, this could result in inaccurate
routing tables, network partitioning, and deteriorating performance. routing tables, network partitioning, and deteriorating performance.
3.3. Adaptive Stabilization 3.3. Adaptive Stabilization
A self-tuning DHT takes into consideration the continuous evolution A self-tuning DHT takes into consideration the continuous evolution
of network conditions and adapts to them. In a self-tuning DHT, each of network conditions and adapts to them. In a self-tuning DHT, each
peer collects statistical data about the network and dynamically peer collects statistical data about the network and dynamically
adjusts its stabilization rate, neighborhood set size, and finger adjusts its stabilization rate, neighborhood set size, and finger
table size based on the analysis of the data [ghinita2006]. table size based on the analysis of the data [ghinita2006].
skipping to change at page 8, line 21 skipping to change at page 8, line 13
requiring each peer to only know how to contact its current successor requiring each peer to only know how to contact its current successor
on the identifier circle. Queries for a given identifier could then on the identifier circle. Queries for a given identifier could then
be passed around the circle via the successor pointers until they be passed around the circle via the successor pointers until they
encounter the first peer whose identifier is equal to or larger than encounter the first peer whose identifier is equal to or larger than
the desired identifier. Such a lookup scheme uses a number of the desired identifier. Such a lookup scheme uses a number of
messages that grows linearly with the number of peers. To reduce the messages that grows linearly with the number of peers. To reduce the
cost of lookups, Chord maintains also additional routing information; cost of lookups, Chord maintains also additional routing information;
each peer n maintains a data structure with up to numBitsInNodeId each peer n maintains a data structure with up to numBitsInNodeId
entries, called the finger table. The first entry in the finger entries, called the finger table. The first entry in the finger
table of peer n contains the peer half-way around the ring from peer table of peer n contains the peer half-way around the ring from peer
n. The second entry contains the peer that is 1/4th of the way n. The second entry contains the peer that is 1/4th of the way
around, the third entry the peer that is 1/8th of the way around, around, the third entry the peer that is 1/8th of the way around,
etc. In other words, the ith entry in the finger table at peer n etc. In other words, the ith entry in the finger table at peer n
contains the identity of the first peer s that succeeds n by at least contains the identity of the first peer s that succeeds n by at least
2^(numBitsInNodeId-i) on the Chord ring. This peer is called the ith 2^(numBitsInNodeId-i) on the Chord ring. This peer is called the ith
finger of peer n. The interval between two consecutive fingers is finger of peer n. The interval between two consecutive fingers is
called a finger interval. The ith finger interval of peer n covers called a finger interval. The ith finger interval of peer n covers
the range [n.id + 2^(numBitsInNodeId-i), n.id + the range [n.id + 2^(numBitsInNodeId-i), n.id +
2^(numBitsInNodeId-i+1)) on the Chord ring. In an N-peer network, 2^(numBitsInNodeId-i+1)) on the Chord ring. In an N-peer network,
each peer maintains information about O(log2(N)) other peers in its each peer maintains information about O(log2(N)) other peers in its
finger table. As an example, if N=100000, it is sufficient to finger table. As an example, if N=100000, it is sufficient to
maintain 17 fingers. maintain 17 fingers.
Chord needs all peers' successor pointers to be up to date in order Chord needs all peers' successor pointers to be up to date in order
to ensure that lookups produce correct results as the set of to ensure that lookups produce correct results as the set of
participating peers changes. To achieve this, peers run a participating peers changes. To achieve this, peers run a
skipping to change at page 12, line 27 skipping to change at page 12, line 40
6.1. Estimating Overlay Size 6.1. Estimating Overlay Size
Techniques for estimating the size of an overlay network have been Techniques for estimating the size of an overlay network have been
proposed for instance in [mahajan2003], [horowitz2003], proposed for instance in [mahajan2003], [horowitz2003],
[kostoulas2005], [binzenhofer2006], and [ghinita2006]. In Chord, the [kostoulas2005], [binzenhofer2006], and [ghinita2006]. In Chord, the
density of peer identifiers in the neighborhood set can be used to density of peer identifiers in the neighborhood set can be used to
produce an estimate of the size of the overlay, N [mahajan2003]. produce an estimate of the size of the overlay, N [mahajan2003].
Since peer identifiers are picked randomly with uniform probability Since peer identifiers are picked randomly with uniform probability
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 between peer identifiers in the successor set is (2^numBitsInNodeId)/
(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 34 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 14, line 11 skipping to change at page 14, line 27
may cause a peer to overreact each time a new failure occurs. In may cause a peer to overreact each time a new failure occurs. In
[ghinita2006], K is set 25% of the routing table size. Use of this [ghinita2006], K is set 25% of the routing table size. Use of this
approach is RECOMMENDED. approach is RECOMMENDED.
6.3.1. Detecting Failures 6.3.1. Detecting Failures
A new failure MUST be inserted to the failure history in the A new failure MUST be inserted to the failure history in the
following cases: following cases:
1. A Leave request is received from a neigbhor. 1. A Leave request is received from a neigbhor.
2. A peer fails to reply to a Ping request sent in the situation 2. A peer fails to reply to a Ping request sent in the situation
explained below. If no packets have been received on a explained below. If no packets have been received on a
connection during the past 2*Tr seconds (where Tr is the connection during the past 2*Tr seconds (where Tr is the
inactivity timer defined by ICE [I-D.ietf-mmusic-ice]), a RELOAD inactivity timer defined by ICE [RFC5245]), a RELOAD Ping request
Ping request MUST be sent to the remote peer. RELOAD mandates MUST be sent to the remote peer. RELOAD mandates the use of STUN
the use of STUN [RFC5389] for keepalives. STUN keepalives take [RFC5389] for keepalives. STUN keepalives take the form of STUN
the form of STUN Binding Indication transactions. As specified Binding Indication transactions. As specified in ICE [RFC5245],
in ICE [I-D.ietf-mmusic-ice], a peer sends a STUN Binding a peer sends a STUN Binding Indication if there has been no
Indication if there has been no packet sent on a connection for packet sent on a connection for Tr seconds. Tr is configurable
Tr seconds. Tr is configurable and has a default of 15 seconds. and has a default of 15 seconds. Although STUN Binding
Although STUN Binding Indications do not generate a response, the Indications do not generate a response, the fact that a peer has
fact that a peer has failed can be learned from the lack of failed can be learned from the lack of packets (Binding
packets (Binding Indications or application protocol packets) Indications or application protocol packets) received from the
received from the peer. If the remote peer fails to reply to the peer. If the remote peer fails to reply to the Ping request, the
Ping request, the sender MUST consider the remote peer to have sender MUST consider the remote peer to have failed.
failed.
As an alternative to relying on STUN keepalives to detect peer As an alternative to relying on STUN keepalives to detect peer
failure, a peer could send additional, frequent RELOAD messages to failure, a peer could send additional, frequent RELOAD messages to
every peer in its Connection Table. These messages could be Update every peer in its Connection Table. These messages could be Update
requests, in which case they would serve two purposes: detecting peer requests, in which case they would serve two purposes: detecting peer
failure and stabilization. However, as the cost of this approach can failure and stabilization. However, as the cost of this approach can
be very high in terms of bandwidth consumption and traffic load, be very high in terms of bandwidth consumption and traffic load,
especially in large-scale overlays experiencing churn, its use is NOT especially in large-scale overlays experiencing churn, its use is NOT
RECOMMENDED. RECOMMENDED.
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 1 N
L = --- * ---------------, L = ---------------,
4 Ages[rsize/4] 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 is RECOMMENDED that only the ages of the 25% of routing table. It has been shown that the estimate obtained by using
the youngest peers in the routing table (i.e., the 25th percentile) this method is accurate within 22% of the real join rate
are used to reduce the bias that a small number of peers with very [ghinita2006]. Of course, the size of the routing table affects the
old ages can cause [ghinita2006]. It has been shown that the accuracy.
estimate obtained by using this method is accurate within 22% of the
real join rate [ghinita2006]. Of course, the size of the routing
table affects the accuracy.
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.
Peers receive the uptimes of their successors and predecessors during Peers receive the uptimes of their successors and predecessors during
the stabilization operations since all Update requests carry uptime the stabilization operations since all Update requests carry uptime
values. A joining peer learns the uptime of the admitting peer since values. A joining peer learns the uptime of the admitting peer since
it receives an Update from the admitting peer during the join it receives an Update from the admitting peer during the join
procedure. Peers learn the uptimes of new fingers since they can procedure. Peers learn the uptimes of new fingers since they can
fetch the uptime using a Probe request after having attached to the fetch the uptime using a Probe request after having attached to the
new finger. new finger.
skipping to change at page 16, line 5 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 value 10627 (24*60*60*0.123 = 10627.2). the ceiling of the value 10627.2 (24*60*60*0.123 = 10627.2), that is,
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
structure MUST be set to False. structure MUST be set to False.
A peer MUST store all estimates it receives in Probe requests and A peer MUST store all estimates it receives in Probe requests and
answers during a stabilization interval. When the stabilization answers during a stabilization interval. When the stabilization
timer fires, the peer MUST calculate the estimates to be used during timer fires, the peer MUST calculate the estimates to be used during
the next stabilization interval by taking the 75th percentile of a the next stabilization interval by taking the 75th percentile of a
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^2(N)) 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 estimate of peer failure rate, U, to calculate the time Tf in which N
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 17, line 34 skipping to change at page 17, line 43
"configuration" element. "configuration" element.
self-tuning:number-of-peers-to-probe: The number of fingers to which self-tuning:number-of-peers-to-probe: The number of fingers to which
Probe requests are sent to obtain their network size, join rate, Probe requests are sent to obtain their network size, join rate,
and leave rate estimates. The default value is 4. and leave rate estimates. The default value is 4.
This new element is formally defined as follows: This new element is formally defined as follows:
namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning" namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning"
parameter &= element self-tuning:number-of-peers-to-probe { xsd: parameter &= element self-tuning:number-of-peers-to-probe {
unsignedInt } xsd:unsignedInt }
This namespace is added into the <mandatory-extension> element in the This namespace is added into the <mandatory-extension> element in the
overlay configuration file. overlay configuration file.
8. Security Considerations 8. Security Considerations
In the same way as malicious or compromised peers implementing the
There are no new security considerations introduced in this document. RELOAD base protocol [I-D.ietf-p2psip-base] can advertise false
The security considerations of RELOAD [I-D.ietf-p2psip-base] apply. network metrics or distribute false routing table information for
instance in RELOAD Update messages, malicious peers implementing this
specification may share false join rate, leave rate, and network size
estimates. For such attacks, the same security concerns apply as in
the RELOAD base specification. In addition, as long as the amount of
malicious peers in the overlay remains modest, the statistical
mechanisms applied in Section 6.5 (i.e., the use of 75th percentiles)
to process the shared estimates a peer obtains help ensuring that
estimates that are clearly different from (i.e., larger or smaller
than) other received estimates will not significantly influence the
process of adapting the stabilization interval and routing table
size.
9. IANA Considerations 9. IANA Considerations
9.1. Message Extensions 9.1. Message Extensions
This document introduces one additional extension to the "RELOAD This document introduces one additional extension to the "RELOAD
Extensions" Registry: Extensions" Registry:
+------------------+-------+---------------+ +------------------+-------+---------------+
| Extension Name | Code | Specification | | Extension Name | Code | Specification |
+------------------+-------+---------------+ +------------------+-------+---------------+
| self_tuning_data | 3 | RFC-AAAA | | self_tuning_data | 3 | RFC-AAAA |
+------------------+-------+---------------+ +------------------+-------+---------------+
skipping to change at page 18, line 17 skipping to change at page 18, line 34
Extensions" Registry: Extensions" Registry:
+------------------+-------+---------------+ +------------------+-------+---------------+
| Extension Name | Code | Specification | | Extension Name | Code | Specification |
+------------------+-------+---------------+ +------------------+-------+---------------+
| self_tuning_data | 3 | RFC-AAAA | | self_tuning_data | 3 | RFC-AAAA |
+------------------+-------+---------------+ +------------------+-------+---------------+
The contents of the extension are defined in Section 6.5. The contents of the extension are defined in Section 6.5.
Note to RFC Editor: please replace AAAA with the RFC number for this
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. to the document. The authors would also like to thank Carlos
Bernardos for his comments on the document.
11. References 11. References
11.1. Normative References 11.1. Normative References
[I-D.ietf-mmusic-ice]
Rosenberg, J., "Interactive Connectivity Establishment
(ICE): A Protocol for Network Address Translator (NAT)
Traversal for Offer/Answer Protocols",
draft-ietf-mmusic-ice-19 (work in progress), October 2007.
[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-24 (work in Base Protocol", draft-ietf-p2psip-base-26 (work in
progress), January 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
(ICE): A Protocol for Network Address Translator (NAT)
Traversal for Offer/Answer Protocols", RFC 5245, April
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.
11.2. Informative References 11.2. Informative References
[CAN] Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S. [CAN] Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S.
Schenker, "A scalable content-addressable network", In Schenker, "A Scalable Content-Addressable Network", In
Proc. of the 2001 Conference on Applications, Proceedings of the 2001 Conference on Applications,
Technologies, Architectures and Protocols for Computer Technologies, Architectures and Protocols for Computer
Communications 2001, pp. 161.172. Communications pp. 161-172, August 2001.
[Chord] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., [Chord] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.,
Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A
Scalable Peer-to-peer Lookup Service for Internet Scalable Peer-to-peer Lookup Service for Internet
Applications", IEEE/ACM Transactions on Networking Volume Applications", IEEE/ACM Transactions on Networking Volume
11, Issue 1, 17-32, Feb 2003. 11, Issue 1, pp. 17-32, February 2003.
[I-D.ietf-p2psip-concepts] [I-D.ietf-p2psip-concepts]
Bryan, D., Willis, D., Shim, E., Matthews, P., and S. Bryan, D., Matthews, P., Shim, E., Willis, D., and S.
Dawkins, "Concepts and Terminology for Peer to Peer SIP", Dawkins, "Concepts and Terminology for Peer to Peer SIP",
draft-ietf-p2psip-concepts-04 (work in progress), draft-ietf-p2psip-concepts-05 (work in progress), July
October 2011. 2013.
[Pastry] Rowstron, A. and P. Druschel, "Pastry: Scalable, [Pastry] Rowstron, A. and P. Druschel, "Pastry: Scalable,
Decentralized Object Location and Routing for Large-Scale Decentralized Object Location and Routing for Large-Scale
Peer-to-Peer Systems", In Proc. of the IFIP/ACM Peer-to-Peer Systems", In Proceedings of the IFIP/ACM
International Conference on Distribued Systems International Conference on Distribued Systems Platforms
Platforms Nov. 2001, pp. 329-350. pp. 329-350, November 2001.
[binzenhofer2006] [binzenhofer2006]
Binzenhofer, A., Kunzmann, G., and R. Henjes, "A scalable Binzenhofer, A., Kunzmann, G., and R. Henjes, "A Scalable
algorithm to monitor chord-based P2P systems at runtime", Algorithm to Monitor Chord-Based P2P Systems at Runtime",
20th International Parallel and Distributed Processing In Proceedings of the 20th IEEE International Parallel and
Symposium April 2006. Distributed Processing Symposium (IPDPS) pp. 1-8, April
2006.
[ghinita2006] [ghinita2006]
Ghinita, G. and Y. Teo, "An adaptive stabilization Ghinita, G. and Y. Teo, "An Adaptive Stabilization
framework for distributed hash tables", 20th International Framework for Distributed Hash Tables", In Proceedings of
Parallel and Distributed Processing Symposium April 2006. the 20th IEEE International Parallel and Distributed
Processing Symposium (IPDPS) pp. 29-38, April 2006.
[horowitz2003] [horowitz2003]
Horowitz, K. and D. Malkhi, "Estimating network size from Horowitz, K. and D. Malkhi, "Estimating Network Size from
local information", Information Processing Letters Dec. Local Information", Information Processing Letters Volume
2003, Volume 88, Issue 5, pp. 237-243. 88, Issue 5, pp. 237-243, December 2003.
[kostoulas2005] [kostoulas2005]
Kostoulas, D., Psaltoulis, D., Gupta, I., Birman, K., and Kostoulas, D., Psaltoulis, D., Gupta, I., Birman, K., and
A. Demers, "Decentralized schemes for size estimation in A. Demers, "Decentralized Schemes for Size Estimation in
large and dynamic groups", Fourth IEEE International Large and Dynamic Groups", In Proceedings of the 4th IEEE
Symposium on Network Computing and Applications July 2005, International Symposium on Network Computing and
pp. 41-48. Applications pp. 41-48, July 2005.
[krishnamurthy2008] [krishnamurthy2008]
Krishnamurthy, S., El-Ansary, S., Aurell, E., and S. Krishnamurthy, S., El-Ansary, S., Aurell, E., and S.
Haridi, "Comparing maintenance strategies for overlays", Haridi, "Comparing Maintenance Strategies for Overlays",
In Proc. of 16th Euromicro Conference on Parallel, In Proceedings of the 16th Euromicro Conference on
Distributed and Network-Based Processing Feb. 2008, pp. Parallel, Distributed and Network-Based Processing pp.
473-482. 473-482, February 2008.
[li2004] Li, J., Strinbling, J., Gil, T., and M. Kaashoek, [li2004] Li, J., Strinbling, J., Gil, T., Morris, R., and M.
"Comparing the performance of distributed hash tables Kaashoek, "Comparing the Performance of Distributed Hash
under churn", In Proc. of the 3rd International Workshop Tables Under Churn", Peer-to-Peer Systems III, volume 3279
on Peer-to-Peer Systems 2004. of Lecture Notes in Computer Science Springer, pp. 87-99,
February 2005.
[liben-nowell2002] [liben-nowell2002]
Liben-Nowell, D., Balakrishnan, H., and D. Karger, Liben-Nowell, D., Balakrishnan, H., and D. Karger,
"Observations on the dynamic evolution of peer-to-peer "Observations on the Dynamic Evolution of Peer-to-Peer
networks", In Proc. of the First International Workshop on Networks", In Proceedings of the 1st International
Peer-to-Peer Systems March 2002. Workshop on Peer-to-Peer Systems (IPTPS) pp. 22-33, March
2002.
[maenpaa2009] [maenpaa2009]
Maenpaa, J. and G. Camarillo, "A study on maintenance Maenpaa, J. and G. Camarillo, "A Study on Maintenance
operations in a Chord-based Peer-to-Peer Session Operations in a Chord-Based Peer-to-Peer Session
Initiation Protocol overlay network", In Proc. of IPDPS Initiation Protocol Overlay Network", In Proceedings of
2009 May 2009. the 23rd IEEE International Parallel and Distributed
Processing Symposium (IPDPS) pp. 1-9, May 2009.
[mahajan2003] [mahajan2003]
Mahajan, R., Castro, M., and A. Rowstron, "Controlling the Mahajan, R., Castro, M., and A. Rowstron, "Controlling the
cost of reliability in peer-to-peer overlays", In Cost of Reliability in Peer-to-Peer Overlays", In
Proceedings of the 2nd International Workshop on Peer-to- Proceedings of the 2nd International Workshop on Peer-to-
Peer Systems Feb. 2003. Peer Systems (IPTPS) pp. 21-32, February 2003.
[rhea2004] [rhea2004]
Rhea, S., Geels, D., Roscoe, T., and J. Kubiatowicz, Rhea, S., Geels, D., Roscoe, T., and J. Kubiatowicz,
"Handling churn in a DHT", In Proc. of the USENIX Annual "Handling Churn in a DHT", In Proceedings of the USENIX
Techincal Conference June 2004. Annual Technical Conference pp. 127-140, June 2004.
Authors' Addresses Authors' Addresses
Jouni Maenpaa Jouni Maenpaa
Ericsson Ericsson
Hirsalantie 11 Hirsalantie 11
Jorvas 02420 Jorvas 02420
Finland Finland
Email: Jouni.Maenpaa@ericsson.com Email: Jouni.Maenpaa@ericsson.com
 End of changes. 64 change blocks. 
199 lines changed or deleted 216 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/