Time Correlated Update in Delay Tolerant Networks

We define an end-to-end DTN model and an accompanying data production model. We then consider the performance of patterned memory-clearing sending policies. Subsequently we examine an oracle-based policy, deriving the theoretical optimum performance bound of such a system. We compare this bound with the class of α-parameterized stochastic sending policies and show a convergence of this policy class with the theoretic bound as node memory windows increase towards infinity.

Our model considers the situation in which a sending node produces a new data item each time-step. This node has no timely access to feedback from a downstream sink and can make one of two decisions:
  1. send the full data item produced at this time-step, with lower likelihood of the data arriving but certainty that it can be decoded by the sink
  2. send an encoded difference between this time-step's data item and those sent previously, with higher likelihood of arrival, but lower likelihood of the data being decoded at the sink
convergence of alpha policies model

Our results indicate that a policy which stochastically chooses one of these options based on a tunable parameter &alpha asymptotically approaches the optimal performance that could be achieved with use of a perfect feedback oracle, as the memory window increases. Moreover, much of this convergence is achieved relatively quickly, indicating this may in fact be a good heuristic.

Selected Publications:

Joshua Reich, Vishal Misra and Dan Rubenstein, The Time Correlated Update Problem, Performance Evaluation Review, ACM Sigmetrics, Smirni, Evgenia, ACM Special Interest Group on Measurement and Evaluation, Volume 35, Number 2, pp. 33-35, September, 2007. [Paper] [BibTeX]