Gnutella - Flow Control

Our blue logo

Gnutella Protocol Development

Home :: Developer :: Press :: Research :: Servents

3.5 Flow control

3.5.1 A simple flow control scheme
Source - Latest Draft.

It is very important that all servents have a system for regulating 
the data that passes through a connection.

The most simple way is to close a connection if it gets overloaded.
A better way is to drop broadcasted packets to reduce the amount of
bandwidth used.  A much better way is to do the following:

Implement an output queue, listing pending outgoing messages in
FIFO order.  As long as the queue is less than, say, 25% of its
max size (in bytes queued, not in amount of messages), do nothing.
If the queue gets filled above 50%, enter flow-control mode.  You
stay in flow-control mode (FC mode for short) as long as the queue
does not drop below 25%.  This is called "hysteresis".

The queue size SHOULD be at least 150% of the maximum admissible
message size.

In FC mode, all incoming queries on the connection are dropped.
The rationale is that we would not want to queue back potentially
large results for this connection since it has a throughput problem.

Messages to be sent to the node (i.e. queued on the output queue)
are prioritized:

* For broadcasted messages, the more hops the packet has traveled,
  the less prioritary it is.  Or the less hops, the more prioritary.
  This means your own queries are the most prioritary (hops = 0).

* For replies (query hits), the more hops the packet has traveled,
  the more prioritary it is.  This is to maximize network usefulness.
  The packet was relayed by many hosts, so it should not be dropped
  or the bandwidth it used would become truly wasted.

* Individual messages are prioritized thusly, from the most
  prioritary to the least: Push, Query Hit, Pong, Query, Ping.
  The Bye message being special, it is always sent (i.e. the queue
  cannot be in FC mode since it needs to be cleared before sending
  Bye).

Normally, all messages are accepted.  However, when the message to
enqueue would make the queue fill to more than 100% of its maximum
size, any queued message less prioritary in the queue is dropped.
If enough room could be made, enqueue the packet.  Otherwise, if the
message is a Query, a Pong or a Ping, drop it.  If not, send a
Bye 502 (Send Queue Overflow) message.

3.5.2 SACHRIFC
Source - Christopher Rohrs

SACHRIFC is a simple, but still very effective flow control system 
that drops less important packets first.

3.5.2.1 Goals

SACHRIFC has the following goals:

1. Never drop messages unless bandwidth is at a premium.

2. Minimize latency. Never buffer messages too long.

3. Prefer messages in the following order: pushes (most
important), query replies, queries, pongs, pings
(least important). In other words, if you have to
choose between dropping a push and a query, drop the
query.

4. Prevent any one message type from dominating traffic.
For example, a stream of pushes should not totally
prevent all replies from being routed. This goal is
at odds with (3).

5. Favor less popular replies over more popular ones.
Assume that 10 replies have been routed to query Q1
and 1000 replies have been routed to query Q2. If
you must choose between routing another reply R1 to
Q1 and another reply R2 to Q2, prefer R1.

3.5.2.2 Algorithm

SACHRIFC uses one
application-level buffer per connection. However, each of
these buffers Q consists of a separate queue Qi for each of
the 5 message types. A buffer's query reply queue is sorted
by "GUID volume", with messages whose GUIDs have generated
fewer replies at the head. (This is easily implemented with
a binary heap.) The remaining queues are sorted by time,
with newer messages at the head. A message M is added to
buffer Q as follows

let M have type i
if (queue Qi is full)
remove tail entry from Qi
add M to Qi

SACHRIFC sends messages using a kind of round-robin
algorithm. For simplicity, assume one dedicated reader
thread per buffer Q. This reader continually removes
messages from the queue and forwards them to the network as
follows:

for each of the i message queues Qi in buffer Q
for each of the min(Ni, |Qi|) Mi on the head of Qi
if Mi is not "too old" for that message type
send Mi to the network

By adjusting the ratios N1:N2:N3:N4:N5, you can adjust the
worst-case message type ratio. Perhaps, for example, we'd
like to send 2 replies to every one query if bandwidth is at
a premium. This achieves goals (3) and (4). If you're
really fancy, you can specify ratios in terms of volume, not
counts. You could even make N_QUERY_REPLY proportional to
GUID volume. On the other hand, if the outgoing link
capacity is sufficient, messages ratios are not "shaped".

3.5.2.3 Why LIFO?

The SACHRIFC algorithm uses a LIFO policy for traffic other
than replies. This helps minimize latency (goal 2), without
affecting normal message traffic. To understand why LIFO is
preferable to FIFO, consider a stream of queries being read
at 1 KB/s from connection C1, being forwarded to another
connection C2. For simplicity, assume that all messages are
of the same type. Assume the capacity of C2 is exactly 1
KB/s and the capacity of C1 is infinite.

C1 (infinite capacity) -> ROUTER -> C2 (1 KB/s capacity)

Initially, of course, no messages are dropped. Now we get
an instantaneous burst of 10KB worth of data from from C1.
With a FIFO policy, it will take 10 seconds to sends this
chunk out to C2. Subsequently, C2's buffer will always
contain 10 seconds worth of data, so the C1->C2 latency is
now 10 seconds for all remaining packets. This is clearly
undesirable.

With the LIFO policy, the 10KB chunk will simply be queued.
Subsequent packets will be sent with no latency. Eventually
the 10KB chunk will be dropped because of either condition
above. I think this is much preferable to the FIFO
behavior. Better to screw a few packets a lot than a lot of
packets a little.

Clients should not use the LIFO policy for query routing
protocol (QRP) messages, as QRP depends on in-order
delivery. Nor should servents time out QRP messages.

3.5.3 Others flow-control schemes

A more advanced flow control system can be found at:
http://www.grouter.net/gnutella/


 

 

 

Home :: Developer :: Press :: Research :: Servents

SourceForge.net Logo