Skip to content

Instantly share code, notes, and snippets.

@folex

folex/DHT.md

Created November 21, 2019 09:04
Show Gist options
  • Save folex/12b070c44207cd4b90bb975bcef658ef to your computer and use it in GitHub Desktop.
Save folex/12b070c44207cd4b90bb975bcef658ef to your computer and use it in GitHub Desktop.
Download ZIP
Notes on DHT
Raw
DHT.md

DHT

Terms

Performance

Graphs

  • Hops & Bandwidth on 10k node network with variable churn rate (specified by lifetime) Hops & Bandwidth on 10k node network with variable churn rate (specified by lifetime)

  • Comparing the hopcounts for different DHTs over a 65,536 node network with no failures. Comparing the hopcounts for different DHTs over a 65,536 node network with no failures.

  • Left: Percentage of failed paths for varying percentages of node failures across different routing geometries. Right: Percent increase in average path hop-counts of successful paths for varying percentages of node failures across different routing geometries. path failure and path stretch graphs

  • Kademlia (XOR) with and without proximity heuristics kademlia(xor) with and without proximity heuristics

Notes

  • Geometries themselves make less difference than whether or not they can support PNS and/or PRS. (proximity neighbour selection, proximity route selection)

  • While hopcount is an important metric for measuring the processing and bandwidth requirements at the peers, it does not adequately address the issue of end-to-end latency because each overlay hop could potentially involve significant delays (intercontinental links, satellite links, etc.). As a result, there has been much recent effort to reduce end-to-end latencies in DHT routing algorithms by considering the relative proximity of overlay nodes (i.e., the IP latency between them)

  • Epichord can achieve O(1) hops; 4 hops on 10k network, same as Kademlia

Finally, EpiChord, an overlay which can approach one-hop performance, approached 99% success ratio when the churn level went low (lifetime=1000s). In very high churn, the overlay performed less favourably with a lookup success rate of about 63%. This increases to a more usable 97% as the mean lifetime approaches 300 seconds. Like Kademlia, EpiChord uses reactive routing state maintenance employing lookup response messages to carry routing table update information. EpiChord also uses parallel lookup messages.

  • Viceroy can provide O(log n) path lengths with O(1) to O(log n) neighbors, while PRR, CAN, Chord, Pastry and Kademlia can provide O(log n) path lengths with O(log n) neighbors.

Nature / Geometry

  • PPR is based on a tree geometry, and is one of the first proposed DHT algos
  • Tapestry & Pastry algos are similar in spirit to PRR, although Pastry also uses a ring-like geometry in addition to the tree

Algos

PPR

  • Tree geometry
  • n^(log n)/2 available routes
  • after route is selected, only 1 available next hop
  • have no route selection flexibility => resilience is quite poor; when 30% of the nodes have failed, almost 90% of their paths have failed.

CAN

  • Hypercube geometry
  • have the most flexibility in route selection => 30% of nodes are failed, under 7% of the routes have failed

Viceroy

  • Butterfly geometry
  • Viceroy routing consists of three phases: the first uses O(log n) hops to move up to the first stage, the second uses another O(log n) hops to traverse down the stages until it reaches the vicinity of the destination at which point routing enters its third phase and uses the successor/predecessor neighbors to reach the destination in a O(log n) additional hops.
  • have no route selection flexibility => resilience is quite poor; when 30% of the nodes have failed, almost 90% of their paths have failed.

Chord

  • Ring geometry
  • In Chord, a node with identifier (say) a maintains log n neighbors (called fingers) where the ith neighbor is the node closest to a + 2i on the circle. Hence, a node can route to an arbitrary destination in log n hops because each hop cuts the distance to the destination by half.
  • have the most flexibility in route selection => 30% of nodes are failed, under 7% of the routes have failed

Kademlia

  • XOR geometry
  • Kademia’s routing table permits exactly the same routing entries as for tree geometries such as PRR
  • Kademlia chooses exactly the same routes as PRR when the routing table is fully populated (i.e., no failures);
  • Under failures Kademlia behaves differently: it can fix not only highest bits, but lower too, so there are different paths to each destination, but these paths are of different lengths.
  • 30% of nodes are failed, about 20% of routes have failed
  • On nodes failure, path is stretched (right graph): path failure and path stretch graphs
  • Our PRS heuristic for XOR takes a non-greedy next hop only when its latency is smaller than the latency of the greedy next hop choice by more than the average latency in the network. This primarily helps to avoid very long hops.

Pastry

  • Hybrid geometry: tree + ring
  • Distance can be computed in 2 ways:
    1. tree distance, default
    2. cyclic numeric distance, fallback
  • Paths aren't bound by O(log n), could be worse
  • 30% of nodes are failed, about 20% of routes have failed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment