About
This page contains a selection of graphs that were created based on measurements in the DES-Testbed with several gossip routing variants. Please note that we are currently writing a technical report as summary of all gossip routing experiments and this page will probably not be updated frequently. The graphs are just provided for people who are interested in higher resolution versions that are used in our publications.
The copyright of all figures belongs to Bastian Blywis and Sebastian Hofmann.
Experiment Setup
Position of the source nodes
gossip0 - simple probabilistic forwarding
Most simple gossip routing variant that uses only the parameter p to determine whether a packet shall be forwarded.
Distance of all nodes from the source nodes
The following graphs are based on the data measured with gossip0(p=1.0) and 100 repetitions.
|
|
|
| Source Node A |
Source Node B |
Fraction of nodes receiving the packets in the fraction of executions
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
 |
 |
| Source Node A |
Source Node B |
Fraction of nodes receiving the packets in the fraction of executions
The following figures are just slices of the three-dimensional histograms shown above.
Probability threshold p=0.60
 |
 |
| Source Node A |
Source Node B |
Probability threshold p=0.65
 |
 |
| Source Node A |
Source Node B |
Probability threshold p=0.72
 |
 |
| Source Node A |
Source Node B |
Probability threshold p=0.75
 |
 |
| Source Node A |
Source Node B |
gossip1 - initial flooding
In addition to the pure probabilistic forwarding, the packets sent by the source node are flooded for the first k hops to prevent that the gossiping terminates early.
Fraction of nodes receiving the packets in the fraction of executions
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
 |
 |
| Source Node A |
Source Node B |
gossip2 - two thresholds
This variant has two threshold parameters to determine the probability to forward packets. If the node degree is lower than n, p2 is used and otherwise p.
The inital k-hop flooding of gossip1 also applied.
Fraction of nodes receiving the packets in the fraction of executions
Preceeding neighborhood discovery
 |
 |
| Source Node A |
Source Node B |
Parallel neighborhood discovery
 |
 |
| Source Node A |
Source Node B |
gossip3 - waiting for constant number of duplicates
When a node does not forward a packet due to chance, it is stored instead. If fewer than m duplicates are received in a specific time, the stored packet is sent; otherwise it is finally dropped.
The inital k-hop flooding of gossip1 also applied.
Fraction of nodes receiving the packets in the fraction of executions
Preceeding neighborhood discovery
 |
 |
 |
 |
| Source Node A - 1 |
Source Node A -2 |
Source Node B - 1 |
Source Node B - 2 |
Median fraction of nodes receiving the packets as a function of p
 |
 |
 |
 |
| Source Node A - 1 |
Source Node A - 2 |
Source Node B - 1 |
Source Node B - 2 |
gossip5 - waiting for duplicates from all other neighbors
When a node does not forward a packet due to chance, it is stored as in gossip3. If fewer than the number of neighbors minus 1 duplicates are received in a specific time, the stored packet is sent; otherwise it is finally dropped.
The inital k-hop flooding of gossip1 also applied.
Fraction of nodes receiving the packets in the fraction of executions
Preceeding neighborhood discovery
 |
 |
| Source Node A |
Source Node B |
Parallel neighborhood discovery
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
Parallel neighborhood discovery
 |
 |
| Source Node A |
Source Node B |
gossip6 - adaptive second chance
Shi and Shen try to improve the route discovery phase of AODV. Their approach is called Adaptive Gossip-based Ad Hoc Routing} (AGAR) and is based on gossip3. When a packet is received and the random number is above the threshold p, the packet is stored. Instead of always broadcasting the packet when fewer than m duplicates have been received in the waiting time, the following formula is used to determine whether the packet shall be sent: random(0,1) <= p/(d+1). d is the number of received duplicates.
The inital k-hop flooding of gossip1 also applied.
Fraction of nodes receiving the packets in the fraction of executions
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
 |
 |
| Source Node A |
Source Node B |
gossip7 - delayed forwarding with duplicate counting
Mohammed et al. propose a Probabilistic Counter-based Route discovery (PCBR) for AODV. The general idea is that received packets are always stored when they are received and the number of received duplicates is counted. Packets are forwarded after the random assessment delay (RAD) timer has expired and when not enough duplicates (d <= m) were received. The RAD timer value is randomly chosen from the interval (0, Tmax].
Fraction of nodes receiving the packets in the fraction of executions
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
 |
 |
| Source Node A |
Source Node B |
gossip8 - forwarding considering the node degree
Hanashi et al. propose P-AODV. When a broadcast packet (AODV route request) is received for the first time by a node, the probability p to forward the packet is calculated based on the number of neighbors n. p has a high value when there are few neighbors and has a low value when the node degree is high. The threshold is additionally bounded by pmax and pmin.
Fraction of nodes receiving the packets in the fraction of executions
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
 |
 |
| Source Node A |
Source Node B |
gossip9 - coverage consideration
Abdulai et al. propose the Dynamic Probabilistic Route (DPR) algorithm for AODV. When the node degree n is lower than nf, the algorithm results to flooding. When the node degree n is higher than nf, the additional coverage that can be achieved by forwarding the packet determines the value of p. Each node that forwards a packet attaches a list of its neighbors nc. Upon reception of a packet, a node determines the set of his neighbors that (probably) have not received this packet. If the set is empty, the node will not forward the packet; otherwise the larger the set, the higher the forwarding probability.
Fraction of nodes receiving the packets in the fraction of executions
 |
 |
| Source Node A |
Source Node B |
Median fraction of nodes receiving the packets as a function of p
 |
 |
| Source Node A |
Source Node B |
