Routing in a delay tolerant network

Computer Communication Review - Tập 34 Số 4 - Trang 145-158 - 2004
Sushant Jain1, Kevin Fall2, Rabin Patra3
1University of Washington
2Intel Research, Berkeley
3University of California, Berkeley

Tóm tắt

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.

Từ khóa


Tài liệu tham khảo

R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . Network Flows: Theory, Algorithms, and Applications . Prentice Hall , 1993 . R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

AMSAT. http://www.amsat.org/. AMSAT. http://www.amsat.org/.

10.1145/288235.288256

X. Chen and A. L. Murphy . Enabling Disconnected Transitive Communication in Mobile Adhoc Networks. In Workshop on Principles of Mobile Computing , August 2001 . X. Chen and A. L. Murphy. Enabling Disconnected Transitive Communication in Mobile Adhoc Networks. In Workshop on Principles of Mobile Computing, August 2001.

CPLEX : Linear Programming Solver. http://www.ilog.com/. CPLEX: Linear Programming Solver. http://www.ilog.com/.

CPLEX : Linear Programming Solver. http://www.ilog.com/. CPLEX: Linear Programming Solver. http://www.ilog.com/.

10.1145/863955.863960

L. R. Ford and D. R. Fulkerson . Flows in Networks . Princeton University Press , 1962 . L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

S. Gao . Routing Problems in Stochastic Time-Dependent Networks with Applications in Dynamic Traffic Assignment. Master's thesis , MIT , 2002 . S. Gao. Routing Problems in Stochastic Time-Dependent Networks with Applications in Dynamic Traffic Assignment. Master's thesis, MIT, 2002.

P. Honeymoon and S. Bellovin . PATHALIAS: The Care and Feeding of Relative Address. In USENIX Conference , 1986 . P. Honeymoon and S. Bellovin. PATHALIAS: The Care and Feeding of Relative Address. In USENIX Conference, 1986.

B. Hoppe and É. Tardos. The Quickest Transshipment Problem . In SODA , Jan. 1996 . B. Hoppe and É. Tardos. The Quickest Transshipment Problem. In SODA, Jan. 1996.

10.1145/605397.605408

B. Kotnyek . An Annotated Overview of Dynamic Network Flows. Technical Report RR-4936 , INRIA , Sept. 2003 . B. Kotnyek. An Annotated Overview of Dynamic Network Flows. Technical Report RR-4936, INRIA, Sept. 2003.

J. A. Magliacane. PREDICT: Satellite Tracking Software. http://www.qsl.net/kd2bd/predict.html/. J. A. Magliacane. PREDICT: Satellite Tracking Software. http://www.qsl.net/kd2bd/predict.html/.

10.1109/ICNP.2001.992756

10.1145/938985.939012

R. Ogier . Minimum-delay Routing in Continuous-time Dynamic Networks with Piecewise-constant Capacities. Networks , 18 : 303 -- 318 , 1988 . R. Ogier. Minimum-delay Routing in Continuous-time Dynamic Networks with Piecewise-constant Capacities. Networks, 18:303--318, 1988.

10.1145/79147.214078

10.1109/MC.2004.1260729

10.5555/1060289.1060319

10.1109/SNPA.2003.1203354

TIER Project. http://tier.cs.berkeley.edu/. TIER Project. http://tier.cs.berkeley.edu/.

Wizzy Project. http://www.wizzy.org.za/. Wizzy Project. http://www.wizzy.org.za/.

Thông tin
Thông tin xuất bản

Computer Communication Review

Tập 34 Số 4

145-158

Thông tin tác giả