Improving Cache Consistency with Minimal Network Contention and Cache Replication in Server Based MANET

Abstract

In most server-based schemes, server is not usually aware of what data items are currently cached, as they might have been replaced or deleted from the network due to node disconnections. In this method a cache consistency scheme for caching the database data in MANET is implemented which enable the server to be aware of the cache distribution and make the data items consistent with their version at the server. In this method the queries that are submitted by requesting nodes are stored in special nodes, called query directories (QDs) ,and uses these queries to locate the data that are stored in the nodes hat requested them called caching nodes(CNs).The overall design provides a complete caching system in which the server sends to the clients selective updates that adapt to their needs this reduces wireless traffic in MANET. In this method only one caching node is allowed to cache for a particular data and if the request rate for the particular data is high then there is more number of hits in a particular QD&CN for that data .In order to avoid this the concept of cache replication is implemented. The replicated cache cannot come under the same QD in order to avoid the network congestion in that QD.

Index Terms

Cache consistency, Data caching, cache replication, MANET

INTRODUCTION

A Mobile Ad Hoc Network (MANET) is a collection of wireless mobile nodes forming a temporary network without the need for base stations or any other preexisting network infrastructure. However frequent path changes cause significant numbers of routing packets to discover new path. Each MANET node can serve as a router, and may move arbitrary and dynamically connected to form network depending on their positions and transmission range. Caching technique is an efficient solution for increasing the performance in message or data communication. Cooperative caching is the scheme which allows the sharing and coordination of cached data among multiple clients. However, frequent disconnections and mobility of the clients make cache consistency a challenging problem. Effective cache invalidation strategies are required to ensure the consistency between the cached data at the clients and the original data stored at the Server[4]. when cache techniques are used, data consistency issues must be addressed to ensure that clients see only valid states of the data. Cache consistency algorithms are used to maintain the consistent copies of data. Server invalidation is a consistency approach in which the server broadcast the invalidation report to all clients in the network, if the copy is up to date, the server informs the client that the data have not been modified; else the update is sent to the client. This server invalidation scheme is a strong consistency algorithm in which the users are served usually fresh data items This work describes a server-based scheme implemented on top of the COACS caching architecture.

Approach

In COACS, elected query directory (QD) nodes cache submitted queries and use them as indexes to data stored in the nodes that initially requested them (CN nodes)

In Fig 1 RN(request node) send a query to QD(query directory),the QD maintains a table which contains the details about cache node and data’s in the cache node then it forwards the request to the cache node which has desired data item.CN sends the reply message back to the RN , Since COACS did not implement a consistency strategy, the system described in this paper fills that void and adds several improvements: 1) Enabling the server to be aware of the cache distribution in the Network, 2) making the cached data items consistent with their version at the server, and 3) adapting the cache update process to the data update rate at the server relative to the request rate by the clients. 4) Minimizing the cache hit ratio by cache replication With these changes, the overall design provides a complete caching system in which the server sends to the clients selective updates that adapt to their needs and reduces the average query response time, and minimizes cache hit ratio[8].

The rest of the paper is organized as follows: Section 2 presents the related work..Section 3 describes the SSUM mechanism In Section 4 we propose Cache replication technique for reducing cache hit ratio. We devote Section 5 the performance evaluation of our scheme. Finally, we conclude the paper in Section 6.

RELATED WORK

Caching frequently accessed data items on the client side has recognised as an important technique to reduce access delay and network traffic in a limited bandwidth mobile environments. Several cache invalidation methods are used for achieving cache consistency. Replication protocols are used for maintaining consistency in data transfer.

Consistency Approaches

The study compares three consistency approaches: Adaptive TTL, Polling-every-time, and Invalidation. The two approaches such as invalidation and pollingevery- time are considered as strong consistency. In invalidation approach, The web server keeps track of all the client sites that cache a document, and when the document is changed, sends invalidation messages to the clients. In the Polling-every-time approach, every time the user requests a document and there is a cached copy, the cache first contacts the web server to validate the cached copy, then returns the copy to the user. In adaptive TTL, the cache manager assigns a time-to-live attribute to a document, if TTL value expires then the cached copy needed to be updated. This approach is considered as weak consistency model and consumes more network bandwidth. Thus strong consistency approach overcomes the problem by minimizing the bandwidth consumption.

COACS system for MANETS

COACS is a distributed caching scheme that relies on the indexing of cached queries to make the task of locating the desired database data more efficient and reliable. Nodes can take on one of two possible roles: CNs and QDs. A QD’s task is to cache queries submitted by the requesting mobile nodes, while the CN’s task is to cache data items (responses to queries). When a node requests data that is not cached in the system (a miss), the database is accessed to retrieve this information. Upon receiving the response, the node that requested the data will act as a CN by caching this data. The nearest QD to the CN will cache the query and make an entry in its hash table to link the query to its response In order to find data in a system of only CNs, all the nodes in the network would need to be searched. This is where QDs come into play in the proposed system. QDs act as distributed indexes for previously requested and cached data by storing queries along with the addresses of the CNs containing the corresponding data. In this paper, we refer to the node that is requesting the data as the RN, which could be any node, including a CN or a QD. The QD nodes make up the core of the caching system. To cope with the limited resources of mobile devices and to decrease the response time of the system, several QDs are used to form a distributed indexing system. If one QD receives a request that it has not indexed, the request is passed on to another QD[1].

replication is used minimize the cache hit ratio also and made data frequently available in the network.

SSUM MECHANISM

SSUM is a server-based approach that avoids many issues associated with push-based cache consistency approaches. Specifically, traditional server-based schemes are not usually aware of what data items are currently cached, as they might have been replaced or deleted from the network due to node disconnections.

Basic Operation

In SSUM, the server autonomously sends data updates to the CNs, meaning that it has to keep track of which CNs cache which data items. This can be done using a simple table in which an entry consists of the id of a data item (or query) and the address of the CN that caches the data. A node that desires a data item sends its request to its nearest QD. If this QD finds the query in its cache, it forwards the request to the CN caching the item, which, in turn, sends the item to the requesting node (RN). Otherwise, it forwards it to its nearest QD, which has not received the request yet. If the request traverses all QDs without being found, a miss occurs and it gets forwarded to the server which sends the data item to the RN. In the latter case, after the RN receives the confirmation from the last traversed QD that it has cached the query, it becomes a CN for this data item and associates the address of this QD with the item which, in turn, adds the CN’s address to the data item in its memory. This setup allows the server to send updates to the CNs directly whenever the data items are updated. In the fig 3, the requesting nodes (RNs) submit queries to their nearest QDs, if the match is not found then QD forwards the Request to another QD[8], again the match is not found then forwards the request to the server and RN gets the reply from the server.

2. Basically every time when a node make a request for a data the ratio Ru/Rr is calculated. When the ratio within the replication's threshold value then the data is allowed for the replication.

3. Once the ratio below 0.75 the caching node send the request to the server for cache replication and get the permission for the replication. After a new node get that particular data it is allowed for caching that data by sending QCRP message to the new node.

SIMULATION SETUP

In this section, we are going to simulate the query delay and the update delay by replicating the data.

Network and cache simulation Parameters

A single database server is connected to the wireless network through a fixed access point, while the mobile nodes are randomly distributed. The client cache size was fixed to 200 Kb, meaning that a CN can cache between 20and 200 items, while the QD cache size was set to 300 Kb, and therefore, a QD can cache about 600 queries. We used the least recently used (LRU) cache replacement policy when the cache is full and a data item needs to be cached. Each scenario started with electing one QD, but more were elected when space was needed.

Each scenario lasted for 2,000 seconds and repeated 10 times with the seed of the simulation set to a new value each time, and the final result was taken as the average of the 10 runs.

Results

In this experiment , we tune the query rate. We find that, when the query rate increases, there is increase in Traffic, the data update rate is high. By using cache replication the query request rate decreases ,and the traffic also decreases in fig.5when there is more number of query ,there will be delay in the query reply, this delay can be reduced by replicated data. when the data is replicated for more than one node, the query delay decreases.

The fig 5 shows there is a decrease in query request rate by data replication. The smart server update Mechanism updates the data in the cache node with the current version in the server so the reply of stale document decreases in the MANET.

CONCLUSION AND FUTURE WORK

In this paper, we presented a novel mechanism for maintaining cache consistency in a Mobile Ad hoc Network. Our approach was built on top of the COACS architecture for caching data items in MANETs and searching for them. We analyzed the performance of the system through a gain loss mathematical model and then evaluated it while comparing it with the Updated Invalidation Report mechanism. The presented results illustrated the advantage of our proposed system in most scenarios. The evaluation results confirmed our analysis of the scalability of the system. That is, they indicate that even when the node density increases or the node request rate goes up, the query request delay in the system is either reduced or remains practically unaffected, while the cache update delay experiences a moderate rise.

Yet, even if a higher update delay means that the probability of nodes getting stale data increases, the proposed system includes a provision for keeping track of such nodes and supplying them with fresh data within a delta time limit. Hence, it can be concluded that the system can scale to a moderately large network even when nodes are requesting data frequently. Moreover, the increase in the node speed and disconnection rate also only affected the cache update delay, and to a lesser extent, the traffic in the network. This reflects on the robustness of the architecture and its ability to cope with dynamic environments.

For Our Future Work, We Will Do a Thorough investigation of possible threats that could disrupt the operations of SSUM and devise security mechanisms that safeguard it by either building on existing approaches, or developing new ones.

References

H.Artail,H.Safa,K.Mershad,Z.AbouAtme,N.Sulieman,”COAC S:A Cooperative and adaptive Caching System for MANETS,”IEEETrans.MobileComputing,vol.7,no.8,pp.961- 977,Aug.2008 H.Artail and K.Mershad,”MDPF: Mnimum Distance PacketForwarding for Search Applications in Mobile AdHocNetwork,”IEEETrans.MobileComputing,vol.8,no.10,p p.1412-1426,oct.2009 K. G.Cao,”A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments,”IEEE Trans.Knowledge and Data Eng.,vol 15,no.5,pp.1251-1265,sept.2003 P.Cao and C.Liu,”Maintaining Strong Cache Consistency intheWorldWideWeb,”IEEETrans.Computers,vol.47,no.4,pp. 445-457,apr.1998 K.Shanmugavadivu and Dr M.Madheswaran,”caching Technique for Improving data retrival performance in mobile adhoc networks . J.Yuen,E.Chan,K.Lain,andH.Lueng,”Cache Invalidation scheme for Mobile computing with real-time Data,vol.29,no.4,pp.34-39,dec.2000 H.Maalouf and M.Gurcan,”Minimisation of the Update Response Time in Distributed DatabaseSystem,2002