Performance Analysis of Few Replication-Based Routing Protocol in Delay Tolerant Network

Performance Analysis of Few Replication-Based Routing Protocol in Delay Tolerant Network

Sunny Saikia Mousumi Ara Ahmed Satyajit Sarma(Guide)

Dept of Information Technology Dept of Information Technology Dept of Information Technology

GU Institute of Science and Technology

Guwahati, Assam, India

GU Institute of Science and Technology

Guwahati, Assam, India

GU Institute of Science and Technology

Guwahati, Assam, India

Abstract with the rise of new technologies there arise a new class of challenged wireless network derived from deep space communication known as Delay Tolerant Network or DTN characterized by intermittent connectivity, long delay, asymmetric data rate and high error rate. DTN networks lack instantaneous end-to-end communication path between the source and destination, these are opportunistic networks. Due to which routing protocols are of great concern in these class of network. In this paper we have investigated and compared the performance of five DTN routing protocols namely: EPIDEMIC, PROPHET, PROPHETv2, RAPID and SPRAY

AND WAIT using two different simulation setup in the ONE simulator. One by analyzing the performance by varying the message TTL(Time to Leave) and keeping the buffer size constant, next by varying the buffer size and keeping the message TTL constant. The performance is compared based on three metrics namely: overhead ratio, average latency and delivery probability in both the scenarios. From the results obtained in both considerations it is observed that the SPRAY AND WAIT routing protocol gives the best performance.

Keywords Delay tolerant networks, EPIDEMIC, PROPHET, PROPHETv2, Spray and wait, RAPID, opportunistic network environment (ONE)

. INTRODUCTION

DTN or disruption tolerant network is a practical class of challenged wireless network evolved from Mobile ad hoc Network. In 2002 Kelvin Fall [1] coined the term delay tolerant network and the DTN acronym by adopting some of the ideas of interplanetary network design to terrestrial networks. DTN networks are characterized by limited resources, long delay, asymmetric data rate, high error rate Intermittent connectivity and low SNR (Signal to Noise Ratio). The data transmission process of DTN networks as compared to the traditional networks is quite different, there is no fixed end-to-end path between the end hosts in a DTN network and the network topology is dynamic. All the nodes in a DTN network can act as a router with a transmission range and buffer (to store data as it adopts a store-and- forward policy).The data transmission takes place when a mobile node comes into transmission range of another mobile

node until then the message is stored in its buffer. Examples of DTN include Exotic Media Networks, Vehicular Networks, Military Ad-Hoc Networks, Terrestrial Mobile Networks, and Sensor/Actuator Networks etc.

In this paper we have analyzed and compared the performance of five different DTN replication-based routing protocols (EPIDEMIC; PROPHET; PROPHETv2; RAPID;

Spray and Wait) using two different simulation scenario one by varying the message TTL and keeping buffer size constant and another by varying the buffer size and keeping the message TTL constant. These five protocols were analyzed on three different metrics namely Over Head Ratio, Delivery Probability and Average Latency. The details of the simulation setup along with the metrics are given in section 3.

The rest of the paper is organized as follows: section 2 Briefly gives a review of routing in DTN and an abstract of the five routing protocols viz. EPIDEMIC, PROPHET, PROPHETv2, Spray and Wait and RAPID. Section 3 describes the details of the simulator used and the simulation setup for both the considered scenarios. Section 4 discusses the simulation results. Section 5 concludes this paper.

1. ROUTING IN DTN

   As compared to the traditional routing protocol assumptions there is no end-to-end path between the source and destination in a DTN network to route data. Due to this lack of connectivity between the end hosts the main objective of routing in this challenged network is to maximize the message delivery probability, minimize delivery latency along with it also minimize the use of resources (i.e. network bandwidth, buffer space and battery energy). To fulfill these objectives many routing protocols have been devised which is basically based on store-and-forward mechanism. Routing protocols in DTN can be classified based on many characteristics. In this paper we have adopted the popular taxonomy used by Balasubramanian et al. [2] to classify a large number of DTN routing protocols based on whether the protocol is replication based or forwarding based. Protocols that create replicas of messages are known as replication based and those that do not create replicas are known as forwarding based. There is also variation in the replication

   based protocols as the number of replicas created is different in different protocols.

   In this paper we have analyzed the performance of five different replication based protocols namely: EPIDEMIC, PROPHET, PROPHETv2, RAPID and SPRAY AND WAIT,

   as replication-based protocols can allow for substantially better message delivery ratios as compared to the forwarding- based protocols.

   1. EPIDEMIC Routing

      Vahdat et al and Becker [3] proposed the first routing protocol for DTN which is known as the EPIDEMIC routing protocol. It is flooding based in nature i.e. it creates multiple copies of the same message and spreads it across the network to reach the destination host. Each node maintains a bundle summary vector describing each bundles destination, length and hop count. An anti-entropy session takes place when two nodes encounter each other, where they compare their bundle summary vector to ascertain missing bundles. Nodes stop their anti-entropy session when they have the same bundle summary vector. EPIDEMIC routing gives a high probability of message delivery but it wastes a lot of resources.

   2. PROPHET

      PROPHET [4] or probabilistic routing protocol is developed by Lindgren et al to overcome the problem face by EPIDEMIC protocol. Probabilistic Routing Protocol is implemented using the knowledge of History of Encounters and Transitivity. It enables communication between participating nodes wishing to communicate in an intermittently connected Network where at least some of the nodes are mobile. In PROPHET every node uses a probabilistic metric called delivery predictability to transfer messages to a reliable node, the higher the delivery predictability for a node it indicates that it is more reliable than other nodes to forward the message to destination. PROPHET also has some disadvantage, an important drawback of PROPHET routing is its inability to support priorities.

   3. PROPHETv2

      PROPHETv2 is an updated version of PROPHET routing protocol. The design and ideas of PROPHETv2 are almost same as PROPHET routing protocol but a minor modification is done in coding i.e. in evaluation function. Simulation evaluations done shows that PROPHETv2 perform better than the former PROPHET routing protocol, basically in cases of heterogeneous network mobility scenarios.

   4. RAPID

      RAPID [6] act as a Resource Allocation Protocol for Intentional DTN. The basic idea of RAPID protocol is to intentionally optimize a single routing metric i.e. average delay, missed deadlines, or maximum delay. The main concept of the RAPID protocol is use of a utility function. This utility function assigns a utility value, depending on the routing metric whic to be optimized. This is also defined as the expected contribution of the packet to the routing metric. RAPID is also a flooding based routing protocol in nature. It

      first replicate those packet which are able to result is highest increase of utility function. So it is also called as a utility- driven resource allocation model.

   5. SPRAY and WAIT

      Spray and Wait [7] protocol is a flooding or replication based routing protocol that provide a limitation in blind forwarding message strategy of EPIDEMIC routing. This is done by associating number L to messages that indicates the maximum allowable copies of the message. The Spray and Wait protocol mainly consist of two phase- Spray phase and Wait phase. In Spray phase L message copies are first spread to L distinct "relays" and then it goes to wait phase. In this phase it waits until it reached the destination. For queue management, Spray and Wait protocol uses FIFO strategy. This protocol reduced the wastage of resource and so it gives better performance than EPIDEMIC and even PROPHET routing protocol also.

2. SIMULATION SETUP

   The protocols mentioned in this paper are simulated using the Opportunistic Network Environment (ONE) Simulator (Keranen et al.2009). It is a simulation environment which is designed especially for DTN network protocols. It is an agent-based discrete event simulation engine. It is written in Java. Modeling of node movement, inter-node contacts, routing and message handling are the main functions of the ONE simulator. Through visualization, reports and post-processing tools result collection and analysis are done. A detailed description of the simulator is available in [8] and the ONE simulator project page [9] where the source code is also available.

   1. Simulation Parameters

      The Table 1 summarizes the simulation configuration Used for the first scenario where the message TTL (Time to leave) is varied and buffer size is kept constant. The Table 2 summarizes the simulation configuration used when the message TTL is kept constant and the buffer size is varied.

   2. Performance Metrics

      The following metrics are used for the performance analysis of the mentioned five protocols:

      1. Over Head Ratio: It gives a measure of the extra number of packets needed for actual delivery of the data packets by the routing protocol.

         Overhead ratio = (R-D)/D (1) Where D is a number of messages delivered to their destination and R is a number of messages forwarded by relay nodes.

      2. Delivery Probability: The delivery probability or delivery ratio gives a measure of the total number of messages delivered to their destination to total number of messages created at source node.

         Delivery ratio = D/G (2) Where G is the number of messages created at source and D is a number of messages delivered to destination.

      3. Average Latency: It gives the measure of average time between the creation of message and when it is received by the destination.

3. RESULTS AND DISCUSSION

   The performance of the above mentioned five protocols are analyzed on the ONE simulator using the above mentioned parameters on three metrics namely: delivery probability, average latency and overhead ratio. Two experiments have been conducted. The first experiment

   =

   Average Delay = (

   1 (R – G))/n (3)

   simulates a network with varying message TTL and constant buffer size. The second experiment simulates a network with

   Where n is the number of messages delivered to their destinations, R is the time when a message e reaches to its destination, and G is the time when a message e is created.

   TABLE I: SIMULATION PARAMETER FOR CONSTANT BUFFER SIZE

   Parameter	Value
   Total Simulation Time	12 Hours
   Movement Model	ShortestPathMapBasedMovement
   World Size	4500 X 3400 m
   Node Buffer Size	5M
   No of Nodes	126
   Interface transmit Speed	2 Mbps
   Node Movement Speed	Min=0.5 m/s Max=1.5 m/s
   Message Size	500 KB to1 MB
   Message Creation Rate	One message per 25-35 sec
   Routing Protocol	EPIDEMIC; PROPHET;PROPHETv2; RAPID; Spray and Wait
   Interface Transmit Range	10 m
   msgTTL	60,120,180,240,300,360

   TABLE II : SIMULATION PARAMETER FOR CONSTANT TTL

   Parameter	Value
   Total Simulation Time	12 Hours
   Movement Model	ShortestPathMapBasedMovement
   World Size	4500 X 3400 m
   Node Buffer Size	2M; 4M; 6M; 8M; 10M
   No of Nodes	126
   Interface transmit Speed	2 Mbps
   Node Movement Speed	Min=0.5 m/s Max=1.5 m/s
   Message Size	500 KB to1 MB
   Message Creation Rate	One message per 25-35 sec
   Routing Protocol	EPIDEMIC; PROPHET;PROPHETv2; RAPID; Spray and Wait
   Interface Transmit Range	10 m
   msgTTL	300

   varying buffer size and keeping message TTL constant. Table

   1 and Table 2 show the simulation parameters for constant buffer size and constant message TTL respectively.

   1. Impact of varying message TTL

      The first experiment has been conducted by changing the values of the message TTL. The simulation is conducted for TTL values 60,120.180,240,300 and 360 minutes respectively. As the TTL value increases the delay also increases. The impact of changing the TTL on the three performance metrics are discussed below.

      1. Delivery Probability: From the Fig.1 it is evident that the delivery probability of Spray And Wait routing protocol in the considered scenario is high and it increases from 0.36 to 0.45 as message TTL increases from 60 to 360 minutes. The delivery probability of the RAPID routing protocol (which increases from 0.31-0.40, as TTL increases) is high as compared to PROPHETv2, PROPHET and EPIDEMIC. The delivery probability of PROPHETv2 remains almost constant (approx 0.33) and gives better delivery probability than PROPHET and EPIDEMIC routing protocol. Whereas the delivery probability of PROPHET and EPIDEMIC remains almost constant (approx 0.25) as message TTL increases (60- 360 minutes).

      2. Average Latency: From the simulation result as shown in Fig.2 it is obvious that the average Latency experienced by packets is lowest in the Spray and Wait routing protocol. It is also evident that the average latency experienced by all the five routing protocol increases with increase in TTL, this is due to the fact that with increasing TTL the lifetime of the packet increases and it has to wait more and more in the buffer before it is either delivered to the destination node or it is being discarded due to lifetime expiry. So the Average latency increases with the increase in the lifetime of the message(i.e. message TTL), and Average- latency is highest in case of RAPID routing protocol as compared to PROPHET, PROPHETv2, EPIDEMIC and SPRAY AND WAIT.

      3. Overhead Ratio: From Fig.3 we find that the overhead ratio of the Spray and Wait routing protocol is minimum as compared to RAPID, PROPHET, PROPHETv2 and EPIDEMIC. Overhead ratio of Spray and Wait decreases and almost becomes constant(approx 0.18) as TTL increase (120-360 minutes).Overhead ratio of RAPID decreases from marginally 54 packets to approx 42 packets as TTL increases. Whereas Overhead ratio of PROPHETV2 increases from 43

      Probability

      packets to 57 packets, again Overhead ratio of EPIDEMIC and PROPHET increases with increasing TTL.

      Delivery Probability

      0.5 Epidemic

      Prophet Prophetv2

      0

      Rapid

      60 120 180 240 300 360

      TTL (mins)

      Spray and

      Wait

      Fig. 1. Impact of varying message TTL on delivery probability

      Average Latency

   2. Impact of varying Buffer Size

      The second experiment has been conducted by changing the values of the buffer size. The simulation is conducted for buffer size of 2M, 4M, 6M, 8M and 10M respectively, on the three performance metrics mentioned above using the simulation parameter mentioned in Table 2.

      1. Delivery Probability: From Fig.4 it is obvious that the delivery probability of Spray and Wait routing protocol in the considered scenario is high and it increases from 0.21 to

         0.67 as message buffer size increases from 2 to 10 Mbytes. The delivery probability of the RAPID routing protocol (which increases from 0.21-0.65, as buffer size increases) is high as compared to PROPHETv2, PROPHET and EPIDEMIC. The delivery probability of PROPHET and EPIDEMIC routing protocol remains almost equal and delivery probability of PROPHETv2 is slightly better than PROPHET and EPIDEMIC routing protocol.

      2. Average Latency: From Fig.5 which gives the variation in average latency experienced by the message bundle on varying the buffer size it is obvious that the average Latency experienced by packets is lowest in the Spray and Wait routing protocol. And highest in the RAPID routing protocol. PROPHETv2 is slightly better than EPIDEMIC and PROPHET in case of the average latency of the message bundles.

         Avg. Latency

         5500

         4000

         2500

         1000

         60 120 180 240 300 360

         Epidemic Prophet Prophetv2 Rapid

         Spray and Wait

      3. Overhead Ratio: From Fig .6 which gives the variation of overhead ratio against varying buffer size we come to the conclusion that the overhead ratio of the Spray and Wait routing protocol is minimum as compared to RAPID,PROPHET,PROPHETv2 and EPIDEMIC. Overhead ratio of Spray and Wait decreases (25-12) as buffer size increases (2-10 Mbytes). Overhead ratio of RAPID is comparatively better than PROPHETv2, PROPHET and EPIDEMIC routing protocol. While overhead ratio of the PROPHETv2 routing protocol nearly remains constant (approx 54) with increasing buffer size.

   Prophet

   100

   Epidemic

   150

   Overhead Ratio

   Fig. 2. Impact of varying message TTL on Average Latency

   Overhead Ratio

   Rapid

   60 120 180 240 300 360

   Prophetv2

   50

   0

   Fig. 3. Impact of varying message TTL on Overhead Ratio

   Delivery Probability

   0.7

   Epidemic

   0.35

   Prophet

   Prophetv2

   0

   Rapid

   Buffer size ( Mbytes)

   Spray and Wait

   2 4 6 8 10

   Probability

   Fig. 4. Impact of varying Buffer size on Delivery Probability

   Average Latency

   6000

   Epidemic

   Prophet

   2 4 6 8 10

   Spray and Wait

   Buffer size ( Mbytes)

   Rapid

   2000

   Prophetv2

   4000

   Avg. Latency

   Overhead Ratio

   Fig. 5. Impact of varying Buffer size on Average Latency

   Overhead Ratio

   150

   Epidemic

   100

   Prophet

   2 4 6 8 10

   Spray and

   Buffer size (Mbytes) Wait

   Rapid

   0

   Prophetv2

   50

   Fig. 6. Impact of varying Buffer size on Overhead Ratio

4. CONCLUSION

In this paper we have analyzed the performance of five DTN replication-based routing protocols (EPIDEMIC; PROPHET; PROPHETv2; Spray and Wait and RAPID) using two simulation parameter. First by varying the message TTL and keeping buffer size constant; and second one by varying the buffer size and keeping the message TTL constant. The analysis clearly shows that the Spray and Wait

routing protocol gives best results for the three considered performance metrics namely: delivery probability, overhead ratio and average latency in both the simulation environment. So among the considered five routing protocols the Spray and Wait routing protocol gives the best performance in the given set of conditions and considered scenario.

REFERENCES

1. K. Fall, A Delay-Tolerant Network Architecture for Challenged Internets, in Proc. ACM SIGCOMM Conf. on Application, technologies, architectures, and protocols for computer communications (New York, NY, USA, 2003) pp. 27-34.

2. Aruna Balasubramanian, Brian Neil Levine, and Arun Venkataramani. DTN routing as a resource allocation problem. In Proc. ACM SIGCOMM, August 2007.

3. A. Vahdat and D. Becker, EPIDEMIC routing for partially connected ad hoc networks, Technical Report CS-200006, Duke University,

   April.

4. A. Lindgren, A. Doria, and O. Schelen, Probabilistic routing inintermittently connected networks, in The First International Workshop on Service Assurance with Partial and Intermittent Resources (SAPIR), 2004.

5. A. Lindgren, A. Doria, and O. Schelen, Probabilistic routing in intermittently connected networks. SIGMOBILE Mob, Comput. Commun. Rev. vol. 7, no. 3, 2003, pp. 19-20.

6. B. Aruna, L. B. Neil, and V. Arun, DTN Routing as a Resource Allocation Problem, SIGCOMM07, Kyoto, Japan, August 2731, 2007.

7. T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, in Proc. ACM SIGCOMM workshop on Delay-tolerant networking,

   (Philadelphia, PA, USA, August 2005), pp. 252259.

8. A. Ker¨Anen, opportunistic network environment simulator. special assignment report, helsinki university of technology, Department of Communications and Networking, May 2008.

9. Tkk/Comnet. Project page of the ONE simulator. [Online]. Available: http://www.netlab.tkk.fi/tutkimus/dtn/theone, 2009.

10. A. Ker¨Anen, opportunistic network environment simulator. special assignment report, helsinki university of technology, Department of Communications and Networking, May 2008.

11. Harminder Singh Bindra and A. L. Sangal, Performance Comparison of

RAPID, Epidemic and Prophet Routing Protocols for Delay Tolerant Networks, International Journal of Computer Theory and Engineering Vol.4,No.2,April2012