Direct Connect: Just These Guys, Ya Know?

Bloom filters

Currently, to ensure that a search query reaches all clients that might have files in their share matching it, DC hubs must broadcast that search query to all connected clients. This works, but scales poorly bandwidthwise with the number of distinct clients in a hub. DC++ 0.704 adds support for Bloom filters to ameliorate this bandwidth issue.

A Bloom filter, as used by a DC client or hub, concisely summarizes the contents of a share by constructing a bit vector which allows for probabalistic queries as to the presence of a file with a specified hash in that share. A motivating advantage of such a construction that whereas even filelists which contain only hashes will grow linearly with the number of files in the share. Further, such a fully accurate representation should not be compressible, because cryptographic hashes aim for each output bit to be independently 50% likely enabled and thus maximize apparent entropy. Instead, Bloom filters sacrifice losslessness in favour of an output that has a small size which need not grow with that of the share.

However, to remain useful in this filesharing context, such lossiness must remain limited. In particular, a Bloom filter produces false positives but not false negatives: it can state that an object exists when it does not, but it will never state conversely that an object does not exist if it does. A hub, given a Bloom filter representation of a share can thus safely refrain from sending a hash search query to a connected client the Bloom filter of the share of which has no record of a hash. This can save considerable bandwidth and allow a combination of more clients within the same bandwidth or a similar number of clients using less bandwidth.

A Bloom filter is determined by the hash keys in use and the table size. The smaller the ratio between the number of objects in the table and size of the table, the lower the false positive rate. Further, an optimal table does not utilize just one key but multiple keys simultaneously, such that the presence of an object in the table implies that the bits corresponding to each keys as applied to the input object are all enabled. Thus, when inserting an object for which hash functions used as keys map to bits 58, 1093, and 9865, then those bits are all enabled. Then to check whether that object might exist in the table, then one checks whether any one of bits 58, 1093, and 9865 are enabled. If all of them are, then it is possible that the object is in the table. However, if any of them are not, then the object is not in the table.

Bloom filters, then, allow for a scalable, efficiently constructed, efficiently queried, and efficiently communicated summary of the contents of a share which allows for hubs to spend less bandwidth wastefully broadcasting search queries.

Don’t forget that you can make topic suggestions for blog posts in our “Blog Topic Suggestion Box!”

Context and message types in ADC

Two things are similar, but not the same in ADC. It is the context and type of messages.

The message types are stated in section 3.3. in the spec, and “specifies how messages should be routed and thus which additional fields can be found in the message header”.

Context, stated in section 5., are an abstraction of how messages should be sent.

Usually, action are stated to be used in context rather than by their message type to allow the client and hub decide for themselves what type should be used. (This can also be future proof.)

For example, the action MSG allow contexts F and T, which are “F – From hub (hub-client TCP)” and “T – To hub (hub-client TCP)”. What the F type mean is that a MSG message will originate from a hub and the T type will originate from a client (“and go to the hub”). That is, a client may want to send a message as a broadcast message to all users in the hub, or send them a direct (or echo) message. So instead of having the action MSG allow “B, D, E type for clients”, the context (abstraction) T is used instead.

The wording “hub-client TCP” does not mean the message always originates from the hub. It’s simply a choice of words to denote that it’s a hub and client TCP session, not who initiated the session or message.

Don’t forget that you can make topic suggestions for blog posts in our “Blog Topic Suggestion Box!”