Engage Others or Leave it to the Source? On Optimal Message Replication in DTNs Under Imperfect Cooperation

The message replication strategy, namely the way message copies are generated and diffused (a.k.a. sprayed) in the network, is a fundamental, yet not thoroughly explored, component of all multi-copy message forwarding schemes in opportunistic networks. Whereas almost all related protocols rely to some extent on the assistance of intermediate nodes for relaying message copies towards their destination, the generation of new message copies may either involve them or be carried out exclusively by the message source. This paper first formulates and solves analytical models for the performance of the two most popular message spraying strategies under imperfect node cooperation and homogeneous exponentially distributed pairwise node inter-contact times. Numerical results suggest that as the node cooperation decreases source replication consistently outperforms binary replication, i.e., the optimal variant of intermediate node-assisted replication under nominal conditions of full node cooperation. The analytical conclusions are also verified for more realistic node mobility patterns through trace-driven experimentation. We then formulate the ideal selection of replication mode as a finite-horizon Continuous Time Markov Decision Process with restricted decision epochs and solve it for the optimal spraying policy. The optimal policy coincides with the binary-(source-) spraying in the presence of few (resp. many) misbehaving nodes. To better approximate it at intermediate levels of misbehavior intensity, we introduce and analyze a simple static spraying policy permitting source-destination space-time paths of up to three hops. Our work deepens the understanding of a core operation embedded in a broad range of multi-copy DTN forwarding protocols. At the same time, it advocates a more thorough approach to the design and evaluation of DTN forwarding that accounts for beyond-nominal conditions.