29-12-2012, 06:17 PM
Efficient Implementation of Conditional Shortest Path Routing in Delay Tolerant Networks
1Efficient Implementation.pdf (Size: 1.17 MB / Downloads: 56)
Abstract
Routing in delay tolerant networks (DTN) is a challenging problem because at any given time instance, the probability that there is an end-to-end path from a source to a destination is low. Since the routing algorithms for conventional networks assume that the links between nodes are stable most of the time and do not fail frequently, they do not generally work in DTN’s. Therefore, the routing problem is still an active research area in DTN’s To realize the DTN vision, routes must be found over multiple unreliable, intermittently-connected hops. Many researchers have investigated this fundamental challenge, to overcome these challenges, this paper propose Conditional Shortest Path Routing (CSPR) protocol that routes 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. 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.
INTRODUCTION
Delay-tolerant networks (DTNs) have the potential to connect devices and areas of the world that are not well-served by current networking technology. Instead of relying on end-to-end network connectivity, DTNs take advantage of temporary connections to relay data in a fashion similar to the postal network [1]. These networks could be useful in scenarios ranging from interconnecting sensors to connecting remote regions of the world.
Routing algorithms in DTN’s utilize a paradigm called store-carry-and-forward. 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. Then the message is forwarded to it. Based on this paradigm, several routing algorithms with different objectives (high delivery rate etc.) and different routing techniques (single-copy [2] [3], multi-copy [4] [5], erasure coding based [6] etc.) have been proposed recently. However, some of these algorithms [7] used unrealistic assumptions.
LITERATURE SURVEY
Work on DTN networks shows that it is possible to automatically route in networks, even when nodes are mobile and the link quality varies. There is a huge body of work on routing protocols [13-15] and metrics [16, 17] for this environment. However, these protocols and metrics find end-to-end paths, and do not support communication between nodes in different network partitions.
Recent studies on routing problem in DTN’s have focused on the analysis of real mobility traces (human [11], vehicular [18] etc.). Different traces from various DTN environments are analyzed and the extracted characteristics of the mobile objects are utilized on the design of routing algorithms for DTN’s. An approach that uses a single copy of each message is presented by Jain et al. [7].
CONDITIONAL SHORTEST PATH ROUTING MECHANISM
Existing system
Message delivery in sparse DTN is difficult due to the fact that the network graph is rarely (if ever) connected. A key challenge is to find a route that can provide good delivery performance and low end-to-end delay in a disconnected network graph where nodes may move freely. Some bridge nodes are identified based on their centrality characteristics, i.e., on their capability to broker information exchange among otherwise disconnected nodes. Due to the complexity of the centrality metrics in populated networks the concept of ego networks is exploited where nodes are not required to exchange information about the entire network topology, but only locally available information is considered. Then SimBet Routing is proposed which exploits the exchange of pre-estimated "between’s' centrality metrics and locally determined social "similarity' to the destination node. We present simulations using real trace data to demonstrate that SimBet Routing results in delivery performance close to Epidemic Routing but with significantly reduced overhead. Additionally, we show that SimBet Routing outperforms PRoPHET Routing, particularly when the sending and receiving nodes have low connectivity
Networking module
Client-server computing or networking is a distributed application architecture that partitions tasks or workloads
between service providers (servers) and service requesters, called clients. Often clients and servers operate over a
computer network on separate hardware. A server machine is a high-performance host that is running one or more
server programs which share its resources with clients. A client also shares any of its resources; Clients therefore
initiate communication sessions with servers which await (listen to) incoming requests.
Multi Hop Module
Analyze the load for a homogeneous multi-hop wireless network for the case of straight line routing in shortest path routing is frequently approximated to straight line routing in large multi-hop wireless networks. Since geographical and geometric attributes of nodes and routes affect the nodal load, we employ results from geometric probabilities to solve the problem. Based on our analytical results, we are able to show the precise relationship between the number of nodes and the load at each node, and the geographical distribution of the relaying load over the network for different scenarios. Interestingly, straight line routing itself can balance the relay load over the disk in certain cases. This info shown in Fig 4 and 5.
CONCLUSIONS AND FUTUREWORK
Delay-Tolerant network (DTN) is a network in which no simultaneous end-to-end path exists. And the messages delivered in the DTN usually have large delivery latency due to network partition. These special characteristics make DTN routing a challenging problem. For this purpose, we updated the shortest path based routing algorithms using conditional intermeeting times and proposed to route the messages over conditional shortest paths. Finally, we ran simulations to evaluate the proposed algorithm and demonstrated the superiority of CSPR protocol over the existing shortest path routing algorithms.