More Web Proxy on the site http://driver.im/

article

Replication routing in DTNs: a resource allocation approach

Authors:

Aruna Balasubramanian,

Brian Neil Levine,

Arun VenkataramaniAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 2

Pages 596 - 609

https://doi.org/10.1109/TNET.2009.2036365

Published: 01 April 2010 Publication History

Abstract

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 likelihood of finding a path with limited information, and so these approaches have only an incidental effect on such routing metrics as maximum or average delivery delay. In this paper, we present RAPID, an intentional DTN routing protocol that can optimize a specific routing metric such as the worst-case delivery delay 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 that determine how packets should be replicated in the system. We evaluate RAPID rigorously through a prototype 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 outdoor DTN. 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.

References

[1]

"One laptop per child," {Online}. Available: http://www.laptop.org

[2]

"TIER project," UC Berkeley {Online}. Available: http://tier.cs. berkeley.edu/

[3]

A. Balasubramanian, B. N. Levine, and A. Venkataramani, "Replication routing in DTNs: A resource allocation approach," UMass Amherst, Tech. Rep. 09-51, 2009.

[4]

N. Banerjee, M. D. Corner, and B. N. Levine, "An energy-efficient architecture for DTN throwboxes," in Proc. IEEE INFOCOM, May 2007, pp. 776-784.

[5]

C. Boldrini, M. Conti, and A. Passarella, "Modelling data dissemination in opportunistic networks," in Proc. ACM CHANTS, New York, NY, 2008, pp. 89-96.

Digital Library

[6]

J. Burgess, G. Bissias, M. D. Corner, and B. N. Levine, "Surviving attacks on disruption-tolerant networks without authentication," in Proc. ACM MobiHoc, Sep. 2007, pp. 61-70.

Digital Library

[7]

J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, "MaxProp: Routing for vehicle-based disruption-tolerant networks," in Proc. IEEE INFOCOM, Apr. 2006, pp. 1-11.

[8]

B. Burns, O. Brock, and B. N. Levine, "MV routing and capacity building in disruption tolerant networks," in Proc. IEEE INFOCOM, Mar. 2005, pp. 398-408.

[9]

G. Casella and R. L. Berger, Statistical Inference, 2nd ed. Pacific Grove, CA: Duxbury, 2002.

[10]

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, Apr. 2006, pp. 1-13.

[11]

C. Chekuri, S. Khanna, and F. B. Shepherd, "An O(√(n)) approximation and integrality gap for disjoint paths and unsplittable flow," Theory Comput., vol. 2, no. 7, pp. 137-146, 2006.

[12]

"CPLEX," {Online}. Available: http://www.ilog.com

[13]

J. Davis, A. Fagg, and B. N. Levine, "Wearable computers and packet transport mechanisms in highly partitioned ad hoc networks," in Proc. IEEE ISWC, Oct. 2001, pp. 141-148.

Digital Library

[14]

N. Garg, S. Sobti, J. Lai, F. Zheng, K. Li, A. Krishnamurthy, and R. Wang, "Bridging the digital divide," ACM Trans. Storage, vol. 1, no. 2, pp. 246-275, May 2005.

Digital Library

[15]

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, 1999, pp. 19-28.

Digital Library

[16]

B. Hull et al., "CarTel: A distributed mobile sensor computing system," in Proc. ACM SenSys, Oct. 2006, pp. 125-138.

Digital Library

[17]

S. Jain, M. Demmer, R. Patra, and K. Fall, "Using redundancy to cope with failures in a delay tolerant network," in Proc. ACM SIGCOMM, Aug. 2005, pp. 109-120.

Digital Library

[18]

S. Jain, K. Fall, and R. Patra, "Routing in a delay tolerant network," in Proc. ACM SIGCOMM, Aug. 2004, pp. 145-158.

Digital Library

[19]

E. Jones, L. Li, and P. Ward, "Practical routing in delay-tolerant networks," in Proc. ACM CHANTS, Aug. 2005, pp. 237-243.

Digital Library

[20]

J. Leguay, T. Friedman, and V. Conan, "DTN routing in a mobility pattern space," in Proc. ACM CHANTS, Aug. 2005, pp. 276-283.

Digital Library

[21]

A. Lindgren, A. Doria, and O. Schelén, "Probabilistic routing in intermittently connected networks," in Proc. SAPIR Workshop, Aug. 2004, pp. 239-254.

[22]

A. Maffei, K. Fall, and D. Chayes, "Ocean instrument Internet," in Proc. AGU Ocean Sci. Conf., Feb. 2006, OS45D-14.

[23]

W. Mitchener and A.Vadhat, "Epidemic routing for partially connected ad hoc networks," Duke Univ., Tech. Rep. CS-2000-06, 2000.

[24]

J. Ott and D. Kutscher, "A disconnection-tolerant transport for drivethru Internet environments," in Proc. IEEE INFOCOM, Mar. 2005, pp. 1849-1862.

[25]

C. Papadimitriou, Computational Complexity. Reading, MA: Addison Wesley, 1994.

[26]

J. Partan, J. Kurose, and B. N. Levine, "A survey of practical issues in underwater networks," in Proc. ACM WUWNet, Sep. 2006, pp. 17-24.

Digital Library

[27]

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, May 2003, pp. 30-41.

[28]

T. Small and Z. Haas, "Resource and performance tradeoffs in delay-tolerant wireless networks," in Proc. ACM WDTN, Aug. 2005, pp. 260-267.

Digital Library

[29]

T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Spray and wait: An efficient routing scheme for intermittently connected mobile networks," in Proc. ACM WDTN, Aug. 2005, pp. 252-259.

Digital Library

[30]

T. Spyropoulos, K. Psounis, and C. S. Raghavendra, "Performance analysis of mobility-assisted routing," in Proc. ACM MobiHoc, May 2006, pp. 49-60.

Digital Library

[31]

T. Spyropoulos, K. Psounis, and C. Raghavendra, "Single-copy routing in intermittently connected mobile networks," in Proc. IEEE SECON, Oct. 2004, pp. 235-244.

[32]

J. Widmer and J.-Y. Le Boudec, "Network coding for efficient communication in extreme networks," in Proc. ACM WDTN, Aug. 2005, pp. 284-291.

Digital Library

[33]

Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network," Wireless Netw., vol. 8, no. 2/3, pp. 153-167, 2002.

Digital Library

[34]

P. Zhang, C. M. Sadler, S. A. Lyon, and M. Martonosi, "Hardware design experiences in ZebraNet," in Proc. ACM SenSys, Nov. 2004, pp. 227-238.

Digital Library

[35]

X. Zhang, G. Neglia, J. Kurose, and D. Towsley, "Performance modeling of epidemic routing," in Proc. IFIP Netw., May 2006.

Digital Library

Cited By

Verma ASavita Kumar S(2021)Routing Protocols in Delay Tolerant Networks: Comparative and Empirical AnalysisWireless Personal Communications: An International Journal10.1007/s11277-020-08032-4118:1(551-574)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s11277-020-08032-4
Fan XHuang CZhu JFu BHe Z(2019)Replication-Based Data Dissemination in Connected Internet of VehiclesWireless Communications & Mobile Computing10.1155/2019/21505242019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/2150524
Zhang FGao HLiu LLi NWang WFujita MDong JArai M(2019)A trajectory-aware routing algorithm for unmanned aerial vehicle networksProceedings of the 5th International Conference on Communication and Information Processing10.1145/3369985.3369997(259-266)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3369985.3369997
Show More Cited By

Index Terms

Replication routing in DTNs: a resource allocation approach
1. General and reference
  1. Cross-computing tools and techniques
    1. Design
    2. Performance
2. Networks
  1. Network services
    1. Network management

Recommendations

DTN routing as a resource allocation problem
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications

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 ...
DTN routing as a resource allocation problem

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 ...
Surviving attacks on disruption-tolerant networks without authentication
MobiHoc '07: Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing

Disruption-Tolerant Networks (DTNs) deliver data in network environments composed of intermittently connected nodes. Just as in traditional networks, malicious nodes within a DTN may attempt to delay or destroy data in transit to its destination. Such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 2

April 2010

339 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2010

Revised: 04 May 2009

Received: 21 September 2008

Published in TON Volume 18, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
422
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Verma ASavita Kumar S(2021)Routing Protocols in Delay Tolerant Networks: Comparative and Empirical AnalysisWireless Personal Communications: An International Journal10.1007/s11277-020-08032-4118:1(551-574)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s11277-020-08032-4
Fan XHuang CZhu JFu BHe Z(2019)Replication-Based Data Dissemination in Connected Internet of VehiclesWireless Communications & Mobile Computing10.1155/2019/21505242019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/2150524
Zhang FGao HLiu LLi NWang WFujita MDong JArai M(2019)A trajectory-aware routing algorithm for unmanned aerial vehicle networksProceedings of the 5th International Conference on Communication and Information Processing10.1145/3369985.3369997(259-266)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3369985.3369997
Fan XHuang CZhu JFu B(2019)R-DRA: a replication-based distributed randomized algorithm for data dissemination in connected vehicular networksWireless Networks10.1007/s11276-018-01895-325:7(3767-3782)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11276-018-01895-3
Ma HZheng GWu HJi BLi J(2019)A multi attribute decision routing for load-balancing in crowd sensing networkWireless Networks10.1007/s11276-017-1528-825:1(13-28)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11276-017-1528-8
Asadpour MHummel KGiustiniano DDraskovic S(2017)Route or CarryIEEE Transactions on Mobile Computing10.1109/TMC.2016.256129116:3(843-856)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2561291
He ZZhang D(2017)Cost-efficient traffic-aware data collection protocol in VANETAd Hoc Networks10.1016/j.adhoc.2016.09.02155:C(28-39)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.adhoc.2016.09.021
Abbas AShah BKim K(2017)Adaptive Forwarding Scheme for Bounded Time Constraint in Delay Tolerant NetworksWireless Personal Communications: An International Journal10.1007/s11277-017-4269-196:2(1803-1817)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11277-017-4269-1
Khalid ORais RMadani S(2017)Benchmarking and Modeling of Routing Protocols for Delay Tolerant NetworksWireless Personal Communications: An International Journal10.1007/s11277-016-3654-594:3(859-888)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s11277-016-3654-5
Yasmin SBin Rais RQayyum A(2016)Resource aware routing in heterogeneous opportunistic networksInternational Journal of Distributed Sensor Networks10.1155/2016/29079802016(2-2)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2016/2907980
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents