Network Overview

Figure 2: Network Overview

At startup, GPU does not know of any other computer to connect to. Gnutella provides a node discovery technique to solve this problem (the GWebCache[9]): web servers run by volunteers host special scripts (implemented in php, Perl or as compiled cgi) where a new GPU client can register its IP number. GPUs successively download a list of IPs from previous registrations. These IPs are then tried one by one to find other computers that still run the GPU.

Depending on the connection speed, GPU tries to keep the number of established connections between a minimum and a maximum. Typical values for a 28 kbit modem are a minimum of 3 and a maximum of 6 connections, for an ADSL connection, these are 8 and 20, respectively. If GPU is below the minimum number and short of IPs, it connects again to the above mentioned web servers (sometimes referred to as host catchers), registers its IP number again and tries to connect to the new IPs it downloads to establish outgoing connections. At the same time, new nodes entering the network see the IP number registered by the GPU on the web servers and attempt to connect to them, so that the GPU gets incoming connections.

Incoming packets representing computational jobs or file searches are routed using flooding. In flooding, once a packet reaches a node, it is immediately sent out over all its other connections [3]. A Time-To-Live stamp on packets prevents them from walking indefinitely through the network.

Additionally, GPUs keep a list of packets they routed recently: an incoming packet that already belongs to the list is thrown away. In this manner, the list cuts circles in the network. If we think of the network as a graph where nodes represent computers and links connections between them, the list ensures that our graph is a Direct Acyclic Graph (DAG).

In this list, the tuple (packet, incoming connection) is stored. Using tuple information, GPUs can then route back the answer directly to the job submitter, without using the flooding approach.

Briefly, Gnutella uses flooding to submit requests and dedicate routing to receive answers. Finally, because Gnutella does not scale well in this configuration, Ultrapeers are introduced so that the network tends to shape itself into a tree. Ultrapeers are fast nodes that maintain many connections, while slow nodes only keep one connection to one Ultrapeer.

A short introduction to Peer-to-Peer is [20], Gnutella and GPU are discussed in [3].