Overview
Gnutella’s original search system had a serious weakness. It used flooding.
When a node searched for a file, it sent the query to its neighbors. Those neighbors passed it to their neighbors, and the process continued until the query’s time-to-live value reached zero.
This worked, but it gave the searching node very little control.
A search for a common file could create far more traffic than necessary. Thousands of nodes might receive the query, and the network might return hundreds or thousands of results that the user did not need.
A search for a rare file had the opposite problem. It might reach too few useful nodes and return nothing.
GUESS changes this model. The name stands for Gnutella UDP Extension for Scalable Searches.
Instead of broadcasting one query across a large part of the network, a client contacts Ultrapeers one at a time. Each query has a time-to-live value of one. The client stops as soon as it has enough results or reaches a reasonable search limit.
This process is sometimes called Ultrapeer crawling.
GUESS gives the client direct control over how far a search goes. Popular files can be found with only a few requests. Rare files can be searched for more deeply. The network no longer has to treat every search as if it were equally difficult.
Because these requests are sent to many short-lived peers, GUESS normally uses UDP instead of opening a new TCP connection for every request.
The result is a search system that uses less bandwidth, memory, and processing power while still improving the chance of finding rare files.
Why Flooding Does Not Scale
The original search model has two separate problems.
First, the number of nodes reached by a query is unpredictable.
Second, the number of results returned by those nodes is also unpredictable.
The Number of Queried Nodes Is Uncontrolled
Gnutella is a changing network. Nodes connect and disconnect constantly. Some parts of the network are densely connected, while others are sparse.
The flooding model responds to this uncertainty by sending each query as widely as it can.
Traditional Gnutella queries often used a time-to-live value of seven. Every node forwarded the query to all eligible neighbors. The number of reached nodes depended on the shape of the network at that moment.
This created uneven results.
A common search in a highly connected part of the network could generate a huge amount of traffic.
A rare search in a weakly connected part of the network might not travel far enough to find anything.
The searching client had no useful way to adjust the search while it was running.
The Number of Results Is Also Uncontrolled
Even if every query reached the same number of nodes, the number of returned results would still vary greatly.
Some search terms match many files. A search for a broad term such as “text” may match a large part of a user’s shared library. A search for one exact document may match only a single file on the entire network.
Nodes also share different amounts of data. One node may share a handful of files. Another may share thousands.
This means that the result count depends on both the number of nodes reached and the particular nodes that receive the query.
Users often receive far too many results for popular content and too few results for rare content.
GUESS addresses this by allowing the client to expand the search gradually.
The GUESS Search Model
A GUESS client sends a query to one Ultrapeer at a time.
Each outgoing query uses a time-to-live value of one. The receiving Ultrapeer checks its own data and forwards the query to its connected leaves. It does not flood the query into the wider Ultrapeer network.
The client then waits briefly for results.
If it has enough results, it stops.
If it does not have enough results, it sends the same search to another Ultrapeer.
This continues until either the client has enough useful results or it reaches its search limit.
This design does not make result counts perfectly predictable. Ultrapeers have different numbers of leaves, and those leaves share different files. Some searches will still return more matches than others.
However, it gives the client far more control than flooding does.
Client and Server Roles
In GUESS, the client is the node that begins the search.
The client may be an Ultrapeer searching for itself, an Ultrapeer searching for one of its leaves, or a leaf that can perform its own UDP searches.
The server is the Ultrapeer that receives the query.
A complete GUESS implementation must support both roles. A developer may begin testing with only the server side, but a client that sends GUESS searches must also be able to receive them.
How a Client Performs a Search
The client keeps a list of Ultrapeers known to support GUESS.
It queries those Ultrapeers one by one.
If the client already has a TCP connection to an Ultrapeer, it should use that connection first. It may send a time-to-live-one query over the existing connection even when the remote Ultrapeer does not support GUESS over UDP.
For all other GUESS servers, the client sends the query over UDP.
The client must pause between requests. Results take time to travel back from the Ultrapeer and its leaves. If the client sends requests too quickly, it may contact many more Ultrapeers than necessary before the first results arrive.
A simple client might begin with a delay of about one and a half seconds. After each request, it could reduce that delay by twenty percent until it reaches a safe minimum.
This is only an example. Developers should test different strategies.
The goal is always the same: send as few queries as possible without making the search feel slow or making rare files too difficult to find.
A client must also decide what counts as enough results.
One implementation might stop after receiving one hundred results or after contacting one thousand Ultrapeers.
A more adaptive client could lower its target as the search continues. For example, if it has contacted five hundred Ultrapeers and found nothing, it may decide that even one useful result is enough.
Search quality should not be judged only by the raw number of results. Finding the requested file matters more than returning a large list.
An aggressive client may appear faster in isolation, but it increases the load on every Ultrapeer. If many clients behave that way, the entire network becomes slower, including the aggressive client itself.
Absolute Client Limits
GUESS places hard limits on client behavior.
A single search must not contact more than ten thousand Ultrapeers.
A client must not seek more than two hundred results.
For the first twenty Ultrapeers, the client must wait at least two hundred milliseconds between requests. This slow beginning allows the client to estimate how common the requested file is.
After that, the client must never contact more than one Ultrapeer every twenty milliseconds.
The client must not query the same Ultrapeer more than once during the same search.
These are maximum limits, not recommended defaults. Normal clients should use much smaller values.
Gnutella depends on participants behaving reasonably. GUESS reduces network traffic only when clients use conservative search strategies.
Searches Proxied for Leaves
An Ultrapeer may perform a GUESS search for one of its leaves.
If the leaf disconnects, the Ultrapeer should stop that leaf’s search. Continuing would waste resources because there is no longer a client waiting for the results.
Leaves That Can Receive UDP
A leaf should perform its own GUESS searches when it can receive UDP packets.
A leaf does not always need a publicly open UDP port. Many firewalls and network address translators allow an incoming UDP packet when the local machine first sent a packet to the same remote address and port.
A leaf can test this when it joins the network.
It sends a UDP ping to a GUESS Ultrapeer. If it receives the UDP pong, it knows that replies can reach it. It should then perform its own GUESS searches instead of asking an Ultrapeer to act as a proxy.
Server Behavior
A GUESS server is always an Ultrapeer.
The Ultrapeer must listen for UDP traffic. It must use the same port number for both its Gnutella TCP traffic and its Gnutella UDP traffic.
When the server receives a query over UDP, it sends the response over UDP from that same port. It must not use a temporary outgoing port.
The server sends query results back toward the node that sent the request.
It must also send a pong as an acknowledgement.
Apart from the transport, the server handles UDP messages much like traditional Gnutella messages received over TCP.
A GUESS Ultrapeer must accept the traditional Gnutella message types on its UDP port.
It must also forward a time-to-live-one UDP query to its leaves. Without this rule, the client would need to use a time-to-live value of two. That would reduce the client’s control and reintroduce some of the problems caused by cycles in the Ultrapeer network.
Query Acknowledgement Pongs
Every GUESS query produces a pong acknowledgement.
The pong has two jobs.
First, it confirms that the server is alive and can receive future requests.
A missing pong does not prove that the server is offline because UDP packets can be lost. A received pong does prove that the server was reachable at that moment.
Second, the pong helps the client discover another GUESS Ultrapeer.
When possible, the acknowledgement should describe a different GUESS Ultrapeer, not the server that received the query. The returned host may be one that the server currently knows through a TCP connection.
If the server does not know another suitable GUESS Ultrapeer, it returns information about itself.
This allows the client to continue searching without sending separate discovery traffic.
Acknowledgement pongs also give a server limited control over incoming load.
An overloaded Ultrapeer may stop sending acknowledgement pongs. Clients will gradually remove it from their active search lists.
A server that does this must treat vendors fairly. It must not continue answering favored clients while silently refusing others, unless a particular vendor is clearly violating the GUESS rules.
The acknowledgement pong must use the same globally unique message identifier as the incoming query.
It must also advertise GUESS support through the appropriate extension.
Discovering GUESS Ultrapeers
A client needs a large and frequently refreshed list of GUESS Ultrapeers.
This is one of the harder parts of the design. It is not enough to discover one or two servers. A deep search for a rare file may need to contact many of them.
GUESS uses several discovery methods.
Traditional Broadcast Pings
A node may use a traditional Gnutella broadcast ping and inspect the returned pongs.
Pongs that contain the GUESS support marker can be added to the node’s cache.
This method works, but it is the least desirable option.
Broadcast pings can consume a great deal of bandwidth when pong caching is not working well. Repeating the process may also return many hosts that are already known.
Acknowledgement Pongs
The preferred discovery method is built into the search itself.
Each server returns an acknowledgement pong that can describe another GUESS Ultrapeer.
This adds no separate discovery traffic. The client learns about new servers while it searches.
UDP Discovery Pings
A node may also send a time-to-live-one UDP ping directly to a known GUESS server.
The receiver returns information about several other GUESS Ultrapeers. A reasonable reply contains roughly five to twenty hosts.
Older gtk-gnutella clients treated a normal UDP ping as a simple test of whether one host was alive. To avoid changing that meaning, GUESS version zero point two requires a discovery ping to include an empty GUE extension.
The returned hosts are packed into an IPP extension instead of being sent as many separate pong messages.
Connection Headers
A node that can send GUESS queries must advertise that fact during the Gnutella connection handshake.
It does this with the X-Guess connection header followed by the supported version number.
This allows leaves to prefer Ultrapeers that support GUESS. It also allows GUESS Ultrapeers to prefer connections to other GUESS Ultrapeers.
Why GUESS Uses UDP
Traditional Gnutella messages were normally sent over TCP.
GUESS could have opened a temporary TCP connection to every Ultrapeer, but that would be expensive.
Creating and closing many TCP connections consumes bandwidth, memory, and processing time. Older versions of Windows also imposed low limits on the number of simultaneous TCP connections.
TCP provides ordered and reliable delivery. That reliability is useful for many applications, but it is not essential for GUESS searches.
If one query packet is lost, the client can continue to another Ultrapeer.
If one result packet is lost, the client may still receive results from many other hosts.
Gnutella peers also leave the network frequently. Perfect transport reliability cannot make an offline peer respond.
UDP avoids connection setup, reduces delay, and fits a search that sends many small requests to a changing set of hosts.
For that reason, a client must use UDP when it does not already have a TCP connection to the target Ultrapeer.
UDP Port Use
A GUESS Ultrapeer must listen on a UDP port.
Port 6346 is recommended because it is the traditional Gnutella port.
A node may use another port when 6346 is already in use.
Whatever port it selects, the node must use the same number for both TCP and UDP. Gnutella messages and headers already carry the TCP port in many places. Reusing the same number allows that existing information to describe both transports.
Packet Size and Fragmentation
UDP sends one datagram at a time.
If a datagram is larger than the maximum packet size supported by part of the network path, the internet layer may split it into fragments.
The receiving machine normally reassembles those fragments automatically.
The danger is that losing one fragment causes the entire datagram to be lost.
GUESS implementations should therefore keep UDP messages small.
A packet size of about five hundred and twelve bytes is very conservative.
Messages below fifteen hundred bytes will avoid fragmentation on most Ethernet networks, but protocol headers also consume part of that space.
Gnutella message data should normally stay well below fifteen hundred bytes.
A target of about one kilobyte is reasonable. Fourteen hundred bytes should be treated as a hard upper limit.
Query responses may contain too many results to fit comfortably in one datagram.
When that happens, the server should divide the response into several smaller query-hit messages.
This adds a small amount of header overhead, but it avoids an all-or-nothing failure. If one packet is lost, the client can still receive the other groups of results.
Congestion
UDP does not provide built-in congestion control.
GUESS is designed to prevent congestion by reducing the total amount of search traffic. In particular, it avoids the large floods of query hits caused by searches for popular content.
If congestion still becomes a problem, clients may need to add their own flow-control rules.
A server already has one basic control. If its UDP receive buffer is overloaded or packets are being dropped, it can stop returning acknowledgement pongs. Clients will then stop selecting it for future searches.
More advanced congestion control is outside the main GUESS design.
Advertising GUESS Support in Pongs
A GUESS Ultrapeer must advertise support through a GUE extension inside its pong messages.
The extension contains one byte for the protocol version.
The high half of the byte contains the major version number. The low half contains the minor version number.
For GUESS zero point two, the major value is zero and the minor value is two.
This format allows major and minor values from zero through fifteen, for a total of two hundred and fifty-six possible version combinations.
Query-Hit Delivery
The original GUESS design routed a leaf’s query hits through its Ultrapeer.
This allowed the Ultrapeer to place the leaf in its push-routing tables. If the leaf was behind a firewall, the Ultrapeer could later help route a push request.
It also avoided placing the searching node’s address directly inside the query. Including an arbitrary reply address could allow an attacker to send traffic toward an unrelated victim.
By 2011, Gnutella had widely adopted out-of-band query-hit delivery and Push Proxy support.
With out-of-band delivery, the initial response does not contain all matching files. It first tells the searching client that results are available. The client can then claim them.
A GUESS client may request this form of delivery.
Before forwarding such a query to its leaves, the Ultrapeer must verify that the UDP source of the request matches the requested out-of-band destination.
This does not eliminate every possible denial-of-service attack, but it prevents the new mechanism from making the old risk worse.
Push Proxy support also makes firewalled leaves easier to handle.
GUESS version zero point two advertises these changes. It remains compatible with version zero point one. A zero point two request sent to a zero point one server can still be processed as a normal GUESS request.
A server may choose not to return full query hits directly when out-of-band delivery is available. This encourages clients to use the less congested method.
Backward Compatibility
GUESS can coexist with older Gnutella clients.
A leaf without GUESS support can still connect to a GUESS Ultrapeer.
A GUESS-capable leaf can still connect to an Ultrapeer that does not support GUESS.
During early deployment, a client may use a temporary hybrid search. It could perform a conservative GUESS search and also send a traditional broadcast query with a smaller time-to-live value, such as four.
This should only be a transition strategy.
The full reduction in network traffic appears only when traditional broadcast searches are replaced by GUESS.
Developers may also begin by implementing only the server side. This makes it possible to test GUESS searches before many clients depend on the new system.
GUESS nodes should continue to handle incoming TCP messages as they did before.
Security
UDP protocols often create a risk of traffic-reflection attacks.
An attacker may send a packet with a forged source address. The server then sends a larger response to the victim whose address was forged.
The original GUESS design reduces this risk by sending responses back to the actual source of the incoming datagram. The query does not contain a separate address telling the server where to send the result.
Later out-of-band delivery requires an additional check. The server must confirm that the requested destination matches the UDP origin before forwarding the query.
Query keys, described later, add another layer of protection by proving that the requester recently received a packet at its claimed address.
Network Cycles Matter Less
Flooded networks must carefully handle cycles.
A cycle allows the same message to travel through different paths and return to nodes that have already seen it. This wastes bandwidth, memory, and processing time.
GUESS queries do not travel through the Ultrapeer network. Each query reaches one Ultrapeer and its leaves.
As a result, cycles between Ultrapeers no longer create large numbers of duplicate search messages.
A duplicate may still occur when one leaf is connected to several Ultrapeers and the client later sends the same query to more than one of them.
Push Downloads Become More Reliable
Traditional push requests could fail because the file owner might be many Gnutella hops away.
A push request had to pass through each intermediate node. If any one of those nodes disconnected, the request could fail.
With GUESS, the node that reports the file is much closer to the searching node.
Depending on whether each side is a leaf or an Ultrapeer, the path is usually only one to three Gnutella hops.
This greatly improves the chance that a push request will reach the file owner.
GUESS does not, by itself, allow two fully firewalled hosts to establish a download. Other proxy and firewall-traversal systems are still needed for that case.
Stopping a Search Actually Stops It
In a flooding system, pressing a stop button does not recall queries that are already moving through the network.
With GUESS, the client controls each new request.
When the user stops the search, the client can simply stop contacting more Ultrapeers.
This immediately prevents additional network traffic.
The exception is a search being proxied by another Ultrapeer. In that case, the leaf must signal the proxy, and the proxy must stop the remaining work.
Query Keys
The 2011 GUESS additions require a query key before a client may send a UDP query to a server.
To obtain one, the client sends a UDP ping containing the QK extension.
The server calculates a key for the requesting host and returns it in a pong with its own QK extension.
The server learns the requester’s address from the incoming UDP datagram. It does not trust an address supplied inside the message.
The client then includes that query key in its later UDP query.
When the server receives the query, it checks the key before processing the search.
A query key is easy for the server to recalculate, so the server does not need to keep a separate stored record for every client.
This mechanism makes address spoofing and traffic reflection more difficult.
Protecting the Pong Cache
A GUESS client depends on cached addresses of other GUESS servers.
An attacker could try to poison that cache by filling it with dead, false, or attacker-controlled addresses.
The 2011 gtk-gnutella design uses two pong caches.
The normal operating cache is filled during searches. It uses a most-recently-used replacement policy.
A larger introduction cache is filled when servers introduce themselves. It uses a least-recently-used replacement policy.
When possible, returned hosts are selected from the operating cache.
gtk-gnutella also uses an address-spreading method. When one server reports another host, that host can be removed from the reporting server’s local cache.
This helps distribute host addresses more evenly across the network instead of allowing every cache to become dominated by the same small set of nodes.
Server Introductions
A normal query-key ping can come from any GUESS client, including a leaf.
The server must not assume that every node requesting a query key is an Ultrapeer suitable for its discovery cache.
An Ultrapeer introduces itself by adding a GUE extension to its query-key ping.
In GUESS zero point two, this introduction contains three bytes.
The first byte contains the GUESS version.
The next two bytes contain the node’s UDP listening port in little-endian order.
This is necessary because a network address translator may replace the packet’s temporary source port. The explicit listening port tells the server where future GUESS traffic should be sent.
Only Ultrapeers should include this introduction data.
Requesting More Hosts
A query-key ping may also include the SCP extension.
When it does, the receiving server returns additional GUESS host addresses packed inside an IPP extension in the pong.
GUESS zero point two also allows a normal query to include an empty SCP extension.
This tells the server that the client is prepared to read more GUESS addresses from the acknowledgement pong.
Before forwarding the query to leaves, the server should remove the QK and SCP extensions. Those fields are meaningful only between the GUESS client and the Ultrapeer.
UDP Compression
A later Gnutella extension allowed UDP packets to be compressed.
Its normal signaling method used a bit in the time-to-live field.
That method cannot safely be used for a GUESS query. A server that does not understand the compression extension might read the altered field as a time-to-live value of nine instead of one.
GUESS therefore uses an empty Z extension in the query to say that compressed replies are accepted.
A server that does not understand the extension can safely ignore it.
Compressed query hits are marked according to the UDP compression rules when they are sent back.
The server should remove the Z extension before forwarding the query to leaves.
Semi-Reliable UDP
Gnutella later introduced a semi-reliable UDP layer.
This layer can compress messages and improve delivery without requiring a full TCP connection.
Implementations should prefer semi-reliable UDP over the older Z extension when both sides support it.
Support is advertised through flags in the query’s former speed field.
As semi-reliable UDP becomes available, the older compression extension should be treated as obsolete.
Final Design Principle
GUESS replaces one large, uncontrolled search with many small, controlled searches.
The searching client decides when to continue and when to stop.
Popular files require only a few requests.
Rare files may require a longer crawl.
The network spends its resources according to the difficulty of the search instead of treating every query the same way.
This lowers the cost of operating an Ultrapeer and makes it more likely that users will leave capable nodes running.
The design works only when clients remain conservative. A client that ignores pacing and result limits can still abuse the network.
Used correctly, GUESS turns Gnutella search from an uncontrolled flood into an adaptive process.
References
The GUESS design builds on earlier work about Gnutella search, Ultrapeers, query meshes, UDP delivery, push proxies, protocol extensions, packet sizing, pong-cache poisoning, UDP compression, and semi-reliable UDP.
Important sources include work by Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Christopher Rohrs, A. Singla, V. Falco, S. Darwin, T. Klingberg, Scott Bradner, Richard Stevens, Jeffrey Mogul, Steve Deering, Jason Thomas, Neil Daswani, Hector Garcia-Molina, Raphael Manfredi, and the Gnutella Developer Forum.
The original proposal also refers to the Gnutella Protocol Specification version zero point four, the extensible Gnutella handshake, the Gnutella Generic Extension Protocol, the Push Proxy proposal, and research on search and replication in unstructured peer-to-peer networks.
Authors and Acknowledgements
The original GUESS proposal was written by Susheel Daswani and Adam Fisk of LimeWire.
Later updates were added by Raphael Manfredi for gtk-gnutella.
The authors thanked Christopher Rohrs, the LimeWire team, Gordon Mohr of Bitzi, Jakob Eriksson, Jason Thomas of Swapper, Raphael Manfredi of gtk-gnutella, Michael Stokes of Shareaza, Phillipe Verdy, Sam Berlin, the Gnutella Developer Forum, and the LimeWire open-source community.