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

peers for peer i: L i = (LD i , LR i ), where LD i is a set of several peers with the
shortest distances from peer i, and LR i is a set of randomly selected peers. In
Zhang et al.'s results,|LR i |=|LD i |and 5≤|LR i |+|LD i |≤8.
Subsequently, peer i sends a probing message to each of the peers on the
list. The latter will then reply with their neighbor information. Peer i then
assembles all such neighbor information as a candidate list LC i . For each
peer j∈LC i , peer i computes the values of two parameters: the frequency
f i (j) representing the number of times peer j shows up in LC i thus far, and
estimated distance D(i, j) between peer i and j. Furthermore, an important
parameter, called normalized distance estimation d i (j) is determined:

D(i, j)
max k∈LC i D(i, k)

d i (j) = (4.13)

where 0 < d i (j)≤1.
One interesting way to interpret the significance of these parameters is
as follows: LC i is a sampling of peers in the network; f i (j) is a sampling of
the degree of each candidate j; and d i (j) is an estimated distance between
peer i and j. With such interpretation, another parameter, called connection
preference is computed:

P i (j) = γP F i (j) + (1−γ)P D i (j) (4.14)

where P D i (j) is the distance preference of peer i connecting to peer j, and
thus, serves as the probability that peer i selects peer j as one of its immediate
neighbors. Accordingly, it is defined as:

1
d i (j) −α

P D i (j) = (4.15)

1

d i (k) −α k∈LC i

where−∞< α≤1.
By the same token, the degree preference, denoted by P F i (j), is the prob-
ability that peer i selects peer j as one of its immediate neighbors. Here, the
more incident edges peer j has in the network, the higher the probability it ap-
pears in other peers' candidate lists. Accordingly, degree preference is defined
as:

f i (j)−β

P F i (j) = (4.16)

k∈LC i f i (j)−β

where−∞< β≤1.
The parameters, α, β, γ serve as “control knobs” in adjusting the topology
of the P2P network. Specifically, larger values of α and γ are more suitable for
delay sensitive applications. On the other hand, a larger β and a smaller γ are
more suitable for applications that require a better balancing of load. Most
importantly, Zhang et al. showed that their proposed scheme could indeed
generate P2P network structures with power law properties [Zhang et al.,
2005a].