:BEP: 33 :Title: DHT Scrapes :Version: 9c5c1dd1b372016e05af84fb34fccac6752ef54a

Last-Modified:Thu Jul 21 10:45:38 2016 -0400
Author:The 8472
Status:Draft
Type:Standards Track
Content-Type:text/x-rst
Created:20-Jan-2010
Post-History:

Abstract

This BEP specifies an extension to the BitTorrent DHT (BEP 5) to support scrapes via distributed counting based on bloom filters.

Rationale

Scrapes are an important part of the BitTorrent ecosystem as they allow users to assess the state of a torrent and clients to determine which swarm to select next in their seeding queue, without having to participate in the swarm first.

These options are currently not available in the absence of a tracker, this BEP aims to rectify this.

Approach

Due to the lack of replication, inaccurate routing table maintenance and stores on nodes outside the circle of the K closest nodes announces are often scattered over a dozen or more nodes around the target key, with no single node having a complete set of peers.

Estimating the swarm size based on such random distributions would be very noisy and border on guessing since the number of values nodes share for any given key is not known, and thus either averaging or adding them can be required in the extreme cases.

For distributed counting Bloom Filters are suitable because their population count can be estimated, they are compact and performing unions is trivial

Bloom Filters

To keep things simple and ensure compatibility all implementations must be functionally equivalent to the following pseudocode (all variables are unsigned):

// fixed parameters
k = 2
m = 256*8

// the filter
byte[m/8] bloom

function insertIP(byte[] ip) {

    byte[20] hash = sha1(ip)

    int index1 = hash[0] | hash[1] << 8
    int index2 = hash[2] | hash[3] << 8

    // truncate index to m (11 bits required)
    index1 %= m
    index2 %= m

    // set bits at index1 and index2
    bloom[index1 / 8] |= 0x01 << index1 % 8
    bloom[index2 / 8] |= 0x01 << index2 % 8
}

// insert IP 192.168.1.1 into the filter:
insertIP(byte[4] {192,168,1,1})

Only IP addresses (v4 or v6) may be inserted into the bloom filters. Port numbers or host names are not allowed.

Calculating the estimate

To estimate the count of items in a bloom filter the following equation can (see [1]) be used:

k = 2
m = 256*8

c = min(m-1,countZeroBits(bloom))

size = log(c /m) / (k * log(1 - 1/m))

The same equation can be used to estimate the size of a union of sets represented by bloom filters simply by ORing the bits of each filter.

With the chosen parameters the false error rate approaches one around 8000 inserted values, at this point the size estimation breaks down.

Improved algorithms to calculate the cardinality of the union of bloom filters may work beyond that limit for somewhat disjoint sets but they require further research.

Test Vectors

Inserting the addresses 192.0.2.0 - 192.0.2.255 and 2001:DB8:: - 2001:DB8::3E7 (ranges are inclusive) into a bloom filter must result in the following array of bytes in hex representation:

F6C3F5EA A07FFD91 BDE89F77 7F26FB2B FF37BDB8 FB2BBAA2 FD3DDDE7 BACFFF75 EE7CCBAE
FE5EEDB1 FBFAFF67 F6ABFF5E 43DDBCA3 FD9B9FFD F4FFD3E9 DFF12D1B DF59DB53 DBE9FA5B
7FF3B8FD FCDE1AFB 8BEDD7BE 2F3EE71E BBBFE93B CDEEFE14 8246C2BC 5DBFF7E7 EFDCF24F
D8DC7ADF FD8FFFDF DDFFF7A4 BBEEDF5C B95CE81F C7FCFF1F F4FFFFDF E5F7FDCB B7FD79B3
FA1FC77B FE07FFF9 05B7B7FF C7FEFEFF E0B8370B B0CD3F5B 7F2BD93F EB4386CF DD6F7FD5
BFAF2E9E BFFFFEEC D67ADBF7 C67F17EF D5D75EBA 6FFEBA7F FF47A91E B1BFBB53 E8ABFB57
62ABE8FF 237279BF EFBFEEF5 FFC5FEBF DFE5ADFF ADFEE1FB 737FFFFB FD9F6AEF FEEE76B6
FD8F72EF

For the 1256 inserted values the calculated estimate should be 1224.9308

Implementations must be tested for correctness before deployment since incorrect bloom filter implementations would completely distort scrape results.

New ANNOUNCE_PEER semantics

If the requesting node is seeding the torrent it announces then it must add a "seed"=1 key/value-pair to the "a" dictionary in the request.

The response is unchanged.

New GET_PEERS semantics

Requests now support two new parameters in the "a" dictionary: "noseed"=1 and "scrape"=1

If "noseed" is set to 1 in the request then the responding node should try to fill the values list with non-seed items on a best-effort basis.

If "scrape" is set to 1 in the request and the responding node has database entries for that infohash then it must add two fields to the "r" dictionary in the response:

"BFsd" : Bloom Filter representing all stored seeds for that infohash "BFpe" : Bloom Filter representing all stored peers for that infohash

Each field must be 256 bytes in size and generated based on the algorithm described in the previous chapter.

The requesting nodes may perform sanity checks on the returned bloom filters, e.g. checking if they are not full (within the 6000 entry limit defined below) or if the returned values are actually contained in either of the two filters.

Implementations which also implement BEP 32 must take care not to exceed the specified packet sizes since the filters require over 512 bytes in the packet. This can be achieved by returning less values and only returning the mandatory node lists even when additional ones are requested.

Tokens may be omitted under certain conditions (see changed announce accounting). If a node does not return a token it indicates that it currently cannot accept announces for this infohash. Thus the requesting node should only announce to the K nodes which are the the closest to the target and have returned a token.

Handling legacy responses

If a response only contains a "values" list when a scrape has been requested then an implementation may generate a bloom filter for that list locally.

Due to the absence of seed/peer information the filter should be considered as a peer filter. Before inserting values into the filter it should check if the IPs are not present in the seed filters of other nodes to prevent the item from being counted as seed and peer at the same time.

Changed announce accounting

Nodes following this BEP must store the seed status of announcing nodes, if no seed key was present or the value was not 1 then it should assume that the announcing node is a peer.

Nodes must store peer information as sets of unique IPs for each infohash. I.e. <Infohash,IP> tuples in the database must be unique while port numbers, seed status and other values may be updated.

Nodes should try to keep max(seeds,peers) below 6000 since the bloom filters reach a false positive rate of 1.0 as they approach a set size of ~8000 entries . This can be achieved by not responding with tokens to get_peers requests for an infohash which has reached this limit.

Scrape scheduling

Scrapes for active torrents can be piggybacked on the announces and thus should only incur minimal additional cost.

Inactive torrents on the other hand must be scheduled carefully since clients can potentially keep track of hundreds of inactive torrents for every active one.

  • Clients should only perform DHT scrapes on torrents where no tracker is available or tracker scrapes are not successful
  • The number of concurrently active scrapes for inactive torrents should be limited, e.g. 4 during startup and 1 for steady state operation.
  • Intervals between scrapes should be somewhat randomized to avoid wave-like traffic patterns.
  • Scrapes for inactive torrents should be performed with a lower RPC concurrency and more lenient timeouts than regular lookups as they have a low priority. 3 concurrent RPC calls and 10s timeouts should be sufficient.
  • Caching node lists from previous lookups to the same torrents can significantly cut down on the lookup traffic for repeated scrapes to the same torrents

Acknowledgements

Thanks to Juliusz Chroboczek to let me bounce ideas off him.

References

[1]Broder, Andrei; Mitzenmacher, Michael (2005), "Network Applications of Bloom Filters: A Survey" (http://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf)