Understanding stateful vs stateless communication strategies for ad hoc networks

Structural change and uncertainty are fundamental properties of an ad hoc network, making it difficult to develop communication strategies, i.e., network-level approaches to transport data from sender to receiver. At a basic level, change and uncertainty affect how long any state maintained by a communication strategy remains useful, and so influence the trade-offs made to collect that state. In this paper, we introduce a framework for organizing the decision space for deciding when a communication strategy should maintain state, and what type of state should be maintained, in an ad hoc network. The framework is based on our observation that three network properties (connectivity, unpredictability, and resource contention) determine when state is useful. Using the framework, we make three contributions. First, we illustrate the framework by showing an instantiation in terms of specific measures that can be used to describe a network setting. Second, we validate the framework by showing it correctly and consistently organizes the decision space for different communication strategies. Finally, we demonstrate the analytic power of the framework by using it to (1) uncover surprising aspects of well-known traces, and (2) identify the need for, and value of, a new strategy for network communication.