Home › Gossip Routing

Gossip Routing

des-sert

Many routing protocols use a flooding scheme to spread information in the network. Flooding is fairly reliable but often more packets are sent than are necessary to cover all nodes. Gossip routing introduces a probabilistic element to flooding. Each node randomly determines if a packet will be forwarded or dropped. This approach can significantly reduce the number of packets in the network.

Description:

The core idea of gossip routing is based on epidemic processes in nature, especially the spreading of diseases. When a pathogen is infectious enough, after short time a whole population will be infected. An infected individual will be the pathogen carrier and will infect other individuals. When an infected individual meets an uninfected one, there is a particular probability that the healthy one will become infected. For the research of epidemic processes it is interesting to determine for which infection probability and/for how many initial infected there will be an epidemic/pandemic.

Gossip desease

In gossip routing protocols the packets can be considered as the infection and the nodes as individuals. Mesh routers can "infect" each other with particular information, e.g., the topology control information in OLSR. Each router that receives a packet and is not the destination will select a random number. If this number is below a specific threshold p, the packet is forwarded by broadcast and is otherwise dropped. Depending on the value of the threshold, a packet sent by a source may be received by few or most nodes in the network.

Percolation theory is another domain of research that acts as inspiration for gossip-based protocols. Percolation theory states that for a specific network/percolation model there exists a particular probability pc. For p<pc few nodes will receive packets and for p>=pc almost all will receive them. At pc the system, i.e., the network radically changes its behavior.

The following two graphs were created based on measurements in the DES-Testbed with a gossip routing daemon. The two graphs show the median fraction (red line in the box plots) of nodes receiving the packets as a function of p. More graphs based on our experiments are available here.

gossip0 from source node A gossip0 from source node A
 Source Node A Source Node B

 

Variants:

In the following list the implemented gossip variants are given. Most gossip variants are extensions of others.

  • gossip0(p): p stands for the gossip threshold. A packet therefore is forwarded when random(0, 1) ≤ p, otherwise the packet will be dropped.
  • gossip1(p,k): A packet can be forwarded to the next k hops with p = 1.0. This can be used as a flooding mechanism.
  • gossip2(p,k,p2,n): If the node has less than n neighbors, use p2 to determine the packet forwarding.
  • gossip3(p,k,m): If a packet is not forwarded due to chance, store the packet. If fewer than m duplicates are received in some specific time, send the stored packet; otherwise drop it finally.
  • gossip4(p,k,k'): Each node has a zone of k' hops. If a packet is received that is destined to a node within this zone, than the packet is sent as unicast over a route found by some proactive unicast routing protocol. This variant is inspired by the Zone Routing Protocol (ZRP).
  • gossip5(p,k): Same behavior as gossip3 but if fewer than the number of neighbors minus 1 duplicates are received, then the stored packet is sent.
  • gossip6: is based on the gossip3 modification of Zhongmin Shi and Hong Shen 
  • gossip7: is based on the work of Mohammed et al.
  • gossip8: is based on the work of Hanashi et al.
  • gossip9: is based on the work of Abdulai et al.