Searching in DHTs (Structured)

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*".

DHT

CHORD Algorithm

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.

Store Information

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.

Search possibilities

1. Every peer knows every other O(n) routing table size.

2. Peers know successor O(n) search cost.

Search Information

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.

Example