Conditional Shortest Path Routing in Delay Tolerant Networks

Abstract:

                             This article studies Delay tolerant networks (DTNs) where each node knows the probabilistic distribution of contacts with other nodes. Delay tolerant networks are characterized by the sporadic connectivity between their nodes and therefore the lack of stable end-to-end paths from source to destination. Since the future node connections are mostly unknown in these networks, opportunistic forwarding is used to deliver messages. Based on the observations about human mobility traces and the findings of previous work, we introduce a new metric called conditional intermeeting time. We propose Conditional Shortest Path Routing (CSPR) protocol that route the messages over conditional shortest paths in which the cost of links between nodes is defined by conditional intermeeting times rather than the conventional intermeeting times. When a node receives a message from one of its contacts, it stores the message in its buffer and carries the message until it encounters another node which is at least as useful (in terms of the delivery) as itself. Through trace-driven simulations, we demonstrate that CSPR achieves higher delivery rate and lower end-to-end delay compared to the shortest path based routing protocols that use the conventional intermeeting time as the link metric.

Existing System:

                      A connected hypercube with faulty links and/or nodes is called an injured hypercube. A distributed adaptive fault-tolerant routing scheme is proposed for an injured hypercube in which each node is required to know only the condition of its own links. Despite its simplicity, this scheme is shown to be capable of routing messages successfully in an injured n-dimensional hypercube as long as the number of faulty components is less than n. Moreover, it is proved that this scheme routes messages via shortest paths with a rather high probability, and the expected length of a resulting path is very close so that of a shortest path. Since the assumption that the number of faulty components is less than n in an n-dimensional hypercube might limit the usefulness of the above scheme, a routing scheme based on depth-first search which works in the presence of an arbitrary number of faulty components is introduced. Due to the insufficient information on faulty components, however, the paths chosen by this scheme may not always be the shortest. To guarantee all messages to be routed via shortest paths, the authors propose to equip every node with more information than that on its own links. The effects of this additional information on routing efficiency are analyzed, and the additional information to be kept at each node for the shortest path routing is determined.

Proposed System:

                        In this proposed system, we redefine the intermeeting time concept between nodes and introduce a new link metric called conditional intermeeting time. It is the intermeeting time between two nodes given that one of the nodes has previously met a certain other node. This updated definition of intermeeting time is also more convenient for the context of message routing because the messages are received from a node and given to another node on the way towards the destination. Here, conditional intermeeting time represent the period over which the node holds the message. To show the benefits of the proposed metric, we propose conditional shortest path routing (CSPR) protocol in which average conditional intermeeting times are used as link costs rather than standard intermeeting times and the messages are routed over conditional shortest paths (CSP). We compare CSPR protocol with the existing shortest path (SP) based routing protocol through real trace- driven simulations. The results demonstrate that CSPR achieves higher delivery rate and lower end-to-end delay compared to the shortest path based routing protocols. This show how well the conditional intermeeting time represents internode’s link costs (in the context of routing) and helps making effective forwarding decisions while routing a message. Routing algorithms in DTN’s utilize a paradigm called store-carry-and-forward. We generated the multiple messages from a random source node to a random destination node at each t seconds. Clearly, CSPR algorithm delivers more messages than SPR algorithm.

Algorithm Description:

              Our algorithm basically finds conditional shortest paths (CSP) for each source-destination pair and routes the messages over these paths. We define the CSP from a node n0 to a node nd as follows:

               CSP (n₀, n_d) = {n₀, n₁, . . . , n_d−1, n_d | R_n0 (n₁|t) +

                 d−1

                   ∑ Τ_ni (n_i+1|n_i−1) is minimized.}          

                    i=1

Here, t represents the time that has passed since the last meeting of node n₀ with n₁ and R_n0 (n₁|t) is the expected residual time for node n₀ to meet with node n₁ given that they have not met in the last t time units. R_n0 (n₁|t) can be computed as in with parameters of distribution representing the intermeeting time between n₀ and n₁. It can also be computed in a discrete manner from the contact history of n₀ and n₁.

Assume that node i observed d intermeeting times with node

j in its past. Let τ _i ¹ (j), τ _i ² (j), . . . τ _i ^d(j) denote these values. Then:

                      d

         R_i (j|t) = (∑      f ^k_i (j)/| {T ^k_i (j≥t}|) where,

                           k=1

           

            f ^k _i(j) ={  T ^k_i(j)-t       if  T ^k_i(j) ≥t

                          0                 otherwise  

Here, if none of the d observed intermeeting times is bigger

than t (this case occurs less likely as the contact history

grows), a good approximation can be to assume R_i(j|t) = 0. 

We will next provide an example to show the benefit of CSP

over SP. Consider the DTN illustrated in Figure 4. The weights of edges (A, C) and (A, B) show the expected residual time of node A with nodes C and B respectively in both graphs.But the weights of edges (C, D) and (B, D) are different in both graphs. While in the left graph, they show the average intermeeting times of nodes C and B with D respectively, in the right graph, they show the average conditional intermeeting times of the same nodes with D relative to their meeting with node A. From the left graph, we conclude that SP(A,D) follows (A,B,D). Hence, it is expected that on average a message from node A will be delivered to node D in 40 time units. However this may not be the actual shortest delay path. As the weight of edge (C, D) states in the right graph, node C can have a smaller conditional intermeeting time (than the standard intermeeting time) with node D assuming that it has met node A. This provides node C with a faster transfer of the message to node D after meeting node A. Hence, in the right graph, CSP(A, D) is (A,C,D) with the path cost of 30 time units. Each node forms the aforementioned network model and collects the standard and conditional intermeeting times of other nodes between each other through epidemic link state protocol. However, once the weights are known, it is not as easy to find CSP’s as it is to find SP’s. where the CSP(A, E) follows path 2 and CSP(A,D) follows (A, B, D). This situation is likely to happen in a DTN, if τD(E|B) ≥ τD(E|C) is satisfied. Running Dijkstra’s or Bellman-ford algorithm on the current graph structure cannot detect such cases and concludes that CSP(A, E) is (A, B,D, E).

Future Enhancement:

                                 In future work, we will look at the performance of the

proposed algorithm in different data sets to see the effect of conditional intermeeting time in different environments. Moreover, we will consider extending our CSPR algorithm by using more information (more than one known meetings) from the contact history while deciding conditional intermeeting times. For this, we plan to use probabilistic context free grammars (PCFG) and utilize the construction algorithm. Such a model will be able to hold history information concisely, and provide further generalizations for unseen data.

Hardware Requirements:

•         System                : Pentium IV 2.4 GHz.

•         Hard Disk            : 40 GB.

•         Floppy Drive      : 1.44 Mb.

•         Monitor               : 15 VGA Colour.

•         Mouse                 : Logitech.

•         Ram                     : 256 Mb.

Software Requirements:

•         Operating System        : - Windows XP Professional.

•         Front End                     : - Asp .Net 2.0.

•         Coding Language         : - Visual C# .Net.