Integrated Query Caching Technique For Efficient Caching Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

ABSTRACT

Mobile Ad-hoc Networks (MANETs) are dynamic in nature, and therefore, a reliable caching scheme is more difficult to achieve. Links between nodes may constantly change as nodes move around, enter, or leave the network. This can make storing and retrieving cached data particularly difficult and unreliable. The use of mobile devices adds even more complexity due to their relatively limited computing resources (e.g., processing power and storage capacity) and limited battery life. It follows that an effective caching system for MANETs needs to provide a solution that takes all of these issues into consideration. An important policy of such a solution is not to rely on a single node but to distribute cache data and decision points across the network. With distribution, however, comes a new set of challenges. The most important of which is the coordination among the various nodes that is needed in order to store and find data. This paper introduces a scheme of query based data caching system called Integrated Query Caching Technique (IQCT) for MANETs. Query Node (QN) is the central component of the IQCT scheme, in which the query requests are stored in query Indexer (QI) and these stored queries are used as indexes to data cached in nodes that previously requested them. Based on the Hit Count (HC) measurement the frequently asked data's stored in its Local Cache (LC). Simulations with the ns-2 software were used to study the performance of the system in terms of average delay and hit ratio and to compare it with the performance of other caching schemes for MANETs.

1 INTRODUCTION

MANET is made of a collection of mobile nodes that can be interconnected by a multi-hop path and without any need of a wired infrastructure. Therefore, it can be seen as an autonomous system or a multi-hop wireless extension. Recently, with the rising popularity of multimedia applications and potential commercial/military usage of MANET, better throughput and guaranteed QoS are demanding from the mobile Ad Hoc Networks. One of the challenges in the study of MANET routing protocols is the evaluation and design of an effective routing protocol that works at low data rates and responds to dynamic changes in network topology due to node mobility. Several routing protocols have been standardized by the Internet Engineering Task force (IETF) to address ad-hoc routing requirements.

Although routing is an important issue, the ultimate goal of a MANET is to provide mobile nodes with access to services, but for any service to be successful it needs to be accessible from most mobile devices. In MANETs accessing services and data over the network can be very slow and hence, caching frequently accessed data is an effective technique for improving performance. While caching data on the device is useful for the device itself, this mechanism does not provide a consistent framework for allowing all other devices in the network to benefit from this data. Therefore, devising an effective caching strategy for the whole MANET is of special importance since it allows for improving the performance of the network as a whole.

In this paper we propose a new model for caching database data in MANETs through caching the queries and some frequent responses on QN, caching data (numerical, textual, or mixed data) on the node requires the reservation of storage space, which is limited on mobile devices and hence, we need to make every attempt to save space and be able to increase the collective amount of cached data in the network. Our caching model is based on caching the SQL statements that correspond to queries and their return data. The Query Indexer (QI) stores the queries without the data and also associates these queries with the Provider Node (PN) that hold the corresponding data. If the requested query is present in the QI it points to the node where the actual data resides and increments the HC value by 1. The QN stores a copy of data in its local cache if HC value exceeds the threshold value λ.

The rest of this paper is organized as follows: In Section 2, a survey of caching strategies in ad-hoc network is given, followed by Section 3, which describes the related work. Section 4 describes the proposed system and provides an analysis and derives expressions for the system parameters and performance measures. Section 5 is dedicated to describing the simulation experiments and discussing the results. Finally, Section 6 concludes the paper.

2 CACHING STRATEGIES IN AD-HOC NETWORKS

Cache management in mobile ad hoc networks, in general, includes the following issues to be addressed:

1) The cache discovery algorithm that is used to efficiently discover, select, and deliver the requested data item(s) from neighboring nodes. In a cooperative architecture, the order of looking for an item follows local cache to neighboring nodes, and then to the original server.

2) Cache admission control - this is to decide on what data items can be cached to improve the performance of the caching system.

3) The design of cache replacement algorithm - when the cache space is sufficient for storing one new item, the client places the item in the cache. Otherwise, the possibility of replacing other cached item(s) with the new item is considered.

4) The cache consistency algorithm which ensures that updates are propagated to the copies elsewhere, and no stale data items are present.

2.1 CACHE DATA AND CACHE PATH

In Cache Data, intermediate nodes cache the data to serve future requests instead of fetching data from the data center. To avoid storage space wastage, a conservative rule should be followed: A node does not cache the data if all requests for the data are from the same node. When the cache size is very large or for some particular data that are interested by most nodes, the conservative rule may decrease the cache performance because data are not cached at every intermediate node. However, in mobile networks, nodes usually have limited cache spaces to store only frequently accessed data.

Data-path caching scheme is also a kind of effective scheme to reduce data request delays without causing a large number of data clones. In Cache Path, mobile nodes cache the data path and use it to redirect future requests to the nearby node which has the data instead of the faraway data center.

2.2 CACHE MANAGEMENT POLICIES

Cache management is more complex in caching because deciding what to cache can also depend on the node's neighbors. Cooperative caching presents two problems: cache replacement and cache admission control.

2.2.1 CACHE REPLACEMENT

Caching is a key technique in mobile computing environment for improving the data retrieval performance. Due to cache size limitations, cache replacement algorithms are used to find a suitable subset of items for eviction from the cache. In this case, if an accessed data object is to be cached, some other cached data objects have to be evicted to accommodate the newly accessed object. In the client-server model of mobile/wireless data access, the update process plays an important role because it makes cached data obsolete. Thus, a replacement policy may have to utilize update information besides access information. Most replacement policies which are widely used in other systems have been introduced into mobile/wireless network client caching, such as Least- Recently-Used (LRU) and Least-Frequently-Used (LFU) replacement policies [13]. These replacement policies basically use access time or access frequency to determine which data object to be replaced.

2.2.2 CACHE ADMISSION CONTROL

When a mobile node receives the requested data item, a cache admission control is triggered to decide whether it can cache this item. Inserting a data item into the cache might not always be favorable because it can lower the probability of cache hits. For example, replacing a data item that will be accessed soon with a data item that won't be accessed in the near future degrades performance. We can use the cache replacement value function to implement cache admission control simply by comparing the requested item's cost to the cached item with the highest cost. To increase data accessibility, a node cannot cache data that some neighbors already cache; rather, it uses its local space to cache more data. The primary idea is that [14], in order to increase accessibility, we try to cache as many data items as possible, while trying to avoid too much duplication.

2.3 CACHE INVALIDATION

The wireless network bandwidth between mobile clients and servers is limited. The cache technology in traditional conception is able to reduce the traffic, so it avoids the network congestion efficiently. Traditional methods include that servers broadcast cache invalidation information to clients and that clients query servers to verify the cache information. Due to the character of often disconnection in clients, clients are unable to receive the invalidation information during the disconnection. Thus the whole cache should be invalidated after reconnection. Our study of cache invalidation in an MANET environment is motivated by the following observations:

1) The communication model in an MANET is different from that in the cellular environment - in an MANET a multi-hop communication is employed.

2) The cost for a broadcast in an MANET is different from that in the cellular environment - a broadcast may lead to flooding of the whole network.

3) The connectivity to a server is less stable than that in the cellular environment - due to the user mobility a mobile node may be disconnected or isolated from the server or other mobile nodes.

3 RELATED WORKS

By reference [1] Database access is normally handled using Structured Query Language (SQL) and as such, we can either cache the sent SQL queries (or statements) along with the corresponding return data, or replicate the database data among the mobile nodes. We base our caching model on caching the SQL statements that correspond to queries and their return data. In effect, our proposed architecture makes query discovery the underlying service that enables access to cached database data. The entities in the architecture are the Service Manager (SM) and its backup (BSM), the Query Directories (QDs) and their respective backups (BQDs), and the mobile nodes that cache the query responses, which we refer to as the Caching Nodes (CNs). The CNs only stores the query responses, i.e., the database data, and associates them with the queries that caused them to be returned by the database server. Similarly, the QDs store the queries without the data and also associate these queries with the CNs that hold the corresponding data. Finally, the SM keeps track of which nodes have the role of QDs and BQDs and makes assignments and reassignments based on availability and fairness criteria.

The data consistency [2] [11] between mobile devices and the server follows the approach proposed in SACCS algorithm. In SACCS, each data item in a server is associated with a flag bit. When an item is retrieved by a mobile device, the corresponding flag bit is set indicating that a valid copy may be available in the mobile cache. When the data item is updated, the server immediately broadcasts its invalidation report (IR) to mobile devices and resets the flag bit. The reset flag bit implies that there is no valid copy in any mobile cache. Hence, subsequent updates do not broadcast IR until the flag bit is set again.

In article [3] considers the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least one-fourth (one-half for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes.

By reference [4] [12] [13] 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.

Several other researches focus on caching mechanism [5] [6] [7] [8] [10] in mobile database system. Web caching [9] and Web prefetching are two important techniques used to reduce the noticeable response time perceived by users. Note that by integrating Web caching and Web prefetching, these two techniques can complement each other since the Web caching technique exploits the temporal locality, whereas Web prefetching technique utilizes the spatial locality of Web objects.

4 PROPOSED SCHEME

4.1 OVERVIEW OF THE DSR PROTOCOL

We use the Dynamic Source Routing protocol (DSR) [16] in this paper to illustrate the effects of caching; since DSR operates entirely on-demand and thus clearly shows the caching behavior. In source routing algorithm, each data packet contains complete routing information to reach its destination. Additionally, in DSR each node uses caching technology to maintain route information that it has learnt. There are two major phases in DSR, the route discovery phase and the route maintenance phase. Route Discovery is the mechanism by which a node S wishing to send a packet to a destination node D obtains a source route to D. Route Discovery is used only when S attempts to send a packet to D and does not already know a route to D. Route Maintenance is the mechanism by which node S, while using a source route to D, is able to detect when the network topology has changed such that it can no longer use its route to D because a link along the route no longer works. When Route Maintenance indicates a source route is broken, S can attempt to use any other route it happens to know to D, or can invoke Route Discovery again to find a new route for subsequent packets that it sends. Route Maintenance is used only when S is actually sending packets to D. DSR works with low control overhead, compare to others routing protocols (e.g. AODV, DSDV).

4.2 INTEGRATED QUERY CACHING TECHNIQUE

4.2.1 BASIC CONCEPTS

Integrated caching technique is a distributed caching scheme, in which we assign the role of QN for the specific mobile nodes for query indexing and data caching. Information about the available QN is then broadcasted across the mobile network so all mobile nodes know the number of QNs and where to send their queries to get the data (if such queries are cached). Forwarding pointers can be used to link QNs, the QN contains two major parts namely QI and LC. The QI store the queries without the data and also associate these queries with the Node (N) that hold the corresponding data called PN. If the requested query is not available in the QI means it store the query and passes its request to another QI, which is in the nearest distance. The QI contains the SN address, RN address, Query Request ID, Hit Count value. If the Hit Count value exceeds the predefined threshold value that particular data will be stored in its LC for future request and the corresponding link in the QI will be marked.

4.2.2 CACHING PROCESS

N1

N10

N9

REQ2

REQ1

QN1

QN3

RN

REP2

REQ1

N6

N2

PN

REP1

N8

REP1

N3

N7

REP1

N4

QN2

N5

Fig1: Ad-hoc network used to demonstrate IQCT

Fig1 shows the Ad-hoc network topology, which is used to demonstrate the functions of IQCT. According to DSR, when a mobile node needs a particular data, it sends a REQ message to the nearest QN. If it has the query request already in its QI it points to the node which has the requested data. In case the query not available in the current QI, it forward the request to the another QI which is nearest to that. Again it forward the REQ message to the node which holds the actual data called PN. Finally PN sends the REP message through the shortest path.

In our Example, the RN sends the request to QN1, it has the requested query so that, it points to the node PN. Now PN send the reply in the shortest path which is calculated already, at the same time QN1's HC value is incremented by1. When the HC value exceeds the predefined threshold value one copy of that corresponding data is stored in its local cache. In case the same data requested by the some other node means the QN1 will act as a cache and reply directly. As implied from above, each QN becomes a Cache Node once it obtains the results of its query and will thus participate in providing caching services to the network. If its designated storage space ever becomes full of cached results, it may use one of the replacement algorithms (e.g., least recently used or least frequently used) to store the new result at the expense of an old one.

4.3 PSEUDOCODE FOR IQCT

At RN;

Send REQ to QN;

Rec REP from node or QN;

At QN:

Rec REQ message from the SN;

Check the Query availability;

If (available)

{

Forward to the destination location (PN);

Increments HC by1;

If (HC> λ)

{

Save a copy a of corresponding data in LC;

Mark the corresponding query as MQ in QI;

}

}

Else

{

Save a copy of the Query and forward to next QI;

}

At PN:

Rec REQ from QI;

Send the REP message to nearest RN or Neighbor;

4.4 QUERY NODE SELECTION

Query Node is the important component of our system so it must be selected carefully. Preference [4] should be given to nodes that are expected to stay the longest in the network and have sufficient resources. The resources might be,

Long duration

Long battery power

High memory

High Bandwidth

Low mobility

∈ { DUR, BAT, MEM, BW, MOB }------1

The number of QN is depends on the memory and battery power of that node. In some exceptional case (i.e. no node have sufficient resources) the storage space in the QI becomes full the IQCT choose efficient cache replacement algorithm.

CONTENT OF QUERY NODE

QUERY INDEXER

LOCAL CACHE

Query Indexer ID : QID

Response Data ID: RID

Query indexer current location: ( Xnq, Ynq )

Source address Data: SA

One way hash table contains the queries;

Data;

Hit count value : ĥ

Some marked queries: MQ

Neighbor Details: NQ

Table1: Demonstrate the content of QN

4.5 ALGORITHM ANALYSIS

Given a set of data items D= {d1, d2, d3……di} such that for each item di ε D, a size si >0, also given that cache capacity of each client is C should be grater than the data size.

Cp = ------ 2

If rtot and rsuc denote the total number of requests and the number of successfully received data items, then throughput (μ) can be calculated as,

μ =------ 3

μ = (rsuc ⁄ rtot) *100 ------ 4

The average hit ratio also correlated with this success ratio. An access request succeeds if and only if at least one of the connected mobile hosts holds the original or a valid copy of the target data item. The equation 5 used to calculate the average hit ratio (Ä¥)

Ä¥ = (rsuc * HC)

rtot *100 ------ 5

4.6 ADVANTAGES OF IQCT

Maximize Network Performance

Scalability

Provide End-To-End Reliable Communications

Reduce Possible Delays

Minimize Losses

4.6 IQCT PROCESSING CHART

QN

RN SEND REQ

NO

GOTO NEXT QI

CHECK QUERY AVAILABILITY IN QI

YES

NO

IF

(HC>λ)

INCREMENT HC BY 1

YES

RETREIVE DATA

FFROM LC

SEND REQ

PN

SEND REP

5 PERFORMANCE EVALUATIONS

We demonstrate through simulations the performance of our designed cache placement algorithms over randomly generated network topologies. We simulated our algorithms on a network of randomly placed 100 nodes in an area of 700 X 500. Note that the nominal radio range for two directly communicating nodes in the ns2 simulator is about 250 meters. In our simulations, we assume 1000 data items of varying sizes. Two randomly placed QNs stores the Queries and point to the PN and the size of the QI is 75Kbits and LC size is 75Kbits i.e. capable of storing 100 packets. We choose the size of a data item randomly between 100 and 1500 bytes.

5.1 DELAY

Each query is essentially a request for a data item, the time interval between two consecutive queries is known as the query generation time and follows exponential distribution with mean value TQG which we vary from 3 to 40 seconds. Here, query success ratio is defined as the percentage of the queries that receive the requested data item within the query success timeout period. In our simulations, we use a query success timeout of 40 seconds.

In fig2, X-axis shows query generation time and Y-axis shows the delay in seconds. When TQG is small, more queries are generated and the system workload is high. As a result, the average query delay is high. As TQG increases, less queries are generated and the average query delay drops.

The Hybrid Cache and COACS algorithms attain delay of 1sec at 5 and 2sec TQG (s) respectively; in case of IQCT its maximum delay is only 0.7. Hybrid Cache algorithm produces 20% delay for 100 queries, IQCT produces only 14%. When the Delay value reduces it automatically improve the Query success ratio is depicted in Fig 2(b). Fig2(c) shows that if cache size increases the query latency will minimized because of reduced searching process in the network.

Fig 2(a): Variations in delay with respect to query generation time

Fig 2(b): Variations of Query success ratio

Fig2 (c): Variation in Query latency with respect to Cache Size

5.2 NUMBER OF HOP COUNT

The main problem that MNs face in sparse environments is the high probability of packet collisions (because of broadcasting), which reduces throughput capacity. In the below graph X-axis shows the time in seconds and Y-axis shows the Hop count value. The traditional caching technique like cache data, cache path required high number of hop count because of the broadcasting nature of multi hop communication. In IQCT hop count value is increases to certain level then suddenly reduces because of the nature of LC in QN, since the number of hops is closely related to the communication latency. When the time is 20sec the traditional caching schemes produces 2.2% of hop count, in case of IQCT hop count measure increases upto 1.6 then reduces. The reason behind this sudden reduction of Hop count is LC, because it generates the REP from its cache. Therefore our proposed IQCT scheme improves the system performance 60% by number of hop count reduction.

TIME

HOP COUNT

5

10

15

20

25

1.1

1.2

1.4

1.6

1

Table 2: shows hop count % of IQCT

Fig3: Variations in hop count with respect to Time(s)

5.3 CACHE HIT RATIO

Fig4(a) compares the cache hit ratio of Power Aware Caching (PAC) algorithm and our proposed IQCT, X-axis shows the query arrival time and Y-axis shows the cache hit ratio. Cache hit ratio as a function of the number of clients. As can be seen, the cache hit ratio of our algorithm increases as the number of client increases. It can be expressed as,

Query arrival rate α Number of clients

In the below graph 4(a), when the query arrival rate is 10sec, PAC algorithm gives the hit ratio of 0.15, but IQCT produce 0.2 i.e. 5% improvement in the starting stage itself. When it is increases into 60 our algorithm shows 30% improvement in the hit ratio. 4(b) shows that disconnect probability is indirectly proportional to hit ratio. In case of disconnection also our algorithm produce 15% better hit ratio compare to PAC algorithm.

Disconnect probability α 1

Hit ratio

Fig4 (a): Variations in cache hit ratio with respect to query arrival rate

Fig4 (b): Variations in it ratio with respect to disconnect probability

5.4 TRAFFIC RATE

The traffic is defined as the total hop count of data transmissions for retrieving data that are performed during the simulation time. When the query generation rate lower, the traffic produced by all these schemes also lower [15]. In case of no-cache scheme the maximum traffic reached to 7% and the traditional caching produces 4.5%. The traffic rate is also correlated with transmission range, when the radio communication range is very small, every method produces low traffic. This is because the number of mobile hosts connected to each other is less. For TQG 70 the IQCT scheme produces only 3% of traffic. Our proposal decreases the network traffic 20% because queries are stored in QI this property makes the system without flooding.

Fig5: Traffic variation with respect to query generation rate

5.5 LINK FAILURE RATE

When the data fails to reach the destination within the TTL period means it generates RERR message this strategy is called as link failure. In IQCT mechanism this kind of link failure reduced because of QI takes less time than TTL value to reach the destination. The LC also reduce the link failure, in case the QN goes out of transmission range an ordinary simple searching algorithm is used. In traditional caching scheme link failure is gradually increased upto 0.8% but IQCT reaches only 0.2%. When compared to traditional caching technique IQCT produce 60% less link failure

NUMBER OF

NODES

LINK FAILURE RATE (%)

Traditional caching

IQCT

5

10

15

20

50

0.1

0.2

0.3

0.4

0.8

0.0

0.01

0.02

0.05

0.2

Table3: shows the link failure rate

Fig6: Link failure rate when number of node increases

6 CONCLUSIONS

In this paper, we designed and evaluated Integrated Query based Caching Technique to efficiently support data access in ad hoc networks. Caching scheme in mobile ad hoc networks is an important issue, with each mobile device carrying only a fraction of the data. Instead of storing data or data path, we proposed that the Query Indexer stores the query without any actual data and the Local Cache to store frequently asked data. The proposed scheme can dynamically optimize performance or power based on the available resources and the performance requirements. Based on a data component concept, different techniques (indexing and caching) are applied to deal with different components of the data according to their update frequency. Simulation results showed that the proposed algorithm can cut the query delay by a factor of 2 and double the throughput compared to the traditional algorithms. To conclude this paper, this section presents some suggestions on improving our proposed schemes.

As part of our future work, we are planning to address replica allocation, cache management policies in environments where update of data items occurs.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.