NODE LOOK UP IN PEER-TO-PEER NETWORK

NODE LOOK UP IN PEER-TO-PEER NETWORK

P2P: Large connection of computers, without central control where typically each node has some information of interest.

No central control for routing

No central data repository

Has several legitimate uses !!

So two basic questions:

How to make data at each node available ?

How to find required information ?

Both question are of course interrelated, but we will look at them seperately.

ASSUMPTION

We assume that each record (data to be shared) can be identified by a ASCII string such as the filename.

Over the past 3-4 years there has been several proposals for P2P architectures, we will look at Chord.

Uses a hash function such as SHA-1. SHA-1 converts a variable length input into a highly random 160 bit value

BASIC OF CHORD

Using SHA-1 Chord hashes,

node IP addresses   node identifiers (160 bits)

names of records keys (160 bits)

STORING RECORD

Conceptually the 2^160 nodes are arranged into a circle increasing clockwise.

For example, for  2^5 nodes would be conceptually arranged as

successor (k) is the first real node after k.

To store data name, a node N creates a tuple (name, N's IP address) and stores the tuple at successor(hash(name)). The original data remain at N, just the tuple is stored at successor(hash(name)).

If hash(name) = 22, then the tuple is stored at node 27

To find information name, a node does key = hash(name), then gets the record tuple from successor(key).

Simple ? Mostly, except for implementing successors(key) efficiently

FINDING RECORS

Each node needs to store the IP addresss of its successor. 

Initially, the network start out with just a few nodes, where all nodes know each other and they can easily arrange themselves into a the Chord ring and successor(k) can be computed.

When a node tries to join, it calcuates its node Id say p,  then asks any node already in the ring to find successor(p), asks successor(p) for successor(p)'s predecessor and inserts itself between them.

Any node in the ring can find successor(k) by propagating the query around the ring starting with its successor. 

FINGER TABLE

Even if both successor and predecessor pointers are used a sequential search will take time on average O(n/2) [n is the number of nodes]

Chord reduces this seach time using a finger table at each node. The finger table contains upto m entries where each entry i consists of

IP address of succcessor(start[i])

To find a record for key k, a node can directly jump to the closest predecessor of k

Looking up key 16 at node 1

1. Nearest pred. 9 so query sent to 12

2. At 12 nearest pred. of 16 is 14 so query sent to 15

3. 15 knows that 16 is between itself and its successor so 15 send back 20's IP address to  1

MAINTAINING FINGER TABLE

Maintaining the finger table does not come for free. Every time a new node is added a few successors and predecessor entries will change.