The HeavyMole communication protocol

The HeavyMole network is composed of nodes, i.e there is client/server aspect. Each node is uniquely identified by a Global User Identificator (GUID). This GUID is a randomly chosen 64 bits integer.

Each node knows a limited number of neighbours, with which he can communicate. These neighbours are contained in what we call the 'usertable'. The first task of the communication protocol is thus to build this usertable and to keep it up-to-date.

Each node can share a number of files. Each set of files shared by one user is contained in a data structure that we will call a 'filetree'. To get better global search results, the filetree of a given node will be duplicated on several other nodes. A second task of the protocol will thus be to duplicate our filetree, to keep the copies up-to-date when our filtree changes and to detect when a node that hosts our filetree, or from which we host the filetree, goes on/offline.

The third task of the protocol (in fact his goal) is to send requests, to search hosted filetrees and to send answers.

The usertable is a data structure containing a number of users. A number of coefficients that we call preference coefficients (PC) are associated with each user (in fact, we will have one PC for each message type). They are used to choose best adressees w.r.t the type of the message to send, and to keep only best neighbours. The usertable maintains an index by user's GUID, and an index for each PC.

When the application is launched for the first time, the usertable is empty. To get started, we ask to some central server a number of users, randomly chosen among all those that are logged on this server. Once this is done, we'll never have to ask to the server again, except if it happens that all users we know are offline.

When a LOGIN message (or any other message containing user information) is received on the network, the user it contains is put in the usertable if it's not full. If the user already exists, his information is updated.

The usertable is constantly kept up-to-date as follows. Each N seconds, next user in table is pinged (PING). When the user replies (PONG), the time taken by the message to go and come back is used to compute the PC for this user. In fact, each PC has its own compute method based on the ping time, and on other informations (number of hosted files and request handling capacity) that are contained in the PONG message (see see below for details about computing PCs) If the user has still not replied the next time he is pinged, all his PCs are set to 0.

When all users have been pinged, the usertable is checked. If there are not enough users or if the mean PC is too low, we ask to other users on the network some users of their own table (ASKUSERTABLE/SENDUSERTBALE) and we remove bad users. If there are no online users (i.e if mean PC = 0) we ask to a central server. Then we start pinging the users again.

NB: To prevent from having to contact central servers too often or if all servers are unreachable, we also keep a second data structure on hard disk, containing all users received (with a maximum size of several thousands users). When we have no online users in the table, we first look in this structure and try all users until we have found M online users. This insures that after some time using HeavyMole, the probability that we know no online user will be very low.

As we said before, each node will try to duplicate his filetree on several other nodes. In fact, each node is trying to keep a fixed number H of online copies of his filetree. To achieve this, we keep a list of online hosters, which is checked at regular intervals. When the number of online hosters is under H, we send a FILETREEPROPOSE message on the network to ask to other nodes to host our filetree. When a node receives such a message, it checks if its hosting capacity is not reached, and if this is the case it replies to accept the filetree (FILETREEACCEPT). When the sender gets the reply, a TCP connection is established and his filetree is uploaded.

We see that each node must have some list holding hosted filetrees. When a filetree is downloaded, it is put in the list along with information about the hosted user. This list is updated in the same way as the usertable. Each N seconds, next hosted user is pinged (HOSTERPING). If the user does not reply (HOSTERPONG), we mark him as offline in the list. When a node is pinged by one of his hosters, he knows that this hoster is online and it is added to the list of online hosters, if it is not already in it.

When our filetree changes, we must find a way to warn hosters. Each time our filetree is scanned, the difference with previous version (delta) is computed and saved, and a new version is created. In this way, we keep a trace of the history of all changes to the filetree. When a filetree is downloaded, the version number is also given. When a node pings a hosted user, it also gives the filetree version it has. If a newer version is available, the update which is composed of all computed deltas since the old version are uploaded and applied to the hosted filetree.

When we want to search the HeavyMole network, we first check in our filetree to get immediately some answers, then we send a REQUEST message. When a node receives a request, it is put in a buffer and forwarded to other users (see below for more explanations on message forwading). If buffer is full, the request is dropped. When the request is extracted from the buffer and handled, all or a part of hosted filetrees are searched (searchingcapacity <= hostingcapacity). An ANSWER message is sent to the sender of the request when one or more files matching the request are found. (see A.? for details on request syntax and on searching a filetree). If there are two many answers to fit in one UDP packet, it is sent in sevral packets.

Now we have seen all types of messages, why they are sent and how they are handled, we are going to see how those messages are sent and forwarded on the network.

First, we can see that messages can be split up into two groups. The first group contains all messages that are sent by a node to another well-defined node. Those are what we call the Peer-to-peer messages. The second group contains all messages sent by a node and that have no well-defined destination, but that are intended to be received by many other users on the network. Those are what we call the flood messages.

Flood messages are also sent by UDP, for the same reasons as above. Flood messages can again be divided into two groups. One group contains messages that are to be sent to many other nodes: those are called FLOOD messages. The other group contains messages that are to be sent to a few other random users on the network, but that are not in our immediate neighbourhood: those are called ARROW messages.

All these messages have in common that they are first sent to some users from the usertable, and that they are then forwarded by the receivers, and so on... All messages carry a time-to-live (TTL) that is decreased each time the message is forwarded. When a received message has TTL = 0, it is never forwarded. All messages also carry information about the sender. This allows to reply to him directly through P2P, but also to insert/update him in our usertable.

That's here that the preference coefficients associated with the users are used. We said above that for each message type (not with P2P messages of course), a PC was defined, each with its own compute method, to choose best addressees w.r.t the message type. For each PC, there is a pool containing users chosen among the best w.r.t this PC. This pool is computed each time the table is checked (see A.? for details about the algorithm used for extracting a pool from the usertable). When a message of a given type has to be sent or forwarded, neighbours to which we send the message are chosen randomly among the current pool for this message type.

There are two types of FLOOD messages currently used: REQUEST and LOGIN.

All FLOOD messages carry a reference PC (REF_PC), and a minimum and maximum growing factor (MIN_GF and MAX_GF). When a node forwards a FLOOD message, it looks at the mean PC of his current sending pool. If this mean is under REF_PC, the message is forwarded to MIN_GF neighbours, else it is forwarded to MAX_GF neighbours.

Thus the size of the neighbourhood that we reach when we send a message can be chosen with appropriate values of initial TTL and of the MIN_GF and MAX_GF. The REF_PC allows to favour directions with more good nodes.

FLOOD messages coming from me, or from a user from which we already received a FLOOD messages very recently (in last 10 seconds) are never handled nor forwarded. This prevents from explosion in small networks.

There are two types of ARROW messages currently used: FILETREEPROPOSE and ASKUSERTABLE.

ARROW messages, as we already said, are aimed to contact a few random users on network but not in our immediate neighbourhood. This is useful for FILETREEPROPOSE messages. Indeed we've just seen that FLOOD messages (in particular REQUEST messages) are sent to a neighbourhood whose approximate size is chosen at sending time by appropriate parameters values. The main goal of duplicating filetrees is thus to get better results when searching this neighbourhood. It is of course useless for a given filetree to be hosted by 10 users in the reached neighbourhood. What we want is thus to have our filetree hosted by nodes "far" from us. This is what we do with arrow messages. ARROW messages are also used for ASKUSERTABLE, to prevent formation of unconnected sub-networks.

All ARROW messages carry a minimum TTL (MIN_TLL). When a node receives an ARROW message, if message's TTL is greater than MIN_TTL, message is immediately forwarded to one random user from the pool for this message type. Else, the message is handled. If it was not sucessfully handled and TTL is not 0, message is also forwarded to one user. Thus the number of nodes that will sucessfully handle the message is always less than or equal to the number of users we initially sent the message.

We saw above that when a message of a given type has to be sent or forwarded, neighbours to which we send the message are chosen randomly among the current pool for this message type. We are now going to see, for each message type, how the PC is computed.

The main component is the ping (adds [0, +65] to the PC). If the scaled request handling capacity is negative (user's request buffer is more than half-full), the PC is decreased, else it is increased (adds [-50, +25] to the PC). This will have as a result that request will be sent to users whose buffer is not too busy. The number of hosted files is also taken into account, but only for a small part (adds [0, +10] to the PC).

2. LOGIN and ASKUSERTABLE messages