Routing in mobile DTNs: Performance modeling, network coding benefit, and mobility trace modeling

2007 2007

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Computer science
0984: Computer science
Identifier / keyword
Applied sciences; Disruption Tolerant Network; Mobility trace modeling; Network coding; Performance modeling
Routing in mobile DTNs: Performance modeling, network coding benefit, and mobility trace modeling
Zhang, Xiaolan
Number of pages
Publication year
Degree date
School code
DAI-B 68/11, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Kurose, Jim; Towsley, Don
Committee member
Gong, Weibo; Levine, Brian N.
University of Massachusetts Amherst
Computer Science
University location
United States -- Massachusetts
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.