Pong caching schemes

Some ideas on how to implement the Pong caching in practice has been proposed. One caching scheme is presented in [Gnu02] and another scheme is presented in [RF01]. The [Gnu02] draft, [RF01] and some other suggested schemes are available at [RFG03]. This section describes the most important parts of these proposed caching schemes.

All caching schemes are based on the observation that the initial implementations of the Gnutella protocol consumed a lot of bandwidth. Closer examination revealed that connection management with Ping and Pong messages were using more than 50% of the bandwidth. The main reason is of course the broadcasting of Ping messages that propagate through the network consuming lots of bandwidth. Similar results have been presented in [RIF02] and [Rip01].

To reduce the effects of a Ping broadcast Pong caching is deployed. Each Gnutella host stores all Pong messages received in a local cache. When receiving a Ping message a number of messages from the cache are chosen and returned. When returning a cached Pong message the message identifier is of course changed to correspond to the incoming Ping message. A cached Pong message is considered valid for a couple of seconds. Suggestions between 3 and 15 seconds have been proposed.

The Pong caching schemes only apply to Ping messages with a TTL greater than 2 and a hop count greater than 0. Otherwise the incoming Ping message is managed as described in section sec:pingpongopt.

The pseudo code shown in figure fig:pongcachepseudocode is a slightly modified version of one of the schemes presented in the archive of Gnutella protocol proposals at [RFG03].

Illustration 3.1: Pseudo code for a Pong caching scheme

  AddPongEntry(pongmsg) {
      timestamp = CurrentTime()
      CacheInsert(pongmsg, timestamp)
  }

  RemoveExpiredPongs() {
      foreach pong in CACHE
          if (CurrentTime() - pong.timestamp > TIMEOUT)
              RemovePong(pong)
  }

  HandlePing(socket) {
      pingmsg = ReadPing(socket)
      if (pingmsg.ttl < 2)
          ...
      else
          RemoveExpiredPongs()
          if (CACHE.size() >= THRESHOLD)
              pongs = SelectPongsFromCache(THRESHOLD)
              foreach pong in pongs
                  SendPong(pong, socket)
          else
              BroadCastPing(pingmsg)
  }

  HandlePong(socket) {
      pongmsg = ReadPong(socket)
      ...
      if (pongmsg.hops > 0)
          AddPongEntry(pongmsg)
  }

Incoming Ping messages are answered directly if the local cache contains enough items. A certain number of items are selected from the cache and returned. If the cache does not contain enough items to answer the Ping directly, a regular broadcast is performed.

Incoming Pong messages are stored in the cache. The messages stored in the cache are removed after a certain amount of time, keeping the entries in the cache fresh, and hence more reliable.