BANDWIDTH AWARE CACHE INVALIDATION IN ERROR PRONE WIRELESS MOBILE ENVIRONMENTS

Abstract

Caching of data is frequently used by clients to decrease the query response time, conserve the scarce bandwidth and processing power of the server. Cache invalidation is the mechanism by which the clients get informed about the validity of the data present in their cache. For wireless mobile environments, the IR—UIR based approach for cache invalidation is an attractive solution to reduce the query delay when data gets updated frequently at the server. However, it achieves this by increasing the frequency of replication resulting in consumption of large amount of bandwidth. Bit Sequencing approach proposed to address the problem of long disconnection and bandwidth problems cannot be used in this scenario as even a single bit error would 'collapse the entire hierarchy and also the UIR's are too short reports which contain very less data items. In this report we have proposed four techniques for cache invalidation which can be used even in erroneous environments. We used hashing to divide the data items into different groups called buckets. By using the hash key of a bucket the data items in that bucket are represented using less number of bits than is actually required. Since data items are to be accompanied by the time at which they are modified, we reduce the number of bits required to represent time by using the amount of time elapsed since the data item is modified. More levels of hashing are used to reduce the number of packets generated for broadcasting the invalidation report. As the invalidated data items might not be equally distributed to all the buckets we propose another method where buckets might be of unequal sizes. The proposed method is less vulnerable to errors as we broadcast the invalidation information in separate packets for each group. Detailed simulation experiments are carried out to evaluate the proposed methodology. Compared to the previous methods our solution not only requires less bandwidth but also performs well in erroneous environments. Simulation study is carried out on Windows XP environment on a 700MHZ Celeron processor. The language used for simulation is C++. iii