DTN routing as a resource allocation problem
Top Cited Papers
- 27 August 2007
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 37 (4), 373-384
- https://doi.org/10.1145/1282427.1282422
Abstract
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.Keywords
This publication has 25 references indexed in Scilit:
- Surviving attacks on disruption-tolerant networks without authenticationPublished by Association for Computing Machinery (ACM) ,2007
- Performance Modeling of Epidemic RoutingLecture Notes in Computer Science, 2006
- Bridging the digital divide: storage media + postal network = generic high-bandwidth communicationACM Transactions on Storage, 2005
- Network coding for efficient communication in extreme networksPublished by Association for Computing Machinery (ACM) ,2005
- Resource and performance tradeoffs in delay-tolerant wireless networksPublished by Association for Computing Machinery (ACM) ,2005
- Spray and waitPublished by Association for Computing Machinery (ACM) ,2005
- Practical routing in delay-tolerant networksPublished by Association for Computing Machinery (ACM) ,2005
- Probabilistic Routing in Intermittently Connected NetworksLecture Notes in Computer Science, 2004
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problemsPublished by Association for Computing Machinery (ACM) ,1999
- A Minimum Delay Routing Algorithm Using Distributed ComputationIEEE Transactions on Communications, 1977