skip to main content
10.1145/1287791.1287797acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
Article

Analysis of simple counting protocols for delay-tolerant networks

Published: 14 September 2007 Publication History

Abstract

Mobile Wireless Delay-Tolerant Networks (DTNs) are wireless networks that suffer from intermittent connectivity, but enjoy the benefit of mobile nodes that can store and forward packets or messages, and can act as relays, bringing packets and messages closer to their destination through a selective forwarding policy. Many DTN protocols compensate for the unpredictability of the network by distributing multiple message copies in the hopes that at least one will eventually be delivered. As the number of message carriers becomes large these schemes experience diminishing marginal benefits from the addition of more message carriers. We describe and analyze the Simple Counting Protocol, an extremely simple and robust method for limiting the fraction of nodes that carry a copy of a message. We examine the performance of this protocol in conjunction with several abstract mobility models and show that the protocol performs reasonably well in diverse circumstances. The Simple Counting Protocol does not assume much about node mobility, and therefore should be useful for applications where little is known about node encounter patterns. The simplicity of its implementation will hopefully make it a useful substitute for epidemic routing as a naive lower bound in protocol performance comparisons.
We also show how the same simple techniques and principles can be applied in conjunction with more complex heuristic DTN protocols to reduce network resource usage, a scheme we call Intermediate Immunity.

References

[1]
K. Fall. A delay-tolerant network architecture for challenged internets. In ACM SIGCOMM 2003, 2003.
[2]
S. Jain, M. Demmer, R. Patra, and K. Fall. Using redundancy to cope with failures in a delay tolerant network. In SIGCOMM '05, 2005.
[3]
P. Juang, H. Oki, Y. Wang, M. Martonosi, L. Peh, and D. Rubenstein. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with zebranet. In ASPLOS, San Jose, CA, Oct. 2002.
[4]
A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. SIGMOBILE Mob. Comput. Commun. Rev., 7(3):19--20, 2003.
[5]
M. Musolesi, S. Hailes, and C. Mascolo. An ad hoc mobility model founded on social network theory. In MSWiM '04, 2004.
[6]
M. Musolesi, S. Hailes, and C. Mascolo. Adaptive routing for intermittently connected mobile ad hoc networks. In IEEE WOWMOM '05, 2005.
[7]
P. Nain, D. Towsley, B. Liu, and Z. Liu. Properties of random direction models. In INFOCOM 2005, 2005.
[8]
M. Seligman, K. Fall, and P. Mundur. Storage routing for dtn congestion control. Wireless Communications and Mobile Computing, 7(5), 2007.
[9]
R. C. Shah, S. Roy, S. Jain, and W. Brunette. Data mules: Modeling a three-tier architecture for sparse sensor networks. In Proceedings of the 2003 IEEE Workshop on Sensor Network Protocols and Applications, 2003.
[10]
T. Small and Z. J. Haas. Resource and performance tradeoffs in delay-tolerant wireless networks. In ACM SIGCOMM WDTN '05, 2005.
[11]
T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Spray and wait: An effcient routing scheme for intermittently connected mobile networks. In ACM SIGCOMM WDTN '05, 2005.
[12]
A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.
[13]
B. Walker, T. C. Clancy, and J. Glenn. Using localized random walks to model delay-tolerant protocols. In submission.
[14]
W. Zhao, M. Ammar, and E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In MobiHoc '04, 2004.

Cited By

View all
  • (2023)Enhanced Message Replication Technique for DTN Routing ProtocolsSensors10.3390/s2302092223:2(922)Online publication date: 13-Jan-2023
  • (2019)Distributed estimation of global parameters in delay-tolerant networksComputer Communications10.1016/j.comcom.2010.01.01933:13(1472-1482)Online publication date: 4-Jan-2019
  • (2018)Immunization-based redundancy elimination in Mobile Opportunistic Networks-Generated big dataFuture Generation Computer Systems10.1016/j.future.2017.08.05979:P3(920-927)Online publication date: 1-Feb-2018
  • Show More Cited By

Index Terms

  1. Analysis of simple counting protocols for delay-tolerant networks

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        CHANTS '07: Proceedings of the second ACM workshop on Challenged networks
        September 2007
        108 pages
        ISBN:9781595937377
        DOI:10.1145/1287791
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 14 September 2007

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. carrier fraction
        2. delay-tolerant networks
        3. epidemic routing
        4. intermediate immunity
        5. localized random walk
        6. simple counting
        7. time-weighted network storage

        Qualifiers

        • Article

        Conference

        MobiCom/MobiHoc '07
        Sponsor:

        Acceptance Rates

        Overall Acceptance Rate 61 of 159 submissions, 38%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)1
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 18 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2023)Enhanced Message Replication Technique for DTN Routing ProtocolsSensors10.3390/s2302092223:2(922)Online publication date: 13-Jan-2023
        • (2019)Distributed estimation of global parameters in delay-tolerant networksComputer Communications10.1016/j.comcom.2010.01.01933:13(1472-1482)Online publication date: 4-Jan-2019
        • (2018)Immunization-based redundancy elimination in Mobile Opportunistic Networks-Generated big dataFuture Generation Computer Systems10.1016/j.future.2017.08.05979:P3(920-927)Online publication date: 1-Feb-2018
        • (2018)Reasonable routing in delay/disruption tolerant networksFrontiers of Computer Science in China10.1007/s11704-011-0139-25:3(327-334)Online publication date: 11-Dec-2018
        • (2018)Selective Message Forwarding in Delay Tolerant NetworksMobile Networks and Applications10.1007/s11036-008-0096-714:4(387-400)Online publication date: 26-Dec-2018
        • (2016)A message acknowledgment based congestion control (MACC) for delay tolerant networks2016 11th International Conference on Industrial and Information Systems (ICIIS)10.1109/ICIINFS.2016.8263051(815-820)Online publication date: Dec-2016
        • (2014)On the utility of overhearing in DTN2014 IEEE Ninth International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP)10.1109/ISSNIP.2014.6827701(1-6)Online publication date: Apr-2014
        • (2013)Efficient Rostering of Mobile Nodes in Intermittently Connected Passive RFID NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2012.17012:10(2012-2023)Online publication date: 1-Oct-2013
        • (2013)Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and ChallengesIEEE Communications Surveys & Tutorials10.1109/SURV.2012.042512.0005315:2(654-677)Online publication date: Oct-2014
        • (2013)Plankton: An efficient DTN routing algorithm2013 IEEE International Conference on Sensing, Communications and Networking (SECON)10.1109/SAHCN.2013.6645027(550-558)Online publication date: Jun-2013
        • Show More Cited By

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media