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

Towards a formalism for routing in challenged networks

Published: 14 September 2007 Publication History

Abstract

Research on challenged or delay/disruption-tolerant networks has exploded in the past few years with a plethora of algorithms targeted at different versions of the problem. Yet, there have been few formal studies on the fundamental nature of the routing problem in challenged networks. As a step toward closing this gap, we introduce a formal framework relating the problem and solution spaces in challenged networks. We define three fundamental types of challenged networks and several classes of routing mechanisms. We then prove a number of results on the power of each class of routing mechanism in terms of the network types that it can solve. We show that simple variants of MANET protocols can solve two but not all three network types. However, either complete schedule awareness or maximal replication is sufficient to solve even the most general type of challenged network. We extend these results to the bounded-storage and bounded-bandwidth cases. Finally, we briefly discuss a number of avenues in which the core formalism may be extended, including an infinite opportunity model and graph theoretic extensions.

References

[1]
Wizzy project. http://www.wizzy.org.za.
[2]
A. V. A. Balasubramanian, B. N. Levine. Dtn routing as a resource allocation problem. In Proc. ACM SIGCOMM Aug 2007.
[3]
J.-Y. Boudec and P. Thiran. Network Calculus: A Theory of Deterministic Queueing Systems for the Internet Springer, LNCS, 2001.
[4]
B. Burns, O. Brock, and B. Levine. Mv routing and capacity building in disruption tolerant networks. In In Proc. IEEE Infocom August 2005.
[5]
D. Dolev and J. Welch. Crash resilient communications in dynamic networks. IEEE Transactions on Computers 1997.
[6]
P. J. et al. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with zebranet. In Proc. ASPLOS Oct 2002.
[7]
S. B. et al. Delay-tolerant networking: An approach to interplanetary internet. IEEE Communications Magazine June, 2003.
[8]
V. C. et al. Delay-tolerant network architecture, July 2004. Internet-Draft.
[9]
A. Ferreira. On models and algorithms for dynamic communication networks: the case for evolving graphs. In In Proc. ALGOTEL 2002.
[10]
F. Harary. Graph Theory Addison Wesley, 1995.
[11]
K. Harras, K. Almeroth, and E. Belding-Royer. Delay tolerant mobile networks (dtmns): Controlled flooding schemes in sparse mobile networks, 2005.
[12]
J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages and Computation Addison Wesley, 1979.
[13]
S. Jain, M. Demmer, R. Patra, and K. Fall. Using redundancy to cope with failures in a delay tolerant network. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications pages 109--120, 2005.
[14]
S. Jain, K. Fall, and R. Patra. Routing in a delay tolerant network. In SIGCOMM Aug 2004.
[15]
E. Jones, L. Li, and P. Ward. Practical routing in delay-tolerant networks. In In Proc. ACM WDTN 2005.
[16]
A. Lindgren, A. Doria, and O. Scheln. Probabilistic routing in intermittently connected networks. In Proc. ACM Mobihoc 2003.
[17]
P. Marshall. The disruption tolerant networking program, 2005. http://www.darpa.mil/sto/solicitations/DTN/briefs.htm.
[18]
S. Merugu, M. Ammar, and E. Zegura. Space-time routig in wireless networks with predictable mobility. In Georgia Tech Report GIT-CC-04-07 March 2004.
[19]
A. Pentland, R. Fletcher, and A. Hasson. Daknet: Rethinking connectivity in developing nations. IEEE Computer 37(1), 78--83 Jan 2004.
[20]
R. Ramanathan, R. Hansen, P. Basu, R. Hain, and R. Krishnan. Prioritized epidemic for routing in opportunistic networks. In Proc. ACM MobiOpp June 2007.
[21]
J. Sobrinho. An algebraic theory of dynamic network routing. IEEE/ACM Transactions on Networking Oct 2005. (13)5.
[22]
T. Spyropoulos, K. Psounis, and C. Raghavendra. Spray and wait: An efficient routing scheme for intermittently connected wireless networks. In Proc. ACM Sigcomm Workshop on DTN 2005.
[23]
A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks, 2000.
[24]
X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. In In Proc. IFIP Networking 2006.
[25]
Z. Zhang. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Communication Surveys and Tutorials Jan 2006.

Cited By

View all
  • (2016)A DTN routing strategy based on neural networks for urban bus transportation systemJournal of Network and Computer Applications10.1016/j.jnca.2016.02.00264:C(216-228)Online publication date: 1-Apr-2016
  • (2015)Routing with adaptive flooding in heterogeneous mobile networks2015 7th International Conference on Communication Systems and Networks (COMSNETS)10.1109/COMSNETS.2015.7098694(1-8)Online publication date: Jan-2015
  • (2014)Multidimensional (Temporal–Spatio–Social) Structural Characteristics of Mobile Social NetworksMobile Social Networking and Computing10.1201/b17370-5(29-58)Online publication date: 19-Aug-2014
  • Show More Cited By

Index Terms

  1. Towards a formalism for routing in challenged 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. challenged networks
      2. disruption tolerant networks
      3. formalism

      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)3
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 18 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2016)A DTN routing strategy based on neural networks for urban bus transportation systemJournal of Network and Computer Applications10.1016/j.jnca.2016.02.00264:C(216-228)Online publication date: 1-Apr-2016
      • (2015)Routing with adaptive flooding in heterogeneous mobile networks2015 7th International Conference on Communication Systems and Networks (COMSNETS)10.1109/COMSNETS.2015.7098694(1-8)Online publication date: Jan-2015
      • (2014)Multidimensional (Temporal–Spatio–Social) Structural Characteristics of Mobile Social NetworksMobile Social Networking and Computing10.1201/b17370-5(29-58)Online publication date: 19-Aug-2014
      • (2014)Predicting journeys for DTN routing in a public transportation system2014 IEEE 10th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)10.1109/WiMOB.2014.6962216(494-499)Online publication date: Oct-2014
      • (2014)GeoSprayInformation Fusion10.1016/j.inffus.2011.11.00315(102-113)Online publication date: 1-Jan-2014
      • (2013)Disrupted Adaptive Routing: Gossip-Based Routing in Delay-Tolerant NetworksMILCOM 2013 - 2013 IEEE Military Communications Conference10.1109/MILCOM.2013.190(1099-1104)Online publication date: Nov-2013
      • (2013)Quasi-opportunistic contact prediction in delay/disruption tolerant networkGlobal Information Infrastructure Symposium - GIIS 201310.1109/GIIS.2013.6684382(1-6)Online publication date: Oct-2013
      • (2012)Searching for Black Holes in SubwaysTheory of Computing Systems10.5555/2556794.255679550:1(158-184)Online publication date: 1-Jan-2012
      • (2011)Time-varying graphs and dynamic networksProceedings of the 10th international conference on Ad-hoc, mobile, and wireless networks10.5555/2032462.2032496(346-359)Online publication date: 18-Jul-2011
      • (2011)Understanding stateful vs stateless communication strategies for ad hoc networksProceedings of the 17th annual international conference on Mobile computing and networking10.1145/2030613.2030649(313-324)Online publication date: 19-Sep-2011
      • 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