release/src/router/transmission/third-party/dht/README

   1 The files dht.c and dht.h implement the variant of the Kademlia Distributed
   2 Hash Table (DHT) used in the Bittorrent network (``mainline'' variant).
   3
   4 The file dht-example.c is a stand-alone program that participates in the
   5 DHT.  Another example is a patch against Transmission, which you might or
   6 might not be able to find somewhere.
   7
   8 The code is designed to work well in both event-driven and threaded code.
   9 The caller, which is either an event-loop or a dedicated thread, must
  10 periodically call the function dht_periodic.  In addition, it must call
  11 dht_periodic whenever any data has arrived from the network.
  12
  13 All functions return -1 in case of failure, in which case errno is set, or
  14 a positive value in case of success.
  15
  16 Initialisation
  17 **************
  18
  19 * dht_init
  20
  21 This must be called before using the library.  You pass it a bound IPv4
  22 datagram socket, a bound IPv6 datagram socket, and your node id, a 20-octet
  23 array that should be globally unique.
  24
  25 If you're on a multi-homed host, you should bind the sockets to one of your
  26 addresses.
  27
  28 Node ids must be well distributed, so you cannot just use your Bittorrent
  29 id; you should either generate a truly random value (using plenty of
  30 entropy), or at least take the SHA-1 of something.  However, it is a good
  31 idea to keep the id stable, so you may want to store it in stable storage
  32 at client shutdown.
  33
  34
  35 * dht_uninit
  36
  37 This may be called at the end of the session.
  38
  39 Bootstrapping
  40 *************
  41
  42 The DHT needs to be taught a small number of contacts to begin functioning.
  43 You can hard-wire a small number of stable nodes in your application, but
  44 this obviously fails to scale.  You may save the list of known good nodes
  45 at shutdown, and restore it at restart.  You may also grab nodes from
  46 torrent files (the nodes field), and you may exchange contacts with other
  47 Bittorrent peers using the PORT extension.
  48
  49 * dht_ping
  50
  51 This is the main bootstrapping primitive.  You pass it an address at which
  52 you believe that a DHT node may be living, and a query will be sent.  If
  53 a node replies, and if there is space in the routing table, it will be
  54 inserted.
  55
  56 * dht_insert_node
  57
  58 This is a softer bootstrapping method, which doesn't actually send
  59 a query -- it only stores the node in the routing table for later use.  It
  60 is a good idea to use that when e.g. restoring your routing table from
  61 disk.
  62
  63 Note that dht_insert_node requires that you supply a node id.  If the id
  64 turns out to be wrong, the DHT will eventually recover; still, inserting
  65 massive amounts of incorrect information into your routing table is
  66 certainly not a good idea.
  67
  68 An additionaly difficulty with dht_insert_node is that, for various
  69 reasons, a Kademlia routing table cannot absorb nodes faster than a certain
  70 rate.  Dumping a large number of nodes into a table using dht_insert_node
  71 will probably cause most of these nodes to be discarded straight away.
  72 (The tolerable rate is difficult to estimate; it is probably on the order
  73 of one node every few seconds per node already in the table divided by 8,
  74 for some suitable value of 8.)
  75
  76 Doing some work
  77 ***************
  78
  79 * dht_periodic
  80
  81 This function should be called by your main loop periodically, and also
  82 whenever data is available on the socket.  The time after which
  83 dht_periodic should be called if no data is available is returned in the
  84 parameter tosleep.  (You do not need to be particularly accurate; actually,
  85 it is a good idea to be late by a random value.)
  86
  87 The parameters buf, buflen, from and fromlen optionally carry a received
  88 message.  If buflen is 0, then no message was received.
  89
  90 Dht_periodic also takes a callback, which will be called whenever something
  91 interesting happens (see below).
  92
  93 * dht_search
  94
  95 This schedules a search for information about the info-hash specified in
  96 id.  If port is not 0, it specifies the TCP port on which the current peer
  97 is listening; in that case, when the search is complete it will be announced
  98 to the network.  The port is in host order, beware if you got it from
  99 a struct sockaddr_in.
 100
 101 In either case, data is passed to the callback function as soon as it is
 102 available, possibly in multiple pieces.  The callback function will
 103 additionally be called when the search is complete.
 104
 105 Up to DHT_MAX_SEARCHES (1024) searches can be in progress at a given time;
 106 any more, and dht_search will return -1.  If you specify a new search for
 107 the same info hash as a search still in progress, the previous search is
 108 combined with the new one -- you will only receive a completion indication
 109 once.
 110
 111 Information queries
 112 *******************
 113
 114 * dht_nodes
 115
 116 This returns the number of known good, dubious and cached nodes in our
 117 routing table.  This can be used to decide whether it's reasonable to start
 118 a search; a search is likely to be successful as long as we have a few good
 119 nodes; however, in order to avoid overloading your bootstrap nodes, you may
 120 want to wait until good is at least 4 and good + doubtful is at least 30 or
 121 so.
 122
 123 It also includes the number of nodes that recently send us an unsolicited
 124 request; this can be used to determine if the UDP port used for the DHT is
 125 firewalled.
 126
 127 If you want to display a single figure to the user, you should display
 128 good + doubtful, which is the total number of nodes in your routing table.
 129 Some clients try to estimate the total number of nodes, but this doesn't
 130 make much sense -- since the result is exponential in the number of nodes
 131 in the routing table, small variations in the latter cause huge jumps in
 132 the former.
 133
 134 * dht_get_nodes
 135
 136 This retrieves the list of known good nodes, starting with the nodes in our
 137 own bucket.  It is a good idea to save the list of known good nodes at
 138 shutdown, and ping them at startup.
 139
 140 * dht_dump_tables
 141 * dht_debug
 142
 143 These are debugging aids.
 144
 145 Functions provided by you
 146 *************************
 147
 148 * The callback function
 149
 150 The callback function is called with 5 arguments.  Closure is simply the
 151 value that you passed to dht_periodic.  Event is one of DHT_EVENT_VALUES or
 152 DHT_EVENT_VALUES6, which indicates that we have new values, or
 153 DHT_EVENT_SEARCH_DONE or DHT_EVENT_SEARCH_DONE6, which indicates that
 154 a search has completed.  In either case, info_hash is set to the info-hash
 155 of the search.
 156
 157 In the case of DHT_EVENT_VALUES, data is a list of nodes in ``compact''
 158 format -- 6 or 18 bytes per node.  Its length in bytes is in data_len.
 159
 160 * dht_hash
 161
 162 This should compute a reasonably strong cryptographic hash of the passed
 163 values.  It should map cleanly to your favourite crypto toolkit's MD5 or
 164 SHA-1 function.
 165
 166 * dht_random_bytes
 167
 168 This should fill the supplied buffer with true random bytes.
 169
 170 Final notes
 171 ***********
 172
 173 * NAT
 174
 175 Nothing works well across NATs, but Kademlia is somewhat less impacted than
 176 many other protocols.  The implementation takes care to distinguish between
 177 unidirectional and bidirectional reachability, and NATed nodes will
 178 eventually fall out from other nodes' routing tables.
 179
 180 While there is no periodic pinging in this implementation, maintaining
 181 a full routing table requires slightly more than one packet exchange per
 182 minute, even in a completely idle network; this should be sufficient to
 183 make most full cone NATs happy.
 184
 185 * Missing functionality
 186
 187 Some of the code has had very little testing.  If it breaks, you get to
 188 keep both pieces.
 189
 190
 191                                         Juliusz Chroboczek
 192                                         <jch@pps.jussieu.fr>