Routing in delay-tolerant networking

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: • network congestion in clustered areas, • being wasteful with network resources (including bandwidth, storage, and energy), and • network scalability. 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 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: • When the Mule M encounters another Mule E, the predictability for E is increased: P(M,E)new = P(M,E)old + (1 - P(M,E)old) * Lencounter where Lencounter is an initialisation constant. • The predictabilities for all destinations D other than E are 'aged': P(M,D)new = P(M,D)old * γK where γ is the aging constant and K is the number of time units that has elapsed since the last aging. • Predictabilities are exchanged between M and E and the 'transitive' property of predictability is used to update the predictability of destinations D for which E has a P(E,D) value on the assumption that M is likely to meet E again: P(M,D)new = P(M,D)old + (1 - P(M,D)old) * P(M,E) * P(E,D) * β where β is a scaling constant. 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 first introduces the understanding of human mobility into the DTN design. They study the social structures of the between devices and leverage them in the design of forwarding algorithms for Pocket Switched Networks(PSNs). With experiments of real world traces, they discover that human interaction is heterogeneous both in terms of hubs and groups or communities. According to this finding, they propose Bubble Rap, a social-based forwarding algorithm, to improve the forwarding efficiency significantly compared to history-based PROPHET and social-based SimBet algorithms. This algorithm also shows how it can be implemented in a distributed way, which demonstrates that it is applicable in the decentralized environment of PSNs. CafRep Protocol CafRep is a fully localised adaptive forwarding & replication protocol with congestion control and avoidance to enable congestion-aware mobile social framework in heterogeneous DTNs. CafRep uses a combined social, buffer and delay metrics for congestion-aware message forwarding and replication that maximises message delivery ratio and availability of nodes while minimising latency and packet loss rates at times of increasing congestion levels. At the core of CafRep is a combined relative utility driven heuristics that allow highly adaptive forwarding and replication policies by managing to detect and offload congested parts of the network and adapting the sending/forwarding rates based on resource and contact predictions. RACOD RACOD: Routing Using Ant Colony Optimization in DTN introduces learning of paths using ACO and also intelligently decides which message to drop and which message to transfer. In DTN, there is no exact knowledge of destination and thus we need to spread messages in all direction to search for the destination. ACO helps in wandering and building shortest path effectively. Protocol uses light-weight messages called ant to build shortest paths, the ant’s movement in ACO can be mapped with propagation of messages that are replicated in DTN and look for their destination. Moreover, this protocol also gives a better buffer management technique, it introduces a 3-way sort technique which helps in dropping old-aged or malicious messages and thus, reduces buffer overhead. == Forwarding-based routing ==

Delay-Tolerant Link State Routing (dtlsr) DTLSR is implemented in the DTN2 BP implementation and aims to provide a straightforward extension of link-state routing. With DTLSR, link state announcements are sent as in OLSR, but links that are deemed 'down' are not immediately removed from the graph. Instead, 'downed' links are aged out by increasing their metrics until some maximum is reached, at which point they are removed from the graph. The intent of this is to cause data to continue to flow along paths that used to be supported in the hope that they will be supported again in the future. Schedule-Aware Bundle Routing (also Contact Graph Routing) The SABR protocol is an extension of Contact Graph Routing that seeks to provide a routing solution for a wide range of scenarios that include both scheduled and discovered connectivity. For the scheduled connectivity regime, SABR uses a 'contact plan' provided by network management describing the current connectivity and future connectivity schedule. SABR then makes forwarding decisions based on an earliest-arrival-time metric where bundles are routed over the time-varying connectivity graph. SABR uses historical contact information and neighbor discovery to address routing over non-scheduled links. The SABR protocol is being standardized by the Consultative Committee for Space Data Systems. Non-cooperative Routing in Delay-Tolerant Networks The majority of existing routing and data delivery protocols for DTNs assume that mobile nodes willingly participate in data delivery, share their resources with each other, and follow the rules of underlying networking protocols. Nevertheless, rational nodes in real-world scenarios have strategic interactions and may exhibit selfish behaviours due to various reasons (such as resource limitations, the lack of interest in data, or social preferences). For example, in case a node has limited battery resources or the cost of the network bandwidth delivered by mobile network operators is high, it would not be willingly to relay data for others until appropriate incentives are provided. Meanwhile, malicious nodes may attack the network in different ways to disturb the normal operation of the data transmission process. An adversary, for example, may drop received messages but produce forged routing metrics or false information with the aim of either attracting more messages or decreasing its detection probability. This issue becomes more challenging when some colluding attackers boost their metrics to deceive the attack detection systems. However, dealing with the non-cooperative behaviours of mobile nodes in DTNs is very challenging because of the distributed network model and intermittent access of nodes to centralised authorities. == References ==