AN ADAPTIVE MESSAGE REPLICATION TECHNIQUE

AN ADAPTIVE MESSAGE REPLICATION TECHNIQUE (AMRT)

AMRT is a message replication technique that fits onto quota-based routing protocol such that the number of replicas for each generated message is variable at different time. In other words, AMRT provides different upper-limit for the number replicas for each generated message. AMRT takes advantage of estimating the amount of traffic at nodes which source nodes will most likely have contact with them in order to allocate appropriate number of replicas for a generated message. This results in quota routing protocol with a high delivery ratio while the overhead remains low. In addition, the network resources such as bandwidth, buffer space, energy, will be efficiently utilized. Note, AMRT is used to control the network traffic under quota protocol and it is not a routing protocol.

Algorithm

AMRT, every node α establishes a metric called traffic ratio, TR_αthat compares drop_α as the average number of dropped messages at node α and Service_α as the average amount of incoming messages to node α. As an example, suppose that node α receives 120 messages and drops 60 messages upon four contacts. Now, drop_α and Service_α are calculated as follows.

drop_α60415

Service_α120 4 30

In this example, upon each contact of node α, 50% of buffered messages at node α is dropped. In the following, the traffic ratio of node α, TR_α in a given time interval is calculated as follows:

TR_α drop_αService_αwhere Service_α ≥ drop_α

In wordsEquation (3) compares the average number of dropped messages and received messages. Hence, this ratio is obtained based on the information that node α has collected from encountered nodes over a specific time interval. The term ‘time interval’ is used to consider the average number of dropped and received messages in time slices. For example, in a time interval a node may have 10 dropped messages and 100 received messages and in the next interval, 80 dropped messages and 100 received messages. Therefore, we can evaluate the traffic ratio in each interval. In this paper, we use a large interval such that many nodes have the chance to encounter source nodes within in a time interval. This results in the traffic ratio to become more precise as a larger area of the network is covered.

As mentioned, the traffic ratio of a source node is used to determine the number of replicas for each generated message. For this reason, we define a parameter called “acceptable traffic ratio”, ATR_αfor every source node α. Although in the best case, the acceptable traffic ratio is zero which means no message has been dropped. However, this may not be feasible when nodes have limited buffer space and heavy message traffic is in the network. Hence, it is required to accept a level of traffic ratio. Accordingly, the number of replicas changes with respect to the traffic ratio of source nodes’ neighbours. In other words, the allocated number of replicas for each generated message increases or decreases as the subtraction of the source node’s traffic ratio and its acceptable traffic ratio changes. Specifically, C_ias the number of replicas for a new generated messageiis calculated as follows.

C_i ATR_α̶TR_α)C_i-1C_i1

where C_{i -1} represents the number of replicas that the source node αgenerated for the last message. In words Equation (4) controls the injected network traffic at a certain level traffic ratio by increasing or decreasing the number replicas. As an example, suppose that TR_α0.4 and ATR_α=0.2; and also for the last generated message by node α, 20 replicas are generated (C_i-1 20). Hence, for the new generated message i, the number of replicas is calculated as follows.

C_i 0.2̶0.42016

Equation (5) determines that for new generated message i, 16 replicas will be allocated. This reduction in the number of replicas continues while ATR_α̶ TR_α <0. To this end, the traffic ratio of the whole network reaches to the acceptable traffic ratio and the network reaches to a steady state.

We also notice that as the time to next interval may be long enough to obsolete the traffic ratio before its update time, a weight factor drop_αService_α<<Service_αdrop_αis defined in order to weight the traffic ratio. This weight may be decreasing or increasing. It is dependents on the difference between the current traffic ratio and the acceptable traffic ratio. As an example, when ATR_α ̶ TR_α 0, the number of replicas in the system increases that causes the network traffic gradually increases. In such case, γ∈1,Service_αdrop_α. In contrast, when ATR_α̶ TR_α0, the number of replicas in the network decreases that causes the network traffic to gradually become light. In this case,∈(drop_αService_α,1). Specifically, whenever a new message generated by node α, the interval of γ is determined based on the difference of ATR_α and TR_α. Hence, the traffic ratio will be updated as follows.

TR_α TR_α

As an example, suppose that drop_α = 4 and Service_α = 10. Given ATR_α 0.2, the parameter  has to be between drop_αService_α0.4 and one. Here, we assume that  = 0.8. Hence force, after creating a new message, the traffic ratio is updated as follows.

(7)TR_α  0.4  0.8  0.32

In this paper, we assume that the value of γ is the average of the interval. Specifically, when ATR_α ̶TR_α 0, then the value of  is calculated as follows:

 (drop_αService_α 12

Also, when ATR_α ̶ TR_α0, the value of γ is,

 (Service_αdrop_α 12

Algorithm 1 presents the pseudo-code used by source node αto determine the proper number of replicas for a generated message. As mentioned, node αcompares ATR_α and TR_α in order to increase or decrease the number of replicas with respect to the number of replicas for last generated message (Line 2). After injecting the replicas to the network, the traffic ratio needs to be updated locally. Hence, if ATR_α̶ TR_α 0 the average of TR_α and one is calculated as the value of γ (line 4). If ATR_α ̶TR_α0 the average of 1TR_α and one is calculated as the value of γ (line 6). Lastly, the traffic ratio of node αis updated (line 8).

Algorithm 1: AMRT

Input: TR_α, ATR_α, C_i-1

1. FOR every generated message i by node αDO
2. C_i ← C_i ATR_α̶TR_αC_i-1C_i1
3. IFATR_α ̶TR_α 0DO
4. ←TR_α 12
5. ELSE
6. =(1 /TR_α 1)2
7. ENDIF
8. TR_α =TR_α 
9. ENDFOR

EVALUATION

We evaluate AMRT in the Java based simulator Opportunistic Network Environment (ONE) (Keranen, Ott&Karkkainen, 20099. AMRT will be fit onto well-known quota protocols such as EBR(Nelson, Bakh & Kravets, 2009), DBRP (Iranmanesh, Raad & Chin, 2014), and Spray And Wait (Spyropoulos, Psounis &Raghavendra, 2005), in order to evaluate their performance under Map-Based Model (Iranmanesh, Raad & Chin, 2014; Keranen, Ott&Karkkainen, 2009). AMRT will be fit onto well-known quota protocols such as EBR(Nelson, Bakh & Kravets, 2009), DBRP (Iranmanesh, Raad & Chin, 2014). In other words, the performance of said protocol under AMRT is compared against the original version. In this experiment, nodes will experience varying load by adjusting the time between generated messages from 10 seconds (high load), to 30 seconds (medium load), to 60 seconds (light load). In addition, the number of nodes is varied from 50 to 200 in increments of 50. In all experiments, nodes move in an area of approximately 5×3 km2 in downtown Helsinki, Finland and adopt ONE’s default settings. Accordingly, 64% of nodes are pedestrians who move with a speed between 0.5 and 1.5 m/s. Vehicles include 32% of nodes that move with a speed ranging from 2.7 and 13.9 m/s. The rest of nodes are trams that move with a speed between 7 and 10 m/s. all nodes are equipped by IEEE 802.11g which has the radio range 140 meters and the data rate of 54Mbps. Also, every node has a buffer size with a capacity of 20 bundles Note, in all experiments; the message size is 100 KB.

The aim of these experiments is to consider the impact of applying AMRT onto said quota protocols. Hence, the performance of these protocols is not evaluated against each other. Note that as will be discussed in Figure 2, in all experiments, the acceptable traffic ratio used in AMRT is equal to 0.4. The result of simulations evaluates the performance of the improved quota protocol i.e., applied AMRT, and the original version over two well-known performance metrics, namely 1) delivery probability, and 2) average delay. Briefly, delivery probability is the ratio between the number of delivered bundles and the number of generated bundles. The metric average delay is the average time until a bundle is delivered.

The post AN ADAPTIVE MESSAGE REPLICATION TECHNIQUE appeared first on My Assignment Online.