Aruna Balasubramanian
Brian Levine
Arun Venkataramani
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.
- One laptop per child. http://www.laptop.org.Google Scholar
- TIER Project, UC Berkeley. http://tier.cs.berkeley.edu/.Google Scholar
- A. Balasubramanian, B. N. Levine, and A. Venkataramani. DTN Routing as a Resource Allocation Problem. Technical Report 07-37, UMass Amherst, 2007.Google ScholarDigital Library
- N. Banerjee, M. D. Corner, and B. N. Levine. An Energy-Efficient Architecture for DTN Throwboxes. In Proc. IEEE Infocom, May 2007.Google ScholarDigital Library
- J. Burgess, G. Bissias, M. D. Corner, and B. N. Levine. Surviving Attacks on Disruption-Tolerant Networks without Authentication. In Proc. ACM Mobihoc, September 2007. Google ScholarDigital Library
- J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE Infocom, April 2006.Google ScholarCross Ref
- B. Burns, O. Brock, and B. N. Levine. MV Routing and Capacity Building in Disruption Tolerant Networks. In Proc. IEEE Infocom, pages 398--408, March 2005.Google ScholarCross Ref
- G. Casella and R. L. Berger. Statistical Inference. Second Edition. Duxbury, 2002.Google Scholar
- A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms. In Proc. IEEE Infocom, May 2006.Google ScholarCross Ref
- C. Chekuri, S. Khanna, and F. B. Shepherd. An O(√(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Theory of Computing, 2(7):137--146, 2006.Google ScholarCross Ref
- CPLEX. http://www.ilog.com.Google Scholar
- J. Davis, A. Fagg, and B. N. Levine. Wearable Computers and Packet Transport Mechanisms in Highly Partitioned Ad hoc Networks. In Proc. IEEE ISWC, pages 141--148, October 2001. Google ScholarDigital Library
- P. Desnoyers, D. Ganesan, H. Li, M. Li, and P. Shenoy. PRESTO: A Predictive Storage Architecture for Sensor Networks. In Proc. USENIX HotOS, June 2005. Google ScholarDigital Library
- R. Gallager. A Minimum Delay Routing Algorithm Using Distributed Computation. In IEEE Trans. on Communications, volume 25, pages 73--85, Jan 1977.Google ScholarCross Ref
- N. Garg, S. Sobti, J. Lai, F. Zheng, K. Li, A. Krishnamurthy, and R. Wang. Bridging the Digital Divide. ACM Trans. on Storage, 1(2):246--275, May 2005. Google ScholarDigital Library
- V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis. Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. In Proc. ACM STOC, pages 19--28, 1999. Google ScholarDigital Library
- B. Hull et al. CarTel: A Distributed Mobile Sensor Computing System. In Proc. ACM SenSys, pages 125--138, Oct. 2006. Google ScholarDigital Library
- S. Jain, M. Demmer, R. Patra, and K. Fall. Using Redundancy to Cope with Failures in a Delay Tolerant Network. In Proc. ACM Sigcomm, pages 109--120, 2005. Google ScholarDigital Library
- S. Jain, K. Fall, and R. Patra. Routing in a Delay Tolerant Network. In Proc. ACM Sigcomm, pages 145--158, Aug. 2004. Google ScholarDigital Library
- E. Jones, L. Li, and P. Ward. Practical Routing in Delay-Tolerant Networks. In Proc. ACM Chants Workshop, pages 237--243, Aug. 2005. Google ScholarDigital Library
- F. Kelly, A. Maulloo, and D. Tan. Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability. In J. Op. Res. Society, volume 49, pages 237--252, 1998.Google Scholar
- J. Leguay, T. Friedman, and V. Conan. DTN Routing in a Mobility Pattern Space. In Proc. ACM Chants Workshop, pages 276--283, Aug. 2005. Google ScholarDigital Library
- A. Lindgren, A. Doria, and O. Schelén. Probabilistic Routing in Intermittently Connected Networks. In Proc. SAPIR Workshop, pages 239--254, Aug. 2004.Google ScholarCross Ref
- A. Maffei, K. Fall, and D. Chayes. Ocean Instrument Internet. In Proc. AGU Ocean Sciences Conf., Feb 2006.Google Scholar
- W. Mitchener and A. Vadhat. Epidemic Routing for Partially Connected Ad hoc Networks. Technical Report CS-2000-06, Duke Univ., 2000.Google Scholar
- J. Ott and D. Kutscher. A Disconnection-Tolerant Transport for Drive-thru Internet Environments. In Proc. IEEE INFOCOM, pages 1849--1862, Mar. 2005.Google ScholarCross Ref
- C. Papadimitriou. Computational Complexity. Addison Wesley, 1994.Google Scholar
- J. Partan, J. Kurose, and B. N. Levine. A Survey of Practical Issues in Underwater Networks. In Proc. ACM WUWNet, pages 17--24, Sept. 2006. Google ScholarDigital Library
- R. C. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks. In Proc. IEEE SNPA, pages 30--41, May 2003.Google ScholarCross Ref
- T. Small and Z. Haas. Resource and Performance Tradeoffs in Delay-Tolerant Wireless Networks. In Proc. ACM WDTN, pages 260--267, Aug. 2005. Google ScholarDigital Library
- T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks. In Proc. ACM WDTN, pages 252--259, Aug. 2005. Google ScholarDigital Library
- T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Performance analysis of mobility-assisted routing. In ACM MobiHoc, pages 49--60, May 2006. Google ScholarDigital Library
- T. Spyropoulos and K. Psounis and C. Raghavendra. Single-copy Routing in Intermittently Connected Mobile Networks. In IEEE SECON, October 2004.Google ScholarCross Ref
- J. Widmer and J. -Y. Le Boudec. Network Coding for Efficient Communication in Extreme Networks. In Proc. ACM WDTN, pages 284--291, Aug. 2005. Google ScholarDigital Library
- Y. -C. Tseng and S. -Y. Ni and Y. -S. Chen and J. -P. Sheu. The Broadcast Storm Problem in a Mobile Ad hoc Network. Springer Wireless Networks, 8(2/3):153--167, 2002. Google ScholarDigital Library
- P. Zhang, C. M. Sadler, S. A. Lyon, and M. Martonosi. Hardware Design Experiences in ZebraNet. In Proc. ACM SenSys, pages 227--238, Nov. 2004. Google ScholarDigital Library
- X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance Modeling of Epidemic Routing. In Proc. IFIP Networking, May 2006. Google ScholarDigital Library
Index Terms
- DTN routing as a resource allocation problem
Recommendations
DTN routing as a resource allocation problem
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communicationsMany 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 ...
The evolution of a DTN routing protocol - PRoPHETv2
CHANTS '11: Proceedings of the 6th ACM workshop on Challenged networksResearch within Delay- and Disruption Tolerant Networks (DTN) has evolved into a mature research area. PRoPHET is a routing protocol for DTNs that was developed when DTN research was in its infancy and which has been studied by many. In this paper we ...
Replication routing in DTNs: a resource allocation approach
Routing protocols for disruption-tolerant networks (DTNs) 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 ...
Comments