A Survey of Opportunistic Networks
---
paper_title: Delay tolerant networking - bundle protocol simulation

paper_content:

In this paper, we report on the addition of MACHETE bundle protocol model needed to support DTN research. To illustrate the use of MACHETE with the additional BP model, we provide an example simulation and benchmark its performance. We demonstrate the use of the bundle protocol and discuss statistics gathered concerning the total time needed to simulate numerous bundle transmissions.
---
paper_title: Bundle Protocol Specification

paper_content:

This document describes the end-to-end protocol, block formats, and ::: abstract service description for the exchange of messages (bundles) in ::: Delay Tolerant Networking (DTN). This document was produced within ::: the IRTF's Delay Tolerant Networking Research Group (DTNRG) and ::: represents the consensus of all of the active contributors to this ::: group. See http://www.dtnrg.org for more information. This memo ::: defines an Experimental Protocol for the Internet community.
---
paper_title: A message ferrying approach for data delivery in sparse mobile ad hoc networks

paper_content:

Mobile Ad Hoc Networks (MANETs) provide rapidly deployable and self-configuring network capacity required in many critical applications, e.g., battlefields, disaster relief and wide area sensing. In this paper we study the problem of efficient data delivery in sparse MANETs where network partitions can last for a significant period. Previous approaches rely on the use of either long range communication which leads to rapid draining of nodes' limited batteries, or existing node mobility which results in low data delivery rates and large delays. In this paper, we describe a Message Ferrying (MF) approach to address the problem. MF is a mobility-assisted approach which utilizes a set of special mobile nodes called message ferries (or ferries for short) to provide communication service for nodes in the deployment area. The main idea behind the MF approach is to introduce non-randomness in the movement of nodes and exploit such non-randomness to help deliver data. We study two variations of MF, depending on whether ferries or nodes initiate proactive movement. The MF design exploits mobility to improve data delivery performance and reduce energy consumption in nodes. We evaluate the performance of MF via extensive ns simulations which confirm the MF approach is efficient in both data delivery and energy consumption under a variety of network conditions.
---
paper_title: Message ferry route design for sparse ad hoc networks with mobile nodes

paper_content:

Message ferrying is a networking paradigm where a special node, called a message ferry, facilitates the connectivity in a mobile ad hoc network where the nodes are sparsely deployed. One of the key challenges under this paradigm is the design of ferry routes to achieve certain properties of end-to-end connectivity, such as, delay and message loss among the nodes in the ad hoc network. This is a difficult problem when the nodes in the network move arbitrarily. As we cannot be certain of the location of the nodes, we cannot design a route where the ferry can contact the nodes with certainty. Due to this difficulty, prior work has either considered ferry route design for ad hoc networks where the nodes are stationary, or where the nodes and the ferry move pro-actively in order to meet at certain locations. Such systems either require long-range radio or disrupt nodes' mobility patterns which can be dictated by non-communication tasks. We present a message ferry route design algorithm that we call the Optimized Way-points, or OPWP, that generates a ferry route which assures good performance without requiring any online collaboration between the nodes and the ferry. The OPWP ferry route comprises a set of way-points and waiting times at these way-points, that are chosen carefully based on the node mobility model. Each time that the ferry traverses this route, it contacts each mobile node with a certain minimum probability. The node-ferry contact probability in turn determines the frequency of node-ferry contacts and the properties of end-to-end delay. We show that OPWP consistently outperforms other naive ferry routing approaches.
---
paper_title: Forwarding and Replication Strategies for DTN with Resource Constraints

paper_content:

Disruption tolerant network (DTN) refers to the type of sparse mobile ad hoc network where the nodes are connected intermittently. A common strategy to cope with intermittent network connectivity is to use multiple-copy routing for message delivery. However, the resultant replicates of messages incur significant burden on the bandwidth and storage requirements of each node. In this paper, we investigate the effect of excessive message-replications in multiple-copy routing in DTNs under communication bandwidth and buffer constraints. By modeling the message delivery process as a Markov chain, we first analytically derive the delivery latency as a function of message-replication limit for the single-message-delivery case. The performance of the multiple-message-multiple-flow case is then evaluated via extensive simulations. For the latter, we observe that there is an optimal value for the message-replication limit of each message beyond which network performance will degrade. Finally, we propose an alternative forwarding and message-dropping strategy to address the problem of unfairness found in the basic FIFO-with-blocking strategy. Our results show that the average message delivery delay can be reduced by as much as 25% with the proposed scheme.
---
paper_title: MV routing and capacity building in disruption tolerant networks

paper_content:

Disruption-tolerant networks (DTNs) differ from other types of networks in that capacity is exclusively created by the movements of participants. This implies that understanding and influencing the participants' motions can have a significant impact on network performance. In this paper, we introduce the routing protocol MV, which learns structure in the movement patterns of network participants and uses it to enable informed message passing. We also propose the introduction of autonomous agents as additional participants in DTNs. These agents adapt their movements in response to variations in network capacity and demand. We use multi-objective control methods from robotics to generate motions capable of optimizing multiple network performance metrics simultaneously. We present experimental evidence that these strategies, individually and in conjunction, result in significant performance improvements in DTNs.
---
paper_title: Epidemic Routing for Partially-Connected Ad Hoc Networks

paper_content:

Mobile ad hoc routing protocols allow nodes with wireless adaptors to communicate with one another without any pre-existing network infrastructure. Existing ad hoc routing protocols, while robust to rapidly changing network topology, assume the presence of a connected path from source to destination. Given power limitations, the advent of short-range wireless networks, and the wide physical conditions over which ad hoc networks must be deployed, in some scenarios it is likely that this assumption is invalid. In this work, we develop techniques to deliver messages in the case where there is never a connected path from source to destination or when a network partition exists at the time a message is originated. To this end, we introduce Epidemic Routing, where random pair-wise exchanges of messages among mobile hosts ensure eventual message delivery. The goals of Epidemic Routing are to: i) maximize message delivery rate, ii) minimize message latency, and iii) minimize the total resources consumed in message delivery. Through an implementation in the Monarch simulator, we show that Epidemic Routing achieves eventual delivery of 100% of messages with reasonable aggregate resource consumption in a number of interesting scenarios.
---
paper_title: Hybrid routing in clustered DTNs with message ferrying

paper_content:

The mobile wireless research community has invested in the development of routing algorithms and protocols for two distinct environments. The mobile ad-hoc network (MANET) environment is generally assumed to contain relatively dense nodes connected by multi-hop paths, where disconnection is rare. The disruption tolerant network (DTN) environment is generally assumed to contain relatively sparse nodes that are frequently disconnected. We are interested in a different environment in which clusters of nodes have MANET-like dense connectivity, while there is DTN-like sparse connectivity between clusters. We focus in this paper on the case of stationary clusters, where message ferrying provides inter-cluster connectivity. Our routing approach combines message ferry routing with MANET routing through the use of gateway nodes. To best utilize gateway nodes, we develop various algorithms for data aggregation at gateways and transmission scheduling between gateways and the ferry. To further improve performance, we design algorithms to customize ferry routes according to node location and traffic condition. Our hybrid routing schemes are evaluated via extensive simulations.
---
paper_title: Route Design for Multiple Ferries in Delay Tolerant Networks

paper_content:

Routing mechanisms in delay tolerant networks (DTNs) usually rely on nodes' mobilities to bridge gaps in space and time. Though they may depend on the movements of ordinary nodes, it is more desirable to introduce special mobile nodes called ferries dedicated to communication in DTNs. In this paper, we concentrate on the route design problem for multiple ferries. We introduce an analytically tractable model to describe message delivery delay in three different schemes for multiple ferry routing. We give analytical results that reveal the tradeoff between the cost of using more ferries and the performance gains. Driven by the analysis, we propose routing algorithms that can match our theoretical results well. The algorithms are evaluated under extensive network settings via simulations. The results show that our algorithms can reduce the message delivery delay over existing routing algorithms, especially when the nodes are not uniformly distributed in space.
---
paper_title: Mobility increases the capacity of ad-hoc wireless networks

paper_content:

The capacity of ad hoc wireless networks is constrained by the mutual interference of concurrent transmissions between nodes. We study a model of an ad hoc network where n nodes communicate in random source-destination pairs. These nodes are assumed to be mobile. We examine the per-session throughput for applications with loose delay constraints, such that the topology changes over the time-scale of packet delivery. Under this assumption, the per-user throughput can increase dramatically when nodes are mobile rather than fixed. This improvement can be achieved by exploiting a form of multiuser diversity via packet relaying.
---
paper_title: Single-copy routing in intermittently connected mobile networks

paper_content:

Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from source to destination, or such a path is highly unstable and may break soon after it has been discovered. In this context, conventional routing schemes would fail. To deal with such networks we propose the use of an opportunistic hop-by-hop routing model. According to the model, a series of independent, local forwarding decisions are made, based on current connectivity and predictions of future connectivity information diffused through nodes' mobility. The important issue here is how to choose an appropriate next hop. To this end, we propose and analyze via theory and simulations a number of routing algorithms. The champion algorithm turns out to be one that combines the simplicity of a simple random policy, which is efficient in finding good leads towards the destination, with the sophistication of utility-based policies that efficiently follow good leads. We also state and analyze the performance of an oracle-based optimal algorithm, and compare it to the online approaches. The metrics used in the comparison are the average message delivery delay and the number of transmissions per message delivered.
---
paper_title: Routing in a delay tolerant network

paper_content:

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.
---
paper_title: Adaptive routing for intermittently connected mobile ad hoc networks

paper_content:

The vast majority of mobile ad hoc networking research makes a very large assumption - that communication can only take place between nodes that are simultaneously accessible within the same connected cloud (i.e., that communication is synchronous). In reality, this assumption is likely to be a poor one, particularly for sparsely or irregularly populated environments. We present the context-aware routing (CAR) algorithm. CAR is a novel approach to the provision of asynchronous communication in partially-connected mobile ad hoc networks, based on the intelligent placement of messages. We discuss the details of the algorithm, and then present simulation results demonstrating that it is possible for nodes to exploit context information in making local decisions that lead to good delivery ratios and latencies with small overheads.
---
paper_title: Shortest path routing in partially connected ad hoc networks

paper_content:

Ad hoc communication among wireless enabled smart devices is increasingly playing an important role in coordinating distributed applications. Existing ad hoc routing algorithms usually assume the existence of end-to-end path connecting communication nodes. However, due to the power limitation, radio coverage and geography distribution of cooperating nodes, in some scenarios this assumption is unlikely to be valid. We address the issue of data routing in partially connected ad hoc networks. In this situation, data propagation is achieved via mainly pair-wise communication between any two nodes when they are in vicinity. We propose a novel routing framework named shortest expected path routing (SEPR). Instead of blindly flooding messages in the network, SEPR builds up a stochastic model of the ad hoc network and maintains it in a distributed way. A new routing metric, called expected path length, is proposed. By guiding messages flow to shortest expected path nodes, our approach dramatically reduces the number of unnecessary message copies as well as increases the message delivering rate. With a simulation, we evaluate the effectiveness and the efficiency of our approach.
---
paper_title: MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks

paper_content:

Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments.
---
paper_title: Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks

paper_content:

When highly mobile nodes are interconnected via wireless links, the resulting network can be used as a transit network to connect other disjoint ad-hoc networks. In this paper, we compare five different opportunistic forwarding schemes, which vary in their overhead, their success rate, and the amount of knowledge about neighboring nodes that they require. In particular, we present the MoVe algorithm, which uses velocity information to make intelligent opportunistic forwarding decisions. Using auxiliary information to make forwarding decisions provides a reasonable trade-off between resource overhead and performance.
---
paper_title: DTN routing in a mobility pattern space

paper_content:

Routing in Delay Tolerant Networks (DTNs) benefits considerably if one can take advantage of knowledge concerning node mobility. The main contribution of this paper is the definition of a generic routing scheme for DTNs using a high-dimensional Euclidean space constructed upon nodes' mobility patterns. For example, nodes are represented as points having as coordinates their probability of being found in each possible location. We present simulation results indicating that such a scheme can be beneficial in a scenario inspired by studies done on real mobility traces. This work should open the way to further use of the virtual space formalism in DTN routing.
---
paper_title: MV routing and capacity building in disruption tolerant networks

paper_content:

Disruption-tolerant networks (DTNs) differ from other types of networks in that capacity is exclusively created by the movements of participants. This implies that understanding and influencing the participants' motions can have a significant impact on network performance. In this paper, we introduce the routing protocol MV, which learns structure in the movement patterns of network participants and uses it to enable informed message passing. We also propose the introduction of autonomous agents as additional participants in DTNs. These agents adapt their movements in response to variations in network capacity and demand. We use multi-objective control methods from robotics to generate motions capable of optimizing multiple network performance metrics simultaneously. We present experimental evidence that these strategies, individually and in conjunction, result in significant performance improvements in DTNs.
---
paper_title: Epidemic algorithms for replicated database maintenance

paper_content:

Whru a dilt~lhSC is replicated at, many sites2 maintaining mutual consistrnry among t,he sites iu the fac:e of updat,es is a signitirant problem. This paper descrikrs several randomized algorit,hms for dist,rihut.ing updates and driving t,he replicas toward consist,c>nc,y. The algorit Inns are very simple and require few guarant,ees from the underlying conllllunicat.ioll system, yc+ they rnsutc t.hat. the off(~c~t, of (‘very update is evcnt,uwlly rf+irt-ted in a11 rq1ica.s. The cost, and parformancc of t,hr algorithms arc tuned I>? c%oosing appropriat,c dist,rilMions in t,hc randoinizat,ioii step. TIN> idgoritlmls ilr(’ c*los~*ly analogoIls t,o epidemics, and t,he epidcWliolog)litc\ratiirc, ilitlh iii Illld~~rsti4lldill~ tlicir bc*liavior. One of tlW i$,oritlims 11&S brc>n implrmcWrd in the Clraringhousr sprv(brs of thr Xerox C’orporat~c~ Iiitcrnc4, solviiig long-standing prol>lf~lns of high traffic and tlatirl>ilsr inconsistcllcp.
---
paper_title: Epidemic Routing for Partially-Connected Ad Hoc Networks

paper_content:

Mobile ad hoc routing protocols allow nodes with wireless adaptors to communicate with one another without any pre-existing network infrastructure. Existing ad hoc routing protocols, while robust to rapidly changing network topology, assume the presence of a connected path from source to destination. Given power limitations, the advent of short-range wireless networks, and the wide physical conditions over which ad hoc networks must be deployed, in some scenarios it is likely that this assumption is invalid. In this work, we develop techniques to deliver messages in the case where there is never a connected path from source to destination or when a network partition exists at the time a message is originated. To this end, we introduce Epidemic Routing, where random pair-wise exchanges of messages among mobile hosts ensure eventual message delivery. The goals of Epidemic Routing are to: i) maximize message delivery rate, ii) minimize message latency, and iii) minimize the total resources consumed in message delivery. Through an implementation in the Monarch simulator, we show that Epidemic Routing achieves eventual delivery of 100% of messages with reasonable aggregate resource consumption in a number of interesting scenarios.
---
paper_title: Shortest path routing in partially connected ad hoc networks

paper_content:

Ad hoc communication among wireless enabled smart devices is increasingly playing an important role in coordinating distributed applications. Existing ad hoc routing algorithms usually assume the existence of end-to-end path connecting communication nodes. However, due to the power limitation, radio coverage and geography distribution of cooperating nodes, in some scenarios this assumption is unlikely to be valid. We address the issue of data routing in partially connected ad hoc networks. In this situation, data propagation is achieved via mainly pair-wise communication between any two nodes when they are in vicinity. We propose a novel routing framework named shortest expected path routing (SEPR). Instead of blindly flooding messages in the network, SEPR builds up a stochastic model of the ad hoc network and maintains it in a distributed way. A new routing metric, called expected path length, is proposed. By guiding messages flow to shortest expected path nodes, our approach dramatically reduces the number of unnecessary message copies as well as increases the message delivering rate. With a simulation, we evaluate the effectiveness and the efficiency of our approach.
---
paper_title: MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks

paper_content:

Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments.
---
paper_title: Spray and wait: an efficient routing scheme for intermittently connected mobile networks

paper_content:

Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice.
---
paper_title: Probabilistic routing in intermittently connected networks

paper_content:

In this paper, we address the problem of routing in intermittently connected networks. In such networks there is no guarantee that a fully connected path between source and destination exists at any time, rendering traditional routing protocols unable to deliver messages between hosts. There does, however, exist a number of scenarios where connectivity is intermittent, but where the possibility of communication still is desirable. Thus, there is a need for a way to route through networks with these properties. We propose PRoPHET, a probabilistic routing protocol for intermittently connected networks and compare it to the earlier presented Epidemic Routing protocol through simulations. We show that PRoPHET is able to deliver more messages than Epidemic Routing with a lower communication overhead.
---
paper_title: Delay-Tolerant Networking TCP Convergence-Layer Protocol

paper_content:

This document describes the protocol for the TCP-based convergence ::: layer for Delay-Tolerant Networking (DTN). It is the product of the ::: IRTF's DTN Research Group (DTNRG).
---
paper_title: Bundle Protocol Specification

paper_content:

This document describes the end-to-end protocol, block formats, and ::: abstract service description for the exchange of messages (bundles) in ::: Delay Tolerant Networking (DTN). This document was produced within ::: the IRTF's Delay Tolerant Networking Research Group (DTNRG) and ::: represents the consensus of all of the active contributors to this ::: group. See http://www.dtnrg.org for more information. This memo ::: defines an Experimental Protocol for the Internet community.
---
paper_title: Licklider Transmission Protocol - Specification

paper_content:

This document describes the Licklider Transmission Protocol (LTP), ::: designed to provide retransmission-based reliability over links ::: characterized by extremely long message round-trip times (RTTs) and/or ::: frequent interruptions in connectivity. Since communication across ::: interplanetary space is the most prominent example of this sort of ::: environment, LTP is principally aimed at supporting "long- haul" ::: reliable transmission in interplanetary space, but it has applications ::: in other environments as well. LTP does ARQ of data transmissions by ::: soliciting selective- acknowledgment reception reports. It is ::: stateful, and has no negotiation or handshakes. In an Interplanetary ::: Internet setting deploying the Bundle protocol that is being developed ::: by the Delay Tolerant Networking Research Group, LTP is intended to ::: serve as a reliable "convergence layer" protocol operating in pairwise ::: fashion between adjacent Interplanetary Internet nodes that are in ::: direct RF communication. In that operational scenario, and potentially ::: in some other deployments of the Bundle Protocol, LTP runs directly ::: over a data- link layer protocol; when this is the case, forward error ::: correction coding and/or checksum mechanisms in the underlying data- ::: link layer protocol must assure the integrity of the data passed ::: between the communicating entities. Since no mechanisms for flow ::: control or congestion control are included in the design of LTP, this ::: protocol is not intended or appropriate for ubiquitous deployment in ::: the global Internet. When LTP is run over UDP, it must only be used ::: for software development or in private local area networks. When LTP ::: is not run over UDP, it must be run directly over a protocol, ::: (nominally a link- layer protocol), that meets the requirements ::: specified in section 5. This document is a product of the Delay ::: Tolerant Networking Research Group and has been reviewed by that ::: group. No objections to its publication as an RFC were raised.
---
paper_title: TCP's protocol radius: the distance where timers prevent communication

paper_content:

We examine how the design of the Transmission Control Protocol (TCP) implicitly presumes a limited range of path delays and distances between communicating endpoints. We show that TCP is less suited to larger delays due to the interaction of various timers present in TCP implementations that limit performance and, eventually, the ability to communicate at all as distances increase. The resulting performance and protocol radius metrics that we establish by simulation indicate how the TCP protocol performs with increasing distance radius between two communicating nodes, and show the boundaries where the protocol undergoes visible performance changes. This allows us to assess the suitability of TCP for long-delay communication, including for deep-space links.
---
paper_title: Saratoga: a Delay-Tolerant Networking convergence layer with efficient link utilization

paper_content:

Saratoga is a lightweight transport protocol based on the user datagram protocol (UDP/IP). Saratoga was developed by Surrey Satellite Technology Ltd (SSTL) for file transfers of imaging data recorded onboard the Internet-Protocol-Based Disaster Monitoring Constellation (DMC) satellites, and has been in operational use from low Earth orbit since 2004. Saratoga focuses only on efficient communication to the next hop when link connectivity is available, by filling the link with packets sent at line rate. This ensures that as much data as possible is transferred to the peering node during a twelve-minutes-or-less pass over a satellite ground station. Saratoga uses a minimal bandwidth-efficient negative acknowledgement mechanism to ensure reliable data transfer. We examine how Saratoga can be adapted to serve as an efficient convergence layer for delay-tolerant networking (DTN), by transferring DTN bundles as well as files. This will allow DTN networks to increase efficiency of communication across briefly-available disrupted links -for long-distance deep space links as well as for short-distance terrestrial mobile ad-hoc networks.
---
paper_title: Anycast Routing in Delay Tolerant Networks

paper_content:

Anycast routing is very useful for many applications such as resource discovery in Delay Tolerant Networks (DTNs). In this paper, based on a new DTN model, we first analyze the any- cast semantics for DTNs. Then we present a novel metric named EMDDA (Expected Multi-Destination Delay for Anycast) and a corresponding routing algorithm for anycast routing in DTNs. Extensive simulation results show that the proposed EMDDA routing scheme can effectively improve the efficiency of anycast routing in DTNs. It outperforms another algorithm, Minimum Expected Delay (MED) algorithm, by 11.3% on average in term of routing delays and by 19.2% in term of average max queue length. I. INTRODUCTION Thus efficient anycast service is important for supporting these applications in DTNs. Though anycast in the Internet and mobile ad hoc net- works has been studied extensively in the past, due to the unpredictability of network connectivity and delay, and limited storage capacity, anycast in DTNs is a quite unique and challenging problem. It requires both re-definition of anycast semantics and new routing algorithms. Moreover, in unicast in DTNs, the destination of a message is determined when it is generated, while in anycast, the destination can be any one of a group of nodes and during routing, both the path to a group member and the destination can change dynamically according to current mobile device movement situation. In this paper, we define three semantics models of anycast in DTNs, namely CM (Current Membership), TIM (Temporal Interval Membership) and TPM (Temporal Point Membership Model), which unambiguously define the intended receivers of a message in the anycast routing. Based on the model, we also propose a novel routing metric named EMDDA (Ex- pected Multi-Destination Delay for Anycast) which utilizes the uncontrolled random moving characteristic of mobile devices. We use a probabilistic approach that characterizes the practical average delay more accurately and develop a corresponding algorithm. The performance of the algorithm is analyzed and compared by simulation which demonstrates the effectiveness and efficiency of the proposed metric. Our simulations show that the EMDDA routing scheme can effectively improve the efficiency of anycast routing in DTNs. It achieves 11.3% lower average routing delays and 19.2% lower average max queue length compared to another algorithm, Minimum Expected Delay (MED)(2).
---
paper_title: Multicasting in delay tolerant networks: semantic models and routing algorithms

paper_content:

Delay tolerant networks (DTNs) are a class of emerging networks that experience frequent and long-duration partitions. These networks have a variety of applications in situations such as crisis environments and deep-space communication. In this paper, we study the problem of multicasting in DTNs. Multicast supports the distribution of data to a group of users, a service needed for many potential DTN applications. While multicasting in the Internet and mobile ad hoc networks has been studied extensively, due to the unique characteristic of frequent partitioning in DTNs, multicasting in DTNs is a considerably different and challenging problem. It not only requires new definitions of multicast semantics but also brings new issues to the design of routing algorithms. In this paper, we propose new semantic models for DTN multicast and develop several multicast routing algorithms with different routing strategies. We present a framework to evaluate these algorithms in DTNs. To the best of our knowledge, this is the first study of multicasting in DTNs. Our objectives are to understand how routing performance is affected by the availability of knowledge about network topology and group membership and to guide the design of DTN routing protocols. Using ns simulations, we find that efficient multicast routing for DTNs can be constructed using only partial knowledge. In addition, accurate topology information is generally more important in routing than up-to-date membership information. We also find that routing algorithms that forward data along multiple paths achieve better delivery ratios, especially when available knowledge is limited.
---
paper_title: Context-aware multicast routing scheme for disruption tolerant networks

paper_content:

Disruption Tolerant Networks (DTNs) are emerging solutions to networks that experience frequent network partitions and large end-to-end delays. Several schemes have been proposed for multicast routing in DTNs assuming the availability of different amount of knowledge about network topology etc. In this paper, we propose a node-density based adaptive multicast routing scheme which can handle different network scenarios than the existing multicast delivery schemes for DTNs that we are aware of. Our scheme can address the challenges of opportunistic link connectivity in DTNs. Simulation results show that our CAMR scheme performs better than the DTBR and OS-multicast schemes. The CAMR scheme can achieve a better message delivery ratio, with higher transmission efficiency and similar delay performance especially when the nodes are very sparsely connected
---
paper_title: An encounter-based multicast scheme for disruption tolerant networks

paper_content:

Some ad hoc network scenarios are characterized by frequent partitions and intermittent connectivity. Hence, existing ad hoc routing schemes that assume that an end-to-end path exists from a source to a destination do not work in such challenging environment. A store-and-forward network architecture known as the disruption tolerant network (DTN) has been designed for such challenging network environments. Several unicast and multicast routing schemes have been designed for DTNs. However, the existing multicast routing schemes assume a route discovery process that is similar to the existing ad hoc network routing approach. Thus, in this paper, we design an encounter-based multicast routing (EBMR) scheme for DTNs which uses fewer hops for message delivery. We first describe how the EBMR scheme works and then present an analytical framework to estimate the delivery performance of the EBMR scheme. Next, we present some comparisons of the analytical and simulation results to show that our analytical framework provides delivery performance estimates that match closely the observed simulation results. Last but not least, we present simulation results to study the delivery performance of EBMR in different scenarios, e.g. different mobility models, different multicast group size, different number of multicast groups and different node speed. We also compare the performance of the EBMR scheme with other DTN multicast strategies. Our simulation results indicate that the EBMR scheme can achieve higher delivery ratio while maintaining high data transmission efficiency compared to other multicast strategies.
---
paper_title: OS-multicast: On-demand Situation-aware Multicasting in Disruption Tolerant Networks

paper_content:

Disruption Tolerant Networks (DTNs) are emerging solutions to networks that experience frequent network partitions and large end-to-end delays. In this paper, we study how to provide high-performance multicasting service in DTNs. We develop a multicasting mechanism based on on-demand path discovery and overall situation awareness of link availability (OS-multicast) to address the challenges of opportunistic link connectivities in DTNs. Simulation results show that OS-multicast can achieve a better message delivery ratio than existing approaches, e.g. DTBR (a dynamic tree-based routing), with similar delay performance. OS-multicast also achieves better efficiency performance when the probability of link unavailability is high and the duration of link downtime is large.
---
paper_title: Probabilistic routing in intermittently connected networks

paper_content:

In this paper, we address the problem of routing in intermittently connected networks. In such networks there is no guarantee that a fully connected path between source and destination exists at any time, rendering traditional routing protocols unable to deliver messages between hosts. There does, however, exist a number of scenarios where connectivity is intermittent, but where the possibility of communication still is desirable. Thus, there is a need for a way to route through networks with these properties. We propose PRoPHET, a probabilistic routing protocol for intermittently connected networks and compare it to the earlier presented Epidemic Routing protocol through simulations. We show that PRoPHET is able to deliver more messages than Epidemic Routing with a lower communication overhead.
---
paper_title: Web search from a bus

paper_content:

Opportunistic connections to the Internet from open wireless access points is now commonly possible in urban areas. Vehicular networks can opportunistically connect to the Internet for several seconds via open access points. In this paper, we adapt the interactive process of web search and retrieval to vehicular networks with intermittent Internet access. Our system, called Thedu, has mobile nodes use an Internet proxy to collect search engine results and prefetch result pages. The mobile nodes download the pre-fetched web pages from the proxy. Our contribution is a novel set of techniques to make aggressive but selective prefetching practical, resulting in a significantly greater number of relevant web results returned to mobile users. In particular, we prioritize responses in the order of the usefulness of the response to the query, that allows the mobile node to download the most useful response first. To evaluate our scheme, we deployed Thedu on DieselNet, our vehicular testbed operating in a micro-urban area around Amherst, MA. Using a simulated workload, we find that users can expect four times as many useful responses to web search queries compared to not using Thedu's mechanisms. Moreover, the mean latency in receiving the first relevant response for a query is 2.7 minutes for our deployment; we expect Thedu to have even better performance in larger cities that have densely populated open APs.
---
paper_title: Opportunistic email distribution and access in challenged heterogeneous environments

paper_content:

The communication paradigms for delay-tolerant networking have been modeled after email. Supporting email over DTNs in a backwards compatible manner in a heterogeneous environment has yet to be fully defined. In this paper, we present a set of conventions for and extensions to the DTNRG architecture. We have implemented a system that is able to deliver emails within a DTN network, from a DTN network to the Internet, and from the Internet to the DTN network. Our system architecture includes multiple solutions for integrating traditional and DTN-based mail delivery: DTN-based messaging clients for mobile phones and PDAs, a dedicated, stand-alone DTN gateway between the Internet and the DTN network, and a personal DTN mail application proxy. The latter bridges to unmodified mail user agents running on a laptop.
---
paper_title: Disruption tolerant networking proxies for on-the-move tactical networks

paper_content:

A major tenet of network centric warfare is that information sharing is vital to future battlefield superiority. Many plans for implementing NCW envision using IP as the network infrastructure to support information sharing, from wired and satellite networks to tactical networks. Unfortunately, IP implementations depend on the existence of stable end-to-end paths. If a router receives a packet and has nowhere to send it, the packet is dropped. Many tactical networks exhibit disconnections in connectivity that can severely impair, or completely halt, IP traffic. Disconnection tolerant networking (DTN) provides an end-to-end communications service in the presence of network disruptions, including (non-permanent) network partitions. DTN provides its own application programming interface, which is different from the sockets interface commonly used for TCP/IP. One way to adapt existing applications to use DTN is via application layer proxies. These proxies translate from applications' native use of end-to-end IP-based protocols such as TCP and UDP into DTN messages (bundles) that can traverse disrupted networks. This paper describes how DTN application layer proxies can be used with a CONDOR Jump-C2 class vehicle, using an HTTP (Web)-to-DTN proxy as an example.
---
paper_title: Bundling the Web: HTTP over DTN

paper_content:

Mobile users traveling by car, bus, or train usually experience varying connectivity characteristics while they are on their way, including unpredictable (loss of) network access, changes in a data rate, and the like. In short, they operate in a challenged networking environment that is not well suited for many Internet applications. While different approaches have been developed to specifically mitigate (short-term) disconnections while at least partly preserving the end-to-end notion of such applications, Delay-tolerant Networking (DTN) takes a different approach by relying exclusively on asynchronous communications. While this fits well with the mobile user connectivity, particularly interactive applications (such as web access) are affected by the lack of synchronous endto-end interaction. In this paper, we present protocol mechanisms for running HTTP-over-DTN as well as a system architecture for incremental deployment, and we report on findings from measurements performed with our prototype implementation.
---

Title: A Survey of Opportunistic Networks

Section 1: INTRODUCTION
Description 1: Provide an overview of opportunistic networks, including their characteristics, challenges, and applications.

Section 2: Architecture
Description 2: Explain the structure of opportunistic networks, detailing network partitions, the store-carry-forward mechanism, and the role of bundle layers and gateways.

Section 3: Challenges
Description 3: Discuss specific challenges in opportunistic networks such as contact opportunities and storage constraints.

Section 4: NETWORK LAYER
Description 4: Present various routing solutions for opportunistic networks, categorized into forwarding-based and flooding-based approaches.

Section 5: TRANSPORT LAYER
Description 5: Describe the limitations of traditional transport layer protocols in opportunistic networks and introduce alternative protocols like the Licklider Transmission Protocol (LTP) and its extensions.

Section 6: BUNDLE LAYER
Description 6: Discuss the role of the bundle layer in data delivery, including unicast, anycast, and multicast delivery approaches in opportunistic networks.

Section 7: APPLICATION LAYER
Description 7: Explore the issues and solutions for supporting traditional and delay-tolerant applications, such as email and web access, in opportunistic networks.

Section 8: CONCLUSION
Description 8: Summarize the key points and state-of-the-art solutions discussed in the survey, highlighting the ongoing research and future challenges in opportunistic networks.