International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 1
ISSN 2229-5518
Buffer Scheduling Policy for Opportunitic
Networks
Qaisar Ayub, Sulma Rashid, M.Soperi Mohd Zahid
Abstract— In Delay Tolerant Networks (DTNs), the optimal use of buffer management polices can improve the network throughput. In this paper, we propose a buffer management strategy called as Message Drop Control (MDC). This technique controls the message drop by using an upper bound which is the count of buffered message at router and size of the messages. If count exceed the upper bound drop will not occurs else large size message will be dropped from queue. We examine the performance of proposed drop policy by comparing it with existing MOFO, DOA, and LIFO. The simulation results proves that MDC policy out perform well as existing ones in terms of delivery probability, message drop, overhead and buffer time average.
Index Terms—buffer drop policies, Delay tolerance network, Algorithm, buffer scheduling, upper bound, large size message.
—————————— • ——————————
HE internet has turn out to be the most central com- ponent in connecting the devices across the world. In the past decade academic and professional researcher
has proposed numerous approaches to enhance this communication architecture. The traditional networking design like TCP/IP supports end-to-end reliable trans- mission of data over a wired media. However, in some environments such as military activities, emergency oper- ations, and disaster recoveries these fixed physical confi- gurations are difficult to deploy and very expensive. Therefore, there is a need to handle the communication in such highly disrupted applications.
Delay Tolerant Networks (DTNs) [2] is a challenge cri- sis networks by irregular connectivity, high latency time and lacking of end-to-end path from the source to the destination. In these environments, the transmission is carried out by “Store-Carry-Forward” paradigm, where the node stored incoming message, carries it while mov- ing and forward it when transmission opportunity arises. Hence, each node act as router and message delivery is achieved via multiple hops through dynamically con- nected mobile terminals.
DTN routing protocols can be classified in two catego- ries (i) single copy and (ii) multi copy. Multi copy routing protocols [5], [6], [7] diffuse the multiple copies of each message in the network which increases the delivery probability but consumes high volume of network re- sources such as bandwidth, buffer and energy. The single copy [9], [2], [8] routing strategies forwards the single copy of message in the network thus produce less over- head on network resources.
————————————————
• Qaisar Ayub is doing PhD from Universiti Teknologi Malaysia (UTM) Skudai - Johor, 81310, Malaysia. Email: sheikhqaisar@gmail.com.
• Sulma Rashid is doing PhD from Universiti Teknologi Malaysia (UTM) Skudai - Johor, 81310, Malaysia
• M.Soperi Mohd Zahid is a faculity member at Universiti Teknologi Malay- sia (UTM) Department of Computer System & Communication,, faculity of computer science and information system skudai Johar 81310 Malaysia.
Regardless of above valued contributions in routing protocols, one of area which can influence and improve existing routing strategies is the use of message drop pol- icies. In normal conditions the drop occurs when message finds destination or its Time to live (TTL) expires. We consider the scenarios when node buffer runs out of space and it need to store new message. Recent work [11], [12], [10], [4] and [3] have proved that router performance can be improved by adopting accurate drop sequence of al- ready buffered messages.
In this paper we propose buffer management policy for single copy routing protocol First contact. The tech- nique is called as Message Drop Control (MDC) and it schedules the drop sequence by utilizing the number of messages buffered at router and size of messages. To ex- hibit the performance of MDC, we assess four routing performance metrics Message drop, delivery probability overhead and buffer time averages. The proposed policy maximizes delivery probability, buffer time average and minimizes message drop and overhead as compared to existing MOFO, LIFO and DOA.
The rest of this paper is organized as follows: Section 2 presents the existing buffer management polices. In sec- tion 3, we discuss about the first contact routing protocol. The section 4 gives core idea of the buffer optimization and section 5 maps the algorithms of MDC policy .Section
6 displays simulation results and compares it with other buffer strategies follwed by conclusion in section 7.
In this strategy when node buffer overflows then the rou- ter randomly drop the message from queue. Hence all messages have equal deletion priority. The schemes work with out network knowledge and perform poorly in high- ly congested networks
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 2
ISSN 2229-5518
The message with minimum arrival time in the queue will be selected to drop. In this scheme the probability of dropping the source messages is extremely high.
The message with the longest stay time in buffer will be dropped. The idea is that the packet with in buffer for long time has less probability to be conceded to other nodes.
In N-Dropt [11], the message that achieves N number of forwarding will be selected to drop. If there are no mes- sages with N number of forwarded then last packet will be drop first.
When node buffer is full and new transmission arrives with size S, the node search and drops the buffered mes- sage B, if the size of buffered and new arrival is equal. This scheme minimizes the drop of messages. [4]
The message that has been forwarded to maximum num- ber of times will be dropped first, thus that the messages with fewer times more chances of getting forwarded [10].
Each message in node is related with a forwarding pre- dictability FP, initially assigned to 0. When the message is forwarded the FP value is modified and the message with maximum FP value will be dropped first. [10]
The message lies in the threshold size range will be se- lected to drop. [3]
The message contain smallest TTL will be selected to drop. [10]
“Since the node is minimum amount likely to deliver a message for which it has a low P- value. Drop the mes- sage for which the node has the lowest P value.” [10]
According to this strategy when node buffer is full, the message with large size will be drop. [13]
GBD based on global knowledge about the network state. As global Knowledge is required, GBD is difficult to be implemented, thus, it will serve as a point of reference. [12]
“A deployable variant of GBD that uses the new utilities based on estimates of m and n, the m is the number of
nodes that have seen the message and n is those whom have copy of it”. [12]
FBD accounts only for the global information collected using simple message flooding, that is, without consider- ing past history or other messages. [12].
First contact algorithm [2] transmits the single copy of message along a distinct path from the list of intermittent- ly connected mobile nodes. This path selection is random and depends on the local knowledge of router. If no con- tact is available then router waits until the transmission opportunity arises. First contact router only carries the single copy of message thus minimizes the number of transmission, bandwidth, buffer space and energy in con- trast to multi copy schemes.
The objective of buffer management policies is to minim- ize the effect of message drop on the network throughput. It has been evicted [12] that the control on the message drop proves efficient use of network resources and pro- vides additional growth in the router performance. In this section, we give a theoretical summary about the pro- posed buffer scheduling policy and compare it with exist- ing scheme MOFO. However the policy also out performs well as compared to DOA and LIFO.
TABLE 1
NODE CONFIGURATIONS
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 3
ISSN 2229-5518
Consider a snap shot (Table 1) of node A and B mod- eled by store-carry-forward network. Each node has stored M message (s) in its local buffer with message id (Mid), mes- sage size (Msize) , number of forwarding (NoF), Arrival time (AT) and destination (DEST).
We further assume that buffer space for each node is
2500KB, while A is the message rate between two nodes
space is 280Kb therefore M1 and M3 will be dropped to make the room for new arrival.
In this section we will show the comparisons of proposed
and A=1/ E (Z )
where E (Z )
is the average meeting
TABLE 3
time. When node A moves in the transmission range B, then according to FIFO forwarding order, node A for- wards message M14 of size 900KB to node B. In order to accommodate this new arrival node B will follow the MOFO sequence and iteratively drop M5 (280), M2 (200), M4 (320), and M1 (800). This redundant drop of message raises the overhead ratio while minimize buffer time av- erage and delivery ratio.
TABLE 2
NODE CONFIGURATIONS
Node | Mid | Ms | NoF | AT | DEST |
A | M1 | 800KB | 4 | 10s | B |
A | M2 | 200KB | 6 | 23s | D |
A | M3 | 900KB | 3 | 25 | B |
A | M4 | 320KB | 5 | 30s | C |
B | M10 | 300KB | 12 | 22s | A |
B | M11 | 250KB | 9 | 25s | A |
B | M12 | 500KB | 8 | 35s | D |
B | M13 | 650KB | 4 | 38s | A |
B | M14 | 900KB | 2 | 40s | G |
Message Control Drop strategy (MDC) minimizes the drop by defining an upper bound limit (UB). By this, a node while carrying N number of message will not drop any message if N>=UB. In view of table 1 , assume that the Upper- Bound (UB) is 5. When a new transmission arrives, node B (N>=5) will not drop any message which alternatively increase the buffer time average, minimize the overhead and raise the delivery probability.
When Upper-Bound (UB) is less then N number of mes- sages and new transmission arrives at node the largest size message will be dropped from queue. Table 2 depicts the scenario where UB<=N and node A has forwards the message M14 of size 900KB to B. The available buffer
IJSER © 2011 http://www.ijser.org
SYMBOL TABLE
ALGORITHM
International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 4
ISSN 2229-5518
buffer scheduling strategy (MDC) with existing DOA, MOFO and LIFO. The evaluation of schemes have been analyzed under ONE [15] simulator. ONE is a discrete event simulator written in JAVA and have been massive- ly used by various researcher to measure the statistics of disrupted store-carry-forward applications.
We have simulation setup scenario simulated as six groups, in which two of them are pedestrians and one is car group and three of them are from trains group. Three groups(2 pedestrians, 1cars) have 40 nodes and other trains groups have six nodes which are randomly spread with random source and destination over a simulation area of 4500mx3400m. Then, three group moves with a mobility model by shortest path Map Based movement (SPMBM) and trains groups with Map route movement (MBM). Speeds of groups (pedestrians, cars and trains) are 0.5-1.5km/h, 2.7-13.9 km/h and 7-10km/h respective- ly .Every node have DTN capabilities of bundle layer and follow the store carry forward mechanism.
Some other parameters, we suppose that the all DTN nodes converse with one another by transmission range of 10M with 2 Mbps link bandwidth. We have random selected size of messages range from 200k to 500k with infinite TTL time which are randomly created during in- ter message interval .Also we varied the inter message interval from [15s,25s],….[55s,65s] to see the source mes- sage creation on the mobile nodes in term slow/fast gen- erated sources messages. Furthermore, we suppose that three groups have a buffer size of 4MB and other have
10MB with FIFO forwarding order. The above explained set up we generate numerous scenarios for First contact routing protocol with the existing DOA,MOFO,LIFO and proposed Message drop control (MDC) drop policy with simulation end Time 200000s to see the mobility effects on large scale.
Fig. 1. Message Drop Control
DOA, MOFO LIFO and proposed MDC strategy. Message creation interval has been used to monitor the impact of source message creation on the storage. We can observe that at each simulation instance Message Drop Control (MDC) policy reduces the drop and performs better then the existing buffer scheduling schemes. This control on message drop has two fold advantages; first message gets more time to stay in the buffer which raises its delivery probability. Secondly, when a message is dropped out it is the waste of all resources (bandwidth, buffer, transmis- sions, and energy) which it consumes during its mobility.
Fig. 2. Message Delievery probablity
In opportunistic networks, the delivery of message is accomplished via multiple hop(s). On each transmission the message consumes network resources such as band- width, buffer space and energy. Therefore, the successful transmission of messages to their destination proves the efficient use of network resources.
Fig 2 shows the mapping of existing and proposed (MDC) buffer management schemes in terms of delivery probability. We can see that at each message creation in- terval more messages are delivered then the existing strategies. Reason for this, is that when the congestion arises, instead of blind drop, proposed policy (MDC) uses UB to controls the admission of source and relay messag- es [14], therefore this block on drops boost the message stay time in buffer which raises its delivery likelihood.
When a node transmits the messages the most impor- tant aspect on its delivery depends on the storage capabil- ity (buffer) of the intermittently connected mobile nodes. In DTN environment the nodes keeps the messages for long period of time due to network partitioned and end- to-end path unavailability. Hereby the node buffer may run out of space, as a result buffer drop policies overcome this congestion by dropping messages.
Fig 1 plots the effect of message drop with existing
Fig. 3. Overhead ratio
Overhead measure is used to estimate the cost of re- sources required to process the transmission and storage
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 5
ISSN 2229-5518
of message. The algorithms performing well in terms of increasing delivery probability, but produce high over- head that are not reasonable for practical implementation.
Fig 3 represents the affect of proposed MDC policy and existing policies with respect to overhead ratio. We can see that the proposed MDC reduces the overhead in the considered amount. Reason for this, is that the MDC blocks the number of iterations required to select the drop message. Furthermore, MDC not allows nodes to drop message if the criteria fails and the router already holds messages in reasonable amount. In First contact ap- proach, the router always randomly relay the message to the neighboring nodes which is might not towards the destination that sometimes increase the overhead but our policy reduces these protocol oriented overhead.
Delay Tolerance network (DTNs) suffers from long de- lays and the delivery of message highly depends on the time it spends in the buffer of intermediate node. There- fore, increase in the buffer time average grantees the mes- sage transmission towards next hop which might be able to make progress towards destination.
Fig. 4. Buffer Time Average
Fig 4 compares the results of Message Control Drop (MDC) with existing policies in context of buffer time average. We can observe that at each message creation interval, buffer time average of proposed policy is higher then the existing policies. The longer stay of these mes- sages makes router to deliver/relay it to next hops.
In this paper we propose the buffer scheduling policy Message Drop Control which optimizes the single copy routing protocol First Contact. We examine the perfor- mance of proposed policy by comparing it with MOFO, DOA, and LIFO. The simulation model proves that pro- posed policy MDC out perform well for and maximize the router performance in terms of delivery probability, message drop, overhead and buffer time average.
This work is financed by institution scholarship provided by UTM and Ministry of Higher Eduction of Malaysia.
[1] KERÄNEN, A., AND OTT, J. Increasing Reality for DTN Protocol Simulations. Tech. rep., Helsinki University of Tech- nology, Networking Laboratory, July 2007.
[2] K. Fall, “A delay tolerant network architecture for challenged
internets”, in Proc. ACM SIGCOMM, pp.27-24, 2003.
[3] Qaisar Ayub, Sulma Rashid,” T-Drop: An optimal buffer man- agement policy to improve QOS in DTN routing protocols”, Journal of Computing, Vol 2, ISSUE 10,
[4] Rashid, S., et al., E-DROP: An Effective Drop Buffer Manage-
ment Policy for DTN Routing Protocols. International Journal,
2011. 13(7): p. 8-13.
[5] Vahdat and D. Becker, “Epidemic routing for partially- connected ad hoc networks,” Tech. Rep. CS-2000-06, Duke University, July 2000.
[6] T. Spyropoulos, K. Psounis and C. S. Raghvendra "Spray and
Wait Efficient routing in intennittently connected Networks," in Proceeding of Mobile Computer and Communication review Vol. 7,no. 3, July 2003.
[7] R Ramnathan, R. Hansen, P. Basu, R. R Hain and R Krishnan, "
Prioritized Epidemic Routing for Partially Connected Ad Hoc
Networks ", in proceeding of ACM MobiOpp'07, 2007.
[8] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Single- copy routing in intermittently connected mobile networks,” in Proc. IEEE Conf. Sensor and Ad Hoc Communications and Networks (SECON),2004, pp. 235–244.
[9] R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules:
Modeling and analysis of a three-tier architecture for sparse sensor networks,” Elsevier Ad Hoc Networks Journal, vol. 1, pp.
215–233, Sept. 2003.
[10] A.INDGREN AND K. S. PHANSE, “EVALUATION OF QUEUING POLI- CIES AND FORWARDING STRATEGIES FOR ROUTING IN INTERMIT- TENTLY CONNECTED NETWORKS,” IN PROC. OF IEEE COMS- WARE, PP. 1-10, JAN. 2006.
[11] YUN LI, LING ZHAO ,ZHANJUN LIU, QILIE LIU.” N-DROP CON- GESTION CONTROL STRATEGY UNDER EPIDEMIC ROUTING IN DTN.” RESEARCH CENTER FOR WIRELESS INFORMATION NET- WORKS, CHONGQING UNIVERSITY OF POSTS & TELECOMMUNICA- TIONS, CHONGQING 400065,CHINA, PP. 457-460, 2009.
[12] AMIR KRIFA, CHADI BARAKAT, THRASYVOULOS SPYROPOULOS,
“OPTIMAL BUFFER MANAGEMENT POLICIES FOR DELAY TOLE- RANT NETWORKS,” IEEE CONFERENCE ON SENSOR, MESH AND AD HOC COMMUNICATIONS AND NETWORKS (SECON 2008), JUNE
2008.
[13] Sulma Rashid,Qaisar Ayub,”Effective buffer management policy DLA for DTN routing Protocals under congetion”, In- ternational Journal of Computer and Network Security,Vol 2,NO
9,Sep 2010. pp .118-121.
[14] Al-Siyabi, M., H. Cruickshank, and Z. Sun. “Quality of service provisioning for delay tolerant network by implementing ad- mission control model for aircrafts bundles data transmis- sion.”, 2010: ACM.
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 6
ISSN 222S-5518
(15] DELAY TOLERANT NETWORKING RESEAROI GROUP.
HTTP:IIWWWDTNRG.ORG .
IJSER 2011
http /lwww .qser.org