Download Technical Report, Master`s Project

(d) Time t + 3 * dt
Figure 3. Transitivity[9] .
The DTN architecture provides an excellent starting position for implementing cooperative, transitive message relay between peers.
Furthermore, an example implementation of DTN is available, the DTNRI (Delay Tolerant Networking Reference Implementation) [4] . The DTNRI
forms a well-designed, cleanly written, and easily extensible code base, and is made available for public download. Convergence Layer
adapters allow DTNRI to be extended to support arbitrary link technologies. Currently, DTNRI convergence layers exist for UDP and TCP.
Arbitrary routing protocols can be added to the DTNRI by extending a new Router. At present, DTNRI has only a static router that depends on
manually configured routing entries. No dynamic routers exist; this is directly attributable to DTNRI's lack of dynamic neighbor discovery.
Neighbor discovery automates the discovery of peers and the configuration of links to those peers. (To state the same thing in different words:
without neighbor discovery, Step 1 in Figure 2 above is a process of manual configuration.) Without neighbor discovery, DTNRI is not a viable
solution to the problem of message routing in mobile populations of connection impoverished networks. Cooperative, transitive message relay
requires dynamic discovery of peers, automated link configuration of discovered peers, and routing protocols that can effectively build dynamic
routes by learning from patterns observed in such interaction between peers.
2.1.2.2 Directed Mobility
Research into directed mobility highlights the advantage of non-random mobility in connection impoverished challenged networks. Message
ferries[10] use a combination of location awareness (i.e., GPS) and short bursts over long-range radio to arrange rendezvous points.
Autonomous nodes (i.e., robots) move towards these rendezvous points to come into range with the message ferry to exchange messages via
short-range radio. MV [11] improves on message ferries by tracking history of encounters in order to optimize ferry motion for maximum delivery
rate throughout the network.
Other types of directed mobility leverage scheduled routes as opposed to robotic movements. DTLSR [12] is an adaptation of standard IP link
state routing protocols to the challenges of unreliable links. DTLSR serves well in an environment where topology does not change rapidly, such
as networks in which the dynamics stem from link instability.
2.1.2.3 Undirected Mobility
The harder challenge is faced by connection impoverished networks in environments of undirected mobility, since mobility patterns are less
predictable. Because of the scarcity of links, global topology cannot be determined. Since there is no expectation of directly encountering the
destination of each message, and topology is not available to advise routing decisions, messages are cooperatively relayed via encountered
peers. Strategies turn to replication instead, relaying messages to more than one peer to increase chances of delivery. However, in addition to
increasing the chances for delivery, replication also adds a burden to participants' limited storage resources as messages are queued through
the duration of link scarcity. (Recall our assumptions of cooperative relay and limited storage.)
The extreme case of replication, Epidemic[13] , relays a copy of every message in inventory to every peer encountered. In small populations with
low message load, this strategy is effective. However, such unbounded replication has consequences for both storage and bandwidth resources
as population size grows or message load increases. Epidemic cannot scale in networks of nodes with limited storage and bandwidthchallenged links: more storage resources are consumed queuing messages, and links are choked with the bandwidth requirements of
replication.
A modified replication strategy, Probabilistic Routing Protocol using History of Encounters and Transitivy (PRoPHET [14][9] ) proposes
optimizations to Epidemic to scale to higher message load and larger populations. PRoPHET introduces a queuing policy to prevent storage
utilization beyond a user configured quota. Forwarding decisions are guided by a heuristic that estimates the probability of future encounters for
each message's destination; messages are only relayed to peers with higher probability of encountering the message destination.
Observing that human mobility is non-random, PRoPHET tracks the history of encounters with peers as an indicator for the probability of future
meetings. This predictability metric also advises the queuing policy, which optimizes quota enforcement against delivery probability. Transitive
routes are learned by exchanging routing information bases between peers. If peers are not encountered very often, then their routes should
reflect a lower probability; this is accomplished by periodically aging the learned routes.