A Markov Decision Process for Routing in Space DTNs with Uncertain Contact Plans

Delay Tolerant Networking (DTN) has been proposed to provide efficient and autonomous store-carry-and-forward data transport for space-terrestrial networks. Since these networks relay on scheduled contact plans, Contact Graph Routing (CGR) can be used to optimize routing and data delivery performance. However, scheduling uncertainties and faults induced by the harsh space environment can provoke different network connectivity than the one assumed in the provisioned contact plan. In this work, we develop a theoretical model based on a Markov Decision Process (MDP) to determine the Best Routing Under Failures (BRUF). Existing routing solutions are thus compared with the analytical bound obtained from implementing BRUF in PRISM. Results over random networks prove that state-of-the-art CGR is close to the theoretical delivery ratio and that supervised data replication is mandatory to further improve the performance under uncertain contact plans.