Searching in DHTs (Structured)
Last updated
Last updated
Need to know the exact filename.
Keys (filenames) map to node-ids.
Change in file name -> search at different nodes.
No wildcard matching: cannot ask for file "pix*".
All files/data items in the network will have an identifier, which will be hashed to give a key for that particular resource.
If a node needs a file/data, it will hash its name and then send a request using this key.
All n nodes also use the function to hash their IP address, and conceptually, the nodes will form a ring in ascending order of their hashed IP.
The successor node of a key k is the first node whose ID equals k or follows k in the identifier circle, denoted by successor(k).
Every key is assigned to its successor node, so looking up a key k is to query successor(k).
When a node wants to share a file or some data:
Hashes the identifier to generate a key k, and sends its IP and the file identifier to the successor(k).
These are then stored at this node.
All resources are indexed in a large DHT across all participating nodes.
If two or more nodes hold a given file or resource, the keys will be stored at the same node in the DHT, giving the requesting node a choice of requesting the file in one or the other node, or both.
Hashing of search keys AND peer addresses on binary keys of length m.
e.g. m=8, key("jingle-bells.mp3")=17, key(196.178.0.1)=3
Calculates hash of data to get k.
Routing is used to find the node that stores key k (node k).
Calculates hash of data to get k.
Every peer knows every other O(n) routing table size.
Peers know successor O(n) search cost.
When a node wants content.
Hashes data identifier and sends a request to the successor(k).
Reply with the IP of the node that holds the actual data.
How does a node request information from successor(k), when it doesn't know its IP, but only the key?
Every node holds what is known as a finger table.
Contains a list of keys and their successor IP's.
Each node holds the IP of an exponential sequence of nodes that follow it, i.e. entry i of the node k's finger table holds the IP of node k + 2^i.
