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

world” effects which manifested themselves in the bonding among people with
short chains of acquaintances, commonly referred to as six degrees of separa-
tion. According to Watts and Strogatz [Watts and Strogatz, 1998], small-world
networks exhibit features found in both random and regular network struc-
tures. Specifically, the clustering coe cient C i of a node i is the fraction of all
possible edges between adjacent nodes of i that are present:

D i
D max

C i = (4.1)

where D i and D max are the number of adjacent neighbors of node i and the
maximum possible number of incident edges of node i.
Moreover, the clustering coe cient C net of a network is the average clus-
tering coe cient of all nodes:

i C i
|V|

C net = (4.2)

where|V|is the number of nodes in the network.
Consequently, a small-world network typically has a large clustering coef-
ficient as in a regular network but also possesses a small characteristic path
length (i.e., the average distance between nodes) as in a random network.
With such salient connectivity features, small-world networks are e cient
in facilitating information exchange and dissemination, even for malicious
materials such as virus programs. Many P2P applications (e.g., Gnutella
[Gnutella Protocol Development, 2009]) are considered to exhibit small-world
features.
On the other hand, there is another important notion called scale-free
or power-law [Barabasi and Albert, 1999] network topology. In a scale-free
network, the probability that a node is connected to k other nodes is governed
by a power-law distribution, P (k) = k −γ , in which the exponent γ is a value
between 2 and 3. Consequently, a large number of nodes have small degrees
while a small number of nodes (commonly referred to as hubs) have large
degrees. Such a structure, with the hubs, usually exhibits a high resilience
against random node failures.
Another critical issue mandating topology control actions is the topology
mismatch problem, as illustrated in Figure 4.1. The problem is that while two
peers might be logically connected to each other, the “connection” between
them can actually involve a highly ine ciency path traversing many other
peers. Thus, the key issues here are: (1) detection of ine cient logical connec-
tions; and (2) adjustment of topology to better match the underlying physical
topology. There is a large body of research addressing this problem.
Many topology control schemes are based on heuristics because optimal
topology construction, even in the static case, is an NP-hard problem [Liu
et al., 2005b]. Many heuristics use a more or less greedy selection method
using parameters such as resourcefulness and connectedness. Specifically, it
is intuitively a good idea for a new peer or a disconnected peer to attempt