research-article

Practical Routing in Delay-Tolerant Networks

Authors:

Evan P. C. Jones,

Jakub K. Schmidtke,

Paul A. S. WardAuthors Info & Claims

IEEE Transactions on Mobile Computing, Volume 6, Issue 8

Pages 943 - 959

https://doi.org/10.1109/TMC.2007.1016

Published: 01 August 2007 Publication History

Abstract

Delay-tolerant networks (DTNs) have the potential to interconnect devices in regions that current networking technology cannot reach. To realize the DTN vision, routes must be found over multiple unreliable, intermittently-connected hops. In this paper we present a practical routing protocol that uses only observed information about the network. We designed a metric that estimates the average waiting time for each potential next hop. This learned topology information is distributed using a link-state routing protocol, where the link-state packets are "flooded” using epidemic routing. The routing is recomputed each time connections are established, allowing messages to take advantage of unpredictable contacts. A message is forwarded if the topology suggests that the connected node is "closer” to the destination than the current node. We demonstrate through simulation that our protocol provides performance similar to that of schemes that have global knowledge of the network topology, yet without requiring that knowledge. Further, it requires significantly less resources than the alternative, epidemic routing, suggesting that our approach scales better with the number of messages in the network. This performance is achieved with minimal protocol overhead for networks of approximately 100 nodes.

References

[1]

K. Fall, “A Delay-Tolerant Network Architecture for Challenged Internets,” Proc. ACM SIGCOMM, pp. 27-34, Aug. 2003.

Digital Library

[2]

A. Rabagliati, “Wizzy Digital Courier—How It Works,” http://www.wizzy.org.za/article/articleprint/19/1/2/, Apr. 2004.

[3]

A.A. Hasson, D.R. Fletcher, and D.A. Pentland, “A Road to Universal Broadband Connectivity,” Proc. Development by Design Second Int'l Conf. Open Collaborative Design for Sustainable Innovation (dyd02), Dec. 2002.

[4]

E. Brewer, M. Demmer, B. Du, M. Ho, M. Kam, S. Nedevschi, J. Pal, R. Patra, S. Surana, and K. Fall, “The Case for Technology in Developing Regions,” Computer, vol. 38, no. 6, pp. 25-38, June 2005.

Digital Library

[5]

T. Small and Z.J. Haas, “The Shared Wireless Infostation Model,” Proc. MobiHoc, pp. 233-244, June 2003.

Digital Library

[6]

J. Ott and D. Kutscher, “Drive-Thru Internet: IEEE 802.11b for `Automobile' Users,” Proc. INFOCOM, pp. 362-373, Mar. 2004.

[7]

S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K. Scott, and H. Weiss, “Delay-Tolerant Networking: An Approach to Interplanetary Internet,” IEEE Comm. Magazine, vol. 41, no. 6, pp. 128-136, June 2003.

Digital Library

[8]

E.P.C. Jones, L. Li, and P.A.S. Ward, “Practical Routing in Delay-Tolerant Networks,” Proc. ACM SIGCOMM Workshop Delay-Tolerant Networking (WDTN '05), pp. 237-243, Aug. 2005.

Digital Library

[9]

S. Jain, K. Fall, and R. Patra, “Routing in a Delay Tolerant Network,” Proc. ACM SIGCOMM, pp. 145-158, Oct. 2004.

Digital Library

[10]

A. Vahdat and D. Becker, “Epidemic Routing for Partially-Connected Ad Hoc Networks,” Technical Report CS-2000-06, Duke Univ., July 2000.

[11]

J.A. Davis, A.H. Fagg, and B.N. Levine, “Wearable Computers as Packet Transport Mechanisms in Highly-Partitioned Ad-Hoc Networks,” Proc. Int'l Symp. Wearable Computers, pp.141-148, 2001.

Digital Library

[12]

A. Lindgren, A. Doria, and O. Scheln, “Probabilistic Routing in Intermittently Connected Networks,” Lecture Notes in Computer Science, vol. 3126, pp. 239-254, Jan. 2004.

[13]

D. Marasigan and P. Rommel, “MV Routing and Capacity Building in Disruption Tolerant Networks,” Proc. INFOCOM, pp. 398-408, Mar. 2005.

[14]

T. Small and Z.J. Haas, “Resource and Performance Tradeoffs in Delay-Tolerant Wireless Networks,” Proc. ACM SIGCOMM Workshop Delay-Tolerant Networking, pp. 260-267, Aug. 2005.

Digital Library

[15]

K. Tan, Q. Zhang, and W. Zhu, “Shortest Path Routing in Partially Connected Ad Hoc Networks,” Proc. Global Telecomm. Conf. (GLOBECOM '03), pp. 1038-1042, Dec. 2003.

[16]

J. Burgess, B. Gallagher, D. Jensen, and B.N. Levine, “Maxprop: Routing for Vehicle-Based Disruption-Tolerant Networking,” Proc. INFOCOM, Apr. 2006.

[17]

A. Demers, D. Greene, C. Houser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic Algorithms for Replicated Database Maintenance,” SIGOPS Operating Systems Rev., vol. 22, no. 1, pp. 8-32, Jan. 1988.

Digital Library

[18]

K.A. Harras and K.C. Almeroth, “Transport Layer Issues in Delay Tolerant Mobile Networks,” Proc. IFIP-TC6 Networking Conf., 2006.

Digital Library

[19]

T. Spyropoulos, K. Psounis, and C.S. Raghavendra, “Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks,” Proc. ACM SIGCOMM Workshop Delay-Tolerant Networking (WDTN '05), pp. 252-259, Aug. 2005.

Digital Library

[20]

M. Grossglauser and D.N.C. Tse, “Mobility Increases the Capacity of Ad Hoc Wireless Networks,” IEEE/ACM Trans. Networking, vol. 10, no. 4, pp. 477-486, Aug. 2002.

Digital Library

[21]

R.C. Shah, S. Roy, S. Jain, and W. Brunette, “Data Mules: Modeling a Three-Tier Architecture for Sparse Sensor Networks,” Sensor Network Protocols and Applications, pp. 30-41, May 2003.

[22]

W. Zhao, M. Ammar, and E. Zegura, “A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks,” Proc. MobiHoc, pp. 187-198, May 2004.

Digital Library

[23]

D. Nain, N. Petigara, and H. Balakrishnan, “Integrated Routing and Storage for Messaging Applications in Mobile Ad Hoc Networks,” Mobile Networks and Applications (MONET), pp. 595-604, Dec. 2004.

Digital Library

[24]

J. Lebrun, C.-N. Chuah, D. Ghosal, and M. Zhang, “Knowledge-Based Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks,” IEEE Vehicular Technology Conf., pp. 2289-2293, 2005.

[25]

J. Leguay, F. Friedman, and V. Conan, “Evaluating Mobility Pattern Space Routing for DTNs,” Proc. IEEE INFOCOM, Apr. 2006.

[26]

B. Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proc. MobiCom, pp. 243-254, Aug. 2000.

Digital Library

[27]

R. Handorean, C. Gill, and G.-C. Roman, “Accommodating Transient Connectivity in Ad Hoc and Mobile Settings,” Lecture Notes in Computer Science, vol. 3001, pp. 305-322, Jan. 2004.

[28]

M.J. Fischer, N.A. Lynch, and M.S. Paterson, “Impossibility of Distributed Consensus with One Faulty Process,” J. ACM, vol. 32, no. 2, pp. 374-382, Apr. 1985.

Digital Library

[29]

F. Cristian and C. Fetzer, “The Timed Asynchronous Distributed System Model,” IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 6, pp. 642-657, June 1999.

Digital Library

[30]

Dartmouth College, “The Dartmouth Wireless Trace Archive,” http://crawdad.cs.dartmouth.edu/, 2007.

[31]

Univ. of Washington, “Intelligent Transportations Systems,” http://www.its.washington.edu/, 2007.

[32]

Univ. of Waterloo, “DTNSim2 DTN Simulator,” http://shoshin. uwaterloo.ca/dtnsim2/, 2007.

[33]

B. Hull, K. Jamieson, and H. Balakrishnan, “Mitigating Congestion in Wireless Sensor Networks,” Proc. ACM Conf. Embedded Networked Sensor Systems (SenSys '04), Nov. 2004.

Digital Library

[34]

R. Gass, J. Scott, and C. Diot, “Measurements of 802.11 In-Motion Networking,” Proc. IEEE Workshop Mobile Computing Systems and Applications (WMCSA '06), Apr. 2006.

Digital Library

Cited By

Mari JGabillon A(2023)The MauMe network - A LoRa multi-hop collaborative protocol and low-cost implementation exampleComputer Standards & Interfaces10.1016/j.csi.2023.10373386:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.csi.2023.103733
Savita Lobiyal D(2022)Location Based Contact Time Energy Efficient Routing (LCTEE) Approach for Delay Tolerant NetworksWireless Personal Communications: An International Journal10.1007/s11277-019-06543-3108:4(2639-2662)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s11277-019-06543-3
Bansal SKumar D(2022)Enhancing constrained application protocol using message options for internet of thingsCluster Computing10.1007/s10586-022-03727-826:3(1917-1934)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1007/s10586-022-03727-8
Show More Cited By

Index Terms

Practical Routing in Delay-Tolerant Networks
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Signal processing systems
2. Networks

Recommendations

Practical routing in delay-tolerant networks
WDTN '05: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking

Delay-tolerant networks (DTNs) have the potential to connect devices and areas of the world that are under-served by current networks. A critical challenge for DTNs is determining routes through the network without ever having an end-to-end connection, ...
Benchmarking and Modeling of Routing Protocols for Delay Tolerant Networks

Delay Tolerant Networks (DTN) are deployed to establish communications in challenging environments with frequent disruptions and delays due to intermittently connecting nodes, such as sparsely distributed wireless sensor networks and mobile ad hoc ...
Contact expectation based routing for delay tolerant networks

In conventional networks, routing problem can be modeled as the design of an efficient source-to-destination route based on persistent end-to-end paths. However, in a delay tolerant network (DTN), nodes are intermittently connected and thus, the end-to-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Mobile Computing

IEEE Transactions on Mobile Computing Volume 6, Issue 8

August 2007

142 pages

ISSN:1536-1233

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 August 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mari JGabillon A(2023)The MauMe network - A LoRa multi-hop collaborative protocol and low-cost implementation exampleComputer Standards & Interfaces10.1016/j.csi.2023.10373386:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.csi.2023.103733
Savita Lobiyal D(2022)Location Based Contact Time Energy Efficient Routing (LCTEE) Approach for Delay Tolerant NetworksWireless Personal Communications: An International Journal10.1007/s11277-019-06543-3108:4(2639-2662)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s11277-019-06543-3
Bansal SKumar D(2022)Enhancing constrained application protocol using message options for internet of thingsCluster Computing10.1007/s10586-022-03727-826:3(1917-1934)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1007/s10586-022-03727-8
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
Aneja SNagrath PPurohit G(2019)Energy efficient reputation mechanism for defending different types of flooding attackWireless Networks10.1007/s11276-018-01928-x25:7(3933-3951)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11276-018-01928-x
(2018)A novel distributed node searching method in DTNsInternational Journal of High Performance Computing and Networking10.5555/3282715.328272212:3(278-288)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3282715.3282722
Guo MZavlanos M(2018)Multirobot Data Gathering Under Buffer Constraints and Intermittent CommunicationIEEE Transactions on Robotics10.1109/TRO.2018.283037034:4(1082-1097)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TRO.2018.2830370
Saha BMisra SPal S(2017)SeeR: Simulated Annealing-Based Routing in Opportunistic Mobile NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2017.267384216:10(2876-2888)Online publication date: 30-Aug-2017
https://dl.acm.org/doi/10.1109/TMC.2017.2673842
Papaj JDobos LCizmar A(2017)Hybrid MANET---DTN and a New Algorithm for Relay Nodes SelectionWireless Personal Communications: An International Journal10.1007/s11277-016-3733-796:4(5145-5166)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s11277-016-3733-7
Singh AJuyal VSaggar R(2017)Trust based Intelligent Routing Algorithm for Delay Tolerant Network using Artificial Neural NetworkWireless Networks10.1007/s11276-015-1166-y23:3(693-702)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11276-015-1166-y
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents