Topology Control - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 64

η i can be thought of representing different system parameters. For instance, in
a video streaming application in which the upload bandwidth of each peer is
the most critical parameter [Kwong and Tsang, 2008], η i can be considered as
reflecting each peer's upload bandwidth level. On the other hand, in a network
coding-based P2P application, CPU processing power is the most important
and hence, η i represents the processing power of each peer i.
In their mathematical model [Kwong and Tsang, 2008], it is assumed that
η i follows a certain probability density function ρ(η), which is called the node
capacity distribution.
Suppose k i is the degree of peer i. Presumably every peer wants to connect
to a high capacity peer, in the hope that its download performance can be
enhanced. On the other hand, it is probably not a good idea to connect to
a peer with a high node degree because such a node, while it may be of a
high capacity, could also be under a high load. Thus, in Kwong and Tsang's
approach [Kwong and Tsang, 2008], two parameters are used—each peer's
capacity and node degree—for making connection decisions. Specifically, a
probability π i of a peer i that it is connected by a new peer is given by:

η k i

j∈L(t)

π i = (4.9)

η k i

where L(t) is the set of active peers in the system at time t. Intuitively, the
probability π i captures the idea that new peers should heuristically connect
to active peers with a large capacity-to-degree ratio, which can in fact be
considered as a “normalized” node capacity.
However, it is impractical to maintain global network information in order
to compute the probability π i . Thus, Kwong and Tsang [Kwong and Tsang,
2008] employ the Metropolis-Hastings [Hastings, 1970,Metropolis et al., 1953]
to compute the probability in a fully distributed manner as described below.
The P2P network is modeled as a connected graph G = (V, E) with node
set V ={1, . . . , n}and undirected edge set E⊆V×V . Each edge (i, j) is
associated with a transition probability p ij :

1
k i + 1 min

η j k i (k i + 1)
η i k j (k j + 1)

p ij = 1, (4.10)

and each node i is also associated with p ii = 1−

(i,j)∈E p ij .
To compute the edge transition probabilities locally, each node i needs
to broadcast its capacity η i and degree k i to its neighbors so that the lat-
ter can use such information for local computations. These edge transition
probabilities are used for random walk.
When a new peer joins the system, it first contacts m active peers in
the network, possibly with the help of bootstrap servers. The new peer then
dispatches m different walkers to these m nodes. Each walker is associated
with a time-to-live (TTL) value denoted as τ , which represents the number of
iterations in the Metropolis-Hastings algorithm. Each walker is forwarded from