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

half way around the cycle of k cliques. Consequently, the maximum diameter
is given by: 3 2 .
For characteristic path length, let us consider only the distances among the
interior nodes. Now, for each interior node, there are n−1 nodes at distance
1, 2n nodes at distance 3 (i.e., one n-clique apart), 2n nodes at distance 6,
and so on. The sum of the distances for all possible interior nodes is given by:

k − 1
2

j = n−1 + 3n k−1
2

k−1
2

(n−1) + 6n + 1 (4.7)

j=1

The characteristic path length can then be computed by assuming large
values of n:

3
4 n(k−1)(k + 1)
nk

3

4 (k 2 −1)
k

L≈ n +

1 +

= (4.8)

To realize the salient features of the network constructed by the above
method in a real-life BitTorrent system, Dale et al. proposed a simple topology
control action to be implemented in a BitTorrent tracker server. Modifying
the tracker is a much more realistic approach than modifying all BitTorrent
clients. Specifically, the modified tracker assigns an ID to each new peer to
designate an n-clique to which it should join. If all the n-cliques are full already,
the peer receives a new ID; otherwise, the peer receives the ID of the largest
currently unfilled n-clique.
In choosing a list of peers for returning to the new peer for making connec-
tions, the n-clique ID of the new peer is considered. Specifically, the tracker
first randomly selects a small number of peers from n-cliques other than the
one containing the new peer. The rest (i.e., the majority) of the list is formed
by randomly selecting peers from the n-clique containing the new peer. The
experimental results indicate that such simple modifications can already dra-
matically increase the extent of clustering, with only a slight increase in net-
work diameter.
In their simulation results [Dale et al., 2008], it is found that the clustering
coe cients are increased but not to the extent that the theory predicted.
A plausible explanation is that in practice, there is a limit on the number
of connections a peer can initiate in a BitTorrent client. This prevents the
formation of a complete n-clique.
Kwong and Tsang [Kwong and Tsang, 2008] presented a mathematically
sound study on the topology formation and reconstruction schemes in a prac-
tical P2P network. Specifically, their key observation is that peers are highly
heterogeneous in that they have very disparate bandwidth, storage, processing
power capabilities, etc. Thus, it is mandatory to design a suitable protocol for
each peer to make connection decisions, i.e., to which peers it should connect.
The ultimate objective is to form a network with balanced load across peers
and hence, is able to provide stable service quality to users.
To model heterogeneity, Kwong and Tsang [Kwong and Tsang, 2008] use a
single parameter η i for each peer i. Depending on the specific P2P application,