Routing in Delay-tolerant Networking - Routing Protocol Classifications

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. This simple, yet popular, taxonomy was recently used by Balasubramanian et al. to classify a large number of DTN routing protocols.

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".