Problem in computer networking
Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay- and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. A common technique used to maximize the probability of a message being successfully transferred is to replicate many copies of the message in hopes that one will succeed in reaching its destination.
Routing considerations.
There are many characteristics DTN protocols, including routing, must take into consideration. A first consideration is if information about future contacts is readily available. For example, in interplanetary communications, many times a planet or moon is the cause of contact disruption, and large distance is the cause of communication delay. However, due to the laws of physics, it is possible to predict the future in terms of the times contacts will be available, and how long they will last. These types of contacts are known as "scheduled" or "predictable contacts". On the contrary, in disaster recovery networks the future location of communicating entities, such as emergency responders, may not be known. These types of contacts are known as "intermittent" or "opportunistic contacts".
A second consideration is if mobility can be exploited and, if so, which nodes are mobile. There are three major cases, classifying the level of mobility in the network. First, it is possible that there are no mobile entities. In this case, contacts appear and disappear based solely on the quality of the communication channel between them. For instance, in interplanetary networks, large objects in space, such as planets, can block communicating nodes for a set period of time. Second, it is possible that some, but not all, nodes in the network are mobile. These nodes, sometimes referred to as Data Mules, are exploited for their mobility. Since they are the primary source of transitive communication between two non-neighboring nodes in the network, an important routing question is how to properly distribute data among these nodes. Third, it is possible that the vast majority, if not all, nodes in the network are mobile. In this case, a routing protocol will most likely have more options available during contact opportunities, and may not have to utilize each one. An example of this type of network is a disaster recovery network where all nodes (generally people and vehicles) are mobile. A second example is a vehicular network where mobile cars, trucks, and buses act as communicating entities.
A third consideration is the availability of network resources. Many nodes, such as mobile phones, are limited in terms of storage space, transmission rate, and battery life. Others, such as buses on the road, may not be as limited. Routing protocols can utilize this information to best determine how messages should be transmitted and stored to not over-burden limited resources. As of April 2008, only recently has the scientific community started taking resource management into consideration, and this is still an active area of research.
Routing protocol classifications.
While there are many characteristics of routing protocols, one of the most immediate ways to create a taxonomy is based on whether or not the protocol creates replicas of messages. Routing protocols that never replicate a message are considered forwarding-based, whereas protocols that do replicate messages are considered replication-based. 
There are both advantages and disadvantages to each approach, and the appropriate approach to use is probably dependent on the scenario at hand. Forwarding-based approaches are generally much less wasteful of network resources, as only a single copy of a message exists in storage in the network at any given time. Furthermore, when the destination receives the message, no other node can have a copy. This eliminates the need for the destination to provide feedback to the network (except for, perhaps, an acknowledgments sent to the sender), to indicate outstanding copies can be deleted. Unfortunately, forwarding-based approaches do not allow for sufficient message delivery rates in many DTNs. Replication-based protocols, on the other hand, allow for greater message delivery rates, since multiple copies exist in the network, and only one (or in some cases, as with erasure coding, a few) must reach the destination. However, the tradeoff here is that these protocols can waste valuable network resources. Furthermore, many flooding-based protocols are inherently not scalable. Some protocols, such as Spray and Wait, attempt to compromise by limiting the number of possible replicas of a given message.
It is important to note that the vast majority of DTN routing protocols are heuristic-based, and non-optimal. This is due to optimality being, in the general DTN case, NP-hard. More specifically "online algorithms without complete future knowledge and with unlimited computational power, or computationally limited algorithms with complete future knowledge, can be arbitrarily far from optimal".
Replication-based routing.
Replication-based protocols have recently obtained much attention in the scientific community, as they can allow for substantially better message delivery ratios than in forwarding-based protocols. These types of routing protocols allow for a message to be replicated; each of the replicas, as well as the original message itself, are generally referred to as message copies or message replicas. Possible issues with replication-based routing include:
Since network resources may quickly become constrained, deciding which messages to transmit first and which messages to drop first play critical roles in many routing protocols.
Epidemic routing.
Epidemic routing is flooding-based in nature, as nodes continuously replicate and transmit messages to newly discovered contacts that do not already possess a copy of the message. In the most simple case, epidemic routing is flooding; however, more sophisticated techniques can be used to limit the number of message transfers. Epidemic routing has its roots in ensuring distributed databases remain synchronized, and many of these techniques, such as rumor mongering, can be directly applied to routing.
PRoPHET routing protocol.
Epidemic routing is particularly resource hungry because it deliberately makes no attempt to eliminate replications that would be unlikely to improve the delivery probability of messages. This strategy is effective if the opportunistic encounters between nodes are purely random, but in realistic situations, encounters are rarely totally random. Data Mules (mostly associated with a human) move in a society and accordingly tend to have greater probabilities of meeting certain Mules than others. The Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET) protocol uses an algorithm that attempts to exploit the non-randomness of real-world encounters by maintaining a set of probabilities for successful delivery to known destinations in the DTN ("delivery predictabilities") and replicating messages during opportunistic encounters only if the Mule that does not have the message appears to have a better chance of delivering it. This strategy was first documented in a paper from 2003.
An adaptive algorithm is used to determine the delivery predictabilities in each Mule. The Mule "M" stores delivery predictabilities "P"("M","D") for each known destination "D". If the Mule has not stored a predictability value for a destination "P"("M","D") is assumed to be zero. The delivery predictabilities used by each Mule are recalculated at each opportunistic encounter according to three rules:
The protocol has been incorporated into the reference implementation maintained by the IRTF DTN Research Group and the current version is documented in RFC 6693. The protocol has been trialled in real world situations during the Sámi Network Connectivity (SNC) project and is being further developed during the EU Framework Programme 7 project Networking for Communications Challenged Communities (N4C).
MaxProp.
MaxProp was developed at the University of Massachusetts, Amherst and was, in part, funded by DARPA and the National Science Foundation. The original paper is found in the IEEE INFOCOM 2006 conference. MaxProp is flooding-based in nature, in that if a contact is discovered, all messages not held by the contact will attempt to be replicated and transferred. The intelligence of MaxProp comes in determining which messages should be transmitted first and which messages should be dropped first. In essence, MaxProp maintains an ordered-queue based on the destination of each message, ordered by the estimated likelihood of a future transitive path to that destination.
MaxProp core.
To obtain these estimated path likelihoods, each node maintains a vector of size formula_1 (where formula_2 is the number of nodes in the network) consisting of the likelihood the node has of encountering each of the other nodes in the network. Each of the formula_1 elements in the vector is initially set to formula_4, meaning the node is equally likely to meet any other node next. When the node meets another node, formula_5, the formula_6 element of its vector is incremented by 1, and then the entire vector is normalized such that the sum of all entries add to 1. Note that this phase is completely local and does not require transmitting routing information between nodes.
When two nodes meet, they first exchange their estimated node-meeting likelihood vectors. Ideally, every node will have an up-to-date vector from every other node. With these n vectors at hand, the node can then compute a shortest path via a depth-first search where path weights indicate the probability that the link does not occur (note that this is 1 minus the value found in the appropriate vector). These path weights are summed to determine the total path cost, and are computed over all possible paths to the destinations desired (destinations for all messages currently being held). The path with the least total weight is chosen as the cost for that particular destination. The messages are then ordered by destination costs, and transmitted and dropped in that order.
MaxProp additions.
In conjunction with the core routing described above, MaxProp allows for many complementary mechanisms, each helping the message delivery ratio in general. First, acknowledgements are injected into the network by nodes that successfully receive a message (and are the final destination of that message). These acknowledgements are 128-bit hashes of the message that are flooded into the network, and instruct nodes to delete extra copies of the message from their buffers. This helps free space so outstanding messages are not dropped as often. Second, packets with low hop-counts are given higher priority. This helps promote initial rapid message replication to give new messages a "head start". Without this head start, newer messages can be quickly starved by older messages, since there are generally less copies of new messages in the network. Third, each message maintains a "hop list" indicating nodes it has previously visited to ensure that it does not revisit a node.
RAPID.
RAPID, which is an acronym for "Resource Allocation Protocol for Intentional DTN" routing, was developed at the University of Massachusetts, Amherst. It was first introduced in the SIGCOMM 2007 publication, DTN Routing as a Resource Allocation Problem. The authors of RAPID argue as a base premise that prior DTN routing algorithms incidentally effect performance metrics, such as average delay and message delivery ratio. The goal of RAPID is to intentionally effect a single routing metric. At the time of publication, RAPID has been instrumented to intentionally minimize one of three metrics: average delay, missed deadlines, and maximum delay.
RAPID protocol.
The core of the RAPID protocol is based around the concept of a utility function. A utility function assigns a utility value, formula_7, to every packet formula_8, which is based on the metric being optimized. formula_7 is defined as the expected contribution of packet formula_8 to this metric. RAPID replicates packets first that locally result in the highest increase in utility. For example, assume the metric to optimize is average delay. The utility function defined for average delay is formula_11, basically the negative of the average delay. Hence, the protocol replicates the packet that results in the greatest decrease in delay. RAPID, like MaxProp, is flooding-based, and will therefore attempt to replicate all packets if network resources allow.
The overall protocol is composed of four steps:
Spray and Wait.
Spray and Wait is a routing protocol that attempts to gain the delivery ratio benefits of replication-based