Planning and Learning Algorithms for Routing in Disruption-Tolerant Networks

Abstract

We give an overview of algorithms that we have been developing in the DARPA disruption-tolerant networking program, which aims at improving communication in networks with intermittent and episodic connectivity. Thanks to the use of network caching, this can be accomplished without the need for a simultaneous end-to-end path that is required by traditional Internet and mobile ad-hoc network (MANET) protocols. We employ a disciplined two-level approach that clearly distinguishes the dissemination of application content from the dissemination of network-related knowledge, each of which can be supported by different algorithms. Specifically, we present probabilisitc reflection, a single-message protocol enabling the dissemination of knowledge in strongly disrupted networks. For content dissemination, we present two approaches, namely a symbolic planning algorithm that exploits partially predictable temporal behavior, and a distributed and disruption-tolerant reinforcement learning algorithm that takes into account feedback about past performance.