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/