NOTE: Welcome to my public notebook! There are many blogs here, but this is truly just a note. It is an AI re-write of the Gnutella QRP spec formatted for easier reading. It is not precise enough to be used in implementing the protocol, but it is a good introductory text for curious readers. I used this as a refresher when I built my own client a while back.

If you want content written by a human see my Gnutella Explanation

Query Routing for the Gnutella Network

May 16, 2002

Gnutella originally searched for files by broadcasting queries across the network. That means a user’s search request was sent to many connected hosts, even when most of those hosts had no useful result. This wasted a large amount of bandwidth.

Query routing is a way to avoid many of those wasteful broadcasts. Each host builds a small routing table that describes what kinds of files can be reached through each connection. Instead of sending every query everywhere, a host only forwards a query along connections that are likely to lead to a match.

The basic idea is simple. Hosts do not share their full file lists with every neighbor. Instead, they take the keywords from their shared files, hash those keywords into numbers, and store those numbers in a compact table. These tables are exchanged between neighbors. Compression keeps the tables small.

This can greatly reduce the bandwidth needed for search. But it must be used carefully. Poorly designed query routing can harm the network by sending bad routing information, creating too many false positives, or making parts of the network hard to reach.

Later Gnutella clients introduced ultrapeers. Ultrapeers are stronger hosts that handle much of the network traffic for weaker leaf nodes. In that model, leaf nodes send query routing information to their ultrapeers, but ultrapeers do not blindly propagate those tables onward. Client authors should focus on that practical model: leaf nodes give route table updates to ultrapeers, and ultrapeers use those tables to decide which leaves should receive which queries.

The Problem with Broadcast Search

In classic Gnutella, searching is based on broadcasting. If a user searches for a file, the query is sent to neighboring hosts. Those hosts send it to their neighbors, and so on, until the query’s time-to-live reaches zero.

This is simple, but it does not scale well. A single search can touch a large part of the network. Most of the hosts that receive the query cannot answer it. They spend bandwidth and processing time just to say nothing.

This does not necessarily mean the whole Gnutella network has a strict size limit. But it does mean that each search has a cost, and that cost grows quickly as the query spreads.

Reducing query traffic helps the network in two ways. First, it makes search more scalable. Second, it leaves more bandwidth available for the things users actually want: uploading and downloading files.

Other systems have tried to avoid broadcasts. Freenet, for example, uses a clever routing scheme based on names. But that approach has limits. It works best when you know the exact file name. A search for one spelling or file extension may miss a similar file with a different name. It also tends to return one result, which is not what users expect from a broad search.

A better approach is keyword routing. Instead of routing by exact file name, hosts route by the words that appear in shared files. That way, a search for “graphics book” can be sent toward hosts that have files related to both “graphics” and “book.”

Prinkey’s Keyword Routing Idea

Prinkey proposed a keyword-based routing scheme for peer-to-peer networks. The idea is that hosts periodically exchange keyword route tables with their neighbors. Each table tells a host which keywords are reachable through a particular connection.

Imagine a small tree-shaped network. Host A is connected to host B. Host B is connected to hosts C and D. Host B shares a file called “bad joke.” Host C shares “good book.” Host D shares “good joke.”

With ordinary Gnutella search, if host A searches for “bad joke,” the query may be sent to B, C, and D. But only B can answer. C and D receive useless traffic.

With query routing, each host tells its parent what keywords are reachable below it. Host C advertises “good” and “book.” Host D advertises “good” and “joke.” Host B combines that information with its own shared keywords, so host A learns that the connection to B can lead to “bad,” “good,” “book,” and “joke.”

When A searches for “bad joke,” it sends the query to B because B’s route table contains both words. B can then decide whether to answer directly or forward the query further. Since C and D do not contain the word “bad,” B does not need to forward the query to them.

Queries are treated as an AND of keywords. A search for “good joke” means the file should match both “good” and “joke,” not just one of them.

This scheme avoids false negatives. If a reachable host can answer a query, the query will be sent in that direction. But it can still have false positives. For example, a route table might contain both “joke” and “book” because one host has “good joke” and another has “good book.” A search for “joke book” might be forwarded even though no single file matches both words. This is not perfect, but false positives are acceptable if they are not too common.

To save space, keywords are not stored as full strings. Each keyword is hashed into a number. That number selects a bit in a bitmap. If the keyword “good” hashes to position 2, then bit 2 is set. If “book” hashes to position 5, then bit 5 is set.

The table becomes a compact bitmap instead of a long list of strings. To combine two tables, a host performs a logical OR on the bitmaps. This is similar to a Bloom filter. It is small and fast, but it can have hash collisions. If two words hash to the same bit, the table may claim a word is reachable even when it is not. That creates a false positive, not a false negative, so the network still works.

Prinkey’s scheme has two major problems for Gnutella. First, it assumes a tree-shaped network with a clear root. Gnutella is not a clean tree. It is a loose network with many cycles and no central root. Second, if only the root can start searches efficiently, hosts near the top of the tree carry too much traffic.

Gnutella needs a version of keyword routing that works without a tree.

Routing Without a Tree

In a non-tree network, a simple idea would be to let every host send its route table to every neighbor. Each host would combine its own files with the tables it receives from neighbors. Over time, information about files would spread across the network.

That almost works, but it has a serious problem. Routing information can keep spreading even after the original host leaves the network. Old information would remain in tables and cause many false positives. The network would waste bandwidth forwarding queries toward files that are no longer there.

To solve this, route tables need distance information. Instead of saying only, “this keyword exists somewhere through this connection,” a table says, “this keyword is reachable through this connection within this many hops.”

So the route table is not just an array of bits. It is an array of small numbers. Each number is the minimum number of hops to a matching file. If no matching file is known, the entry is set to infinity.

For example, if a table entry says the keyword is reachable in one hop, that means a direct neighbor has it. If it says two hops, the file is behind a neighbor’s neighbor. If it says infinity, no matching file is known through that connection.

When a query has a time-to-live value, the host checks whether the route table says the matching keywords are reachable within that remaining distance. If not, the query is not forwarded on that connection.

Hosts update these tables using a dynamic process. Each host receives route tables from its neighbors. Then it builds new outgoing tables for each connection. When sending a table to one neighbor, the host uses information from its other neighbors and from its own files. It does not simply echo a neighbor’s own information back to it.

This makes the route table describe what can be reached through a connection, not what came from that same connection.

At first, this looks more expensive than a bitmap. A bitmap needs one bit per entry. A distance table needs several bits per entry, because each entry stores a small number. If the maximum useful distance is around ten hops, each entry may need four bits.

But these tables compress well. Most entries are infinity. Many other entries have predictable values. Standard compression algorithms can shrink the tables substantially. Because ordinary compression works well, the protocol does not need many custom table formats.

When to Send Updates

Route tables should be updated when useful information changes. A host should send an update when it adds or removes shared files, when a connection is added or removed, or when routing information from a neighbor changes.

But updates should not be sent too often. If every small change creates an immediate network-wide update, the update traffic could become expensive.

A practical rule is to wait until a connection has been stable for a few minutes before using it for route propagation. Many Gnutella connections are short-lived. Ignoring very new connections avoids wasting effort on peers that disappear quickly.

Another rule is to limit update frequency. A host should not send more than one route table update per connection within a chosen time window. If several changes happen during that window, they should be combined into one update.

If a new table is very similar to the last table sent, the host can send a patch instead of the whole table. A patch contains the difference between the old table and the new one. If very little changed, the patch compresses well and saves bandwidth.

Route Table Update Messages

Gnutella can support this scheme by adding one extensible message type called ROUTE_TABLE_UPDATE. The proposed function code is 0x30.

A route table update message has a payload. The first byte of the payload says what kind of update it is. Two kinds are defined: RESET and PATCH.

A RESET message tells the receiver to throw away the previous table for that connection and create a new empty table. The table has a specific length. The length must be a power of two, because the hash function depends on that. Each entry starts as infinity.

Infinity is usually one more than the maximum useful time-to-live. For example, if the maximum useful distance is ten hops, infinity might be eleven.

After a RESET, the receiver should temporarily treat the connection as unrouted until the table has been filled by patch messages. In practice, this means it may forward all queries along that connection for a short time after startup or reset.

A PATCH message changes the current table. The sender compares the new table to the last table it sent, subtracts the old values from the new values, and produces a list of signed numbers. That list is compressed and split into one or more PATCH messages.

Each PATCH message has a sequence number and a sequence size. These fields let the receiver reassemble the full patch. Messages in a patch sequence must arrive in order. If a message is missing or the sequence is wrong, the receiver should close the connection. Because patches are incremental, there is no safe way to recover from a missing patch.

Patch messages are split into chunks so that a single huge update does not block normal Gnutella traffic. A large update can be interleaved with ordinary queries and responses. A maximum message size around one kilobyte is a reasonable choice.

The protocol defines two compression options. One means no compression. The other means ZLIB compression. Every implementation should support both. More compression methods could be added later, but clients would need some separate way to discover support for them.

When a patch is decompressed, it becomes a sequence of signed numbers. Each entry is stored using either four bits or eight bits. Four-bit entries are often smaller and can reduce compressed table size, but eight-bit entries are also supported. The receiver applies the patch by adding these signed values to the current route table.

Updates do not have to be atomic. A receiver does not need to wait for the entire patch sequence before it begins using or propagating the updated table. This reduces buffering and may allow routing information to spread more quickly.

Compatibility with Older Clients

Older Gnutella clients do not understand query routing. They do not send route tables. This creates a problem.

Imagine a path from host A to host B, then to old client X, then to host C. Since X does not propagate route tables, A may not learn that C is reachable. Queries from A may rarely reach C, even though C might still be able to reach A through ordinary broadcast behavior.

One option is to pretend that the old client has every possible keyword. That would avoid hiding old clients, but it would also undo the benefits of routing. Too many queries would be forwarded through old clients.

A better approach is for newer clients to prefer connections to other newer clients. This can be done through host discovery services, versioned client identifiers, or improved handshake mechanisms. Whether a user wants to connect to older clients should be configurable. Connecting to them may improve reach, but it costs more bandwidth.

Hashing Keywords

A query string contains one or more keywords. Keywords are separated by spaces. For example, “graphics book” contains two keywords: “graphics” and “book.”

Each keyword is mapped into a route table entry with a hash function. The hash function needs three properties.

It must handle keywords of any length. It must be easy and fast to implement on many platforms. And it must allow clients with different table sizes to convert routing information between those sizes.

The third property is important. If one client has a table with one size and another client has a table with a different size, they still need to interoperate. That means a hash value for a smaller table must correspond cleanly to a range of values in a larger table.

The recommended hash process starts by turning the keyword into a 32-bit number. The keyword is treated as a sequence of four-byte little-endian chunks. These chunks are XORed together. If the keyword length is not a multiple of four, it is padded with zero bytes.

Then that 32-bit number is mapped into the table range using multiplication. The multiplier is a 32-bit integer based on the golden ratio, a value commonly used for hashing. Since table sizes are powers of two, the final hash can be computed with integer operations in a platform-independent way.

The hash operates on bytes, not abstract characters. That means text encoding matters. Characters should be encoded in a consistent, canonical form before hashing.

Current implementations lowercase English keywords before adding them to route tables and before checking queries. This is easy for English, but international text is harder. Different languages have different rules for case and canonical forms. Ideally, clients should canonicalize keywords in a language-aware way before hashing or querying.

Scaling Route Tables

Because table sizes can differ, clients need a way to scale one route table into another.

The rule is to treat each table like a number line. When converting from one size to another, each entry in the new table receives the minimum distance from the overlapping entries in the old table.

Taking the minimum is important. If any overlapping part says a keyword is close, the scaled table should preserve that closer distance.

This lets a client convert between table sizes while keeping the basic meaning of the routing information.

How Well Does It Compress?

The main question is whether the bandwidth saved by reducing queries is greater than the bandwidth spent exchanging route tables.

The size of a route table depends on the number of distinct keywords within the search horizon and how well the table compresses. The number of keywords depends on how many users are nearby and how many different files they share.

Early evidence suggests the tables compress well. In one experiment, query replies were recorded for several hours and used to build routing tables. A route table with 65,536 entries, 12,000 keywords, and an infinity value of seven could be sent in a little over twelve kilobytes using four-bit entries. With eight-bit entries, it took about thirteen kilobytes.

That is small enough to be promising.

Search Radius and Network Shape

Query routing does not remove the idea of a search radius. A query still has a maximum number of hops. If the time-to-live is too low, some hosts will not be searched.

But routing changes the tradeoff. Since fewer useless queries are sent, each host may be able to keep more connections open for the same bandwidth cost. More connections can shrink the effective diameter of the network. Many hosts may become reachable in fewer hops.

Gnutella may already behave like a small-world network, where most hosts are only a short number of hops apart. If so, query routing could make search much more efficient without needing extremely large time-to-live values.

Patch Message Examples

The appendix gives several examples of how route table changes can be encoded.

The examples use a tiny table with only eight entries, so they are not realistic. They are only meant to show the mechanics.

In the example, a leaf node first shares a file named “test.” Then it adds a file named “qrp.” Then it stops sharing “test.” Each change is represented as a route table patch.

The same information can be encoded in several ways. The entries can use eight bits or four bits. The patch can be sent as one message or split across multiple messages. It can be compressed or left uncompressed.

For very small tables, compression and splitting are wasteful. For real tables, they matter. Large tables benefit from compression, and splitting prevents one large update from blocking normal traffic.

The examples also show how negative changes are represented. If a keyword disappears from the table, the patch adds a positive value that moves the entry back toward infinity. If a keyword appears, the patch adds a negative value that moves the entry closer to one hop away.

Hash Function Implementation

The appendix also includes a Java implementation of the official query-routing hash function.

The implementation lowercases the input, turns the keyword into a 32-bit value by XORing four-byte chunks, multiplies that value by the golden-ratio-based constant, and returns the requested number of hash bits.

It also includes tests that verify the function returns the same values for known strings. The tests confirm that different capitalizations of the same keyword produce the same hash.

The key point is not Java itself. The key point is that all clients need to compute the same hash values. If different clients hash the same keyword differently, routing tables will not mean the same thing across the network.

Final Thoughts

Query routing can reduce Gnutella’s bandwidth use by a very large amount. Instead of sending every query everywhere, hosts can send queries only where useful answers are likely.

The approach depends on compact route tables, stable update rules, careful compression, and consistent hashing. It also depends on practical deployment choices, especially around ultrapeers and older clients.

The basic promise is strong: fewer broadcasts, less wasted traffic, and more scalable search.

But careless deployment can cause harm. Route tables can become stale. False positives can waste bandwidth. Bad propagation rules can flood the network with useless information. Query routing should be studied carefully, tested in simulations, and deployed conservatively.

Used well, query routing can make Gnutella much more scalable while preserving the broad keyword search behavior that users expect.