3
Copyright (c) 2006, Arvid Norberg
6
Redistribution and use in source and binary forms, with or without
7
modification, are permitted provided that the following conditions
10
* Redistributions of source code must retain the above copyright
11
notice, this list of conditions and the following disclaimer.
12
* Redistributions in binary form must reproduce the above copyright
13
notice, this list of conditions and the following disclaimer in
14
the documentation and/or other materials provided with the distribution.
15
* Neither the name of the author nor the names of its
16
contributors may be used to endorse or promote products derived
17
from this software without specific prior written permission.
19
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29
POSSIBILITY OF SUCH DAMAGE.
33
#include "libtorrent/pch.hpp"
40
#include <boost/cstdint.hpp>
41
#include <boost/bind.hpp>
43
#include "libtorrent/kademlia/routing_table.hpp"
44
#include "libtorrent/kademlia/node_id.hpp"
45
#include "libtorrent/session_settings.hpp"
50
namespace libtorrent { namespace dht
54
typedef asio::ip::address_v4 address;
56
routing_table::routing_table(node_id const& id, int bucket_size
57
, dht_settings const& settings)
58
: m_bucket_size(bucket_size)
59
, m_settings(settings)
61
, m_lowest_active_bucket(160)
63
// distribute the refresh times for the buckets in an
64
// attempt do even out the network load
65
for (int i = 0; i < 160; ++i)
66
m_bucket_activity[i] = time_now() - milliseconds(i*5625);
67
m_bucket_activity[0] = time_now() - minutes(15);
70
boost::tuple<int, int> routing_table::size() const
74
for (table_t::const_iterator i = m_buckets.begin()
75
, end(m_buckets.end()); i != end; ++i)
77
nodes += i->first.size();
78
replacements += i->second.size();
80
return boost::make_tuple(nodes, replacements);
83
size_type routing_table::num_global_nodes() const
85
int first_full = m_lowest_active_bucket;
86
int num_nodes = 1; // we are one of the nodes
87
for (; first_full < 160
88
&& int(m_buckets[first_full].first.size()) < m_bucket_size;
91
num_nodes += m_buckets[first_full].first.size();
94
return (2 << (160 - first_full)) * num_nodes;
97
#ifdef TORRENT_DHT_VERBOSE_LOGGING
99
void routing_table::print_state(std::ostream& os) const
101
os << "kademlia routing table state\n"
102
<< "bucket_size: " << m_bucket_size << "\n"
103
<< "global node count: " << num_global_nodes() << "\n"
104
<< "node_id: " << m_id << "\n\n";
106
os << "number of nodes per bucket:\n-- live ";
107
for (int i = 8; i < 160; ++i)
111
for (int k = 0; k < 8; ++k)
113
for (table_t::const_iterator i = m_buckets.begin(), end(m_buckets.end());
116
os << (int(i->first.size()) > (7 - k) ? "|" : " ");
120
for (table_t::const_iterator i = m_buckets.begin(), end(m_buckets.end());
126
for (int k = 0; k < 8; ++k)
128
for (table_t::const_iterator i = m_buckets.begin(), end(m_buckets.end());
131
os << (int(i->second.size()) > k ? "|" : " ");
136
for (int i = 10; i < 160; ++i)
141
for (table_t::const_iterator i = m_buckets.begin(), end(m_buckets.end());
144
int bucket_index = int(i - m_buckets.begin());
145
os << "=== BUCKET = " << bucket_index
146
<< " = " << (bucket_index >= m_lowest_active_bucket?"active":"inactive")
147
<< " = " << total_seconds(time_now() - m_bucket_activity[bucket_index])
148
<< " s ago ===== \n";
149
for (bucket_t::const_iterator j = i->first.begin()
150
, end(i->first.end()); j != end; ++j)
152
os << "ip: " << j->addr << " fails: " << j->fail_count
153
<< " id: " << j->id << "\n";
160
void routing_table::touch_bucket(int bucket)
162
m_bucket_activity[bucket] = time_now();
165
ptime routing_table::next_refresh(int bucket)
167
TORRENT_ASSERT(bucket < 160);
168
TORRENT_ASSERT(bucket >= 0);
169
// lower than or equal to since a refresh of bucket 0 will
170
// effectively refresh the lowest active bucket as well
171
if (bucket < m_lowest_active_bucket && bucket > 0)
172
return time_now() + minutes(15);
173
return m_bucket_activity[bucket] + minutes(15);
176
void routing_table::replacement_cache(bucket_t& nodes) const
178
for (table_t::const_iterator i = m_buckets.begin()
179
, end(m_buckets.end()); i != end; ++i)
181
std::copy(i->second.begin(), i->second.end()
182
, std::back_inserter(nodes));
186
bool routing_table::need_node(node_id const& id)
188
int bucket_index = distance_exp(m_id, id);
189
TORRENT_ASSERT(bucket_index < (int)m_buckets.size());
190
TORRENT_ASSERT(bucket_index >= 0);
191
bucket_t& b = m_buckets[bucket_index].first;
192
bucket_t& rb = m_buckets[bucket_index].second;
194
// if the replacement cache is full, we don't
195
// need another node. The table is fine the
197
if ((int)rb.size() >= m_bucket_size) return false;
199
// if the node already exists, we don't need it
200
if (std::find_if(b.begin(), b.end(), bind(&node_entry::id, _1) == id)
201
!= b.end()) return false;
203
if (std::find_if(rb.begin(), rb.end(), bind(&node_entry::id, _1) == id)
204
!= rb.end()) return false;
209
void routing_table::node_failed(node_id const& id)
211
int bucket_index = distance_exp(m_id, id);
212
TORRENT_ASSERT(bucket_index < (int)m_buckets.size());
213
TORRENT_ASSERT(bucket_index >= 0);
214
bucket_t& b = m_buckets[bucket_index].first;
215
bucket_t& rb = m_buckets[bucket_index].second;
217
bucket_t::iterator i = std::find_if(b.begin(), b.end()
218
, bind(&node_entry::id, _1) == id);
220
if (i == b.end()) return;
222
// if messages to ourself fails, ignore it
223
if (bucket_index == 0) return;
228
if (i->fail_count >= m_settings.max_fail_count)
231
TORRENT_ASSERT(m_lowest_active_bucket <= bucket_index);
232
while (m_lowest_active_bucket < 160
233
&& m_buckets[m_lowest_active_bucket].first.empty())
235
++m_lowest_active_bucket;
242
b.push_back(rb.back());
243
rb.erase(rb.end() - 1);
246
void routing_table::add_router_node(udp::endpoint router)
248
m_router_nodes.insert(router);
251
// this function is called every time the node sees
252
// a sign of a node being alive. This node will either
253
// be inserted in the k-buckets or be moved to the top
255
// the return value indicates if the table needs a refresh.
256
// if true, the node should refresh the table (i.e. do a find_node
258
bool routing_table::node_seen(node_id const& id, udp::endpoint addr)
260
if (m_router_nodes.find(addr) != m_router_nodes.end()) return false;
261
int bucket_index = distance_exp(m_id, id);
262
TORRENT_ASSERT(bucket_index < (int)m_buckets.size());
263
TORRENT_ASSERT(bucket_index >= 0);
264
bucket_t& b = m_buckets[bucket_index].first;
266
bucket_t::iterator i = std::find_if(b.begin(), b.end()
267
, bind(&node_entry::id, _1) == id);
269
bool ret = need_bootstrap();
271
//m_bucket_activity[bucket_index] = time_now();
275
// TODO: what do we do if we see a node with
276
// the same id as a node at a different address?
277
// TORRENT_ASSERT(i->addr == addr);
279
// we already have the node in our bucket
280
// just move it to the back since it was
281
// the last node we had any contact with
284
b.push_back(node_entry(id, addr));
285
// TORRENT_LOG(table) << "replacing node: " << id << " " << addr;
289
// if the node was not present in our list
290
// we will only insert it if there is room
291
// for it, or if some of our nodes have gone
293
if ((int)b.size() < m_bucket_size)
295
if (b.empty()) b.reserve(m_bucket_size);
296
b.push_back(node_entry(id, addr));
297
// if bucket index is 0, the node is ourselves
298
// don't updated m_lowest_active_bucket
299
if (bucket_index < m_lowest_active_bucket
301
m_lowest_active_bucket = bucket_index;
302
// TORRENT_LOG(table) << "inserting node: " << id << " " << addr;
306
// if there is no room, we look for nodes marked as stale
307
// in the k-bucket. If we find one, we can replace it.
308
// A node is considered stale if it has failed at least one
309
// time. Here we choose the node that has failed most times.
310
// If we don't find one, place this node in the replacement-
311
// cache and replace any nodes that will fail in the future
312
// with nodes from that cache.
314
i = std::max_element(b.begin(), b.end()
315
, bind(&node_entry::fail_count, _1)
316
< bind(&node_entry::fail_count, _2));
318
if (i != b.end() && i->fail_count > 0)
320
// i points to a node that has been marked
321
// as stale. Replace it with this new one
323
b.push_back(node_entry(id, addr));
324
// TORRENT_LOG(table) << "replacing stale node: " << id << " " << addr;
328
// if we don't have any identified stale nodes in
329
// the bucket, and the bucket is full, we have to
330
// cache this node and wait until some node fails
331
// and then replace it.
333
bucket_t& rb = m_buckets[bucket_index].second;
335
i = std::find_if(rb.begin(), rb.end()
336
, bind(&node_entry::id, _1) == id);
338
// if the node is already in the replacement bucket
340
if (i != rb.end()) return ret;
342
if ((int)rb.size() > m_bucket_size) rb.erase(rb.begin());
343
if (rb.empty()) rb.reserve(m_bucket_size);
344
rb.push_back(node_entry(id, addr));
345
// TORRENT_LOG(table) << "inserting node in replacement cache: " << id << " " << addr;
349
bool routing_table::need_bootstrap() const
351
for (const_iterator i = begin(); i != end(); ++i)
353
if (i->fail_count == 0) return false;
358
// fills the vector with the k nodes from our buckets that
359
// are nearest to the given id.
360
void routing_table::find_node(node_id const& target
361
, std::vector<node_entry>& l, bool include_self, int count)
364
if (count == 0) count = m_bucket_size;
367
int bucket_index = distance_exp(m_id, target);
368
bucket_t& b = m_buckets[bucket_index].first;
370
// copy all nodes that hasn't failed into the target
372
std::remove_copy_if(b.begin(), b.end(), std::back_inserter(l)
373
, bind(&node_entry::fail_count, _1));
374
TORRENT_ASSERT((int)l.size() <= count);
376
if ((int)l.size() == count)
378
TORRENT_ASSERT(std::count_if(l.begin(), l.end()
379
, boost::bind(&node_entry::fail_count, _1) != 0) == 0);
383
// if we didn't have enough nodes in that bucket
384
// we have to reply with nodes from buckets closer
385
// to us. i.e. all the buckets in the range
386
// [0, bucket_index) if we are to include ourself
387
// or [1, bucket_index) if not.
389
for (int i = include_self?0:1; i < bucket_index; ++i)
391
bucket_t& b = m_buckets[i].first;
392
std::remove_copy_if(b.begin(), b.end(), std::back_inserter(tmpb)
393
, bind(&node_entry::fail_count, _1));
396
std::random_shuffle(tmpb.begin(), tmpb.end());
397
size_t to_copy = (std::min)(m_bucket_size - l.size()
399
std::copy(tmpb.begin(), tmpb.begin() + to_copy
400
, std::back_inserter(l));
402
TORRENT_ASSERT((int)l.size() <= m_bucket_size);
404
// return if we have enough nodes or if the bucket index
405
// is the biggest index available (there are no more buckets)
407
if ((int)l.size() == count
408
|| bucket_index == (int)m_buckets.size() - 1)
410
TORRENT_ASSERT(std::count_if(l.begin(), l.end()
411
, boost::bind(&node_entry::fail_count, _1) != 0) == 0);
415
for (size_t i = bucket_index + 1; i < m_buckets.size(); ++i)
417
bucket_t& b = m_buckets[i].first;
419
std::remove_copy_if(b.begin(), b.end(), std::back_inserter(l)
420
, bind(&node_entry::fail_count, _1));
421
if ((int)l.size() >= count)
423
l.erase(l.begin() + count, l.end());
424
TORRENT_ASSERT(std::count_if(l.begin(), l.end()
425
, boost::bind(&node_entry::fail_count, _1) != 0) == 0);
429
TORRENT_ASSERT((int)l.size() == count
430
|| std::distance(l.begin(), l.end()) < m_bucket_size);
431
TORRENT_ASSERT((int)l.size() <= count);
433
TORRENT_ASSERT(std::count_if(l.begin(), l.end()
434
, boost::bind(&node_entry::fail_count, _1) != 0) == 0);
437
routing_table::iterator routing_table::begin() const
439
// +1 to avoid ourself
440
return iterator(m_buckets.begin() + 1, m_buckets.end());
443
routing_table::iterator routing_table::end() const
445
return iterator(m_buckets.end(), m_buckets.end());
448
} } // namespace libtorrent::dht
added
removed
src/kademlia/routing_table.cpp
