Gallagher, B., D. Jensen, and B. N. Levine (2004). Explaining routing performance in disruption tolerant networks. University of Massachusetts Amherst, Technical Report 05-57.

Abstract

Many routing algorithms for both traditional and ad hoc networks require a complete and contemporaneous path of peers from source to destination. Disruption Tolerant Networks (DTNs) attempt to deliver messages despite a frequently disconnected link layer (e.g., due to peer mobility, limited communication range, and power management limitations). While several algorithms have been proposed for routing in DTNs, this has not yet led to an understanding of the fundamental issues underlying routing performance in these networks. In this paper we explain the performance of routing algorithms for DTNs in terms of their ability to utilize a set of three no-cost drop criteria. The criteria are necessary and sufficient for identifying messages that may be dropped without degrading the overall delivery rate. The criteria identify whether a route exists with sufficient bandwidth, whether a message has been delivered already, and whether some other peer will deliver the message. We also use the criteria to design a new routing algorithm that we call NoCostDrop, which appears to be the first routing algorithm to take advantage of all three criteria. We show that NoCostDrop outperforms existing algorithms over a wide range of network conditions. Most novel in our approach is the use of a distributed list of delivered messages, which can easily be combined with existing routing algorithms to improve their performance.

Text

A PDF version of this paper is available.

---

Feedback Fineprint