Summary of gossip protocol for mesh networking

This page summarizes a simple gossip protocol for use in wireless mesh networks I designed for the course Design of Multi-Agent Systems. In such a network, nodes are dependent on the voluntary re-transmission of their messages by third parties in order to reach destinations that are more than one hop away. This creates a situation where a node can act selfishly, by relying on others to route its messages messages, but refusing to route on behalf of other nodes when it can do so. Nearby nodes may be able to observe this behavior and blacklist the offender, but in existing mesh networking systems there is no mechanism for this information to propagate through the network. We propose one such extension, that allows knowledge about altruistic behavior to propagate through the network using a gossip mechanism. It includes a verification mechanism, which prevents rogue nodes from injecting fake messages to prop up their status in the network. This verification relies on the fact that wireless traffic can be observed by all nodes in range, and therefore fake claims of contributions can be detected by other nodes in the neighborhood and rejected through a voting mechanism.

Preliminary studies using an implementation of the protocol in a simulated environment are promising, but a rigorous study of the network conditions and possible counter-attacks is necessary before further conclusions can be made. Furthermore, the proposed mechanism is not scalable to large networks in its current form, which would require limiting the spread of information.

Protocol

This project implements a subset of the Dynamic Source Routing protocol (RFC 4728) with two extensions aimed at improving the fairness of resource usage of participants in the ad-hoc network. Both extensions are designed with promiscuous reception in mind and depend on a simple gossip protocol for the dissemination of information throughout the network.

The first extension is traffic notification. The goal of this extension is to ensure that all nodes are eventually notified of any traffic that is routed through the network. This notification includes the route used by the traffic. These notifications allow nodes to keep track of the extent to which others help maintaining the network by routing traffic.

The second extension is source blacklisting. This allows nodes to determine a blacklist of nodes that they currently do not want to route for. Nodes will be excluded from route discovery for these sources. Together with traffic notification, this allows nodes to blacklist selfish nodes (nodes that use up more network resources than they contribute), thereby incentivize all nodes to act in the common good.

Message types

We will assume that the origin of messages can be verified, for example through public-key cryptography, but this is out of the scope of this project. This is important for the traffic verification and blacklist messages.

Hello messages

Message type: HELLO

HEADER: 
node source
int time

BODY:
{node1 last-hello-1}
{node2 last-hello-2}
..............

Hello messages are transmitted periodically and used to discover other nodes in the network. All nodes maintain a node cache where they store the node IDs of other nodes together with the timestamp of the last hello they heard about. When transmitting a hello message, they broadcast their node cache to their immediate neighbors. Upon reception the neighbors add all unknown nodes and update the hello value if the one they receive is newer. They will eventually spread this information further when they next transmit a hello message. Nodes with a last-hello that is older than some threshold are assumed to have left the network and may be removed from the node cache.

Next to the node cache, each node maintains a list of its immediate neighbors and since when they have been neighbors.

Route request (RREQ)

Message type: RREQ

HEADER:
node source
node dest
int route_id

BODY:
NODE origin
NODE hop1
NODE hop2
....

A route request is broadcast by a node that wants to transmit data to some destination. It contains a unique route ID. Every node will re-transmit the request the first time it receives it, if it does not have the source on its blacklist, adding itself as the next hop. When the RREQ reaches the destination, it will contain a list of hops that constitute a valid route from source to destination.

Route reply (RREP)

Message type: RREP

HEADER:
node source
node dest
int route_id
int nexthop_idx

BODY
node source
node hop1
node hop2
node hop3
node dest

When a destination receives a RREQ intended for that node, it sends back a route reply along the encompassed route to the source node. Only the first RREQ for any route ID is answered, this should generally correspond to the shortest route from source to destination that does not contain hops blacklisting that source. This way the source node will learn of the route and be able to transmit data packages to the target.

The RREP will contain the full route. The header contains a field indicating the index of the next hop, initialized to point to the hop just before the destination. This is decremented on each re-transmission, and used by intermediate hops to know where to forward the message until it reaches the source.

Data package

Message type: DATA

HEADER:
node source
node dest
int route_id
int sequence

BODY:
NODE next
NODE next+1
NODE next+2
....
NODE dest

A source that has used route discovery can send data packages along the route it discovered. This message contains the route ID, the hops along the route, and a sequence number that should be unique for each package in combination with the route ID if multiple messages are transmitted along the same route.

Route error

Because all messages are sent in promiscuous mode, intermediate hops can hear data packages be re-broadcast by the next hop along the route. If they do not hear this, that means the route is broken because a node has moved or because the node changed its blacklist or ran out of battery. In this case they stop re-broadcasting, and the previous hop will know that the route is broken. This way the error propagates back to the source, which can then search for a new route.

Traffic verification

Whenever a node overhears the re-transmission of a data package not along its own route, it stores a observed package entry in its observed traffic cache indicating the route ID, transmitting hop’s node ID, and timestamp.

Gossip message

The distribution of secrets is the basis of both traffic verification and source blacklisting. In a secrets update message, a node advertizes the two newest secrets of each node it knows, together with all votes it has received about those secrets and the hops of all routes mentioned in the secrets. Thus, a complete gossip message is structured as follows:

• List of secrets
• List of votes, each identified by the tripe (node_id, sequence_nr, caster) where the node ID and sequence nr. identify the secret the vote is about
• List of routes mentioned in the contained secrets, where each route consists of a unique route ID (assigned when rhe route reply is sent) and a list of hops (where each hop is the node ID of a node on the hop).

A single secret contains the following information

• The node ID and sequence number of the secret. The sequence number is incremented when a node creates a new secret, so together the node ID and sequence number uniquely identify the secret
• The start and end of the time period this secret describes. Time periods should be incrementing between secrets and not overlap.
• The traffic flows this node claims to have routed in this period, by route. This is a list of entries of the following form:
  • The route ID
  • The number of messages routed in the secret period

Each neighbor casts one vote for each secret. The nodes do this by comparing the claimed traffic flows to their observed traffic cache. The vote can be either accept (the traffic matches with observations) or reject (the traffic does not match with observations) The criteria by which this is decided can depend on the node’s strategy.

Because only the newest secrets for each node are broadcast in the gossip messages, each secret is circulated only for some period of time. When the secret is superseded, each node removes the secret form its internal buffer and counts all related votes. Based on this, it judges the truthfulness of the secret. This information is used to construct the blacklist.

Processing of incoming of secrets

If the node is a neighbor, cast a vote about the validity of the secret Store the secret in the buffer until two newer secrets have arrived. Then, count votes for the secret and if it is accepted use the stored balance to update secret count.

Judging of secrets

The way nodes judge secrets from other nodes depends on their strategy. The simplest mechanism is to have some threshold for the minimum number of accept votes and for the minimum ratio of accept to reject.

Estimation of verified traffic flows

Based on the processed secrets, nodes obtain a lower bound on verified traffic flow in each hop. This is used to generate an estimate of the flow in the entire route. This is then used to credit nodes in the internal balances. These balances in turn can be used to inform the blacklist construction.

Network simulation

A simulation of a network running the proposed protocol was written in c++11, with message passing based on the cppzmq bindings of the ZeroMQ brokerless messaging framework. This simulation implements a number of nodes that communicate with each other. Nodes move around randomly in the two-dimensional simulation space and expend battery charge for each message they transmit. Since all control messages are assumed to be tiny compared to the data packages, they will be much cheaper to transmit.

At every time step, each node receives messages from other nodes that are within its range and broadcasts new messages to all nodes within its range. All transmitted messages are delivered in the next time step to all agents within range of the sender. All communication is through messages, with different message types defined implementing those in the protocol specification.

In the simulation, nodes can use different strategies, namely: selfish, naive, and gossiping. The naive nodes act altruistically but do not participate in the gossip mechanism or use information learned from it. When only naive and selfish nodes participate, naive nodes quickly exhaust their battery to route on behalf of the selfish nodes, and the network collapses. When a sufficient number of gossip nodes is added, they will start detecting and blacklisting the selfish nodes, and the stability of the network is maintained for a much longer period.