Gnutella Protocol Development
Home :: Developer :: Press :: Research :: Servents
PING REDUCTION SCHEME
Version 1.1 D.R.: 1
Tue, 17 Oct 2001
Emixode Communications
148 South Wells Ave
Glenolden, PA 19036-1741
info@emixode.com
Status: This document applies to the Gnutella Protocol version 0.4 and up.
1. Introduction
The purpose of the Ping Reduction Scheme (scheme) is to reduce the amount of
PING packets (Ping) and corresponding PONG packets (Pong) transmitted over the
Gnutella Network (GNet), which currently accounts for a fast majority of Gnet
traffic (traffic, bandwidth).
The main objective is to keep complexity and system requirements of such
scheme at lowest levels possible, while maintaining effectiveness.
Note: With each Ping, a receiving Gnutella client (client) responds with a
Pong accordingly. Although some clients may refrain from sending such Pongs
under certain circumstances, this document will focus on the Pongs actually
sent in response to a Ping.
2. Outline
Without a ping-reducing scheme, Pings traverse freely over the GNet. Usually,
a single Ping will result in more than one corresponding Pong, as multiple
clients respond.
As the GNet grows, more Pings will be sent over the network. Equally so, the
number of Pongs will increase, sometimes at a higher rate because multiple
clients will respond to a single Ping. Currently, the number of Pings and
Pongs combined account for the majority of the GNet traffic as a result.
However, Pongs have a pattern. Because a Pong from a single, unique client
does not change, it can be temporarily stored (cached) by those who receive
it. If at this point a Ping is received by a client that cached the Pong
response, there would be no need to forward the Ping to the unique client, and
will return a Pong from its cache.
This scheme will exploit those patterns when reducing the amount of Pings (and
thus Pongs) being transmitted over the GNet. The scheme will temporarily store
a Pong it received as a result to a Ping it had broadcasted. Any subsequent
Pings are not broadcasted and instead, a Pong is returned from the cache.
3. The scheme at work
The client implementing this scheme would require an additional table (array,
list) to hold the Pong entries it cached. Each such entry should hold the
following information:
IP Address
Port
Number of files share
Size of files shared, in Kbytes
Timestamp entry was added
Unique Connection Identifier (ie., Handle of Socket)
Essentially, this is the same information provided in a Pong, with the
addition of a timestamp. The timestamp serves two purposes:
1) Filter outdated Pongs from the cache.
2) Keep memory requirements acceptable.
Initially, this table would contain no cached Pongs. That would mean that the
client is required to let the Ping pass. As the Ping generates the
corresponding Pongs, these Pongs are stored in the table before they are being
routed the path they came, according to the Gnutella Protocol specifications.
As it stores each such Pong into the table, it places the current time (or
time and date) in the Timestamp field for this entry, as well as a unique
identifier referencing the connection through which this Pong was received.
Before we drop a Ping and respond with a Pong, we first need to ensure the
number of entries in the table meets a certain threshold. The threshold
ensures that the client sends out a minimum number of Pongs. By default, the
threshold is set at 20 ({Tr}).
If there are less than {Tr} entries in the table, Pings are still allowed to
pass. If there are {Tr} or more entries, the client will drop the Ping from
the network and respond with {Tr} Pongs, each containing unique date retrieved
from the table.
The method a client selects {Tr} entries from the table for use in the Pongs
may vary. The two accepted methods are "First in, Last out" (or, oldest first)
or randomly selected entries. However, at all times the method should NOT
select entries for which the Unique Connection Identifier is equal to the
connection for which the entry is destined, in order to prevent a Pong being
routed over a path it previously travelled.
Because Pongs easily become outdated, we have to ensure that the Pongs do not
become too old to be useful. Therefore, the client will filter out all entries
from the table that are older than a certain period. By default, this is
10 seconds ({To}). It is recommended not to increase this period beyond
15 seconds.
The client has three opportunities to filter the table for outdated entries
(delete old entries). The first is at the point it needs to make a decision to
pass a Ping through or drop it from the network; before making the decision,
it will first filter all the entries in the table and then makes the decision
based on how many entries are left in the table, depending on {Tr}.
The second option is to have a thread or messaging function which filters the
table at set intervals, independent of the Ping/Pong routine of the client.
This option may prove the most efficient for most programming languages.
The third option is to filter the table each time a new entry is added. Before
the actual entry is added to the table, the table is being filtered for its
outdated entries. This may prove an exhaustive option.
As the table is being filtered, it will reduce the amount of available entries
and thus equally reducing the memory requirements. Should the number of
entries fall below {Tr}, the client MUST pass a subsequent Ping or Pings in
order to store new entries in the table. Otherwise, the client must drop
the Ping or Pings and return {Tr} results.
3.1 - Not all Pings are equal
There are three versions of the Pings, two of which may not require
intervention of this cache scheme. One is where the Ping's Time To Live (TTL)
is set at 1 and Hop count at zero (0). This Ping requires that only the client
returns a Pong and drop the Ping from the network.
Second is a Ping with a TTL set at 2 and Hop count at zero (0), also known as
a Crawler Ping. To the client, the Pong is already known: the Pong returned
from clients directly connected to it. Although the client is not required to
respond on behalf of its directly connected clients, it may choose to do so
and drop the Ping as well.
In both these cases, this scheme does NOT apply. Thus, it is safe to state
that only a Ping with a TTL higher than 2 is suitable for this scheme.
3.2 - What not to cache
All pongs with a hop count of zero (0) should NOT be added to the table, to
prevent caching Pongs that may have come from a neighboring client that
implemented this or another scheme.
Obviously, duplicate entries would only artificially inflate the number of
entries in the table while serving no purpose. Therefore, duplicate entries
should be omitted, which can be done at during the filtering process, or
verifying the table before adding a new entry.
3.3 - Options
A client may choose to add additional filtering criteria. Such options include
connecting to the IP addresses from the entries in the table, and verify they
are indeed capable of accepting an incoming connection. However, these are
solely the option of the developer implementing this scheme and is not
mandatory.
Query Hit packets and Push Request packets contain IP addresses and ports,
which can also be found in Pongs. A client may opt to use this data to add
entries to the table. Possible implications of doing such is an inaccurate
horizon estimating, especially concerning the number of files shared and the
file size, as this is not present. A benefit is that this would reduce the
reliance on Pongs (and thus passing Pings). However, there may be additional
side effects of using these two packets for a purpose they were not initially
designed for.
4. Pseudo Code
Below a pseudo code, how the scheme might be implemented:
const Record = (IPAddress, Port, FilesShared, FileSize, TimeStamp,
SocketHandle);
const Treshold = 20
const Timeout = 10
var Table = array of Record
func AddToTable(IPAddress, Port, FilesShared, FileSize, SocketHandle) {
new Record
Record.IPAddress = IPAddress
Record.Port = Port
Record.FilesShared = FilesShared
Record.FileSize = FileSize
Record.SocketHandle = SocketHandle
Record.TimeStamp = Now()
Add Record to Table
}
func FilterTable {
var Counter
for Counter = 1 to Table.ItemCount do {
if SecondsDifference(Table.Record(Counter).TimeStamp, Now()) > Timeout {
Delete From Table Record(Counter)
}
}
}
func SendPongFromCache(SocketHandle) {
var Counter
Counter = 0
while Counter < Treshold do {
if Table.Record(Counter).SocketHandle <> SocketHandle then {
SendPong( Table.Record(Counter) )
Increase Counter by 1
}
}
}
.
.
.
func HandlePing {
if TTL < 2 then {
.
.
.
} else {
FilterTable()
if Table.ItemCount >= Treshold {
.
.
SendPongFromCache(Socket_Handle)
.
.
} else {
.
.
BroadcastPing()
.
.
}
}
}
.
.
.
func HandlePong {
.
.
.
if Hops > 0 then {
AddToTable(Pong.IP, Pong.Port,
Pong.FilesShared, Pong.FileSize,
Socket_Handle)
}
}
5. Issues
This scheme is experimental, however has been proven to be effective in
reducing up to 96%. However, these results may vary depending the
implementation of this scheme.