1.12 A home on the Internet — Ludovic Courtès — Delay-Tolerant Networks
  • Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges [zhang06:routing-dtn]
    Zhensheng Zhang (San Diego Research Center, USA), appeared in IEEE Communications Surveys & Tutorials, January 2006

    The article provides a survey of approaches to packet routing in delay-tolerant networks (DTNs), including an interesting erasure-coding-based approach. In a sense, mobile DTNs are very similar to MoSAIC's cooperative backup approach.

  • Bundle Protocol Specification (Internet Draft) [scott07:bundle]
    Keith L. Scott, Scott Burleigh (The MITRE Corporation, VA, USA), April 2007

    Draft specification of the bundle protocol used in DTNs.

  • Using Redundancy to Cope with Failures in a Delay Tolerant Network [jain05:using]
    Sushant Jain, Michael Demmer, Rabin Patra, Kevin Fall (University of Washington, USA), Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), 2005

    This paper complements wang05:erasure-coding. This paper acknowledges the fact that the is no single answer as to whether erasure codes are preferable over simple replication as a means to propagate messages in a DTN. A simple example illustrates this, in a way similar to lin04:revisited. The paper studies this problem as an optimization problem of the allocation of message replicas/fragments to a given path (a problem similar to that of optimal replica placement in distributed stores). They explain that optimizing both delay and delivery success rate is an NP-hard problem. They compare through simulation several allocation strategies with the same storage overhead in several scenarios. The evaluated allocation strategies are:

    Simple Replication
    The source send full replicas to the r best paths.
    Simple Replication with Coding
    An equal proportion of coded blocks are sent over the r best paths (this is similar to the above).
    Proportional
    The number of fragments allocates to each path is proportional to its success probability.
    Markowitz
    A complex thing...
    Mixed Integer Programming
    Another one...
    This assumes that path probabilities are known beforehand. With low path success probabilities (and equal probability for all paths), ``proportional'' yields a success rate worse than that of ``simple replication'' because more fragments need to reach their destination. The authors also note that splitting of a simply-replicated message significantly decreases the delivery probability of the whole message (because one full replica of each part of the message is needed). Finally, they estimate the impact of inaccurate guesses of path probabilities by varying the number of history records (samples) used as input to the estimation process.

  • Delay-Tolerant Networking Architecture (RFC 4838) [cerf07:dtn-arch]
    Vinton G. Cerf, Scott C. Burleigh, Robert C. Durst, Kevin Fall, Adrian J. Hooke, Keith L. Scott, Leigh Torgerson, Howard S. Weiss (Google Corporation, VA, USA), April 2007

    An informational RFC on DTNs.

  • Erasure-Coding Based Routing for Opportunistic Networks [wang05:erasure-coding]
    Yong Wang, Sushant Jain, Margaret Martonosi, Kevin Fall (Princeton University, NJ, USA), Proceeding of the ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005

    The paper discusses the use of erasure-coding based routing in DTNs whereby:

    • the source messages are erasure-encoded;
    • only the source of a message can propagate fragments of the source message (i.e., relays do not further forward fragments.)
    Using traces from ZebraNet juang02:zebranet (which actually didn't work well since only one tracking collar collected data), they then compare their EC routing approach to a simple-replication approach according to several metrics: data success rate (probability that the message was delivered within a given amount of time), data latency, and routing overhead. They identify a tradeoff in terms of latency where: erasure coding yields better worst case delay than simple replication, but provides lower data success rates for short deadlines. The paper then provides a theoretical comparison of simple-replication and EC, assuming delay variables follow a Pareto distribution.

  • A Delay-Tolerant Network Architecture for Challenged Internets [fall03:dtn]
    Kevin Fall (Intel Research, Berkeley, CA, USA), Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), August 2003

    This position paper is one of the foundations of DTNs. It provides an overview of the rationale behind DTN architectures. DTN are described as an asynchronous message delivery system, akin to email, where overlay routing is used to route messages across networking regions, with DTN gateways acting as bridges among regions. DTN protocols are to be layered on top of existing protocols (e.g., at the application layer). The paper mentions naming issues, path selection and security issues. As far as security is concerned, they propose to protect against flooding with useless messages using a centralized authorization scheme; this appears to not scale well (one has to register with the central authority to use the network) and to address only narrow attack scenarios.

  • Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet [juang02:zebranet]
    Philo Juang, Hidekazu Oki, Yong Wang, Margaret Martonosi, Li-Shiuan Peh, Daniel Rubenstein (Princeton University, USA), appeared in ACM SIGOPS Operating Systems Review, 2002

    One of the first practical delay-tolerant networks and a very interesting and well-written paper. Its purpose is to collect information about movements of zebras (wildlife tracking) by equipping zebras with a tracking collar. The collar contains two different radio transmitters. The idea is that eventually, data collected must be sent to the researchers who are supposed to pass by every now and then by car.

  • Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case [spyro07:efficient]
    Thrasyvoulos Spyropoulos, Konstantinos Psounis, Cauligi Raghavendra (University of Southern California, CA, USA), appeared in ACM/IEEE Transactions on Networking, 2007

    (To appear.) The paper describes possible optimization of single-copy routing protocols for intermittently-connected mobile networks (ICMS, a kind of DTNs). Single-copy protocols require few (storage) resources, unlike flooding protocols. However, they are usually expected to be slower.

  • Estimation Based Erasure Coding Routing in Delay Tolerant Networks [liao06:estimation]
    Yong Liao, Kun Tan, Zhensheng Zhang, Lixin Gao, Proceeding of the International Conference on Communications and Mobile Computing, 2006

    The idea is to combine to ideas to improve routing in DTNs:

    1. Select relays based on estimates of their probability to reach the destination. This idea stems from the observation that in many scenarios, not all nodes are equivalent: certain nodes are more capable than others of reaching a given destination. This is similar from the history-based estimates used in Flashback loo03:backup-pan and OmniStore karypidis05:exploiting.
    2. Erasure-code messages so that only part of the fragments (coded blocks) of a message can be handed to a relay. The idea is to improve on ``all-or-nothing'' decisions where either a full message or nothing is handed to relays.
    In practice, nodes estimate the average contact frequency (ACF) or each other; then, a source node distributes fragments of its message proportionally to the node's ACF. Simulation results show that estimation-based erasure coding routing (EBEC) performs better than estimation-based routing (EBRS) under the simulated scenario. The simulation parameters are hard to analyze: the absolute node density is very low (1.5 nodes per million of square units), but three fourth of each node's waypoints lie in a small region (density is 4 nodes per 1000 square units); furthermore, nodes move and have a fairly large communication range (100 units).

  • Security Considerations in Space and Delay Tolerant Networks [farrell06:security-dtn]
    Stephen Farrell, Vinny Cahill (Trinity College Dublin, Ireland), Proceedings of the 2nd IEEE International Conference on Space Mission Challenges for Information Technology, 2006

    Discusses security issues with delay-tolerant networks (DTNs), specifically in the framework of space mission networks. The paper is very informal. It provides a rough description of what the issues might be in such networks, in the presence of untrusted peers, and when using either the ``bundle protocol'' or the licklider transmission protocol (LTP)---both of which are being standardized by IETF. They authors do not actually provide any solution and only vaguely describe the issues.

  • Network Coding for Efficient Communication in Extreme Networks [widmer05:coding]
    J?rg Widmer, Jean-Yves Le Boudec (DoCoMo Euro-Labs, Munich, Germany), Proceeding of the ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005
  • ParaNets: A Parallel Network Architecture for Challenged Networks [harras07:paranets]
    Khaled A. Harras, Mike P. Wittie, Kevin C. Almeroth, Elizabeth M. Belding (University of California, Santa Barbara, CA, USA), Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, February 2007

    The article proposes a parallel networking architecture to leverage the various networking technologies available: on one hand, DTNs, and on the other, technologies such as cellular phone networks and satellites. The identify a number of challenges in providing seamless operation over such a wide-range of networks, such as: switching among different networking technologies at the transport layer depending on the type of packet to be transmitted (e.g., small vs. large packet, ACKs, etc.), providing transport-independent addressing (i.e., an address must remain valid and routable regardless of the underlying transport), and leveraging wireless technology diversity for security purposes (e.g., exchanging cryptographic material over satellite). They then advocate the use of a protocol tree (where the direct leaves of the application are a different transports) rather than a stack. Simulation results show that DTNs where 100% of nodes are ``ParaNet-enabled'' perform better in terms of delay and cost (i.e., number of messages transmitted).

(made with skribilo)