At its peak around 2003, Limewire occupied roughly one-third of desktop computers worldwide, with the Gnutella network sustaining millions of concurrent nodes. The network achieved massive scale while remaining fully decentralized and free of global file indexes or coordination servers.

Early Gnutella searches used flood routing: a query traveled to every neighboring peer, which forwarded it to their neighbors, continuing until the time-to-live (TTL) counter expired or a match was found. The elegance of this approach—fitting entirely in a programmer's head—enabled rapid ecosystem growth and diverse client implementations. However, it created a scalability trap.

With each peer typically maintaining four connections, query traffic expanded geometrically: one peer sending to four neighbors, each forwarding to three new peers (excluding the source), yielding 4, then 12, then 36, then 108 forwarded copies. Most recipients had nothing relevant to offer but still bore the full cost of receiving, parsing, inspecting, deduplicating, and forwarding the message. The network spent most bandwidth proving peers lacked the requested file. This remained tolerable for thousands of machines but became crippling at millions of simultaneous users.

By 2003, the limitations became undeniable. Gnutella clients transitioned to the Query Routing Protocol (QRP), which divided the network into two roles: leaves (ordinary peers with limited bandwidth, uptime, or connectivity) and ultrapeers (well-provisioned nodes with DSL or better, sufficient memory and file descriptors, and high availability). Clients could automatically promote themselves based on measured resources.

Under QRP, leaves periodically sent each connected ultrapeer a compact, approximate summary of searchable terms in their file library—not a literal file list, but a lossy representation answering a single question: might this peer have files matching these search terms? The answer was binary: maybe, or definitely not.

This summary, called a QRP table, was implemented using structures resembling Bloom filters. A client canonicalized shared filenames into tokens (e.g., "Ubuntu Server 2024.iso" yielded terms like "ubuntu," "server," "2024," "iso," and potentially "ubunt," "ubun" for prefix matching). Each term was hashed to a table position. Rather than storing the original text, the slot merely recorded presence as a bit. A 65,536-slot table compressed to 8 KiB—a fraction of the 365 KiB required to store 6,300 filenames in plain text.

When a query arrived at an ultrapeer, it checked the query's canonicalized terms against each connected leaf's QRP table. If all terms matched (or exceeded a fuzzy-match threshold), the query was forwarded; if any term was definitively absent, it was suppressed. Most queries therefore avoided traveling to leaves where no match could exist, recovering substantial bandwidth.

QRP tables were transmitted via two message types. A RESET message instructed a peer to discard its current table and initialize a new one of a specified size. PATCH messages then updated the table incrementally, representing unchanged entries as no-op values that compressed well over the wire. This allowed leaves to keep ultrapeers synchronized as shared file collections changed without expensive full retransmits.

The architecture accepted false positives (querying a leaf that lacked the file, wasting some bandwidth) to avoid false negatives (suppressing a query that would have found a result). QRP table construction was therefore conservative, optimizing for recall over precision.

QRP tables primarily routed leaf-to-ultrapeer queries. Some ultrapeers supported "last-hop QRP," merging tables from directly connected leaves and propagating the combined summary to neighboring ultrapeers. This optimization allowed single-hop queries to be filtered at the peer's boundary when no further forwarding was possible. Multi-hop queries still relied on ultrapeers' best judgment, since neighboring ultrapeers might forward farther into the backbone.

Gnutella2 adopted QRP, and the mechanism remains embedded in surviving Gnutella clients today. The protocol balanced simplicity with efficiency: it required no distributed hash table, no global index, and no central authority, yet scaled from thousands to millions of nodes by routing queries selectively to peers with a statistical chance of answering them.