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:
- 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
- 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
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.
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.