QHT

From Gnutella2
Jump to navigation Jump to search

Root Packets
CRAWLA - CRAWLR
HAW - LNI
KHL - KHLA - KHLR
PI - PO - PUSH
QKA - QKR
Q2 - QA - QH2 - QHT
UPROC - UPROD

/QHT - Query Hash Table

The query hash table update packet supplies an update to the query hash table for the sending node. It supports two operations: clear existing table, and patch existing table with new data.

Sending

The /QHT packet should be sent when the local or aggregate query hash table has changed.

Receiving

Upon receiving a /QHT packet, the local hub should patch the query hash table for the connection on which the packet was received. If the connection is to a leaf node, the hub should update its aggregate table and queue a propagation of that table to neighbouring hubs in the cluster.

Payload

The payload is of the same format as Gnutella1's "query routing protocol" message: The first byte is a command byte, 0x00 indicates a reset command, while 0x01 indicates a patch command.

Reset


typedef struct
{
BYTE command; // = 0 (reset)
LONG table_size_in_entries; // = 2^(size_in_bits)
BYTE infinity; // = 1
} QHT_RESET;

A reset packet establishes a new table and clears it (replacing any existing table). In Gnutella2 the value of infinity must always be 1. Note that the table size is measured in entries rather than bits, so it is equal to 2N where N is the number of bits.

Patch


typedef struct
{
BYTE command; // = 1 (patch)
BYTE fragment_no; // = number of this patch fragment
BYTE fragment_count; // = number of patch fragments
BYTE compression; // = 0 for none, = 1 for deflate
BYTE bits; // = 1 for Gnutella2
(data)
} QHT_PATCH;

Patches may be fragmented into more than one packet if necessary, in which case the fragment number and count fields are used to reassemble the patch. Note that fragments must be sent in correct order.

Patches may be compressed - in this case the whole patch is compressed, rather than compressing fragments individually. One compression type is defined: deflate compression.

Gnutella2 always uses tables with 1 bit per entry, so the bit count must be 1.

The patch data in uncompressed form is of (2N)/8 bytes length, where N is the table bit size. This is exactly the same size as the table which is being patched. To apply the patch, simply XOR the existing table with the patch data. In other words, whenever there is a 1 bit, the bit in the existing table is toggled.