towards a formalism for routing in challenged networks
Research on challenged or delay/disruption-tolerant networks has exploded in the past few years with a plethora of algorithms targeted at different versions of the problem. Yet, there have been few formal studies on the fundamental nature of the routing problem in challenged networks. As a step toward closing this gap, we introduce a formal framework relating the problem and solution spaces in challenged networks. We define three fundamental types of challenged networks and several classes of routing mechanisms. We then prove a number of results on the power of each class of routing mechanism in terms of the network types that it can solve. We show that simple variants of MANET protocols can solve two but not all three network types. However, either complete schedule awareness or maximal replication is sufficient to solve even the most general type of challenged network. We extend these results to the bounded-storage and bounded-bandwidth cases. Finally, we briefly discuss a number of avenues in which the core formalism may be extended, including an infinite opportunity model and graph theoretic extensions.
formalism challenged networks disruption tolerant networks