Content deleted Content added
m Reverted edits by 87.236.212.137 (talk) to last revision by Liance: nonconstructive edits |
|||
Line 68:
=== 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]].
| |||