Information Technology Reference
In-Depth Information
messages dissemination, suppose node N that should be selected as a child of Node P
had not been selected, in the worst case, N will receive the notification from its prede-
cessor as the range narrows. We can prove that binary-multicast tree disseminate mes-
sages in the same time complexity with a multicast tree of
ON
.
When a node leaves, it notifies its predecessor and successor, they (or one of them)
propagates this change to all nodes over the domain using a process similar to a
node's arrival.
(log
)
2
4.4
Routing Tables Maintenance
Only nodes in local table are notified when a node leaves, in a purely distributed over-
lay of Comb, this node is probably also in global tables of other nodes from outer
domains. To this end, a heartbeat with nodes in global table to keep alive is necessary.
Every
t
seconds afterwards, a heartbeat message is sent to each node item in global
table to keep-alive, if a heartbeat is not acknowledged until time fires, we treat it as a
departed node, and do ID transformation to find a new substitute item through BP or
any other nodes as in node join.
For each node K with an ID of
ID
in Node N's global table, heartbeats can carry
k
k
N
the destination identifier of
ID
=
ID
+
ID
, when node K receives the heart-
dest
host
domain
ID
, a redirection should be sent back to node
K with the new substitute node responsible for
beats and find it isn't responsible for
dest
ID
.
The period
t
is chosen such that 80% nodes lives longer than
dest
t
seconds, as-
−
λ
t
sume node lifetime
t
follows an exponential distribution
ft
()
=λ
e
(
t
>
0)
, then:
ln(0.8)
+∞
ftdt
()
=
0.8
t
=−
(4)
g
λ
t
g
The expectation of
t
is:
1
Et
[]
==
λ
l
,so we have
t
≈
0.2
l
(5)
g
Another situation need to be taken into account is that not all nodes leave the sys-
tem normally; some nodes may fail without any notifications. Hence, a mechanism to
handle failed nodes is needed. Periodically, a node sends an announcement to its im-
mediate predecessor to state its existence, a node also sets timer for its successor's
announcement.
If an announcement is received from node N which is already in local table by
node P , P would reset the timer for the next announcement. If node
N
is not in the
local table of P or P's timer for N is fired, then P adds/deletes N to/from local table,
and broadcast the membership change to all the nodes in domain through a binary-
multicast tree.
