Need of Removing Delivered Message Replica from Delay Tolerant Network - A Problem Definition

Published Online November 2012 in MECS (http://www. DOI: 10.5815/ijcnis.2012.12.06

As technology advances at ostensibly inexorable stride, the world we sentient in is changing. In today’s the world, we are regulars of not only goods and services, but information. The potentials obsessed by technology and the Internet have led to an aptitude to yield and munch an unparalleled volume of information through a varied variety of channels — computing anywhere, perhaps everywhere, and at any time. With the satiety and growing sophistication of personal mobile devices, and short-range wireless communications included on phones, MP3 players, games consoles, and other sensors, there are countless prospects to create, publish, and ingest information. Taking benefit of the direct contacts which occur when these devices are in close vicinity allows us to share and dispense information in new ways, exploiting the capacity existing at the boundaries of the network. There are also states where immobile infrastructure is entirely or partly absent and communication can only be sustained with an ad hoc paradigm. In pushing communication into increasingly incoherent (disconnected) regions and challenging locations such as inaccessible villages or into the realm of space, we face new demands in the establishment of end-to-end communication: information must be tolerant of possibly extended delays and networks may be recurrently disconnected[1]. Messages must be buffered at nodes while we await upcoming contacts or mobile nodes cross disconnections, carrying messages amongst isolated clusters.

Under challenged networks, there is raised level of inherent uncertainty and any arbitrary node totally lacks network state information (i.e. information about other nodes in the network, network topology, etc.) and thus has to formulate its own operating decisions. A network of this type is clearly not appropriate to the provision of real-time information such as voice or video, rather it is well-matched to provision of information which is tolerant of delay to a certain degree.

Delay-/Disruption-Tolerant Networking is an overlay architecture intended to operate above the protocol stacks of the distinct ICNs and enable gateway functionality between them through the use of storage capacity, a variety of protocol techniques, replication and parallel forwarding, forward error correction and many other techniques for overcoming communication impairments[1].

Among the two categories of DTN routing schemes, the multi-copy routing schemes achieve higher delivery probability as compared to the single copy routing scheme. This improvement is achieved at the cost of higher resource utilization i.e. multi-copy routing protocols requires more buffer space, more bandwidth, incur more overheads and consume other vital network resources[2].

It is evident from the literature that most of the work in the field of routing in delay tolerant network is related to designing and formulating the routing strategy which should use minimal amount of network information and should forward the message in efficient manner. Not much of the literature is found which deals with the messages copies which are left over in the network at the time of message delivery. These message copies still utilize the network resources and the nodes still continues to assume these as undelivered messages. So nodes continues to work upon these messages in the normal routing process which in turn replicate these messages copies in the network leading to occupancy of more network resources by these delivered message copies. These resources which are being held by the copies of delivered messages are of no use for the performance of the network rather they degrade the performance of the network. So the major gap being identified from the review of the literature related to the routing in DTN is existence of useless replicas (of delivered messages) in the network and no mechanism is there to deal with these replicas except the TTL expiry.

Mostly the routing protocols are self-integrated with the storage management techniques. For example, Hop based TTL is added to Spray and Wait[3], passive cure to PEAR [4]. Also there is vast amount of work already carried out by many researchers about the buffer management policies.

Our method basically relaxes resources to prevent exhaustion and take care of storage overflow problem in contrast to counter measures in work by Krifa [5]

The contribution of this work is the deletion of useless replicas of the messages which are already delivered to the intended destination. As these replicas continues to use the resources and contribute in further replication at the next contact opportunity. So these replicas consumes the valuable resources of the network like storage, bandwidth, energy of nodes etc. deleting these replicas relaxes these resources and thus this freed up resources can be utilized for the replication/communication of the undelivered messages in more efficient manner.

We evaluate our proposed method by simulation, on four major DTNs routing algorithms: Epidemic[6], Spray and Wait[3], ProPHET[7] and MaxProp[8] .

Section-II provides the background about message replication in the delay tolerant networks. In this we have explained the replication process with the help of example and shown how the replicas exists in the network even after the delivery of the message to the intended destination. In section-III we have carried out the hypothetical simulation in which we have deleted the all the replicas of the message as and when it is delivered to the intended destination. At present we are not concerned with the procedure of how to identify the replica and how to delete it, we have just dropped the message copies when any of the copy reached the destination. Section-IV concludes the paper.

• II.    Message Replication in Delay Tolerant Network

In the Delay Tolerant Networks communication opportunities are intermittent. Network is partitioned and no continuous end-to-end path exists from source to destination. Over the course of time, link comes up and down. Due to occasional partial connectivity or node mobility, the sequence of connectivity graphs over a time interval are overlapped to get an end-to-end path from source to destination. It implies that a message could be sent over an existing link, get buffered at the next hop until the next link in the path comes up, and so on and so forth, until it reaches the final destination. This routing is often referred to as Store-Carry-Forward Routing[9].

The example below explains the above mentioned replication process and show the existence of replica after the delivery of bundle/message to the destination. Further we executed hypothetical simulation in which it has been deduced that there is scope of improvement in the performance of multi copy routing scheme if these replicas are removed from the network after the bundle has been delivered to the destination.

In the fig. 1, at time t1 source ‘S’ generates a message for the Destination ‘D’. At this point of time there exists different disjoint regions of networks and S is connected to only 1, 2 and 3 nodes. At time t2, the source S forwards the message to the node 3.

At time t1        At time t2      At time t3

Fig. 1: Network and data bundle status at time instances t1, t2 and t3

At time instance t3, the node 3 moves to the new location and thus the node 3 come in contact of region with nodes 7, 8,9,10 and 11. At time t4, node 3 forwards the message to node 7 which in turn is forwarded to node 11(time instances t5). In this process the node S, 3 and 7 retains a copy of the forwarded bundle fig. 2.

At time t4      At time t5      At time t6

Fig. 2: Network and data bundle status at time instances t4,t5 and t6

Then node 11 at time t6 moves to new point in the network and thus comes in the communication range of node 14 (fig. 2). A link is established between 11 and 14 and thus node becomes the member of region with nodes 14, 15, 16 and D.

The message is forwarded to node 14 by node 11 retaining the copy of the original message. This message is forwarded to node D (Destination) by node 14 again retaining the copy of it (time instance t7 fig. 3). At time t8 the message is delivered to the intended destination. But if we see the fig. 3 and the state of the network we can identify that in this process there exists 5 replicas of this delivered message which are now useless and are utilizing the resources. These messages will keep on utilizing the resources and will participate in further replications as these nodes are not aware of the delivery of the message to the final destination. So there is great need of removing these replicas from the network so as to free up the held resources. And this can be achieved if the delivery information is communicated back to these nodes.

At time t7

At time t8

Fig. 3: Network and data bundle status at time instances t7 and t8

• III.    Problem Formulation

  In order to improvement in

  
  

analyze the percentage scope of the performance of DTN routing protocols by deleting the replicas after delivering the bundle to destination, we have carried out a hypothetical simulation. In this simulation, at the time of delivery of message to the destination we have deleted all the replicas from the network and evaluated the performance in this scenario (at this point of time we are not concerned how to delete the replica so we have not focusing on procedure of deletion, we have just dropped the replicas from network). Then we compared this performance values to the base routing protocols performance values and evaluated the percentage scope of improvement in the performance.

• a)    Simulation Setup

The above mentioned simulation is carried out using Opportunistic Network Environment (ONE) simulator [10]. ONE is an agent-based discrete event simulation engine. At each simulation step the engine updates a number of modules that implement the main simulation functions. The main functions of the ONE simulator are the modeling of node movement, inter-node contacts, routing and message handling. Result collection and analysis are done through visualization, reports and postprocessing tools. The elements and their interactions are shown in figure 4.

The detailed simulations parameters are summarized in table .

Table 1: Simulation Parameter for the hypothetical simulation in which all replicas are deleted from the network when the message is delivered to the destination.

Scenario Setting
Name		simulateConnection	updateInterval		endTime
Default_scenario		True	0.1 s		43200 s
Interface Specific Setting
Name	Type			Transmit Speed	Transmit Range

btInterface

SimpleBroadcastInterface

250k

30 m

Node Group Specific Settings

й 8 У о О 5

Й о

8

8

Он сл

ад

о

у     й ^ й й S ® s ё & О а ^

д Q   Он < о g м      5 сл

о о

Й

■П in о

й 8

о

Message Creation Parameters

Events.n rof

Events1.class

Events1.interval

Events1.size

Events1.hosts

Events1.prefix

1

Message Event Generator

15,30 s

250k, 2M

0, 39

M

Movement Model Settings

MovementModel.rngSeed

MovementModel.worldSize

MovementModel.warmup

1

4500, 3400 m

1000 s

Style

Bold and Italic : Category Heading

Bold: Attribute

Italic : Attribute value

Attribute which is varied

• b)    Results

The results obtained are summarized in the table 2. We have analyzed that maximum scope of improvement is there in Prophet routing protocol. There we have seen 36%, 71%, and 31% improvement in delivery probability, overhead ratio and average latency respectively. Further in Epidemic routing protocol there is 31%, 14% and 26 % scope of improvement in delivery probability, overhead ratio and average latency respectively. The overall comparison is also depicted in graph Fig. 5.

Table 2: % improvement in the performance of considered routing protocols when all replicas are deleted

Protocol	Delivery Probability			Overhead Ratio			Average Latency
	g 8 ад	У й >, Pi с	8 8 Он 8	У "pH § 8 ад	У U 2 £ Pi _у с	8 8 Рн 8	У "рн g 8 ад	У Pi _у с	8 8 8
Epidemic	0.71	0.93	31.76	26.56	13.80	48	2734.06	2014.76	26.30
Spray And Wait	0.8105	0.93	15.91	15.94	5.99	62	2258.82	1570.71	30.46
MaxProp	0.9657	0.96	0.25	9.69	8.84	8.77	1468.96	1359.92	7.42
Prophet	0.6988	0.95	36.13	23.54	6.86	70.8	2585.92	1778.99	31.20

From the results it is evident that when the replicas of the delivered messages are deleted from the network the delivery probability, overhead ratio and average latency of the all the considered routing protocols improves by a great extent. These results motivate us to design a mechanism to delete these replicas from the network as soon as the data message is delivered to the intended destination.

Fig. 5: Comparison of scope of improvement in routing protocols performance when all the replicas are deleted after delivery of message to the destination.

In this paper we have tried to identify problems associated with the existence of the replicas of the already delivered messages. Also we have estimated percentage scope of improvement in performance of Delay Tolerant Routing Protocols by deleting the replicas of the delivered messages from the network. It is found that if the replicas are deleted at the same time when the data bundle is delivered then there is maximum performance improvement in PROPHET routing protocols. The Epidemic, Spray and Wait routing protocols also showed the performance improvement. There was marginal improvement in the MaxProp routing protocol. In future work we are working to define mechanism for the deletion of these replicas from the network.