| Abstract | In this paper, we present a routing algorithm for a class ofdynamic networks called the Delay Tolerant Networks (DTNs). The proposed
algorithm takes into account the quintessential DTN characteristic namely,
intermittent link connectivity. We modify the breadth first search (BFS)
algorithm to take into account link state changes and find the quickest
route between source and destination nodes. We adopt a message drop policy
at intermediate nodes to incorporate storage constraint. We also introduce
the idea of time-varying storage domains where all nodes connected for a
length of time act as a single storage unit by sharing the aggregated
storage capacity of the nodes. We evaluate the routing algorithm with and
without storage domain in an extensive simulation. We analyze the
performance using metrics such as delivery ratio, incomplete transfers
with no routes and dropped messages. The DTN topology dynamics are
analyzed by varying: number of nodes generating traffic, link probability,
link availability through combinations of downtime/uptime values, storage
per node, message size, and traffic. The delay performance of the proposed
algorithms is conceptually the same as flooding-based algorithms but
without the penalty of multiple copies. More significantly, we show that
the Quickest Storage Domain (Quickest SD) algorithm distributes the
storage demand across many nodes in the network topology, enabling
balanced load and higher network utilization. In fact, we show that for
the same level of performance, we can actually cut the storage requirement
in half using the Quickest SD algorithm.
|
