1 Introduction

In mobile wireless networks, the end-to-end communication between users can not be available all time, or may never becomes available. For this scenario, we use a network approach known as Delay/Disruption Tolerant Networks—DTN [1]. In these networks, the message storage is persistent due to the use of the store-carry-and-forward mechanism, in which a node stores a message for later in a new contact, forward it [2]. To increase the chances of delivery and reduce the time that a message takes to reach the destination, many forwarding protocols have been proposed where multiple copies of a message are disseminated in the network.

Unfortunately, many of these copies remain stored in the intermediate nodes after their delivery to the destination. The use of message removal mechanisms aims thus to reduce the occupancy rate of such copies in the buffer of nodes and enable more efficient data exchange on the network.

In this context, this paper proposes a mechanism that uses the acknowledgment information of a message by the destination to remove from buffers of intermediate nodes the possible obsolete copies of this message. This information (copies of messages) is stored in a list that is exchanged at every contact between nodes, allowing an update of both.

The main contributions of our paper are threefold: (i) the proposal of an obsolete message removal mechanism; (ii) the implementation of the proposed mechanism and some state-of-art mechanisms as IMMUNE, IMMUNE-TX, and TTL in the ONE (Opportunistic Networking Environment) simulator; (iii) the evaluation of such mechanisms when combined with the Epidemic, Spray and Wait, and Bubble Rap forwarding protocols under two different realistic scenarios and two human mobility datasets.

This paper is organized as follows. In Sect. 2, related works are presented and discussed. The proposed mechanism will be described in Sect. 3. An evaluation of the mechanisms is presented in Sect. 4. In Sect. 5, the results are presented and discussed. Finally, Sect. 6 concludes this work.

2 Related Works

The obsolete message removal problem has attracted significant attention of the networking community in the literature. We discuss some of these works in the following. In the work [3], the TTL (time-to-live) is used to limit the number of message copies disseminated in the network. Thus, the TTL is set based on time and network hops. A node has initially a defined \(TTL_{max}\) value. This value is decremented every second until zero. The messages are replicated while the TTL value is greater than zero. When the time expires (i.e., TTL equals zero), all messages are simultaneously deleted.

The work at [4] presents a mechanism for removing copies of messages. The presented approach is composed into two parts: (i) distribution of acknowledgment messages (ACK) and (ii) the use of auxiliary nodes to retransmit ACK messages. The ACKs are also divided into active ACK and passive ACK. The passive ACK will only be forwarded to a node that receives a copy of a message that has been delivered to the destination. The passive ACK messages are distributed slowly and copies are deleted accordingly. In active ACK, a node that has an ACK of any message transfers this ACK to any neighbor node (broadcast-like). The concepts of passive and active ACK are used by three message discarding strategies proposed at [5], which are based on the Shared Wireless Infostation Model (SWIM): IMMUNE and IMMUNE-TX, using passive ACK, and VACCINE, using active ACK. In the first two strategies, nodes become “immune” after receiving a known obsolete message: when a node receives a message that has already been delivered to the destination, it rejects the new copy of this message, avoiding unnecessary retransmissions. The IMMUNE-TX mechanism also has the function of immunizing “the node” with an obsolete message, but it goes beyond, immunizing the neighbor that tried to pass the obsolete message. On the other hand, VACCINE tries to immunize “all nodes” once a message has been delivered.

In [6], authors present a DTN buffer management policy to deal with the message removal problem. When a node’s buffer is full and needs space to store a new message, the longest message in the buffer is discarded. This strategy was called droplargest (DLA). In [7] is presented a Reactive Weight Based Buffer Management Policy for DTN Routing Protocols. These mechanisms has however the drawback of affecting the operation of applications that generate large messages.

Additionally, in [8] a survey and comparison of various buffer management policies for DTNs are performed and a new policy is presented based on encounter rate of nodes and context information such as TTL, number of available replicas and maximum number of forwarded bundle replicas. These papers perform buffer management by removing messages (including messages not yet delivered) in order to avoid its overflow. So, these removal policies are not the subject of this paper, but can be investigated in future works.

Apart from the solutions dealing with the message removal problem, there is more and more a worry from the networking community in bringing a realistic consideration to simulation environments. This has been done by the use of real traces describing human mobility in network simulators. In [9], the authors conducted a study on the patterns of human mobility and its use in mobile network simulations. They found that the pattern of human mobility suffers from external influences and are not found as random because mobility is related to social contexts. Moreover, they observed the existence of different mobility patterns related to these contexts. Finally, it was emphasized the importance of using models that are able to provide more realistic results in the simulations such as the use of traces describing human mobility to increase the accuracy of simulations.

Authors in [10] perform a study on the use of real mobility traces in simulated environments. In this analysis, five real mobility traces were used together with the Epidemic protocol and compared with existent mobility models. Results clearly show the differences in the Epidemic protocol performance when applied to real or modeled mobility. Therefore, this outcomes strongly recommend, when possible, the use of real traces on the evaluation.

Based on the above described observations, the next sections describe a detailed evaluation of our proposed mechanism when compared to different message removal mechanisms and when real mobility traces are considered.

3 The Proposed Mechanism

This section introduces our mechanism named ReMO—Removal Mechanism for Obsolete messages. ReMO is based on the VACCINE strategy [5], that models the impact of the removal of redundant copies of already delivered messages that still occupy storage space in the intermediate nodes.

The operation of the ReMO can be described as follows. Each node has a list storing the identifier of each message that has been delivered to the destination. When a node comes in contact with another node, they then exchange/update their respective lists. If there is any record of a message already delivered to the destination, the node remove it from its buffer. After this phase (i.e., removal of locally stored obsolete messages), the nodes can then exchange messages as dictated by the used forwarding protocol.

A pseudo code of ReMO algorithm is described at Algorithm 1, where L is the delivered messages control lists, \(n_{1}\) is the transmitter node and \(n_{2}\) is the receiver node. The great advantage of the ReMO mechanism is that it is independent of the used routing protocol.

figure a

4 The Influence of Removal Mechanisms on the Performance of DTN Routing Protocols

It is expected that, with the removal of obsolete messages in DTN, it will be possible to make better use of the nodes’ buffers, thus allowing for a better network performance, especially by increasing the delivery rate and decreasing the delay of routing protocols that use messages replication techniques. The proposed mechanism and other evaluated mechanisms (IMMUNE, IMMUNE-TX, and TTL) were implemented in the ONE simulator.

The rest of this section will present the used routing protocols and also a description of the simulation parameters and of the performance metrics that were used.

4.1 Routing Protocols

According to [11], the routing protocols for DTN are classified as: (i) flooding based, (ii) replication (or controlled flooding) based and (iii) forwarding based. As the forwarding-based protocols do not create copies of a message, only the first two classes will be analyzed. Moreover, as there are many protocols for each class, the following well-known and most used ones were chosen: the Epidemic protocol, that is based on flooding, the Spray and Wait protocol, that is based on replication, and the BUBBLE Rap protocol, that is based on replication according to social context of nodes.

In [2] the Epidemic protocol is proposed and its operation is given as follows. Each node has a list of the messages in its buffer. When meeting neighbor nodes, their message lists are exchanged and, if there are different messages in their buffers (i.e., there are differences in their lists), nodes exchange the missing messages. We can observe two important factors in this protocol. First, it greatly increases the number of copies circulating in the network and, consequently, also increases the destination delivery probability. The second factor is that multiple copies spreading over network causes the filling of nodes’ buffers more quickly. These factors should be mitigated by using a mechanism to remove messages.

In [12] is shown the Spray and Wait protocol, where the routing process is divided into two parts: (i) the spraying phase (spray), when \(L - 1\) copies of a message are disseminated in the network, and (ii) the hold phase (wait), when a node only forward the message if the destination is met, i.e., direct transmission. To simulate this protocol, the L parameter was set to the default value of 6.

The BUBBLE Rap protocol [13] uses the social relations of nodes as a decision on forwarding messages. Its operation is based on the centrality and community metrics, where each node participates in a community and its centrality is proportional to its popularity (node connectivity degree). It also has a global centrality in the network for routing messages out of a community. It has two phases, Bubble-up in the global community and Bubble-up in the local community, always choosing the nodes with the highest centrality for routing messages. To simulate this protocol, the K parameter was set to the value of 5 and the \(familiar\,Threshold\) parameter to the value of 700, as [14].

4.2 Compared Mechanisms

The removal mechanisms aim to inform intermediate nodes that a message was delivered to the destination node, enabling the removal of message replies throughout the network. These are also known as Anti-packet, which prevent the node of receiving again a message already discarded. In this context, the mechanisms used for comparison reasons in our analysis are: the TTL set to 50 %Footnote 1 of the total simulation time (named TTL50 % hereafter), the IMMUNE, and the IMMUNE-TX. The mechanisms were implemented as mathematical models cited in [5] and can be combined with any routing protocol.

4.3 Description of Simulation Parameters

In the evaluation of different scenarios using a DTN, two real mobility traces were used: UCL1 [15] and RollerNet [16], both available in CRAWDAD,Footnote 2 which have significant differences in user mobility. The UCL1 mobility trace was obtained through the movement of people along the campus of the University College London. The trace of RollerNet refers to the movement of skaters through the streets of Paris. In this one, there is a peculiarity which is the “accordion effect” on movement of users over time, due to two existing mobility standards: one where the skaters agglomerate, waiting for the release of some junction, and the other when they are skating normally along a route [17]. This peculiarity periodically generates high connectivity between users, which may influence the operation of the DTN, unlike other scenarios as the UCL1.

For the representation of network and users of UCL1 scenario in the ONE simulator, each generated message file contains 8640 messages randomly distributed in time between 20 nodes over the six days of simulation. In RollerNet scenario, each generated message file contains 2160 messages randomly distributed in time between 62 nodes along the three hours of simulation.

In addition, 10 rounds of simulation were performed for each set of analyzed parameters. We then computed the confidence interval of 95 % from the obtained results, according to the T-student distribution.

4.4 Performance Metrics

We analyzed the following performance metrics: delivery ratio, average delay and messages overhead. Delivery ratio is given by the number of delivered messages divided by the number of messages created during a simulation. Average delay is defined as the average time it takes for a message to be delivered, since when it is generated until when it reaches its destination. Message Overhead is given by the number of forwarded messages divided by the number of messages delivered during a simulation.

5 Results

This section presents the obtained results and evaluates the mechanisms performance according to their delivery ratio, average delay, and messages overhead.

5.1 Delivery Ratio

Figure 1 analyzes the delivery ratio of UCL1 scenario. Figure 1a, related to Epidemic protocol, shows for different buffer sizes, an improvement of the protocol performance when jointly applied with removal mechanisms of obsolete messages: discards are lowered, increasing the delivery probability at destinations. The ReMO mechanism also obtained a better performance for this protocol, which is due to the removal of more obsolete messages, leaving more buffer space to store other messages and consequently, increasing the delivery probability. As the other mechanisms do not remove as many messages as ReMO, their performance were worst, but still, a bit better than the case where no removal mechanism is applied (cf. Original). Among the analyzed mechanisms, TTL50 % had the worst performance due to the fact that many messages were created in the beginning of the simulation and had not enough time to reach the destination, thus being discarded.

Figure 1b shows the results related to Spray and Wait protocol, which, contrarily to Epidemic, controls the number of copies of each message. As for Epidemic, ReMO had a better result due to its implementation, which enhances the removal of obsolete messages in the buffers. With TTL50 %, Spray and Wait protocol did not show a good result because messages are discarded after 50 % of the simulation time, preventing their delivery.

Fig. 1
figure 1

Delivery ratio in the UCL1 scenario. a Epidemic. b Spray and Wait. c Bubble Rap

Full size image

Figure 1c related to Bubble Rap shows that better performances were obtained when removal mechanisms were applied in nodes with small buffer sizes (i.e., between 1 and 10 MB). As the buffer sizes increases, we see a performance improvement of the Original case (where no removal mechanism is used), which gets better results than when removal mechanisms are applied, except for the ReMo protocol, which still presents better performance. This may be explained by the limited number of redundant copies generated by Bubble Rap protocol, which limits the benefits of removal mechanisms. For the mobility trace with few nodes, we observed that IMMUNE and IMMUNE-TX mechanisms present the worst performance for buffers greater than 12 MB. At this stage the buffer does not overflow anymore. As these mechanisms do not spread the list of delivered messages to all nodes, they exchange a greater number of obsolete messages, negatively impacting the results. In all cases, ReMO maintains a better performance up to 25 MB. The results for the TTL50 % mechanism is the worst. As it discards messages during the simulation time, delivery probability greatly reduces once Bubble Rap protocol uses social context to forward messages to the destination by selecting nodes with higher popularity. As the lifetime of messages reduces, it directly influences this mechanism worsening its performance.

Finally, IMMUNE and IMMUNE-TX mechanisms brought the same performance to the three routing protocols. Moreover, in all results of Fig. 1, the performance gains on protocols are usually bounded by the size of nodes buffer equal to 10 MB.

Delivery ratio of Rollernet scenario is shown in Fig. 2. In Fig. 2a, related to Epidemic protocol, it is observed an improvement of message delivery ratio when using ReMO. It maintains the buffer occupation below 80 % even when buffer size has only 1 MB, favoring the reception of new messages and thus, increasing the probability of delivering more messages to destinations. This improvement also occurs within IMMUNE-TX because node mobility increases its message removal mechanism, so performance gets close to ReMO. On the other side, IMMUNE does not exchange information with intermediate nodes, but still keeps a slightly better performance when compared to the case with no removal mechanism. If compared to TTL50 %, the performance of IMMUNE degrades as buffer size increases.

Fig. 2
figure 2

Delivery ratio in the Rollernet scenario. a Epidemic. b Spray and Wait. c Bubble Rap

Full size image

Figure 2b shows that message removal mechanisms were ineffective in the Rollernet when applied with the Spray and Wait protocol, which has the characteristic of low buffer occupancy. In Fig. 2c, related to Bubble Rap protocol, it is observed that the delivered ratio with ReMO mechanism is kept constant at approximately 83 % for any size of buffer, due to the removal of obsoleted messages, which increases the number of new received messages. The IMMUNE-TX mechanism also obtained a good result once it removed more messages than the other remaining mechanisms. TTL50 % surprisingly had a good performance. Having a closer look at existing contacts in the mobility trace, we observe that in the first half of the simulation, 1851 contacts happen between nodes, while 3080 contacts happen in the second half. Therefore, the delivery ratio at this second half of the simulation is improved by the higher number of contacts, what explain the obtained results.

5.2 Average Delay

Figure 3 shows the average delay obtained when the UCL1 scenario is used. In Fig. 3a, it can be observed that ReMO has the worst result. That is because the message removal affects the buffer space management policy, which is configured to remove oldest messages when buffer occupancy is above a certain limit. With less buffer occupancy, older messages are not removed and have a higher chance to be delivered to destination, which increases the average delay. The same situation occurred with IMMUNE and IMMUNE-TX mechanisms, but with lower average delays incurred since they remove less messages. TTL50 % provided the best result due to the metric definition. As its experiment time was divided in two half, time intervals between messages creations and their deliveries at the destinations are relatively small in each half part, leading to lower average delays.

Fig. 3
figure 3

Average delay in the UCL1 scenario. a Epidemic. b Spray and Wait. c Bubble Rap

Full size image

The same observation is applied to the other two protocols shown in Fig. 3b, c. In Fig. 3b, it is observed that the removal mechanisms were quite ineffective once the Spray and Wait protocol limits message dissemination and that makes the results close to the case without message removal mechanism. In Fig. 3c related to Bubble Rap protocol, it is also observed that the average delays are worst when using message removals mechanisms. Again, this behavior is intrinsic related to the metric definition and to the fact that removing messages already delivered helps to keep old messages in buffer, which would be discarded in situations of higher buffer occupancies.

Fig. 4
figure 4

Average delay in the Rollernet scenario. a Epidemic. b Spray and Wait. c Bubble Rap

Full size image

Figure 4 shows the average delays obtained for the Rollernet scenario. In Fig. 4a, related to Epidemic protocol, it is observed that ReMO has significantly improved the average delay and kept it almost constant, compared to the others removal mechanisms and to the original case. In this scenario, node mobility is much higher, increasing contact frequency and consequently increasing message exchange. This favors message delivery (as shown in Fig. 2a) and reduces the incurred average delay. In Fig. 4b, related to Spray and Wait protocol, message removal mechanisms did not improved the average delay because of the limits imposed by this protocol at the message dissemination. Finally, in Fig. 4c, related to Bubble Rap protocol, it can be verified that ReMO kept average delay constant with buffer size increase and had the best performance for this metric in this scenario.

5.2.1 Messages Overhead

Figure 5 shows the message overhead generated by routing protocols in the UCL1 scenario. In Fig. 5a, related to the Epidemic protocol, it can be verified that ReMO reduces the message overhead generated by the protocol, which is due to the removal of obsolete messages that would be otherwise forwarded. The other mechanisms also reduced obsolete messages, but less than ReMO. With buffer size of 1 MB, ReMO removed an average of 1648 obsolete messages for this scenario, while IMMUNE-TX removed 1454 and IMMUNE removed 1419 obsolete messages. It can be observed that the number of removed messages is directly proportional to the result of message overhead. In Fig. 5b, related to the Spray and Wait protocol, it can be observed that even for this protocol, that forwards a lower number of messages, the removal of obsolete messages yet reduces message overheads, specially with the use of ReMO. In Fig. 5c, related to the Bubble Rap protocol, it can be observed that ReMO mechanism had the best result since it removed more obsolete messages than the other mechanisms.

Fig. 5
figure 5

Messages overhead in the UCL1 scenario. a Epidemic. b Spray and Wait. c Bubble Rap

Full size image

Figure 6 shows the message overhead generated by routing protocols in the Rollernet scenario. In Fig. 6a, related to the Epidemic protocol, it can be observed a significative reduction of message overhead with the use of ReMO compared to the other mechanisms. The Rollernet scenario presents a great mobility of nodes, favoring the number of message forwarding by the Epidemic protocol and, consequently, message deliveries. The removal of obsolete messages lowers the number of copies of these messages that would be otherwise forwarded. The increase in buffer size also increases the average number of delivered messages, thus reducing message overhead. It can be observed that with ReMO the message overhead is almost the same despite the buffer size.

It is also possible to observe that the TTL50 % had less message overhead than ReMO for a buffer size of 10 MB. In Fig. 6b, related to the Spray and Wait protocol, once more it is observed that the obsolete message removal mechanisms did not affect message overhead incurred by this protocol. This protocol limits the number of copies forwarded by each node and the mobility characteristics of this scenario favors message deliveries at destinations, making obsolete message removal quite ineffective. In Fig. 6c, related to the Bubble Rap protocol, it can be observed that ReMO maintains a constant and extremely low message overhead over buffer variation, compared to the other solutions. This behavior can be explained by the characteristic of the Bubble Rap protocol of removing messages that has less chance to be delivered at the destinations, which is intensified by the ReMO mechanism and thus, drastically reduces the number of messages forwarded through the network.

Fig. 6
figure 6

Messages overhead in the Rollernet scenario. a Epidemic. b Spray and Wait. c Bubble Rap

Full size image

6 Conclusions

This paper presented a mechanism called ReMO to remove obsolete messages already delivered to their destinations at Delay Tolerant Networks. ReMO was compared to other two mathematical mechanisms cited in [5], IMMUNE and IMMUNE-TX, and with the TTL of 50 % of total simulation time. All presented mechanisms, including ReMO, can be used independently of the DTN forwarding protocol. By analyzing the simulation results, it is possible to conclude that the ReMO mechanism presented the best overall performance. It was also possible to observe that, even when used with a forwarding protocol that controls the number of disseminated messages, like the Spray and Wait protocol, or when used with a social-based protocol that disseminates messages based on the social context of the node, like the Bubble Rap protocol, ReMO presented an improvement of the evaluated performance metrics. With the Epidemic protocol, that disseminates messages to every node with which a contact has been made (i.e., the worst case in terms of redundant message dissemination), ReMO also improved the results.

The use of real mobility traces enabled more realistic simulations and, from them, it was possible to observe that, depending on the mobility conditions, i.e., number of nodes and contact time intervals between nodes, the use of ReMO mechanism can better improve the overall performance of the DTN.

As future work, we intend to investigate the energy consumption incurred at nodes when ReMO is applied as well as apply energy-related improvements to the strategy, if necessary. Moreover, the study of how mobility affects the ReMO performance is also left to future works.