20-07-2012, 01:10 PM
CACHE INVALIDATION SCHEME FOR MOBILE COMPUTING SYSTEMS WITH REAL-TIME DATA
1CACHE INVALIDATION SCHEME.doc (Size: 472 KB / Downloads: 25)
Abstract
In this paper, we propose a cache invalidation scheme called Invalidation by Absolute Validity Interval (IAVI) for mobile computing systems. In IAVI, we define an absolute validity interval (AVI), for each data item based on its dynamic property such as the update interval. A mobile client can verify the validity of a cached item by comparing the last update time and its AVI. A cached item is invalidated if the current time is greater than the last update time plus its AVI. With this self-invalidation mechanism, the IAVI scheme uses the invalidation report to inform the mobile clients about changes in AVIs rather than the update event of the data items. As a result, the size of the invalidation report can be reduced significantly. Through extensive simulation experiments, we have found that the performance of the IVAI scheme is significantly better than other methods such as bit sequence and timestamp.
Introduction
Recent advances in mobile communication technology have greatly increased the functionality of mobile information services. An important application of mobile computing systems is to provide various types of real-time information such as stock quotes, weather conditions and traffic information, to mobile clients [SLR99]. A number of efficient data dissemination strategies have been proposed in recent years. Amongst the proposed methods, most are based on data broadcast as it is very cost effective in disseminating a substantial amount of information to a large number of mobile clients [AAFZ95, DCKV97].
Related Work
Caching frequently accessed data items on the client side has been recognised as an important technique to reduce access delay and network traffic in a limited bandwidth mobile environment. Barbara and Imielinski, in one of the earliest work in this area, proposed three different variants of this approach Broadcasting Timestamp (TS), Amnesic Terminals (AT) and Signatures (SIG) depending on the expected duration of network disconnection [BI94]. However, the algorithms are only effective if the clients have not been disconnected for a period exceeding an algorithm specific parameter. Otherwise the entire cache has be to be discarded even though some of the cached data items might still be valid.
Jing et. al. proposed a bit-sequence scheme (BS) in
which the invalidation report consists of bit sequences associated with a set of timestamps [JEHL95]. Using the information embedded in the bit sequences, a client needs only to invalidate its entire cache if more than half of the data items have been updated in the server since its last invalidation time.
Absolute Validity Interval (AVI)
An important characteristic of the data items in a mobile computing system is that they possess different degrees of real-time properties, e.g., they often represent the current status of the objects in the external environment, whose value may change quite rapidly [SLR99]. Examples include news updates and the latest market prices of stocks. Due to the real-time properties of the data items, updates, which are captured by some external devices or obtained from data vendors, are required to maintain the validity of the data values. Usually, stale (invalid) data values are much less useful.
Basically, there are two types of update arrival
patterns: periodic and sporadic. For example, the arrival of the most current price of a stock is sporadic. For some data items, it may not be necessary to track all the changes in values. It might be sufficient to only sample the changes to the status of the actual objects periodically (an example is road traffic conditions).
Performance Study
We have compare d the performance of IAVI with two efficient schemes, Bit-Sequence (BS) [JEHL95] and Timestamp (TS) [BI94]. Furthermore, an idealized cache invalidation scheme called Perfect Server (PS) is also developed for comparison purposes. In PS, it is assumed that the system has full knowledge of the content of all the mobile clients ’ caches . As a result , the invalidation report s generated by PS will only contain the update information of the data items cached in the mobile client’s caches, thus, releasing more broadcast bandwidth for data dissemination. Such a scheme would be too costly to implement in real-life as it requires the generation of updates regarding the content of mobile client caches continuously to the mobile server.
Conclusions
In a mobile computing environment, mobile clients are usually equipped with local cache for reducing latency in data accesses. However, the frequent disconnection of mobile clients from the network and updates occurring at the mobile server introduces the problem of cache incoherence. Several cache invalidation schemes, such as Timestamps and Bit- sequence have been proposed to maintain cache coherence efficiently. The former sends out detailed update records within the predefined window frame to its client for cache invalidation while the latter organizes and records the update records in a report whose size depends on the database size.