Editing Distributed hash table (section)

=== Overlay network ===
Each node maintains a set of [[Data link|link]]s to other nodes (its ''neighbors'' or [[routing table]]). Together, these links form the overlay network.<ref>{{Citation|last1=Galuba|first1=Wojciech|title=Peer to Peer Overlay Networks: Structure, Routing and Maintenance|date=2009|encyclopedia=Encyclopedia of Database Systems|pages=2056–2061|editor-last=LIU|editor-first=LING|editor-link=Ling Liu (computer scientist)|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_1215|isbn=9780387399409|last2=Girdzijauskas|first2=Sarunas|editor2-last=ÖZSU|editor2-first=M. TAMER}}</ref> A node picks its neighbors according to a certain structure, called the [[network topology|network's topology]].

All DHT topologies share some variant of the most essential property: for any key {{mvar|k}}, each node either has a node ID that owns {{mvar|k}} or has a link to a node whose node ID is ''closer'' to {{mvar|k}}, in terms of the keyspace distance defined above. It is then easy to route a message to the owner of any key {{mvar|k}} using the following [[greedy algorithm]] (that is not necessarily globally optimal): at each step, forward the message to the neighbor whose ID is closest to {{mvar|k}}. When there is no such neighbor, then we must have arrived at the closest node, which is the owner of {{mvar|k}} as defined above. This style of routing is sometimes called [[key-based routing]].

Beyond basic routing correctness, two important constraints on the topology are to guarantee that the maximum number of [[Hop (networking)|hops]] in any route (route length) is low, so that requests complete quickly; and that the maximum number of neighbors of any node (maximum node [[Degree (graph theory)|degree]]) is low, so that maintenance overhead is not excessive. Of course, having shorter routes requires higher [[maximum degree]]. Some common choices for maximum degree and route length are as follows, where {{mvar|n}} is the number of nodes in the DHT, using [[Big O notation]]:

{| class="wikitable"
|-
! Max. degree !! Max route length !! Used in !! Note
|-
| <math>O(1)</math> || <math>O(n)</math> ||  || Worst lookup lengths, with likely much slower lookups times
|-
| <math>O(1)</math> || <math>O(\log n)</math> || [[Koorde]] (with constant degree) || More complex to implement, but acceptable lookup time can be found with a fixed number of connections
|-
| <math>O(\log n)</math> || <math>O(\log n)</math> || [[Chord (peer-to-peer)|Chord]] <br/> [[Kademlia]] <br/> [[Pastry (DHT)|Pastry]] <br/> [[Tapestry (DHT)|Tapestry]] || Most common, but not optimal (degree/route length).  Chord is the most basic version, with Kademlia seeming the most popular optimized variant (should have improved average lookup)
|-
| <math>O(\log n)</math> || <math>O(\log n/\log (\log n))</math> || [[Koorde]] (with optimal lookup) || More complex to implement, but lookups might be faster (have a lower worst case bound)
|-
| <math>O(\sqrt{n})</math> || <math>O(1)</math> ||  || Worst local storage needs, with much communication after any node connects or disconnects
|}

The most common choice, <math>O(\log n)</math> degree/route length, is not optimal in terms of degree/route length tradeoff, but such topologies typically allow more flexibility in choice of neighbors. Many DHTs use that flexibility to pick neighbors that are close in terms of latency in the physical underlying network. In general, all DHTs construct navigable small-world network topologies, which trade-off route length vs. network degree.<ref>{{Cite thesis|url=https://infoscience.epfl.ch/record/130838?ln=en|title=Designing peer-to-peer overlays a small-world perspective|last=Girdzijauskas|first=Sarunas|date=2009|website=epfl.ch|publisher=EPFL|doi=10.5075/epfl-thesis-4327 |access-date=2019-11-11|archive-date=2020-03-03|archive-url=https://web.archive.org/web/20200303182938/https://infoscience.epfl.ch/record/130838?ln=en|url-status=live}}</ref>

Maximum route length is closely related to [[Diameter (graph theory)|diameter]]: the maximum number of hops in any shortest path between nodes. Clearly, the network's worst case route length is at least as large as its diameter, so DHTs are limited by the degree/diameter tradeoff<ref>{{citation |url=http://maite71.upc.es/grup_de_grafs/table_g.html |title=The (Degree, Diameter) Problem for Graphs |publisher=Maite71.upc.es |access-date=2012-01-10 |archive-url=https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/ |archive-date=2012-02-17 |url-status=dead }}</ref> that is fundamental in [[graph theory]]. Route length can be greater than diameter, since the greedy routing algorithm may not find shortest paths.<ref>Gurmeet Singh Manku, Moni Naor, and Udi Wieder. [http://citeseer.ist.psu.edu/naor04know.html "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks"] {{Webarchive|url=https://web.archive.org/web/20080420030133/http://citeseer.ist.psu.edu/naor04know.html |date=2008-04-20 }}. Proc. STOC, 2004.</ref>