Routing in mobile DTNs: Performance modeling, network coding benefit, and mobility trace modeling
We study three related problems on unicast routing in Disruption-Tolerant Networks (DTNs), i.e., resource-challenged networks where contemporaneous end-to-end connectivity cannot be assumed. We particularly focus on mobility-induced DTNs with opportunistic contacts.
First, we propose a unified framework based on Ordinary Differential Equations (ODEs) to study the performance of a class of epidemic style routing schemes. Derived as the limit of Markov process model under proper scaling, the ODE models capture the propagation and recovery process of data packets under different schemes. We derive a rich set of closed-form results using the ODE models, and quantitatively characterize the performance trade-off achieved by different schemes. We also show that compared to the Markovian model, the ODE models have the additional advantages of analytic tractability and scalability in numerical solution.
Next, we investigate the benefit of applying Random Linear Coding (RLC), a special type of network coding, to epidemic style routing in resource-constrained DTNs. We explore different ways to apply network coding, and study both the case where there is a single block of packets propagating through the network, and the case where blocks of packets arrive continuously to multiple unicast flows. Our results show that due to its increased randomness, the RLC-based scheme achieves the minimal block delivery delay with high probability and improves the block delivery delay versus number of transmission trade-off. The relative benefit of network coding is even more significant when the node buffer is limited.
Last, we study mobility traces taken from UMass DieselNet, an operational bus-based DTN. We analyze the bus-to-bus contact traces in order to develop a generative model that can be used to generate synthetic traces with similar DTN routing performance as the original trace. Focusing on inter-contact times, we show that an aggregate model for the inter-contact time is too coarse a model to accurately capture DTN routing performance. We then construct a route-level inter-contact time model based on the trace, which captures interesting mobility structure within the trace and is shown to capture epidemic routing performance more accurately than the aggregate model.