RFC 7363

Self-Tuning Distributed Hash Table (DHT) for REsource LOcation And Discovery (RELOAD)

📅 published September 2014, from ietf

RFC 7363 Title Block 🎀

Self-Tuning Distributed Hash Table (DHT) for REsource LOcation And Discovery (RELOAD) 💖

okay so this is RFC 7363 🦋 It was put out by the Internet Engineering Task Force (IETF), and the authors are J. Maenpaa and G. Camarillo, both from Ericsson. It's a Standards Track document, so implementers are expected to follow it, and it was published in September 2014. Its ISSN is 2070-1721. The header doesn't list anything it obsoletes or updates, so it doesn't replace or change any earlier RFC 🌸

Abstract ✨

okay so REsource LOcation And Discovery (RELOAD) is a peer-to-peer (P2P) signaling protocol that gives you an overlay network service 🫶 The peers in a RELOAD overlay network team up to run an overlay algorithm that organizes the overlay and handles storing and retrieving data 💅 This doc explains how the default topology plugin of RELOAD can be extended to support self-tuning. That means it adapts to changing conditions like churn and network size 🦋

Status of This Memo 💅

This is an Internet Standards Track document ✨

It's a product of the IETF and it represents the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). If you want more on Internet Standards, check out Section 2 of RFC 5741 📚 For the current status, any errata, and how to send feedback, go to http://www.rfc-editor.org/info/rfc7363 🌈

Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved 💜

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they were in effect on the date of publication. Please read those carefully, bestie, because they describe your rights and restrictions for this document 🙈 Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License 🔥

Table of Contents 🧚

1. Introduction ....................................................2
2. Terminology .....................................................3
3. Introduction to Stabilization in DHTs ...........................5
   3.1. Reactive versus Periodic Stabilization .....................5
   3.2. Configuring Periodic Stabilization .........................6
   3.3. Adaptive Stabilization .....................................7
4. Introduction to Chord ...........................................7
5. Extending Chord-Reload to Support Self-Tuning ...................9
   5.1. Update Requests ............................................9
   5.2. Neighbor Stabilization ....................................10
   5.3. Finger Stabilization ......................................11
   5.4. Adjusting Finger Table Size ...............................11
   5.5. Detecting Partitioning ....................................11
   5.6. Leaving the Overlay .......................................11
6. Self-Tuning Chord Parameters ...................................12
   6.1. Estimating Overlay Size ...................................12
   6.2. Determining Routing Table Size ............................13
   6.3. Estimating Failure Rate ...................................13
        6.3.1. Detecting Failures .................................14
   6.4. Estimating Join Rate ......................................14
   6.5. Estimate Sharing ..........................................15
   6.6. Calculating the Stabilization Interval ....................17
7. Overlay Configuration Document Extension .......................17
8. Security Considerations ........................................18
9. IANA Considerations ............................................18
   9.1. Message Extensions ........................................18
   9.2. New Overlay Algorithm Type ................................19
   9.3. A New IETF XML Registry ...................................19
10. Acknowledgments ...............................................19
11. References ....................................................19
   11.1. Normative References .....................................19
   11.2. Informative References ...................................20

1. Introduction ✨

okay so REsource LOcation And Discovery (RELOAD) [RFC6940] is a peer-to-peer signaling protocol that can maintain an overlay network and store data in it and retrieve data from it 🫶 For interoperability reasons, RELOAD specifies one overlay algorithm, called "chord-reload", and it is mandatory to implement 💖 This document extends chord-reload by introducing self-tuning behavior ✨

DHT-based overlay networks are self-organizing, scalable, and reliable 🌸 But these perks come at a cost: peers need to use network bandwidth to maintain routing state 😭 Most DHTs run a periodic stabilization routine to counter the bad effects of churn on routing 🔥 To configure a DHT's parameters, you usually need to know things like churn rate and network size ahead of time 🙈 Those values then get used to set the DHT in a static way, with fixed values for things like the size of the successor set, the size of the routing table, and the rate of maintenance messages 💀 The problem is that a low failure rate and low communication overhead can't both be achieved with fixed parameters. A way better approach is to let the system take the evolution of network conditions into account and adapt to them 👑

This document extends the mandatory-to-implement chord-reload algorithm and makes it self-tuning. Using the self-tuning feature is optional 🦋 But when it is used, every peer in the RELOAD overlay network needs to support it 🫶 A RELOAD overlay that uses self-tuning says so in its RELOAD overlay configuration document, by using the CHORD-SELF-TUNING algorithm name from Section 9.2 in the topology-plugin element 🎀 Two main perks of self-tuning: users no longer have to tune every DHT parameter perfectly for their operating environment, and the system adapts when conditions change 🌈

The rest of this document is structured like this 💅 Section 2 defines the terms used in the document. Section 3 talks about other ways to do stabilization in DHTs, including reactive stabilization, periodic stabilization, and adaptive stabilization. Section 4 introduces the Chord DHT algorithm. Section 5 explains how this document extends the stabilization routine of chord-reload. Section 6 explains how the stabilization rate and routing table size get calculated adaptively 🧚

2. Terminology 🌸

The BCP 14 key words are "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL". In this document they are to be interpreted as described in [RFC2119] 💖

This document uses terminology and definitions from the RELOAD base specification [RFC6940] ✨

Here are the main terms, bestie 📚

  • numBitsInNodeId: The number of bits in a RELOAD Node-ID 🔢
  • DHT: Distributed Hash Tables are a class of decentralized distributed systems that offer a lookup service that works kind of like a regular hash table. Given a key, any peer in the system can retrieve the value tied to that key. The job of keeping the mapping from keys to values is spread across the peers 🫶
  • Chord Ring: The Chord DHT uses a ring topology and orders identifiers on an identifier circle of size 2^numBitsInNodeId. That circle is called the Chord ring. On the Chord ring, the responsibility for a key k goes to the node whose identifier equals to or immediately follows k 🦋
  • Finger Table: A data structure with up to (but typically fewer than) numBitsInNodeId entries, maintained by each peer in a Chord-based overlay. The ith entry in peer n's finger table holds the identity of the first peer that succeeds n by at least 2^(numBitsInNodeId-i) on the Chord ring. That peer is called the ith finger of peer n. For example, the first entry in peer n's finger table holds a peer halfway around the Chord ring from peer n. The whole point of the finger table is to speed up lookups 🚀
  • n.id: In this document, this abbreviation refers to the Node-ID of peer n 🌈
  • O(g(n)): Informally, saying that some equation f(n) = O(g(n)) means that f(n) is less than some constant multiple of g(n). For the formal definition, please see [Weiss1998] 🧠
  • Omega(g(n)): Informally, saying that some equation f(n) = Omega(g(n)) means that f(n) is more than some constant multiple of g(n). For the formal definition, please see [Weiss1998] 🧠
  • Percentile: The Pth (0<=P<=100) percentile of N values arranged in ascending order is found by first calculating the (ordinal) rank n=(P/100)*N, rounding the result to the nearest integer, and then taking the value at that rank 📊
  • Predecessor List: A data structure holding the first r predecessors of a peer on the Chord ring 🎀
  • Successor List: A data structure holding the first r successors of a peer on the Chord ring 💜
  • Neighborhood Set: The term for the set of peers included in a given peer's successor and predecessor lists 🫶
  • Routing Table: The contents of a given peer's routing table include the set of peers that peer can use to route overlay messages. The routing table is made up of the finger table, the successor list, and the predecessor list 🗺️

3. Introduction to Stabilization in DHTs 🌸

DHTs use stabilization routines to counter the bad effects of churn on routing 😭 The point of stabilization is to keep each peer's routing information consistent with the overlay topology, which keeps changing 🔄 There are two alternative approaches to stabilization: periodic and reactive [Rhea2004] ✨ Periodic stabilization can either use a fixed stabilization rate or calculate the stabilization rate adaptively 💖

3.1. Reactive versus Periodic Stabilization 🎀

okay so there are two ways a peer can do stabilization, and they're kinda opposite vibes 💅. In reactive stabilization, a peer reacts to the loss of a peer in its neighborhood set, or to the appearance of a new peer that should be added to its neighborhood set, by sending a copy of its neighbor table to all peers in the neighborhood set. Periodic recovery is the chill one 🌸. It happens independently of changes in the neighborhood set. A peer periodically shares its neighborhood set with each member of that set, or with a subset of them.

The chord-reload algorithm [RFC6940] supports both reactive and periodic stabilization ✨. [Rhea2004] showed that reactive stabilization works well for small neighborhood sets (i.e., small overlays) and moderate churn 🦋. But in large-scale overlays (e.g., 1000 peers or more [Rhea2004]) or high-churn overlays, reactive stabilization runs the risk of creating a positive feedback cycle, which can eventually result in congestion collapse 😭. [Rhea2004] also shows that a 1000-peer overlay under churn uses significantly less bandwidth and has lower latencies when periodic stabilization is used than when reactive stabilization is used. Reactive stabilization performed well when there was no churn in those experiments, but its bandwidth use jumped dramatically under churn 💀. At higher churn rates and larger overlays, periodic stabilization uses less bandwidth, and the resulting lower contention for the network leads to lower latencies 🔥.

That's why most DHTs, such as CAN [CAN], Chord [Chord], Pastry [Pastry], and Bamboo [Rhea2004], use periodic stabilization [Ghinita2006] 👑. Bamboo is a fun plot twist here 🙈. Its first version used reactive stabilization, and that caused it to suffer from degradation in performance under churn. To fix this, Bamboo was modified to use periodic stabilization.

In Chord, periodic stabilization is typically done both for successors and fingers. [Krishnamurthy2008] analyzes an alternative strategy 🧚. In this strategy, called the "correction-on-change maintenance strategy", a peer periodically stabilizes its successors but does not do so for its fingers. Instead, finger pointers are stabilized in a reactive fashion. The results in [Krishnamurthy2008] imply that although the correction-on-change strategy works well when churn is low, periodic stabilization outperforms it when churn is high 🌈.

3.2. Configuring Periodic Stabilization 🍓

When periodic stabilization is used, you have to pick an appropriate execution rate for the stabilization procedure 😤. If the execution rate is high, changes in the system get detected quickly, but the communication overhead goes up. If the stabilization rate is low and the churn rate is high, routing tables go stale and DHT performance deteriorates. So the real challenge is setting the parameters so the overlay still achieves the desired reliability and performance in challenging conditions, such as heavy churn. This naturally results in high cost when the churn level is lower than expected, or poor performance or even network partitioning when conditions are worse than expected 💅.

Besides picking a stabilization interval, you also need an appropriate size for the neighborhood set and for the finger table, whether or not periodic stabilization is used 🎀.

The current approach is to configure overlays statically ✨. That works when perfect information about the future is available. If the operating conditions of the network are known in advance and stay static for the lifetime of the system, it's possible to choose fixed optimal values for parameters such as stabilization rate, neighborhood set size, and routing table size. But if the operating conditions (e.g., the size of the overlay and its churn rate) change over time, it's not possible to get both a low lookup failure rate and a low communication overhead with fixed parameters [Ghinita2006] 😩.

Let's make it concrete with Chord 🦋. To configure the Chord DHT algorithm, you need to select values for the following parameters: size of successor list, stabilization interval, and size of the finger table. To pick a good stabilization interval, you need to know the expected churn rate and overlay size. According to [Liben-Nowell2002], a Chord network in a ring-like state remains in a ring-like state as long as peers send Omega(square(log(N))) messages before N new peers join or N/2 peers fail. So in a 500-peer overlay churning at a rate where one peer joins and one peer leaves the network every 30 seconds, an appropriate stabilization interval would be on the order of 93 s ⏰.

According to [Chord], the size of the successor list and finger table should be on the order of log(N) 🧠. A successor list of modest size already makes it very unlikely that a peer loses all of its successors, which would cause the Chord ring to become disconnected. Good options are log2(N) or 2*log2(N), and 2*log2(N) is the successor list size used in [Chord]. So in a 500-peer network, each peer should maintain on the order of nine successors and fingers 🌸. Now, if the churn rate doubles and the network size stays the same, the stabilization rate should double as well. The appropriate maintenance interval would then be on the order of 46 s 🔥. And if the churn rate becomes, e.g., six-fold and the network grows to 2000 peers, you should maintain on the order of 11 fingers and successors, with a stabilization interval on the order of 42 s 👑. If you kept using the old values, you could get inaccurate routing tables, network partitioning, and deteriorating performance 😭.

3.3. Adaptive Stabilization 🌈

A self-tuning DHT takes the continuous evolution of network conditions into account and adapts to them 🧚. In a self-tuning DHT, each peer collects statistical data about the network and dynamically adjusts its stabilization rate, neighborhood set size, and finger table size based on analysis of that data [Ghinita2006]. [Mahajan2003] shows that with self-tuning, it's possible to achieve high reliability and performance even in adverse conditions, with low maintenance cost 🙌. Adaptive stabilization has also been shown to outperform periodic stabilization in terms of both lookup failures and communication overhead [Ghinita2006] 💖.

4. Introduction to Chord ✨

Chord [Chord] is a structured P2P algorithm that uses consistent hashing to build a DHT out of several independent peers 🎀. Consistent hashing gives each peer and each resource a fixed-length identifier. Peers use SHA-1 as the base hash function to generate the identifiers. As specified in RELOAD base [RFC6940], the length of the identifiers is numBitsInNodeId=128 bits. The identifiers are ordered on an identifier circle of size 2^numBitsInNodeId. On that circle, key k is assigned to the first peer whose identifier equals or follows the identifier of k in the identifier space. The identifier circle is called the Chord ring 💅.

Different DHTs differ a lot in performance when bandwidth is limited 😮. Compared to other DHTs, Chord's advantages include that it uses bandwidth efficiently and can achieve low lookup latencies at little cost [Li2004] 🦋.

Now, a super simple lookup mechanism on a Chord ring would have each peer only know how to contact its current successor on the identifier circle 🧚. Queries for a given identifier could then get passed around the circle via the successor pointers until they hit the first peer whose identifier is equal to or larger than the desired identifier. But that scheme uses a number of messages that grows linearly with the number of peers, which is a big ngl no 💀. To reduce the cost of lookups, Chord also maintains additional routing information. Each peer n maintains a data structure with up to numBitsInNodeId entries, called the finger table. The first entry in the finger table of peer n contains the peer halfway around the ring from peer n. The second entry contains the peer that is 1/4th of the way around, the third entry the peer that is 1/8th of the way around, and so on 🌈.

Put another way, the ith entry in the finger table at peer n contains the identity of the first peer s that succeeds n by at least 2^(numBitsInNodeId-i) on the Chord ring. This peer is called the ith finger of peer n. The interval between two consecutive fingers is called a finger interval. The ith finger interval of peer n covers the range [n.id + 2^(numBitsInNodeId-i), n.id + 2^(numBitsInNodeId-i+1)) on the Chord ring 🍓. In an N-peer network, each peer maintains information about O(log(N)) other peers in its finger table. As an example, if N=100000, it's sufficient to maintain 17 fingers 🫶.

Chord needs all peers' successor pointers to be up to date so that lookups produce correct results as the set of participating peers changes 🔥. To achieve this, peers run a stabilization protocol periodically in the background. The stabilization protocol of the original Chord algorithm uses two operations: successor stabilization and finger stabilization. However, the Chord algorithm of RELOAD base defines two additional stabilization components, as we'll discuss below 👀.

To increase robustness when peers fail, each Chord peer maintains a successor list of size r, containing the peer's first r successors 💪. The benefit of successor lists is that if each peer fails independently with probability p, the probability that all r successors fail simultaneously is only p^r 🙌.

The original Chord algorithm maintains only a single predecessor pointer. But multiple predecessor pointers (i.e., a predecessor list) can be maintained to speed up recovery from predecessor failures ✨. The routing table of a peer consists of the successor list, finger table, and predecessor list 💖.

5. Extending Chord-Reload to Support Self-Tuning ✨

okay so this section is where chord-reload gets its glow-up 💅 It explains how the mandatory-to-implement chord-reload algorithm from RELOAD base [RFC6940] can be extended to support self-tuning 🦋

chord-reload supports both reactive and periodic recovery strategies, but when the self-tuning mechanisms from this document are used, the periodic recovery strategy is the one that runs 🔁 chord-reload also says a peer needs to keep at least three predecessors and three successors 🧚 When self-tuning is on, the right sizes for the successor list and predecessor list get worked out adaptively, based on the estimated network size. More on that in Section 6 🌸

Just like in RELOAD base [RFC6940], every peer has a stabilization timer ⏰ When it fires, the peer restarts the timer and runs the overlay stabilization routine. In chord-reload, overlay stabilization has four components:

  1. Update the neighbor table. We refer to this as "neighbor stabilization".
  2. Refreshing the finger table. We refer to this as "finger stabilization".
  3. Adjusting finger table size.
  4. Detecting partitioning. We refer to this as "strong stabilization".

RELOAD base [RFC6940] also has peers send periodic messages as part of neighbor stabilization, finger stabilization, and strong stabilization 📨 For neighbor stabilization, a peer periodically sends an Update request to every peer in its connection table, and the default time is every ten minutes ⏱️ For finger stabilization, a peer periodically searches for new peers to put in its finger table, and that defaults to one hour 🕐 This document also specifies how the neighbor stabilization and finger stabilization intervals can be figured out adaptively, based on what the overlay is actually doing 📊 The subsections below walk through how this document extends those four components 💖

5.1. Update Requests

As described in RELOAD base [RFC6940], neighbor and finger stabilization are implemented with Update requests 📬 RELOAD base defines three types of Update requests: 'peer_ready', 'neighbors', and 'full' 🎀 No matter the type, every Update request includes an 'uptime' field. The self-tuning extensions need to know the uptimes of peers in the routing table, so the sender of an Update request puts its current uptime (in seconds) in the 'uptime' field ⏳ No matter the type, all Update requests MUST include an 'uptime' field. That one's non-negotiable 🙅‍♀️

When self-tuning is used, each peer decides on its own what size the successor list, predecessor list, and finger table should be 🧠 So the 'predecessors', 'successors', and 'fingers' fields in RELOAD Update requests are variable length. As specified in RELOAD [RFC6940], variable-length fields are preceded by length bytes on the wire 📏 For the successor list, predecessor list, and finger table, there are two length bytes, which allows lengths up to 2^16-1. You can work out how many NodeId structures are in each field from those length bytes, because a single NodeId structure is 16 bytes 🔢

Now the important part 👀 If a peer receives more entries than will fit into its successor list, predecessor list, or finger table, the peer MUST ignore the extra entries. A peer may also receive fewer entries than it currently has in its own data structure. In that case, it uses the received entries to update only a subset of the entries in its data structure 🫶 For example, a peer with a successor list of size 8 might get a successor list of size 4 from its immediate successor. Then the received list can only update the first few successors on the peer's successor list, and the rest of the successors stay intact 💅

5.2. Neighbor Stabilization

In the neighbor stabilization operation of chord-reload, a peer periodically sends an Update request to every peer in its connection table 📤 In a small, low-churn overlay, the traffic this makes is usually fine 🌈 But in a big overlay with moderate or high churn, the traffic can stop being acceptable, because the connection table is large and the stabilization interval is relatively short 😭 The self-tuning mechanisms in this document are especially built for that second kind of overlay 🦋 So when self-tuning is used, each peer only sends a periodic Update request to its first predecessor and first successor on the Chord ring, and it MUST NOT send Update requests to anyone else 🙅‍♀️

The neighbor stabilization routine runs when the stabilization timer fires ⏰ To start it, a peer sends an Update request to its first successor and its first predecessor. The type of that Update request MUST be 'neighbors' 🎀 The Update request includes the successor and predecessor lists of the sender. If a peer that gets such an Update request learns from those lists that new peers could be added to its neighborhood set, it sends Attach requests to the new peers 🧚

Once a new peer has been added to the predecessor or successor list, an Update request of type 'peer_ready' is sent to the new peer 💌 That lets the new peer insert the sender into its neighborhood set 🫶

5.3. Finger Stabilization

chord-reload specifies two alternative methods for searching for new peers to add to the finger table 🔍 Both alternatives can be used with the self-tuning extensions in this document ✨

Right after a new peer has been added to the finger table, a Probe request is sent to that new peer to fetch its uptime ⏳ The 'requested_info' field of the Probe request MUST be set to contain the ProbeInformationType 'uptime' defined in RELOAD base [RFC6940] 🎯

5.4. Adjusting Finger Table Size

chord-reload defines how a peer can make sure its finger table is the right size for efficient routing 🧮 The self-tuning mechanisms in this document produce a network size estimate, and that estimate can be used directly to calculate the optimal finger table size 🤯 This mechanism is used instead of the one chord-reload specifies. Each time the stabilization timer fires, a peer uses the network size estimate to decide whether it needs to adjust the size of its finger table. How that's done is explained in Section 6.2 📖

5.5. Detecting Partitioning

This document does not require any changes to the mechanism chord-reload uses to detect network partitioning 🙌 Nothing to change here, bestie 🫶

5.6. Leaving the Overlay

As specified in RELOAD base [RFC6940], a leaving peer SHOULD send a Leave request to all members of its neighbor table before it leaves the overlay 👋 The 'overlay_specific_data' field MUST contain the ChordLeaveData structure 🎀 The Leave requests sent to successors contain the predecessor list of the leaving peer. The Leave requests sent to predecessors contain the successor list of the leaving peer 📬

Here's the clever bit 🧠 If a given successor can identify better predecessors than the ones already in its predecessor lists, meaning predecessors that are closer to it on the Chord ring, by looking at the predecessor list it got from the leaving peer, then it sends Attach requests to them 💖 Same energy the other way around: if a given predecessor finds better successors by looking at the successor list it got from the leaving peer, it sends Attach requests to them too 🔥

6. Self-Tuning Chord Parameters 🌸

this section explains how to figure out an appropriate stabilization rate and routing table size in an adaptive way 🦋 The proposed mechanism is based on [Mahajan2003], [Liben-Nowell2002], and [Ghinita2006] 📚 To work out a good stabilization rate, three parameters have to be estimated: overlay size N, failure rate U, and join rate L 📊 To work out a good routing table size, the estimated network size N can be used 🧮 Peers in the overlay MUST recalculate the values of the parameters used to self-tune the chord-reload algorithm at the end of each stabilization period, before they restart the stabilization timer ⏰

6.1. Estimating Overlay Size

Techniques for estimating the size of an overlay network have been proposed in a bunch of places, like [Mahajan2003], [Horowitz2003], [Kostoulas2005], [Binzenhofer2006], and [Ghinita2006] 🔍 In Chord, the density of peer identifiers in the neighborhood set can be used to estimate the overall size of the overlay, N [Mahajan2003] 🧠 Peer identifiers are picked randomly, with uniform probability, from the numBitsInNodeId-bit identifier space. So the average distance between peer identifiers in the successor set is (2^numBitsInNodeId)/N 🎀

To estimate the overlay network size, a peer computes the average inter-peer distance d between successive peers, starting from the most distant predecessor and ending at the most distant successor in the successor list 📏 The estimated network size is calculated as:

                     2^numBitsInNodeId
                N = -------------------
                            d

This estimate has been found to be accurate within 15% of the real network size [Ghinita2006] 🎯 Of course, the size of the neighborhood set affects how accurate the estimate is 🤓

During the join process, a joining peer fills its routing table by sending a series of Ping and Attach requests, as specified in RELOAD base [RFC6940] 📨 So a joining peer immediately has enough info to calculate an estimate of the network size 🙌

6.2. Determining Routing Table Size

As specified in RELOAD base [RFC6940], the finger table must contain at least 16 entries 🧚 When the self-tuning mechanisms are used, the size of the finger table MUST be set to max(ceiling(log2(N)), 16), using the estimated network size N 💅

The size of the successor list MUST be set to a maximum of ceiling(log2(N)) 📏 An implementation can put a lower limit on the size of the successor list. For example, the implementation might require the successor list to always be at least three 🫶

The size of the predecessor list MUST be set to ceiling(log2(N)) 🔥

6.3. Estimating Failure Rate 💀

okay so the usual move is to pretend peers join the overlay like a Poisson process with rate L, and leave like a Poisson process with rate parameter U [Mahajan2003] 🎲. You can estimate U by looking at peer failures in the finger table and neighborhood set [Mahajan2003]. If peers fail at rate U, a peer with M unique peer identifiers in its routing table should see K failures in time K/(M*U) ✨. Every peer keeps a history of its last K failures, and the current time gets stuck into that history when the peer joins the overlay 🕰️. The estimate of U is:

                             k
                     U = --------,
                          M * Tk

where M is the number of unique peer identifiers in the routing table, Tk is the time between the first and the last failure in the history, and k is the number of failures in the history. If k is smaller than K, the estimate is computed as if there was a failure at the current time. It has been shown that an estimate calculated in a similar manner is accurate within 17% of the real value of U [Ghinita2006] 🎯.

The size of the failure history K is a balancing act 🤹. Make K bigger and the estimate gets more accurate, but the peer gets less responsive to changes in the failure rate. Make K small and the peer can overreact every time a new failure shows up 😭. In [Ghinita2006], K is set to 25% of the routing table size. Use of this value is RECOMMENDED 💖.

6.3.1. Detecting Failures 🔍

A new failure gets inserted into the failure history in the following cases:

  1. A Leave request is received from a neighbor.
  2. A peer fails to reply to a Ping request sent in the situation explained below. If no packets have been received on a connection during the past 2*Tr seconds (where Tr is the inactivity timer defined by Interactive Connectivity Establishment (ICE) [RFC5245]), a RELOAD Ping request MUST be sent to the remote peer. RELOAD mandates the use of Session Traversal Utilities for NAT (STUN) [RFC5389] for keepalives. STUN keepalives take the form of STUN Binding Indication transactions. As specified in ICE [RFC5245], a peer sends a STUN Binding Indication if there has been no packet sent on a connection for Tr seconds. Tr is configurable and has a default of 15 seconds ⏲️. Although STUN Binding Indications do not generate a response, the fact that a peer has failed can be learned from the lack of packets (Binding Indications or application protocol packets) received from the peer 👀. If the remote peer fails to reply to the Ping request, the sender should consider the remote peer to have failed.

As an alternative to relying on STUN keepalives to detect peer failure, a peer could send additional, frequent RELOAD messages to every peer in its connection table. These messages could be Update requests, in which case they would serve two purposes: detecting peer failure and stabilization. However, as the cost of this approach can be very high in terms of bandwidth consumption and traffic load, especially in large-scale overlays experiencing churn, its use is NOT RECOMMENDED 🙅‍♀️📉.

6.4. Estimating Join Rate 🚪

[Ghinita2006] proposes that a peer can estimate the join rate based on the uptime of the peers in its routing table 🕐. An increase in peer join rate will show up as a decrease in the average age of peers in the routing table. So each peer maintains an array of the ages of the peers in its routing table, sorted in increasing order 📚. Using this information, an estimate of the global peer join rate L is calculated as:

                                  N
                    L = ----------------------,
                         Ages[floor(rsize/2)]

where Ages is an array containing the ages of the peers in the routing table sorted in increasing order, and rsize is the size of the routing table. It has been shown that the estimate obtained by using this method is accurate within 22% of the real join rate [Ghinita2006]. Of course, the size of the routing table affects the accuracy 🤷‍♀️.

For this mechanism to work, peers need to swap information about the time they have been present in the overlay 🔄. Peers get the uptimes of their successors and predecessors during the stabilization operations, since all Update requests carry uptime values. A joining peer learns the uptime of the admitting peer because it receives an Update from the admitting peer during the join procedure 🎉. Peers learn the uptimes of new fingers because they can fetch the uptime using a Probe request after having attached to the new finger 🪝.

6.5. Estimate Sharing 🫶

To make the network size, join rate, and leave rate estimates more accurate, peers share their estimates with each other 💌. When the stabilization timer fires, a peer selects number-of-peers-to-probe random peers from its finger table and sends each of them a Probe request. The targets of Probe requests come from the finger table rather than the neighbor table, since neighbors are likely to make similar errors when calculating their estimates 🙈. The number-of-peers-to-probe is a new element in the overlay configuration document, and it is defined in Section 7 ✨. Both the Probe request and the answer returned by the target peer MUST contain a new message extension whose MessageExtensionType is 'self_tuning_data'. This extension type is defined in Section 9.1. The 'extension_contents' field of the MessageExtension structure MUST contain a SelfTuningData structure:

            struct {
              uint32                   network_size;
              uint32                   join_rate;
              uint32                   leave_rate;
            } SelfTuningData;

Here's what each field in the SelfTuningData structure holds 📝:

  • network_size: the latest network size estimate calculated by the sender.
  • join_rate: the latest join rate estimate calculated by the sender.
  • leave_rate: the latest leave rate estimate calculated by the sender.

The join and leave rates are expressed as joins or failures per 24 hours 🌙. As an example, if the global join rate estimate a peer has calculated is 0.123 peers/s, it would include in the 'join_rate' field the ceiling of the value 10627.2 (24*60*60*0.123 = 10627.2), that is, the value 10628 🧮.

The 'type' field of the MessageExtension structure MUST be set to contain the value 'self_tuning_data'. The 'critical' field of the structure MUST be set to False 🔒.

A peer stores all the estimates it receives in Probe requests and answers during a stabilization interval 🗂️. When the stabilization timer fires, the peer calculates the estimates to be used during the next stabilization interval by taking the 75th percentile (i.e., third quartile) of a data set containing its own estimate and the received estimates 📊.

The default value for number-of-peers-to-probe is 4. This default value is recommended to allow a peer to receive a sufficiently large set of estimates from other peers 💅. With a value of 4, a peer receives four estimates in Probe answers. On the average, each peer also receives four Probe requests, each carrying an estimate. So, on the average, each peer has nine estimates (including its own) that it can use at the end of the stabilization interval 🌟. A value smaller than 4 is NOT RECOMMENDED, because it keeps the number of received estimates from getting high enough. As an example, if the value were 2, there would be peers in the overlay that would only receive two estimates during a stabilization interval. Such peers would only have three estimates available at the end of the interval, which may not be reliable enough, since even a single exceptionally high or low estimate can have a large impact 😬.

6.6. Calculating the Stabilization Interval ⏱️

According to [Liben-Nowell2002], a Chord network in a ring-like state remains in a ring-like state as long as peers send Omega(square(log(N))) messages before N new peers join or N/2 peers fail 🔁. We can use the estimate of peer failure rate, U, to calculate the time Tf in which N/2 peers fail:

                                  1
                           Tf = ------
                                 2*U

Based on this estimate, a stabilization interval Tstab-1 is calculated as:

                                           Tf
                           Tstab-1 = -----------------
                                      square(log2(N))

On the other hand, the estimated join rate L can be used to calculate the time in which N new peers join the overlay. Based on the estimate of L, a stabilization interval Tstab-2 is calculated as:

                                               N
                            Tstab-2 = ---------------------
                                       L * square(log2(N))

Finally, the actual stabilization interval Tstab that is used can be obtained by taking the minimum of Tstab-1 and Tstab-2 🏁.

The results obtained in [Maenpaa2009] indicate that making the stabilization interval too small has the effect of making the overlay less stable (e.g., in terms of detected loops and path failures) 🌀. Thus, a lower limit should be used for the stabilization period. Based on the results in [Maenpaa2009], a lower limit of 15 s is RECOMMENDED, since using a stabilization period smaller than this will with a high probability cause too much traffic in the overlay 🚦.

7. Overlay Configuration Document Extension 🧚

This document extends the RELOAD overlay configuration document by adding one new element, "number-of-peers-to-probe", inside each "configuration" element 🎀.

self-tuning:number-of-peers-to-probe: The number of fingers to which Probe requests are sent to obtain their network size, join rate, and leave rate estimates. The default value is 4.

The RELAX NG grammar for this element is:

namespace self-tuning = "urn:ietf:params:xml:ns:p2p:self-tuning"

parameter &= element self-tuning:number-of-peers-to-probe {
xsd:unsignedInt }?

This namespace is added into the <mandatory-extension> element in the overlay configuration file 📂.

8. Security Considerations 🚨

Okay, this part is serious, bestie 😤. In the same way that malicious or compromised peers implementing the RELOAD base protocol [RFC6940] can advertise false network metrics or distribute false routing table information, for instance in RELOAD Update messages, malicious peers implementing this specification may share false join rate, leave rate, and network size estimates 🕵️‍♀️. For such attacks, the same security concerns apply as in the RELOAD base specification 🔐. On top of that, as long as the number of malicious peers in the overlay stays 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 make sure that estimates that are clearly different from (i.e., larger or smaller than) other received estimates will not significantly influence the process of adapting the stabilization interval and routing table size 🛡️. However, it should be noted that if an attacker is able to impersonate a high number of other peers in the overlay in strategic locations, it may be able to send a high enough number of false estimates to a victim and therefore influence the victim's choice of a stabilization interval 😱.

9. IANA Considerations 🌈

9.1. Message Extensions 📨

okay so this document adds ONE new extension to the "RELOAD Extensions Registry" 💅 it's giving registry glow-up 🌸

+------------------+-------+---------------+
| Extension Name   |  Code | Specification |
+------------------+-------+---------------+
| self_tuning_data |   0x3 |      RFC 7363 |
+------------------+-------+---------------+

the contents of the extension are defined in Section 6.5 🫶 go peek at it if you want the juicy details ✨

9.2. New Overlay Algorithm Type 🦋

this one adds a new overlay algorithm type to the "RELOAD Overlay Algorithm Types" registry 👑 the new algorithm is basically the main character of this whole doc 💜

+-------------------+-----------+
| Algorithm Name    | Reference |
+-------------------+-----------+
| CHORD-SELF-TUNING | RFC 7363  |
+-------------------+-----------+

9.3. A New IETF XML Registry 🎀

this doc registers one new URI for the self-tuning namespace in the "ns" subregistry of the IETF XML registry defined in [RFC3688] 🧚 it's giving namespace drama 💀

URI: urn:ietf:params:xml:ns:p2p:self-tuning

Registrant Contact: The IESG

XML: N/A, the requested URI is an XML namespace

10. Acknowledgments 💖

the authors would like to thank Jani Hautakorpi for his contributions to the document 🫶 they also want to thank Carlos Bernardos, Martin Durst, Alissa Cooper, Tobias Gondrom, and Barry Leiba for their comments on the document 🌈 the squad really showed up for this one 😭✨

11. References 📚

11.1. Normative References 🔥

[RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
           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,
           "Session Traversal Utilities for NAT (STUN)", RFC 5389,
           October 2008.

[RFC6940]  Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and
           H. Schulzrinne, "REsource LOcation And Discovery (RELOAD)
           Base Protocol", RFC 6940, January 2014.

11.2. Informative References 🌸

these are the extra-credit reading list, bestie 📖 no pressure, but they're all worth a look 🤓💜

[Binzenhofer2006]
           Binzenhofer, A., Kunzmann, G., and R. Henjes, "A Scalable
           Algorithm to Monitor Chord-Based P2P Systems at Runtime",
           In Proceedings of the 20th IEEE International Parallel and
           Distributed Processing Symposium (IPDPS), pp. 1-8, April
           2006.

[CAN]      Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S.
           Schenker, "A Scalable Content-Addressable Network", In
           Proceedings of the 2001 Conference on Applications,
           Technologies, Architectures and Protocols for Computer
           Communications, pp. 161-172, August 2001.

[Chord]    Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.,
           Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A
           Scalable Peer-to-peer Lookup Service for Internet
           Applications", IEEE/ACM Transactions on Networking, Volume
           11, Issue 1, pp. 17-32, February 2003.

[Ghinita2006]
           Ghinita, G. and Y. Teo, "An Adaptive Stabilization
           Framework for Distributed Hash Tables", In Proceedings of
           the 20th IEEE International Parallel and Distributed
           Processing Symposium (IPDPS), pp. 29-38, April 2006.

[Horowitz2003]
           Horowitz, K. and D. Malkhi, "Estimating Network Size from
           Local Information", Information Processing Letters, Volume
           88, Issue 5, pp. 237-243, December 2003.

[Kostoulas2005]
           Kostoulas, D., Psaltoulis, D., Gupta, I., Birman, K., and
           A. Demers, "Decentralized Schemes for Size Estimation in
           Large and Dynamic Groups", In Proceedings of the 4th IEEE
           International Symposium on Network Computing and
           Applications, pp. 41-48, July 2005.

[Krishnamurthy2008]
           Krishnamurthy, S., El-Ansary, S., Aurell, E., and S.
           Haridi, "Comparing Maintenance Strategies for Overlays",
           In Proceedings of the 16th Euromicro Conference on
           Parallel, Distributed and Network-Based Processing, pp.
           473-482, February 2008.

[Li2004]   Li, J., Strinbling, J., Gil, T., Morris, R., and M.
           Kaashoek, "Comparing the Performance of Distributed Hash
           Tables Under Churn", Peer-to-Peer Systems III, Volume 3279
           of Lecture Notes in Computer Science, Springer, pp. 87-99,
           February 2005.

[Liben-Nowell2002]
           Liben-Nowell, D., Balakrishnan, H., and D. Karger,
           "Observations on the Dynamic Evolution of Peer-to-Peer
           Networks", In Proceedings of the 1st International
           Workshop on Peer-to-Peer Systems (IPTPS), pp. 22-33, March
           2002.

[Maenpaa2009]
           Maenpaa, J. and G. Camarillo, "A Study on Maintenance
           Operations in a Chord-Based Peer-to-Peer Session
           Initiation Protocol Overlay Network", In Proceedings of
           the 23rd IEEE International Parallel and Distributed
           Processing Symposium (IPDPS), pp. 1-9, May 2009.

[Mahajan2003]
           Mahajan, R., Castro, M., and A. Rowstron, "Controlling the
           Cost of Reliability in Peer-to-Peer Overlays", In
           Proceedings of the 2nd International Workshop on Peer-to-
           Peer Systems (IPTPS), pp. 21-32, February 2003.

[Pastry]   Rowstron, A. and P. Druschel, "Pastry: Scalable,
           Decentralized Object Location and Routing for Large-Scale
           Peer-to-Peer Systems", In Proceedings of the IFIP/ACM
           International Conference on Distributed Systems Platforms,
           pp. 329-350, November 2001.

[RFC3688]  Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688,
           January 2004.

[Rhea2004]
           Rhea, S., Geels, D., Roscoe, T., and J. Kubiatowicz,
           "Handling Churn in a DHT", In Proceedings of the USENIX
           Annual Technical Conference, pp. 127-140, June 2004.

[Weiss1998]
           Weiss, M., "Data Structures and Algorithm Analysis in
           C++", Addison-Wesley Longman Publishing Co., Inc., 2nd
           Edition, ISBN 0201361221, 1998.

Authors' Addresses 🧚

the authors, in case you want to say hi 💌

Jouni Maenpaa
Ericsson
Hirsalantie 11
Jorvas  02420
Finland

EMail: Jouni.Maenpaa@ericsson.com


Gonzalo Camarillo
Ericsson
Hirsalantie 11
Jorvas  02420
Finland

EMail: Gonzalo.Camarillo@ericsson.com
📦 where this page comes from