"Routing in a Delay Tolerant Network"
We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no end-to-end path may ever exist at one time. This situation limits the applicability of traditional routing approaches which tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating algorithms in such environments and use the framework and simulations to compare several algorithms with respect to their performance and required knowledge about network topology and traffic demands. We find that, as expected, those algorithms with limited knowledge tend to perform poorly, but we also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for such environments. To the best of our knowledge this is the first such investigation of the routing issues in DTNs. This is joint work with Sushant Jain (Univ. of Washington) and Rabin Patra (UC Berkeley).