Information Technology Reference
In-Depth Information
the current node to a neighbor node based on the edge transition probability
of the corresponding edge. Each forwarding step leads to decrementing the
TTL.
The new peer then connects to the node where the walker stops (i.e., when
its TTL reaches 0). If the walker stops at a node which is already connected
by that new node, then the walker moves an additional δ hops (in [Kwong and
Tsang, 2008], δ = 1). This is repeated until a previously not connected node
is found. In practice, this process will not go on indefinitely if the network is
large.
Using the above iterative and fully distributed mechanism, the sampled
edge transition probability converges to a steady state distribution that is
equal to the centralized computation of π i given above, when τ→∞. In
[Kwong and Tsang, 2008], it is reported that τ = 10 is already good enough
for a network with 50,000 peers.
To handle peer dynamics, a topology reconstruction process is needed.
Specifically, in Kwong and Tsang's approach [Kwong and Tsang, 2008], each
node i attempts to rebuild r i (where r i ≤1) new link(s) whenever it loses a
link. Here, obviously r i is a probability and its usage is detailed as follows.
Let k i denote the degree of node i after it has lost a link. Now, a heuristic
mechanism is used:
k i
1
= 2
r i =
(4.11)
k i ≥3
r
This is called the probabilistic-rebuilding scheme [Kwong and Tsang, 2008].
The threshold of 2 is to heuristically maintain the situation that each node has
3 more links at any point in time. Now, after the probability r i is determined
as shown above, a random walker is dispatched if the decision is to attempt
the rebuilding. The same random walk-based node selection process is carried
out.
Kwong and Tsang [Kwong and Tsang, 2008] also consider another method
called adaptive-rebuilding scheme which works by limiting the degrees of nodes
so as to prevent overloading. This is counter-balanced by another heuristic
requirement—each node should also try to maintain m links to keep the net-
work's robustness intact. Consequently, in this scheme, the probability r i is
set as:
m−1
k i
r i =
(4.12)
Liu et al. [Liu et al., 2005b] studied intensively about the overlay topol-
ogy mismatch problem. They also proposed several heuristics for dynamically
adjusting the overlay topology to suit the underlying physical topology. Specif-
ically, their topology control protocol relies heavily on: (1) globally synchro-
nized system clocks; and (2) flooding of slow-connection detector messages.
Let us illustrate their topology control protocol using the example shown
earlier in Figure 4.1. As can be seen, C1 and C4 are directly connected in the
physical topology. Furthermore, C2 and C4 are in the same subset, as are C1
Search WWH ::




Custom Search