| The ubiquity of small devices equipped with communication capability has raised interesting issues in providing message passing capability across a network of such devices. Various constraints such as limited energy, storage, and mobility etc. makes it impossible to have a continuous end-to-end path, an assumption which is at the heart of traditional networking and Internet. Such environments with challenging conditions and intermittent connectivity are referred to as Delay Tolerant Networks (DTNs). DTNs arise in various contexts such as satellite networks, deep space networks, sparse mobile ad-hoc networks, sensor networks etc. In this dissertation, we take the first step towards understanding the problem of routing in DTNs. Two facets of the DTN routing problem are considered. First, we consider the problem of routing when the link dynamics are known in advance. Second, we investigate how to use replication to deal with path failures and incomplete information about link dynamics.; For DTNs with known or predictable link dynamics, we propose a framework for developing routing algorithms based on assigning time varying costs to links. Dijkstra's shortest path algorithm is adapted to find efficient routes over the time varying DTN topology. Our cost function can also account for queuing in the network and route around congested points. It is shown that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. |
