An Efficient Lookup Service in DHT Based Communication System - Frontiers in Internet Technologies - page 79

4.2 Identifier

In Comb, the whole overlay is divided into several domains, organized as a two-
layered architecture. Accordingly, the identifier space is separated into two parts:
domain ID and host ID as depicted in Figure 3.

Fig. 3. Comb identifier consists of two parts: domain id and host id

When a node joins into the Comb system, it chooses the nearest domain and takes
the domain ID as the identifier prefix, then applies consistent hashing to its IP address
or URI as the identifier postfix. This assignment also makes it possible to determine
the geographic domain of any nodes by its ID.

4.3 Node Joins and Leaves

Assume that a new joined node named JP (Joined Peer) knows about at least one
node named BP (Bootstrap Peer) already in the system through some out-of-band
methods [2], BP is in the nearest domain from JP . JP copies BP 's local table
and global table in order to build routing tables itself. For the local table, a copy from
BP is enough, but for the global table, ID Transformation is necessary, though it will
function well with a complete copy from BP logically.
ID Transformation:
Suppose

ID = ID

BP

+ ID

AP

JP

BP

get its identifier , and 's

BP domain host

ID = ID

JP

+ ID

JP

ID

BP

= ID

JP

identifier , .

JP domain host domain domain

BP JP

ID define

offset

(B

P JP

, ) =

ID

−

ID

, for each node item in BP 's global Table ,

host host N

JP builds a new item

ID = ID

N

+ | ID

N

− offset BP JP ( , ) | , whose address is

M domain host

fetched through AP .
ID transformation makes global table varies from node to node within a domain,
requests from domain A to domain B are forwarded by different nodes in domain B,
resulting in a network with load balance and scalability. For user information security
and system robust, communication operators always choose nodes only when they are
deployed as BP instead of all nodes in overlay.
Once JP built its routing tables, it need inform other nodes in domain of its
arrival. A multicast tree [15] rooted at JP for disseminating membership changes can
be applied: For a N nodes domain, update messages are propagated to the

TTL

= successors of JP , each message consists of JP 's
identifier and value of TTL. Notified successors continue with message propagating to
their 2 th (i

2 th (TTL 0,..., log

N

2

= − successors and minus TTL by 1 until TTL = 0. An
example of a 8 nodes domain is shown in Figure 4.

i

0,..., TTL 1