Disrupted Adaptive Routing: Gossip-Based Routing in Delay-Tolerant Networks

One of the main challenges for Delay-Tolerant Network (DTN) routing protocols is to limit network transmissions while achieving a high degree of network coverage. Recently there has been much effort on probabilistic forwarding using a gossip-based approach to reduce the network transmissions in MANETs. We apply a gossip-based approach to DTNs and show that it exhibits a phase transition property for delivery ratio: for some values of gossip probabilities and packet lifetimes the delivery ratio is very low and hardly any nodes receive the packet, for the remaining gossip probabilities and packet lifetimes, the delivery ratio is at its highest and a large fraction of the nodes receive the packet. The phase transition thresholds correspond to minimum network transmissions while providing the highest possible delivery ratio. We present Disrupted Adaptive Routing (DAR), a gossip-based DTN routing protocol, that exploits this phase transition property and develops an adaptive algorithm to compute gossip probabilities based on the phase transition thresholds in random networks. Furthermore, we augment DAR with a mechanism that trades off a small packet metadata with the summary vector exchange of the epidemic protocol, thereby reducing the network transmissions even more. We present experimental results that show that DAR outperforms the traditional epidemic routing protocol by 76% in terms of network transmissions while providing 27% improved delivery ratio and 18% lower average packet delay.