-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathswarm.tex
189 lines (167 loc) · 10.1 KB
/
swarm.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
\section{Standard BitTorrent Study}
\subsection{Experimental Setup}
In this section, we will study two types of swarms and compare the
performance of each when using local knowledge, global knowledge or
omniscience for the rarest piece selection algorithm. The difference
between global knowledge and omniscience is that nodes with global
knowledge know which pieces every node in the swarm has but they do
no not know which pieces those nodes are currently
requesting. Omniscient nodes know both what every peer is requesting
and what they have. This allows for very efficient next piece
selection but is impossible without some form of gossip since requests
are only sent to one node whereas have messages are sent to all of a
node's peers. The goal of this section is to explore the potential for
a gossip algorithm to improve BitTorrent. The first set of simulations
use swarms that start with a single seed and a number of leechers.
The seed is altruistic and will stay the entire time. This
simulates a ``healthy'' swarm that will not die, but may benefit from
better replication of pieces. The second type is a swarm with no seeders,
although a complete copy of the file exists within the swarm between a
few nodes. This simulates a situation in which the seeders have left
and a swarm is in an ``unhealthy'' state. None of the nodes are
altruistic and leave as soon as possible. For this swarm,
there are two goals. The primary goal is to simply make sure the swarm
survives, because it is possible for a node to leave with pieces that
only it holds, which means no other node can complete. The second goal
is, if the swarm survives, to determine if global knowledge or omniscience improve
performance.
For all of the experiments below, we are assuming the swarm is sharing a
40 MB file divided into 1000 pieces. All leechers have a download rate
selected from a uniform distribution between 50 and 100 KB/s, which is
approximately what a DSL user achieves in a typical swarm. Finally, all
leechers will join at a random time in the first 100 seconds of the swarm.
The measurements taken for each experiment are simply the download times for
each node in the swarm if the swarms survives to completion or the
number of nodes that are stranded if the swarm dies. We considered
other methods such as metrics to evaluate local vs. global knowledge,
such as a distance metric comparing the list of pieces sorted by
rarity within the peer set vs. rarity globally, but decided that such
metrics were fairly arbitrary and the node download times tell us
what we actually care about: will global knowledge improve a swarm's
performance?
\subsection{Swarms with Seeders}
In this section, we will examine swarms with a single seeder at the beginning
and a number of leechers that join in the first 100 seconds. To ensure
that a diverse set of conditions are studied, the number of nodes in the swarm,
number of peers per node, and the initial seeder's upload rate will be varied.
In the healthiest swarms with a seeder, there should be many nodes, many peers per node, and
a high seeder upload rate. Likewise, the least healthy swarms have fewer nodes,
fewer peers per node, and a lower upload rate for the seeder. However, if too few
nodes exist than the peers allowed per node, then each node will have perfect global
knowledge by default, so the number of nodes must always be kept above
the number of peers per node.
\begin{table*}
\centering
\caption{Swarms with Seeds Results}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
\multicolumn{3}{|c|}{Configuration} & \multicolumn{2}{|c|}{Local} & \multicolumn{2}{|c|}{Global} \\ \hline
Nodes & Peers & Upload Rate & Total Runtime & Average Download Time & Total Runtime & Average Download Time\\ \hline
100 & 10 & 100 & 1780 & 1533 & 2040 & 1734\\
100 & 20 & 100 & 1650 & 1345 & 1700 & 1429\\
100 & 30 & 100 & 1550 & 1396 & 1720 & 1368\\
200 & 30 & 100 & 1950 & 1478 & 2060 & 1565\\
100 & 10 & 80 & 2430 & 2256 & 2500 & 2245\\
\hline\end{tabular}
\label{tab:seedresults}
\end{table*}
Table \ref{tab:seedresults} shows the results for a number of simulations with a single
seeder. The key takeaway for all of the data above seems to be that there
is very little difference in performance between using the peer set or the
global node set for the rarest first piece selection algorithm. Sometimes
local knowledge is better and sometimes global knowledge is better,
but not in any statistically significant fashion. All of the various
scenarios tested above, including slowing down the seeder, decreasing
the number of peers, etc. all showed this same basic pattern. This means
that even if we had an absolutely perfect gossip algorithm, it would do
very little to help improve the performance of these swarms.
Other observations from this data include some obvious things such as
if the seeder's upload rate is decreased, the overall swarm has a much
longer download time. This makes sense because the seeder's upload rate
is divided five ways between its unchoked peers, so it will take more
time for the first copy of pieces to get out into the network and be
replicated. We also ran some even slower seeders such as an as uprate
of 20 that were not finishing in any reasonable amount of time so we
did not collect the run times. One interesting result was that even if
the number of nodes doubles, the performance penalty for node downloading
was essentially negligible. This shows that BitTorrent scales very well
assuming the initial seeder can get the pieces replicated. We can also
see that as the number of peers increases, performance improves somewhat
going from 10 to 20 peers, but seems to reach diminishing returns going
from 20 to 30 peers. This is likely the result the faster nodes to
finding each other and making replicas sooner.
\subsection{Swarms with No Seeders}
The primary goal of this research was not to improve
performance in healthy swarms, but rather to prevent the death of unhealthy
swarms. To determine how effective the existing local knowledge
implementation of BitTorrent is at dealing with this situation, we
create a special swarm with no seed. Instead a single copy of
each piece was spread between four nodes which would leave
upon completing the entire file. This creates the situation in which the
swarm had to create copies of all of the pieces before any of
the four critical nodes left the swarm. This kind of swarm also
resembles a swarm that experiences flash crowd behavior where a
large number of nodes join, complete the file, and then leave. The
four nodes that start this simulation would then be the remainder of
that initial flash crowd while the new nodes joining would represent
the steady stream of nodes that often join after a flash crowd.
Using this ``unhealthy'' swarm simulation setup, we ran the
simulation five times for the three levels of node knowledge discussed
in section 4.1: local knowledge, global knowledge and
omniscience. Five runs were performed for each level of knowledge
because the probabilistic distribution of pieces and upload/download
rates sometimes produce swarms that
cannot be saved. This can be seen in the failure that occurs even
with omniscient nodes. Swarms that survive will finish the simulation
with a single node remaining. Among those swarms which did not survive
the degree of piece replication efficiency can be seen in how many
nodes were stranded. The swarms with fewer peers remaining manage to
replicate the pieces more efficiently and thereby extend the
lifetime of the torrent. We present the results from all five runs for each type
of node knowledge in Table \ref{tab:noseedresults}.
\begin{table*}
\centering
\caption{Swarms with No Seeds Results}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
\multicolumn{11}{|c|}{Experiments}\\ \hline
Runs & 1 & 2 & 3 & 4 & 5 & 1 & 2 & 3 & 4 & 5\\ \hline
Knowledge Type & \multicolumn{5}{c|}{nodes stranded} & \multicolumn{5}{c|}{average times}\\ \hline
Local & 99& 2& 99& 99& 99&1387&2540&1710&2019&1433\\
Global & 99& 99& 99& 99& 46&1850&1464&1369&1535&2391\\
Omniscient & 1& 2& 2& 99& 2&1711&2370&1646&1465&2386\\
Gossip & 11& 99& 1& 7& 99&1981&1254&2293&1901&2130\\ \hline \hline
\multicolumn{11}{|c|}{Summary}\\ \hline
Knowledge Type & \multicolumn{5}{c|}{Average Nodes Stranded} & \multicolumn{5}{c|}{Average Times}\\ \hline
Local & \multicolumn{5}{c|}{80} & \multicolumn{5}{c|}{1818}\\
Global & \multicolumn{5}{c|}{88} & \multicolumn{5}{c|}{1727}\\
Omniscient & \multicolumn{5}{c|}{21} & \multicolumn{5}{c|}{1916}\\
Gossip & \multicolumn{5}{c|}{43} & \multicolumn{5}{c|}{1912}\\
\hline\end{tabular}
\label{tab:noseedresults}
\end{table*}
%variables global, local or omniscient knowledge
%Table
% Runs | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |
%Knowledge Type | nodes stranded | average times |
% local | 99| 2| 99| 99| 99|1387|2540|1710|2019|1433|
% global | 99| 99| 99| 99| 46|1850|1464|1369|1535|2391|
% omniscient | 1| 2| 2| 99| 2|1711|2370|1646|1465|2386|
%Knowledge Type | average nodes stranded | average time |
% local | 80 | 1818 |
% global | 88 | 1727 |
% omniscient | 21 | 1916 |
From the results in Table \ref{tab:noseedresults} we can see that omniscient node knowledge
represents a optimal maximum for the efficiency of piece
replication. Interestingly, global knowledge performs worse than local
knowledge in terms of efficient piece replication. This is because the
global view of the swarms causes the nodes with global knowledge to all
download the same piece from the critical nodes so many copies are
created of one critically rare piece while other critically rare
pieces aren't copied at all. The local knowledge nodes were
more efficient because their notion of the rarest piece was more
diverse. This led them to replicate different pieces and achieve more
efficient replication overall. The primary conclusion to be drawn from
these results is while local knowledge can
occasionally save a swarm, a more intelligent piece replication scheme
would be more effective. This opens the door for BitTorrent gossip to
achieve real gains over the traditional implementation by extending
the lifetime of the torrent in extreme situations.