Optimal and achievable cost/delay tradeoffs in delay-tolerant networks

Abstract

Tradeoffs between the packet delivery delay and various types of packet transportation cost are a recurring theme in Delay-Tolerant Networks (DTNs). In this work we study such tradeoffs, first in a general and then in a mobile wireless setting. In the general setting, we capture the tradeoff between the delivery delay of a packet and its transportation cost (which comprises a transmission component and a storage component) on the cost-delay plane using the Optimal Cost/Delay Curve (OC/DC), for the case when the packet follows optimal routes, and the Achievable Cost/Delay Curve (AC/DC), for the case when a specific (suboptimal) routing protocol is used. Applying the framework of the general setting to mobile wireless DTNs, we evaluate a novel set of geographic routing protocols with delay-tolerant features against both state-of-the-art routing protocols (using their respective average AC/DCs) and also optimal routing (described in terms of the average OC/DC). Compared to the state-of-the-art protocols, our protocols are shown to achieve cost/delay tradeoffs much closer to the optimal one.