DTN routing as a resource allocation problem

By Aruna Devi Balasubramanian, Brian Neil Levine, Arun Venkataramani. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2007

1,153 citations recorded by the source corpus.

Many DTN routing protocols use a variety of mechanisms, including discovering the meeting probabilities among nodes, packet replication, and network coding. The primary focus of these mechanisms is to increase the likelihood of finding a path with limited information, so these approaches have only an incidental effect on such routing metrics as maximum or average delivery latency. In this paper, we present RAPID, an intentional DTN routing protocol that can optimize a specific routing metric such as worst-case delivery latency or the fraction of packets that are delivered within a deadline. The key insight is to treat DTN routing as a resource allocation problem that translates the routing metric into per-packet utilities which determine how packets should be replicated in the system. We evaluate RAPID rigorously through a prototype of RAPID deployed over a vehicular DTN testbed of 40 buses and simulations based on real traces. To our knowledge, this is the first paper to report on a routing protocol deployed on a real DTN at this scale. Our results suggest that RAPID significantly outperforms existing routing protocols for several metrics. We also show empirically that for small loads RAPID is within 10% of the optimal performance.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/5571ff8a4878ac6ad04a24a69e29223d35cc74b7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

CAR: Context-Aware Adaptive Routing for Delay-Tolerant Mobile Networks (2009, background): “In [31], the authors study the DTN routing problem from a resource allocation problem perspective.”
Directional routing and scheduling for green vehicular delay tolerant networks (2012, background): “RAPID [17] is an intentional DTN routing protocol, which treat routing as a resource allocation problem and decides on packet replication according to per-packet utilities.”
PeopleRank: Social Opportunistic Forwarding (2010, background): “In such ad hoc network settings, the devices are often disconnected from each other and use Bluetooth, Wifi, or any other wireless connectivity to exchange and forward data in an opportunistic hop by hop manner.”
Survey of Important Issues in UAV Communication Networks (2016, background): “This is especially critical when nodes have resource constraints [59].”
On the Levy-Walk Nature of Human Mobility (2008, background): “Typically, computer networks are studied using random mobilitymodelsorusingaprobabilisticmodelbasedonaparticular distribution of intercontact times (ICTs), which are defined to be the time durations until two mobile objects meet again after meetingpreviously(e.g.,[ 21 ]).Whilepreviousrandommobility ”
SLAW: A New Mobility Model for Human Walks (2009, background): “Thus, it lacks the regular patterns present in daily human walks.”
Hybrid Satellite-Terrestrial Communication Networks for the Maritime Internet of Things: Key Technologies, Opportunities, and Challenges (2019, neutral): “Various routing methods and protocols have been proposed for terrestrial delay-tolerant ad hoc networks [148], [149], such as epidemic routing [150], probabilistic routing [151], spray”
Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing (2007, background): “As buses travel their routes, they encounter other buses and in some cases are able to establish pair-wise connections and transfer data between them.”
Routing in Delay Tolerant Network (2016, background): “5 Rapid Rapid [9] represents as a utility-driven resource allocation problem.”
Disruption-Tolerant Networking: A Comprehensive Survey on Recent Developments and Persisting Challenges (2012, methodology): “In [96], a utility driven Resource Allocation Protocol for Intentional DTN routing (RAPID) is presented to explicitly optimize a network administrator-specified metric.”
Routing in Socially Selfish Delay Tolerant Networks (2010, methodology): “Since the original algorithms do not define the order of packets to be transmitted during a contact, we adopt the transmission order used in RAPID [5].”
Encounter: based routing in DTNs (2009, background): “Other examples of floodingbased DTN protocols include Prophet [11], RAPID [2] and PREP [14].”
A parsimonious model of mobile partitioned networks with clustering (2009, background): “, [1], [12], [17].”