  Delay-Tolerant Networks (DTN) enable store-carry-and-forward data
transmission in networks challenged by frequent disruptions and high latency.
Existing classification distinguishes between scheduled and probabilistic DTNs,
for which specific routing solutions have been developed. In this paper, we
uncover a gap in-between where uncertain contact plans can be exploited to
enhance data delivery in many practical scenarios described by probabilistic
schedules available a priori. Routing under uncertain contact plans (RUCoP) is
next formulated as a multiple-copy Markov Decision Process and then exported to
local-knowledge (L-RUCoP) and Contact Graph Routing extensions (CGR-UCoP) which
can be implemented in the existing DTN protocol stack. RUCoP and its
derivations are evaluated in a first extensive simulation benchmark for DTNs
under uncertain contact plans comprising both random and realistic scenarios.
Results confirm that RUCoP and L-RUCoP closely approach the ideal delivery
ratio of an oracle, while CGR-UCoP improves state-of-the-art DTN routing
schemes delivery ratio up to 25%.
