what-when-how
In Depth Tutorials and Information
a simulated BitTorrent overlay to look at the distance of peers from the initial seed
and the matrix of peer connections. heir results were based on a homogeneous col-
lection of peers, and were limited to the startup stage of a torrent. Al-Hamra et al.
[4] expanded on those results through simulation with some experimental confir-
mation. hey also examined the diameter of the overlay created, and the robustness
of the overlay to the presence of churn and attacks. Legout et al. [22] performed an
experimental evaluation with around 40 heterogeneous peers, finding interesting
evidence of clustering in the network of peer unchokings.
Our results differ from these earlier results in several ways. We have focused
on experimental evaluation, which captures the intricacies of the formation of
multiple complex networks in BitTorrent. We use over 400 peers and explore the
entire lifespans of the torrents, from the initialization stage to a steady stage. his
enables us to quantitatively evaluate both time-invariant characteristics and those
that evolve in different stages.
We will first look at the characteristics of the networks formed in our exper-
iment. he connectivity matrix of the peers in the experiment is presented and
analyzed in Section 1.3.3. Finally, we will present the differing results of another
experiment with increased churn.
6.3.1 Background of Random Graphs
A network may be presented by a graph
G={P,E}
, where
P
is the set of
N
nodes and
E
is the set of edges, or links, that each connects two nodes in
P
.
Random graphs were first defined by Paul Erdős and Alfréd Rényi [16]. A ran-
dom graph is obtained by starting with a set of n vertices and adding edges between
them randomly. Different random graph models produce different probability dis-
tributions on graphs. Most commonly studied is the Erdős-Rényi model, denoted
G(n,p)
, in which every possible edge occurs independently with probability
p
. A
closely related model, denoted
G(n,M)
, assigns equal probability to all graphs with
exactly
M
edges. he latter model can be viewed as a snapshot at a particular time
(M) of the random graph process
G
n
,
which is a stochastic process that starts with
n vertices and no edges and at each step adds one new edge chosen uniformly from
the set of missing edges.
If instead we start with an infinite set of vertices, and again let every possible
edge occur independently with probability p, then we get an object G called an
ininiterandomgraph
. Except in the trivial cases when p is 0 or 1, such a G almost
surely has the following property:
Given any n + m elements
a
1,
… ,
an
,
b
1,
… ,
bm
Î V, there is a vertex cÎ V that is
adjacent to each of
a
1,
… ,
an
and is not adjacent to any of
b
1,
… ,
bm
.
If the vertex set is countable then there is, up to isomorphism, only a single
graph with this property, namely the Rado graph. hus any countably ininite ran-
dom graph is almost surely the Rado graph, which for this reason is sometimes
called simply the
randomgraph
.
