Planning and Learning Algorithms for Routing in Disruption-Tolerant Networks


M. -O. Stehr and C. Talcott, “Planning and learning algorithms for routing in Disruption-Tolerant Networks,” MILCOM 2008 – 2008 IEEE Military Communications Conference, 2008, pp. 1-8, doi: 10.1109/MILCOM.2008.4753336.


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.

Read more from SRI