forum.bittorrent.org

I think you're right about caching, it definitely makes sense. I would think that caching can be solved separately though, don't you think?

I spent some time thinking about torrent metadata in general, and I wonder if it would make sense to have some slightly more generalized way of specifying how to treat data when it's requested. For instance there could be some prefixes to the names that indicates that its data either return average, median, max, min over some window. This would assume that clients who participate in the swarm announce their understanding of the number of peers and seeds.

For this particular case though, it might make more sense to have the DHT nodes that track the torrent be the authoritative source of the scrape stats, instead of having nodes that announce to it say how many seeds and peers it knows of.

The last missing piece of the puzzle of decentralized torrents are scrapes. Scrapes are necessary for seeding queue ordering...

Since I'm not convinced that ordering the seeding queue according to peer count is such a hot idea, I'd rather we didn't add extra complexity for this purpose.

(Ordering the queue according to seed count is a case of negative feedback, and it causes persistent oscillations in torrent state.)

--Juliusz

Or rather, they should be added together with a weight applied based on their similiarity, effectively only averaging their common nodes and adding those where they differ.

Just take the max.  The node that you queried that has the most peers is the one that has been around the longest, and has the most complete vision of the swarm.

--Juliusz

> e.g. due to perimeter widening

First of all, what you call "perimeter widening" doesn't work, at least not in Kademlia.  Don't do it, unless you are able to give a proof of your extension to Kademlia.  (Not only that it doesn't break the DHT, but also that it serves a useful purpose.)

Second, even if it did work, you wouldn't need it.  If the torrent is very popular, and its 8 closest nodes are overloaded, you won't be able to announce yourself, but you'll still get information about other peers; that gives you 8*50=400 peers to connect to.  While not all of those will be reachable, the 200 or so that will are more than enough to propagate your contact address over PEX.  (And I know that you do implement the "p" parameter to LTEP.)

Third, if Kademlia is implemented right, then the oldest among the 8 nodes have roughly the same data -- excepth when some of them have dropped some data due to overload.  In the latter case, you don't care that you're inaccurate -- the information that "the swarm has a lot of peers" is enough for you to make your queueing decisions.

I'd suggest a simple extension -- get_peers replies should contain the total number of values that the replying node has for a given torrent (which can be, in general, more than the number of returned values).

Another extension could be adding a parameter to get_peers to specify the maximum number of values that the replying node should return -- the default being 50, as per BEP-5.

--Juliusz

Last edited by jch (2009-11-14 09:49:19)

jch wrote:

Speaking about PEX supplementing the DHT -- I see that Azureus doesn't send the "ipv6" parameter in the LTEP handshake.

We do since version 4.3.0.0. Which... has been released yesterday.

The issue is that IPv6 + Windows + Java's nonblocking IO requires Java 7 to work properly, which is still in beta. So most ipv6 capable users are either linux or osx peers and the select few early adopters.

jch wrote:

> e.g. due to perimeter widening

First of all, what you call "perimeter widening" doesn't work, at least not in Kademlia.  Don't do it, unless you are able to give a proof of your extension to Kademlia.  (Not only that it doesn't break the DHT, but also that it serves a useful purpose.)

Intuition tells me that - if properly implemented - it should work as it is no different from nodes close to the key simply failing and thus the nodes around them taking up the duty. Add that get-peers lookups can terminate early if they receive enough value lists and you would achieve your goal by putting load on other nodes than only the closest 8 ones.

jch wrote:

Second, even if it did work, you wouldn't need it.  If the torrent is very popular, and its 8 closest nodes are overloaded, you won't be able to announce yourself, but you'll still get information about other peers; that gives you 8*50=400 peers to connect to.  While not all of those will be reachable, the 200 or so that will are more than enough to propagate your contact address over PEX.  (And I know that you do implement the "p" parameter to LTEP.)

that is probably right, i'm just viewing this from the exhaustiveness angle. I.e. how to cover all peers/seeds and get mostly accurate statistics on big torrents.

Consider that many NATed peers might insert themselves in the table, storing more nodes simply means possibly more non-nated ones to pick from. Assuming 50% nated nodes you'll only have 200 reachable nodes to test left. On a really big torrent (10k seeds, 15k peers for example) that would mean that those 200 nodes would have to act as gateways via PEX into the swarm, but it's possible that they can't simply because all those incoming connections make them reach their connection limit and thus they won't accept further connections.

Attempting to store more peers in the DHT would spread the load and thus improve the time-to-join into the swarm and prevent a few peers from being hammered.

And it's not just the peers that would get hammed... the 8 DHT nodes responsible for those values might get hammered by 25k different IPs with gets and puts over the course of one DHT announce interval.

jch wrote:

Third, if Kademlia is implemented right, then the oldest among the 8 nodes have roughly the same data -- excepth when some of them have dropped some data due to overload.  In the latter case, you don't care that you're inaccurate -- the information that "the swarm has a lot of peers" is enough for you to make your queueing decisions.

"has lots of peers" is not sufficient for sorting torrents properly

jch wrote:

I'd suggest a simple extension -- get_peers replies should contain the total number of values that the replying node has for a given torrent (which can be, in general, more than the number of returned values).

Another extension could be adding a parameter to get_peers to specify the maximum number of values that the replying node should return -- the default being 50, as per BEP-5.

Well, for simplicity's sake i guess this would be better than nothing. But we still should do separate accounting for seeds and peers, thus we'll also have to include an is seed/peer flag into the announces and store those.

You are mixing up routing tables and lookup result sets here. The routing table would remain the same for all nodes, only GET_PEERS lookups would return doctored result sets and thus lead to stores on nodes that are slightly off-target.

This does not lead to any routing table instabilities. In fact, it spreads load over more nodes and thus makes it less likely to force nodes to drop out completely due to overload.

To keep your local buckets of the routing table up to date you'll be using FIND_NODES and PING requests, which would not be affected by perimeter widening. Only GET_PEERS requests would be.

I don't see any problem here.



In fact, what i call perimeter widening has been considered by the kademlia researchers before under the term "caching along the path". It's just not spelled out in detail in their paper. To quote the relevant section:

Like Chord’s clockwise circle metric, XOR is unidirectional.Fo r any given
point x and distance Δ > 0, there is exactly one point y such that d(x, y) = Δ.
Unidirectionality ensures that all lookups for the same key converge along the
same path, regardless of the originating node.Th us, caching <key,value> pairs
along the lookup path alleviates hot spots.Lik e Pastry and unlike Chord, the
XOR topology is also symmetric (d(x, y) = d(y, x) for all x and y).

So, this strategy is actually a part of the Kademlia spec.

jch wrote:

Oh my, there's not much I can answer to such a strong argument, can I?

Strong enough now? :]

jch wrote:

(Kademlia, as described in the paper, has a mechanism for making the window of time during which tables are unsynchronised smaller, but this is not in the Mainline DHT.)

One extremely useful thing in the Kademlia spec are replacement buckets, i suggest implementing them, even though they're not mentioned in the mainline spec. In our implementation they work quite well.

Okay, I think I've finally managed to get my head around this.  Apologies for being a little slow.

Assuming we use the new semantics of get_peers (i.e. we always send nodes even when values are also being sent), perimeter widening should not break anything.

I don't see why two distinct nodes should follow the same path when performing an announce, especially when they have cached nodes from a previous announce.  Hence, I'm not convinced that it buys us anything.  (This should be taken litterally -- I'm not saying they do not follow the same path, I'm only saying that I, personally, individually, speaking only for myself, do not see any argument why they should do, especially when nodes are caching the results of previous announces.)

Perimeter widening does break nodes that follow the older semantics of get_peers (values and nodes being mutually exclusive).

In conclusion, I'm not going to implement it myself, but have no objections to others implementing it.

--Juliusz

anyway, we drifted offtopic. This is supposed to be about scrapes.

To enable scrapes we have to do 2 things:
- provide a get-scrape request and response to query nodes for seed and peer counts stored under a specific key. This reuqest should be implemented with a lower concurrency than regular lookups and caching of the set of first K nodes along the lookup path that returned scrape values
- add a isSeed=1/0 flag to announces (if it is not set at all then the announcing client is assumed to be a peer)

After some tinkering i've found an averaging algorithm that performs better than ANDing in the worst case, but i'm lacking a way to calculate |intersection(A1,...,An)| for bloom filters atm and combining |intersection(A1,A2)| recursively increases errors too much for the algorithm to perform well in the average case;

So ANDing is the way to go for now, but that can be changed in the future since it's only a client-side algorithm. To estimate the number of entries of a bloom filter the following formula can be used:

int size = round(log(1.0 - bitCount/m) / (k * log(1-1.0/m)))



Anyway, apart from finding a better combining method the math stuff work fine, so we just have agree on the protocol-specific aspects.

Feedback please ^^

for documentation purposes:


The goal is to calculate the cardinality of the union of N bloom filters, since the error rate increases towards 1.0 (the |S| towards infinity) as c increases we can't just AND the filters together if the individual filters are already close to their max. capacity. Thus calculating the cardinality via the inclusion-exclusion principle would be the preferred approach, the problem is that intersecting bloom filters is not straight forward due to the probabilities associated with the bits set by each filter.

For bloom filters representing the set Sx the bit count is denoted as cx. 0 <= c <= m. The 0-bit count is m - c.
Bloom filters have the same parameters m (bits) and k (hashes).
exponentiations and logarithms are performed to the basis b = 1 - 1/m.


only applies to singular or unioned bloom filters, not to intersected ones:
|S| = log_b(1 - c/m) / k


Edit, rewritten the problem statement a bit:
_______________________________________________________

Task: intersection of N bloom filters
Basics: Bloom filters are a set representation with a false positive rate. They can map (through k hash functions) an infinite set S onto a finite set BF (represented by a bit array of m elements) where the probability of each bit being set after inserting n elements is p = 1 - (1-1/m)^k*n.
I'll use b = (1-1/m) as basis for exponentials and logarithms.

|S| =~ log_b(1.0 - |BF|/m) / k

Intersection of 2 bloom filters BF1, BF2 representing S1, S2:

As per http://www.eecs.harvard.edu/~michaelm/p … m2005b.pdf

|Si| = the actual cardinality of intersection
|BFi| = the bits set to 1 in the intersected bloom filters

p_i = (1-b^(k*|Si|)) + b^(k*|Si|) * ( 1 - b^(k*(|S1|-|Si|))) * ( 1 - b^(k*(|S2|-|Si|)))
        (term 1)            (term 2)         (tern 3)                         (term 4)

term1 : probability for each bit = 1 if we calculated the bloom filter of the intersection directly
term2 : probability of bits that should be 0
term3 * 4 : but aren't 0 because they were set by different elements in S1 and S2 and thus aren't part of the real intersection

|BFi| =~ m * p_i

replacing |S1|,|S2| with the approximation based on |BF1|,|BF2| we get

|Si| = |intersect(S1,S2)| =~ log_b( (1-|BF1|/m) * (1-|BF2|/m) / ((1-|BF1|/m) + (1-|BF2|/m) - (1 - |BFi|/m))) / k;


Intersection of n bloom filters BF1,...BFn:

|intersect(S1,...,Sn)| = ???

Sorry about the missing posts. Won't happen again in the future!