Performance Evaluation of MaxProp Routing Protocol with DL, FIFO, DLA and MOFO Buffer Management Techniques in DTN under Variable Message Buffer Size

Performance Evaluation of MaxProp Routing Protocol with DL, FIFO, DLA and MOFO Buffer Management Techniques in DTN under Variable Message Buffer Size

Anita Rani1, Sangeeta Rani2, Harminder Singh Bindra3

1. Student of M.Tech.CSE, Chaudhary Devi Lal University, Sirsa

2. Teaching Associate, Computer Sci. & Applications Department, Chaudhary Devi Lal University, Sirsa

3. HOD IT Department, Malout Institute of Management & Information Technology, Malout

Abstract- Delay Tolerant Networks or DTNs are the results of the evolutions in the mobile ad hoc networks (MANETs). In such environments the link between the pair of nodes is frequently disrupted due to the dissemination nature, mobility of nodes, and power outages. Because of the environment nature in Delay Tolerant Networks like under water, ocean sensor networks etc., the delays may be very extensive. To obtain data delivery in such challenging and harsh networking environments, researchers have proposed a technique in which the messages is stored into the buffers of intermediary nodes until it is forwarded to the destination. The message is stored by a node for a long time period in its buffer till the appropriate forwarding opportunity comes. In addition to this, multiple copies of message are often disseminated, so as to increase the delivery probability. Due to the long term storage in buffer and multiple copies of messages results in higher overheads on the nodes. Thus, in order to decrease overhead, proficient buffer management techniques are required to determine which messages should be discarded first, when the nodes are almost full to their buffer capacity. In this paper we have evaluated the performance of four buffer management techniques namely FIFO, DL, DLA and MOFO with MaxProp routing protocol under variable message buffer size. For simulation we have used ONE (Opportunistic Network Environment) simulator. The performance is analyzed on four metrics: Delivery probability, Overhead Ratio, Latency Average and Hop Count Average.

Key Words: Delay Tolerant Networks, DL, FIFO, DLA, MOFO, MaxProp, Opportunistic Network Environment(ONE).

1. INTRODUCTION

Delay Tolerant Networks (DTN) are an important class of emerging networks that exhibit significantly different characteristics from todays Internet, such as intermittent connectivity, large delay, and high loss rates. DTNs arise in a variety of environments such as disaster relief, military, rural Internet access, environmental sensing and surveillance, deep space communications, underwater sensing, and inter-vehicle communication[1]. While not the common case for networking, these environments represent some of the most critical cases, where the ability to communicate can make a

huge difference for human lives. The substantial research in the field of DTN communications have been seen in the past decade. Traditional routing protocols assume that there is an end-to-end connectivity, hence they are not able to work in delay tolerant networks. In DTNs there is no end-to-end connectivity at all the times due to frequent disruptions. Thus, TCP/IT protocols mechanisms fails to communicate in such environment. The delays in DTNs can also occur because of environment nature like underwater, deep space, ocean sensor networks. In order to obtain the higher delivery probabilities of the messages and reliable communication in such challenging networks, many approaches have been adopted. Several issues like increasing the delivery ratio or minimizing the delivery delays, optimizing resources usage etc. has been the main focused area of the researchers. In this study, we have evaluated the performance of MaxProp Routing protocol with four buffer management techniques namely DL, FIFO, DLA and MOFO under variable message buffer size. These techniques were analyzed on the four different metrics namely Delivery Probability, Overhead Ratio, Latency Time Average and Hop Count Average. The detailed simulation setup and performance metrics are given in the sections IV and V.

The remainder of paper is organized as follows: section II and III briefly gives the introduction about the various buffer management techniques and routing protocols. Section IV gives the details of simulator and the simulation setup used to carry out the work. Section V describes the various metrics used for the performance evaluation. Section VI discusses the results and Section VII concludes the paper and lists the directions for future work.

1. BUFFER MANAGEMENT TECHNIQUES

   Buffer Management technology is a fundamental approach that manages the various resources among different situations as per the technique used. An efficient buffer management technique decides at each step that which of the messages is to be dropped first when buffer is full likewise which of the messages are to be transmitted, when bandwidth is limited.

   Some of the popular buffer management techniques are as follows:

   Drop Least Recently Received (DLR)

   In DLR technique as the name implies, the message which is staying for a long time in the buffer will be dropped first. As it has the less probability to be conceded to the other nodes [13].

   Drop Oldest (DOA)

   The message having shortest remaining life time (TTL) is dropped first. The idea of dropping such a message is that if its TTL is small, then it is in the network for a long time and thus as high probability to be already delivered [13].

   Drop Front (DF) FIFO

   This technique drops the messages on the basis of the order in which they entered into the buffer, for example the first message that entered the queue will be the first to be dropped [6].

   Drop Largest (DLA)

   In Drop Largest (DLA) buffer management technique, message having large size will be selected in order to drop[13].

   MOFO (Evict Most Forwarded First)

   MOFO attempts to maximise the propagation of the messages through the network by dropping the message that has been forwarded the maximum number of time. In such way the messages with lower hop count enables to travel further within the network [6].

   DL-Drop Last

   The newly received message is first removed simply.

   MOPR (Evict Most Favorably Forwarded First)

   MOPR keeps the value for each message in its queue and each time a message is replicated. The message value is increased based on the predictability of the message being delivered, using this technique, the message with the highest value is dropped first [6].

   SHLI (Evict Shortest Life time First)

   This technique uses the message timeout value, which specifies when it is no longer useful, such that a message with the shortest remaining life time is dropped first[6].

   LEPR (Evict least probable first)

   LEPR technique works by a node ranking the messages within its buffer based on the predicted probability of delivery of the messages, the message with the lowest probability is dropped first[6].

   This study evaluates the performance of DL, FIFO, DLA and MOFO buffer management techniques on the basis of metrics, delivery probability, overheads ratio, latency time average and hop count average.

2. ROUTING PROTOCOLS

   Epidemic Routing protocol

   In DTN, among all the routing protocols, Epidemic routing protocol is the leading protocol. This protocol is flooding based in nature as all the nodes continuously replicate and transmit the messages to the adjacent nodes that do not already have a copy of the message. Using this protocol, when a node comes into the contact of other node, it checks whether the new node has the copy of this essage or not. If it does not have, then the new message is forwarded to that node. This protocol uses the summary vectors for this task. The node exchanges their summary vectors when they comes in the communication range of each other to decide which message have not been seen by that node. Host request for a copy of a message which it has not seen yet. The receiving host has the complete autonomy to reject or accept the message[16].

   Direct Delivery

   Direct Delivery is a forwarding based routing protocol, in which the message is delivered directly to the destination node and replicating and relaying of the messages does not take place. Among all the routing protocols in DTN, Direct Delivery is resource efficient protocol[2].

   First Contact

   First Contact is also a forward based technique. Using this routing protocol, the nodes transmits the message to the first node which comes in contact and which do not have the message already. The First Contact results in wastage of electric power as forwarding is very extensive. [3].

   RAPID

   RAPID is an acronym for Resource Allocation Protocol for Intentional DTN routing. RAPID models DTN forwarding as a utility-driven resource allocation problem. Routing is achieved by prioritizing messages to be forwarded and messages to be dropped based upon a utility function. The utility metric is dependent on the goal of the network, RAPID defines 3 metrics: Minimizing Average Delay, Minimizing Missed Deadlines and Minimizing Maximum Delay. When using the

   Minimizing Average Delay Metric a node attempts to greedily replicate the message that reduces the average delay among all packets in its buffer. The Minimizing Missed Deadlines Metric replicates the message that has the highest probability of being delivered within its deadline. The Minimizing Maximum Delay Metric replicates the packet with the earliest creation time in order to minimizing the maximum delay for each message[6].

   PRoPHET routing protocol

   Epidemic routing protocol is a resource hungry protocol because it makes no attempt to remove the replications deliberately that would be unlikely to increase the delivery probability of the messages. Such type of strategy is more effective if the opportunities of delivering the messages encounters between the nodes are purely random, but in realistic circumstances, meeting of nodes are rarely totally random. Data Mules such as human beings moves in the society and have higher probabilities of meeting the certain Mules than others. The PRoPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity) protocol used an algorithm that attempts to use the non randomness of the real-world encounters by maintaining the set of probabilities for a successful delivery to the known destinations in DTN.

   MaxProp Routing Protocol

   MaxProp routing protocol is a flooding-based protocol by nature. In MaxProp if a contact is occurred, then all the messages not held by the contact will be replicated and transferred. The MaxProp routing protocol intelligently determines that which messages should be transmitted first and which of the messages should be dropped first. Here an ordered queue is maintained by this protocol based on the destination of each message, ordered by the probability of a future transitive path to that particular destination. When two nodes meet each other, firstly, they exchange their estimated node meeting likelihood vectors. Preferably, each node will have an up to date vector from every other node. With these n vectors at hand, the node can compute the shortest path on the basis of a depth-first search where path weights indicate the probability that the link does not occur [5].

   Spray and Wait

   Spray And Wait makes use of replication, predetermining the number of copies in a static non-adaptive way. This algorithm has two phases: the spray phase, which involves the sender distributing the copies to encountered nodes and the wait phase, in which the nodes that are carrying the message copies follow the Direct Delivery method of routing on behalf of the sender[6].

3. SIMULATION SETUP

   The performance of MaxProp routing protocol with DL, FIFO, DLA and MOFO buffer management techniques were analyzed through simulation using the Opportunistic Network Environment (ONE). The ONE is an agent based discrete event simulation engine. The main functionality of the ONE consists of the modeling of the node movement, inter node contacts using various interfaces, routing, message handling and application interactions. The simulator is configured using text based configuration files that contains the simulation, event generation and reporting parameters. This file also has the defining parameters for the nodes like the storage capability, transmit range, bit rates as well as the routing model to use. Table 1 summarizes the simulation configuration used for the current analysis.

4. PERFORMANCE METRICS

   The following are the performance metrics used for the analysis:

   Delivery Probability

   The delivery probability is a measure of the fraction of the created packets that are delivered to the destination. This is the ratio of the total number of packets that are delivered to their destinations to the total number of packets that are created. Thus this is a direct measurement of how reliably packets are routed in the network by a routing protocol under consideration.

   Overhead Ratio

   The overhead ratio is calculated using the following equation: Overhead ratio =

   (Number of relayed messages Number of delivered messages) / Number of delivered messages

   Here, the term relayed messages refers to the messages that have been forwarded by the source to an intermediate node to be forwarded towards the destination. This number is a measure for the number of packets or copies of packets that have been inducted into the network. The number of delivered messages refers to the total number of created packets that are successfully delivered to the destination. The overhead ratio also shows the amount of the network resources required to deliver a packet from source to its destination[16].

   Latency Average

   The latency measured here is the time that elapses between the creation of a message and its delivery at its destination. This study considers the average of the latency of the packets over the entire simulation time. This is the time as calculated for the delivered packets only. In most protocols, it is desired that

   the value of latency time average is low. In the DTNs environment the latency is acceptable at some extent.

   HopCount Average

   It is the mean hops which a message takes to reach its destination

   Table -1 Simulation Setup of the Study

   Parameter	Value
   Total Simulation Time	43200 seconds
   World Size	4500×3400 meters
   Movement Model	Map Based Model
   Buffer Management Techniques	DL, FIFO, DLA and MOFO
   Routing Protocols	MaxProp
   Node Buffer Size	5, 10, 15, 20, 25, 30, 35, 40 (in MBs)
   No. of Nodes	50
   Interface Transmit Speed	560 kBps
   Interface Transmit Range	30 meters
   Message TTL	90 minutes
   Node Movement Speed	Min.=1.9 m/sec, Max.=3.9 m/sec
   Message Creation Rate	One message per 15-30 sec
   Message Size	250KB to 2MB

5. RESULTS AND DISCUSSION

   Delivery Probability

   The delivery probability of MaxProp routing protocol with DL, FIFO, DLA and MOFO buffer management techniques under variable mssage buffer size is shown in the Chart-1.

   Chart -1: Delivery Probability of MaxProp under Various Buffer Management Techniques

   1. The chart shows that the delivery probability of DL, FIFO and MOFO are same and are increasing equally with the increase in the message buffer size.

   2. The delivery probability of DLA is lower than the other three techniques till 25MB message buffer size and becomes equals to the other three as buffer size increased from 30 to 40MB.

   3. MOFO is slightly better than FIFO, DL, and DLA.

   Overhead Ratio

   The overhead ratio of MaxProp routing protocol with DL, FIFO, DLA and MOFO buffer management techniques under variable message buffer size is shown in Chart-2.

   1. The overlapping lines of FIFO and MOFO clearly depicts that the overhead ratio of both these techniques are equal and are decreasing with the increase in the message buffer size.

   2. Initially, at 5MB message buffer size, the overhead ratio of DLA is lowest but becomes highest between 10MB to 25MB and thereafter it again gets slightly lower than the other three.

   3. At 5MB message buffer size, the overhead ratio for DL is maximum, but dips sharply and becomes equals to FIFO and MOFO after 10MB.

   Latency Time Average

   The latency average of MaxProp routing protocol with DL, FIFO, DLA and MOFO buffer management techniques under variable message buffer size is shown in the Chart-3.

   Chart -2: Overhead Ratio of MaxProp under Various Buffer Management Techniques

   1. The chart describes that the latency average of DL, FIFO and MOFO increases as the message buffer size is increased from 5MB to 10MB.

   2. As the message buffer size is increased further, the latency average of these three techniques declines.

   3. The latency average of DLA is markedly lower than FIFO, DL and MOFO buffer management techniques.

   4. The latency average of DLA increases with the increase in the message buffer size and becomes equals to other three at 40MB.

   Chart -3: Latency Average of MaxProp under Various Buffer Management Techniques

   Hop Count Average

   The hop count average of MaxProp routing protocol with DL, FIFO, DLA and MOFO buffer management techniques under variable message buffer size is shown in Chart-4.

   1. The chart shows that the hop count average of MOFO increases gradually as the message buffer size is increased whereas it decreases in case of DLA.

   2. For the FIFO buffer management technique, the hop count average declines sharply, with the increase in the message buffer size from 5MB to 10MB and then keeps on increasing with the increase in the message buffer size.

   3. DL increases with increasing message buffer size with the slight decline initially from message buffer size 5MB to 10MB

   4. After 30MB message buffer size there is negligible variations in the hop count average for DL, MOFO and FIFO.

   5. At message buffer size 40MB, the values of hop count for all the four techniques becomes almost equal.

   Chart -4: Hop Count of MaxProp under Various Buffer Management Techniques

6. CONCLUSION

This study evaluated the performance of MaxProp routing protocol with DL, FIFO, DLA and MOFO buffer management techniques under variable message buffer sizes. The results show that there are clear benefits of increasing the message buffer size for the parameters Delivery Probability, Overhead Ratio in case of all the buffer management techniques under study. The Delivery Probability, Overhead Ratio and Hopcount average of MOFO with MaxProp gives the best results among all the four buffer management techniques under study. Whereas for the performance metric Latency Time Average, DLA with MaxProp routing protocol is the ideal buffer management technique.

In this study all the buffer management techniques and routing protocol have been simulated on the ONE simulator. They all have not been experienced on a real network. It will be of foremost significance that these techniques using MaxProp routing protocol be tested out on a real network. This study assumes that all the nodes have unlimited energy. This study do not considers for the

energy loss of the network, as the message buffer size increases for all the nodes. Such parameters should take into the account, the energy spent for the network as the message buffer size increased.

REFERENCES

1. Wenrui Zhao. Routing and Network Design in Delay Tolerant Networks. A theses presented to the Academic Faculty of College of Computing, Georgia Institute of Technology, Decem- ber 2006.

2. T. Spyropoulos, K. Psounis, C.S. Raghavendra. Single-copy routing in intermittently connected mobile networks. First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE SECON 2004, pp. 235-244(2004).

3. J. Sushant, K. Fall, R. Patra. Routing in a Delay Tolerant Network. Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications. Vol. 34, No. 4, pp.145-158, 2004.

4. A. Balasubramanian, B.N. Levine, A. Venkatara- mani. DTN Routing as a Resource Allocation Problem. Published in UMASSCSS in year 2007.

5. J. Burgess, B. Gallagher, D. Jensen, B.N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. Published in INFOCOM 2006, 25th IEEE International Con- ference on Computer Communications, pp 1-11.

6. Andrew Michael Grundy. Congestion Control Framework For Delay-Tolerant Communications. A Ph.D thesis, University of Nottingham, July 2012

7. Forrest Warthman et al. Delay Tolerant Networks. Based on DTN Research Group Internet Draft, March, 2003

8. Anders Lindgren, Kauustubh S.Phanse. Evaluation of Queuing Policies and Forwarding Strategies for Routing in Intermit- tently Connected Networks. IEEE 2006

9. Mooi Choo Chauah, Wen- Bin Ma. Integrated Buffer and Route Management in a DTN with Message Ferry. Journal of Information Sciences and Engineering 23, 1123-1139 2007.

10. Jian Shen, SangmanMoh, Ilyong Chung. Routing Protocols in Delay Tolerant Networks: A Comparative Survey. The 23rd International Technical Conference on Circuits/ Systems, (ITC-CSCC 2008)

11. Amir Krifa, ChadiBarakat, Thrasyvoulos Spyropoulos. Optimal Buffer Management Policies for Delay Tolerant Networks.

    Project Team Planete, IRIA Sophia-Antipolis, France, 2008

12. Ari Keranen, Karkkainen, Jorg Ott. Simulating Mobility and DTNs with ONE. Journal of Communications, Vol. 5, No.2, February 2010.

13. Sulma Rashid, Qaisar Ayub, et al. E-DROP: An Effective Drop Buffer Management Policy for DTN

    Routing Protocols. International Journal of Computer Applications (0975 8887) Volume 13 No.7, January 2011

14. G.Fathima, R.S.D.Wahidabanu. Integrating Buffer Management with Epidemic Routing in Delay Tolerant Networks. Journal of Computer Science 7(7):1038-1045, 2011

15. Harminder Singh Bindra, A. L. Sangal. Performance Comparison of RAPID, Epidemic and Prophet Routing Protocols for DelayTolerant Networks. International Journal of Computer Theory and Engineering Vol. 4, No. 2, April 2012

16. Priyanka Gururaj Rotti. Opportunistic Lookahead Routing Protocol For Delay Tolerant Networks. A Theses submitted in Visvesvaraya Technological University, 2008 December 2012