-
-
Notifications
You must be signed in to change notification settings - Fork 993
/
choker.cpp
291 lines (240 loc) · 10.4 KB
/
choker.cpp
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
/*
Copyright (c) 2019, Amir Abrams
Copyright (c) 2014-2020, Arvid Norberg
Copyright (c) 2016, 2018, 2020-2021, Alden Torres
Copyright (c) 2016, Steven Siloti
Copyright (c) 2019, Monson Shao
All rights reserved.
You may use, distribute and modify this code under the terms of the BSD license,
see LICENSE file.
*/
#include "libtorrent/aux_/choker.hpp"
#include "libtorrent/aux_/peer_connection.hpp"
#include "libtorrent/aux_/session_settings.hpp"
#include "libtorrent/aux_/time.hpp"
#include "libtorrent/aux_/torrent.hpp"
#include <functional>
using namespace std::placeholders;
namespace libtorrent::aux {
namespace {
int compare_peers(peer_connection const* lhs, peer_connection const* rhs)
{
int const prio1 = lhs->get_priority(peer_connection::upload_channel);
int const prio2 = rhs->get_priority(peer_connection::upload_channel);
if (prio1 != prio2) return prio1 > prio2 ? 1 : -1;
// compare how many bytes they've sent us
std::int64_t const c1 = lhs->downloaded_in_last_round();
std::int64_t const c2 = rhs->downloaded_in_last_round();
if (c1 != c2) return c1 > c2 ? 1 : -1;
return 0;
}
// return true if 'lhs' peer should be preferred to be unchoke over 'rhs'
bool unchoke_compare_rr(peer_connection const* lhs
, peer_connection const* rhs, int pieces)
{
int const cmp = compare_peers(lhs, rhs);
if (cmp != 0) return cmp > 0;
// when seeding, rotate which peer is unchoked in a round-robin fashion
// the amount uploaded since unchoked (not just in the last round)
std::int64_t const u1 = lhs->uploaded_since_unchoked();
std::int64_t const u2 = rhs->uploaded_since_unchoked();
// the way the round-robin unchoker works is that it,
// by default, prioritizes any peer that is already unchoked.
// this maintain the status quo across unchoke rounds. However,
// peers that are unchoked, but have sent more than one quota
// since they were unchoked, they get de-prioritized.
auto const t1 = lhs->associated_torrent().lock();
auto const t2 = rhs->associated_torrent().lock();
TORRENT_ASSERT(t1);
TORRENT_ASSERT(t2);
// if a peer is already unchoked, the number of bytes sent since it was unchoked
// is greater than the send quanta, and it has been unchoked for at least one minute
// then it's done with its upload slot, and we can de-prioritize it
bool const c1_quota_complete = !lhs->is_choked()
&& u1 > std::int64_t(t1->torrent_file().piece_length()) * pieces
&& aux::time_now() - lhs->time_of_last_unchoke() > minutes(1);
bool const c2_quota_complete = !rhs->is_choked()
&& u2 > std::int64_t(t2->torrent_file().piece_length()) * pieces
&& aux::time_now() - rhs->time_of_last_unchoke() > minutes(1);
// if c2 has completed a quanta, it should be de-prioritized
// and vice versa
if (c1_quota_complete != c2_quota_complete)
return int(c1_quota_complete) < int(c2_quota_complete);
// when seeding, prefer the peer we're uploading the fastest to
// force the upload rate to zero for choked peers because
// if the peers just got choked the previous round
// there may have been a residual transfer which was already
// in-flight at the time and we don't want that to cause the peer
// to be ranked at the top of the choked peers
std::int64_t const c1 = lhs->is_choked() ? 0 : lhs->uploaded_in_last_round();
std::int64_t const c2 = rhs->is_choked() ? 0 : rhs->uploaded_in_last_round();
if (c1 != c2) return c1 > c2;
// if the peers are still identical (say, they're both waiting to be unchoked)
// prioritize the one that has waited the longest to be unchoked
// the round-robin unchoker relies on this logic. Don't change it
// without moving this into that unchoker logic
return lhs->time_of_last_unchoke() < rhs->time_of_last_unchoke();
}
// return true if 'lhs' peer should be preferred to be unchoke over 'rhs'
bool unchoke_compare_fastest_upload(peer_connection const* lhs
, peer_connection const* rhs)
{
int const cmp = compare_peers(lhs, rhs);
if (cmp != 0) return cmp > 0;
// when seeding, prefer the peer we're uploading the fastest to
std::int64_t const c1 = lhs->uploaded_in_last_round();
std::int64_t const c2 = rhs->uploaded_in_last_round();
if (c1 != c2) return c1 > c2;
// prioritize the one that has waited the longest to be unchoked
// the round-robin unchoker relies on this logic. Don't change it
// without moving this into that unchoker logic
return lhs->time_of_last_unchoke() < rhs->time_of_last_unchoke();
}
int anti_leech_score(peer_connection const* peer)
{
// the anti-leech seeding algorithm is based on the paper "Improving
// BitTorrent: A Simple Approach" from Chow et. al. and ranks peers based
// on how many pieces they have, preferring to unchoke peers that just
// started and peers that are close to completing. Like this:
// ^
// | \ / |
// | \ / |
// | \ / |
// s | \ / |
// c | \ / |
// o | \ / |
// r | \ / |
// e | \ / |
// | \ / |
// | \ / |
// | \ / |
// | \ / |
// | V |
// +---------------------------+
// 0% num have pieces 100%
std::shared_ptr<torrent> const t = peer->associated_torrent().lock();
TORRENT_ASSERT(t);
std::int64_t const total_size = t->torrent_file().total_size();
if (total_size == 0) return 0;
// Cap the given_size so that it never causes the score to increase
std::int64_t const given_size = std::min(peer->statistics().total_payload_upload()
, total_size / 2);
std::int64_t const have_size = std::max(given_size
, std::int64_t(t->torrent_file().piece_length()) * peer->num_have_pieces());
return int(std::abs((have_size - total_size / 2) * 2000 / total_size));
}
// return true if 'lhs' peer should be preferred to be unchoke over 'rhs'
bool unchoke_compare_anti_leech(peer_connection const* lhs
, peer_connection const* rhs)
{
int const cmp = compare_peers(lhs, rhs);
if (cmp != 0) return cmp > 0;
int const score1 = anti_leech_score(lhs);
int const score2 = anti_leech_score(rhs);
if (score1 != score2) return score1 > score2;
// prioritize the one that has waited the longest to be unchoked
// the round-robin unchoker relies on this logic. Don't change it
// without moving this into that unchoker logic
return lhs->time_of_last_unchoke() < rhs->time_of_last_unchoke();
}
bool upload_rate_compare(peer_connection const* lhs
, peer_connection const* rhs)
{
// take torrent priority into account
std::int64_t const c1 = lhs->uploaded_in_last_round()
* lhs->get_priority(peer_connection::upload_channel);
std::int64_t const c2 = rhs->uploaded_in_last_round()
* rhs->get_priority(peer_connection::upload_channel);
return c1 > c2;
}
} // anonymous namespace
int unchoke_sort(std::vector<peer_connection*>& peers
, time_duration const unchoke_interval
, aux::session_settings const& sett)
{
#if TORRENT_USE_ASSERTS
for (auto p : peers)
{
TORRENT_ASSERT(p->self());
TORRENT_ASSERT(p->associated_torrent().lock());
}
#endif
int upload_slots = sett.get_int(settings_pack::unchoke_slots_limit);
if (upload_slots < 0)
upload_slots = std::numeric_limits<int>::max();
// ==== rate-based ====
//
// The rate based unchoker looks at our upload rate to peers, and find
// a balance between number of upload slots and the rate we achieve. The
// intention is to not spread upload bandwidth too thin, but also to not
// unchoke few enough peers to not be able to saturate the up-link.
// this is done by traversing the peers sorted by our upload rate to
// them in decreasing rates. For each peer we increase the threshold by
// 2 kiB/s. The first peer we get to whom we upload slower than
// the threshold, we stop and that's the number of unchoke slots we have.
if (sett.get_int(settings_pack::choking_algorithm)
== settings_pack::rate_based_choker)
{
// first reset the number of unchoke slots, because we'll calculate
// it purely based on the current state of our peers.
upload_slots = 0;
int rate_threshold = sett.get_int(settings_pack::rate_choker_initial_threshold);
std::sort(peers.begin(), peers.end()
, [](peer_connection const* lhs, peer_connection const* rhs)
{ return upload_rate_compare(lhs, rhs); });
for (auto const* p : peers)
{
int const rate = int(p->uploaded_in_last_round()
* 1000 / total_milliseconds(unchoke_interval));
// always have at least 1 unchoke slot
if (rate < rate_threshold) break;
++upload_slots;
// TODO: make configurable
rate_threshold += 2048;
}
++upload_slots;
}
// sorts the peers that are eligible for unchoke by download rate and
// secondary by total upload. The reason for this is, if all torrents are
// being seeded, the download rate will be 0, and the peers we have sent
// the least to should be unchoked
// we use partial sort here, because we only care about the top
// upload_slots peers.
int const slots = std::min(upload_slots, int(peers.size()));
if (sett.get_int(settings_pack::seed_choking_algorithm)
== settings_pack::round_robin)
{
int const pieces = sett.get_int(settings_pack::seeding_piece_quota);
std::nth_element(peers.begin(), peers.begin()
+ slots, peers.end()
, [pieces](peer_connection const* lhs, peer_connection const* rhs)
{ return unchoke_compare_rr(lhs, rhs, pieces); });
}
else if (sett.get_int(settings_pack::seed_choking_algorithm)
== settings_pack::fastest_upload)
{
std::nth_element(peers.begin(), peers.begin()
+ slots, peers.end()
, [](peer_connection const* lhs, peer_connection const* rhs)
{ return unchoke_compare_fastest_upload(lhs, rhs); });
}
else if (sett.get_int(settings_pack::seed_choking_algorithm)
== settings_pack::anti_leech)
{
std::nth_element(peers.begin(), peers.begin()
+ slots, peers.end()
, [](peer_connection const* lhs, peer_connection const* rhs)
{ return unchoke_compare_anti_leech(lhs, rhs); });
}
else
{
int const pieces = sett.get_int(settings_pack::seeding_piece_quota);
std::nth_element(peers.begin(), peers.begin()
+ slots, peers.end()
, [pieces](peer_connection const* lhs, peer_connection const* rhs)
{ return unchoke_compare_rr(lhs, rhs, pieces); } );
TORRENT_ASSERT_FAIL();
}
return upload_slots;
}
}