On bounded message replication in delay tolerant networks

Delay tolerant networks (DTN), are wireless networks in which at any given time instance, the probability that there is an end-to-end path from a source to a destination is low. So, the conventional solutions do not generally work in DTNs because they assume that the network is stable most of the time and failures of links between nodes are infrequent. Therefore, store-carry-and-forward paradigm is used in routing of messages in DTNs. To deal with DTNs, researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. For this reason, a family of multi-copy protocols called Spray routing, was proposed which can achieve both good delays and low transmissions. Spray routing algorithms generate only a small, carefully chosen number of copies to ensure that the total number of transmissions is small and controlled. Spray and Wait sprays a number of copies into the network, and then waits till one of these nodes meets the destination. In this paper, we propose a set of spraying heuristics that dictates how replicas are shared among nodes. These heuristics are based on delivery probabilities derived from contact histories.