skip to main content
10.1145/1298306.1298330acmconferencesArticle/Chapter ViewAbstractPublication PagesimcConference Proceedingsconference-collections
Article

Diversity of forwarding paths in pocket switched networks

Published: 24 October 2007 Publication History

Abstract

Forwarding in Delay Tolerant Networks (DTNs) is a challenging problem. We focus on the specific issue of forwarding in an environment where mobile devices are carried by people in a restricted physical space (a conference) and contact patterns are not predictable. We show for the first time a path explosion phenomenon between most pairs of nodes. This means that, once the first path reaches the destination, the number of subsequent paths grows rapidly with time, so there usually exist many near-optimal paths. We study the path explosion phenomenon both analytically and empirically. Our results highlight the importance of unequal contact rates across nodes for understanding the performance of forwarding algorithms. We also find that a variety of well-known forwarding algorithms show surprisingly similar performance in our setting and we interpret this fact in light of the path explosion phenomenon.

References

[1]
V. Borrel, M. D. de Amorim, and S. Fdida. A preferential attachment gathering mobility model. IEEE Communications Letters, 9(10):900--902, 2005.
[2]
T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. WCMC: Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):483--502, 2002.
[3]
A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Pocket Switched Networks: Real-world mobility and its consequences for Opportunistic Forwarding. Technical Report UCAM-CL-TR-617, University of Cambridge, 2005.
[4]
A. Chaintreau, P. Hui, J. Scott, R. Gass, J. Crowcroft, and C. Diot. Impact of human mobility on the performance of opportunistic forwarding algorithms. In Proceedings of IEEE INFOCOM, 2006.
[5]
V. Conan, J. Leguay, and T. Friedman. The heterogeneity of inter-contact time distributions: its importance for routing in delay tolerant networks. ArXiv Computer Science e-prints, Sept. 2006.
[6]
H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli. Age matters: efficient route discovery in mobile ad hoc networks using encounter ages. In ACM MobiHoc '03, pages 257--266, 2003.
[7]
M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. Netw., 10(4):477--486, 2002.
[8]
M. Grossglauser and M. Vetterli. Locating mobile nodes with ease: learning efficient routes from encounter histories alone. IEEE/ACM Trans. Netw., 14(3):457--469, 2006.
[9]
P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot. Pocket switched networks and human mobility in conference environments. In WDTN '05.
[10]
S. Jain, K. Fall, and R. Patra. Routing in a Delay Tolerant Network. In ACM SIGCOMM '04.
[11]
E. P. C. Jones, L. Li, and P. A. S. Ward. Practical routing in delay-tolerant networks. In WDTN '05.
[12]
T. G. Kurtz. Limit theorems for sequence of jump markov processes approximating ordinary differential processes. Journal of Applied Probability, pages 344--356, 1971.
[13]
A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. SIGMOBILE Mob. Comput. Commun. Rev., 7(3):19--20, 2003.
[14]
S. Merugu, M. Ammar, and E. Zegura. Routing in space and time in networks with predictable mobility. Technical Report GIT-CC-04-7, Georgia Institute of Technology, 2004.
[15]
M. Musolesi and C. Mascolo. A community based mobility model for ad hoc network research. In REALMAN '06, pages 31--38, 2006.
[16]
E. Nordstrom, C. Diot, R. Gass, and P. Gunningberg. Experiences from measuring human mobility using bluetooth inquiring devices. In MobiEval 2007: System Evaluation for Mobile Platforms, 2007.
[17]
T. Spyropoulos, K. Psounis, and C. Raghavendra. Single-copy routing in intermittently connected mobile networks. In IEEE SECON '04, pages 145--158, 2004.
[18]
T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In ACMWDTN '05, pages 252--259, 2005.
[19]
A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.
[20]
X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. In Proceedings of IFIP Networking, 2006.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement
October 2007
390 pages
ISBN:9781595939081
DOI:10.1145/1298306
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: 24 October 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dtn
  2. forwarding
  3. path diversity
  4. pocket switched networks

Qualifiers

  • Article

Conference

IMC07
Sponsor:
IMC07: Internet Measurement Conference
October 24 - 26, 2007
California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 277 of 1,083 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2023)A Percolation-Based DTNs Routing Using Fountain CodingIoT as a Service10.1007/978-3-031-37139-4_10(106-116)Online publication date: 19-Jul-2023
  • (2022)A replication strategy for mobile opportunistic networks based on utility clusteringAd Hoc Networks10.1016/j.adhoc.2021.102738125:COnline publication date: 1-Feb-2022
  • (2019)A framework for the evaluation of routing protocols in opportunistic networksComputer Communications10.1016/j.comcom.2019.06.003Online publication date: Jun-2019
  • (2018)Multi-layer-based opportunistic data collection in mobile crowdsourcing networksWorld Wide Web10.1007/s11280-017-0482-921:3(783-802)Online publication date: 1-May-2018
  • (2017)A Comprehensive Forwarding Strategy in DTNs: Theory and PracticeIEEE Transactions on Vehicular Technology10.1109/TVT.2017.272144166:12(11220-11232)Online publication date: Dec-2017
  • (2017)SEBAR: Social-Energy-Based Routing for Mobile Social Delay-Tolerant NetworksIEEE Transactions on Vehicular Technology10.1109/TVT.2017.265384366:8(7195-7206)Online publication date: Aug-2017
  • (2017)Cooperative Data Offload in Opportunistic NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2017.274762125:6(3382-3395)Online publication date: 1-Dec-2017
  • (2017)Mobile social networksComputer Communications10.1016/j.comcom.2016.11.006100:C(1-19)Online publication date: 1-Mar-2017
  • (2017)Two-Level Community-Based Routing in Delay Tolerant NetworksWireless Personal Communications: An International Journal10.1007/s11277-017-4442-696:4(5687-5704)Online publication date: 1-Oct-2017
  • (2016)A Multi-Copy Delegation Forwarding Based on Short-Term and Long-Term Speed in DTNs2016 IEEE 13th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)10.1109/MASS.2016.038(237-245)Online publication date: Oct-2016
  • 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