A Framework for Routing Performance Analysis in Delay Tolerant Networks with Application to Non Cooperative Networks

In this paper, we present a framework for analyzing routing performance in delay tolerant networks. Differently from previous work, our framework is aimed at characterizing the exact {\em distribution} of relevant performance metrics, which is a substantial improvement over existing studies characterizing either the expected value of the metric, or an asymptotic approximation of the actual distribution. In particular, the considered performance metrics are {\em packet delivery delay}, and {\em communication cost}, expressed as number of copies of a packet circulating in the network at the time of delivery. Our proposed framework is based on a characterization of the routing process as a stochastic coloring process, and can be applied to model performance of most stateless delay tolerant routing protocols such as epidemic, two-hops, spray and wait, etc. After introducing the framework, we present examples of its application to derive the packet delivery delay and communication cost distribution of two such protocols, namely epidemic and two-hops routing. \noindent Characterizing packet delivery delay and communication cost distribution is important to investigate fundamental properties of delay tolerant networks. As an example, we show how packet delivery delay distribution can be used to estimate how epidemic routing performance changes in presence of different degrees of node cooperation within the network. More specifically, we consider fully cooperative, non-cooperative, and probabilistic cooperative scenarios, and derive nearly exact expressions of the packet delivery rate under these scenarios based on our proposed framework. The comparison of the obtained packet delivery rate estimation in the various cooperation scenarios suggests that even a modest level of node cooperation (probabilistic cooperation with a low probability of cooperation) is sufficient to achieve 2--fold performance improvement with respect to the most pessimistic scenario in which all potential forwarders drop packets.