Self-Tuning Distributed Hash Table (DHT) for REsource LOcation And Discovery (RELOAD)
Extracted elements (30)
Adaptive stabilization outperforms periodic stabilization in both lookup failures and communication overhead. By having each peer collect statistical data and dynamically adjust stabilization rate, neighborhood set size, and finger table size, high reliability can be achieved even in adverse conditions with low maintenance cost.
Periodic stabilization is preferred over reactive stabilization for large-scale or high-churn overlays because reactive stabilization can create a positive feedback cycle leading to congestion collapse. Research showed that a 1000-peer overlay under churn uses significantly less bandwidth and has lower latencies with periodic stabilization.
Probe targets for estimate sharing are selected from the finger table rather than the neighbor table because neighbors are likely to make similar errors when calculating their estimates, reducing the diversity and value of shared estimates.
Static DHT configuration fails in dynamic environments because fixed parameters cannot simultaneously achieve low lookup failure rates and low communication overhead when operating conditions (overlay size, churn rate) evolve over time. Self-tuning allows the system to adapt dynamically.
The self-tuning feature is optional but when used MUST be supported by all peers in the RELOAD overlay network. Its use is indicated in the RELOAD overlay configuration document via the CHORD-SELF-TUNING algorithm name in the topology-plugin element.
A failure history size K of 25% of the routing table size is RECOMMENDED. Using additional frequent RELOAD messages to every peer in the connection table for failure detection is NOT RECOMMENDED due to excessive bandwidth consumption.
A leaving peer SHOULD send a Leave request to all members of its neighbor table prior to leaving. The 'overlay_specific_data' field MUST contain the ChordLeaveData structure.
A lower limit of 15 seconds for the stabilization period is RECOMMENDED; using a smaller stabilization period will with high probability cause too much traffic in the overlay. A number-of-peers-to-probe value smaller than 4 is NOT RECOMMENDED.
Both the Probe request and the answer from the target peer MUST contain a new message extension with MessageExtensionType 'self_tuning_data', and the 'extension_contents' field MUST contain a SelfTuningData structure.
If a peer receives more entries than fit into its successor list, predecessor list, or finger table in an Update request, the peer MUST ignore the extra entries.
If no packets have been received on a connection during the past 2*Tr seconds, a RELOAD Ping request MUST be sent to the remote peer to detect failure.
Immediately after a new peer is added to the finger table, a Probe request MUST be sent to the new peer to fetch its uptime; the 'requested_info' field MUST contain the ProbeInformationType 'uptime'.
In neighbor stabilization with self-tuning, the type of Update request sent to the first successor and first predecessor MUST be 'neighbors'.
Peers MUST recalculate the values of network size, failure rate, and join rate parameters to self-tune the chord-reload algorithm at the end of each stabilization period before restarting the stabilization timer.
Regardless of Update request type, all Update requests MUST include an 'uptime' field containing the sender's current uptime in seconds. The self-tuning extensions require uptime information on peers in the routing table.
The 'type' field of the MessageExtension structure MUST be set to 'self_tuning_data' and the 'critical' field MUST be set to False.
When self-tuning is used, the finger table size MUST be set to max(ceiling(log2(N)), 16) using the estimated network size N. The successor list MUST be set to at most ceiling(log2(N)), and the predecessor list MUST be set to ceiling(log2(N)).
When self-tuning mechanisms are used, each peer MUST NOT send periodic Update requests to peers other than its first predecessor and first successor on the Chord ring, to avoid excessive traffic in large-scale overlays.
When self-tuning mechanisms are used, the periodic recovery strategy MUST be used (not reactive). The chord-reload algorithm supports both, but self-tuning requires periodic recovery.
Estimate sharing uses Probe requests sent to number-of-peers-to-probe (default 4) random peers from the finger table each stabilization interval. At the end of each interval, the 75th percentile of all collected estimates (own plus received) is used for the next interval.
Failure rate U is estimated as U = k / (M * Tk), where M is the number of unique peer identifiers in the routing table, Tk is the time between first and last failure in the history of K failures, and k is the number of failures. Accurate within 17% of the real value.
Join rate L is estimated as L = N / Ages[floor(rsize/2)], where Ages is an array of routing table peer ages sorted in increasing order and rsize is the routing table size. Accurate within 22% of the real join rate.
Overlay size N is estimated by computing the average inter-peer distance d between successive peers from the most distant predecessor to the most distant successor, then N = 2^numBitsInNodeId / d. This estimate is accurate within 15% of the real network size.
The SelfTuningData structure contains three uint32 fields: network_size (latest network size estimate), join_rate (joins per 24 hours), and leave_rate (failures per 24 hours). This structure is carried in the 'extension_contents' field of a MessageExtension.
The stabilization interval Tstab is the minimum of Tstab-1 (= 1/(2*U) / square(log2(N))) and Tstab-2 (= N / (L * square(log2(N)))), derived from failure and join rate estimates respectively.
A new URI 'urn:ietf:params:xml:ns:p2p:self-tuning' is registered in the IETF XML registry 'ns' subregistry (RFC 3688) for the self-tuning namespace used in overlay configuration documents.
IANA 'RELOAD Extensions Registry' is updated with one new entry: extension name 'self_tuning_data' with code 0x3, defined in RFC 7363 Section 6.5.
IANA 'RELOAD Overlay Algorithm Types' registry is updated with one new entry: algorithm name 'CHORD-SELF-TUNING', referencing RFC 7363. This name is used in the topology-plugin element of the RELOAD overlay configuration document.
Malicious peers may share false join rate, leave rate, and network size estimates via Probe requests, potentially manipulating a victim's stabilization interval. The use of 75th percentile aggregation mitigates this when the number of malicious peers is modest, but an attacker who can impersonate peers in strategic locations may send enough false estimates to influence the victim's behavior.
The 'predecessors', 'successors', and 'fingers' fields in RELOAD Update requests are variable-length, preceded by two length bytes (allowing lengths up to 2^16-1). The number of NodeId structures can be calculated from the length bytes since each NodeId is 16 bytes.