CACHE MANAGEMENT IN MOBILE COMPUTING ENVIRONMENT

Abstract

Mobile computing is the merger of recent phenomenal advances in computing and wireless communication technologies, and enables users to access information without the constraints of being connected to a fixed network. Mobile users need to receive timely and accurate information in order to make critical decisions (e.g., stock market information, trading, etc.). We can envision the scenario of the near future where mobile data access will be readily available to the user from anywhere at anytime. However, various constraints of mobile computing environments, such as narrow bandwidth of wireless communication channels and severe resource constraints of mobile devices add a new dimension to the technical challenges before this vision becomes a reality. Thus, sophisticated data management and resource management techniques are needed to enhance the performance of mobile data access. The work presented in this thesis is an effort to addresses these issues by proposing new and efficient cache management schemes for single and multi hop mobile computing environments. First part of the thesis addresses the cache invalidation issue in single hop based mobile environment, where mobile clients access data through a mobile support station that is one hop away. We propose a Update Report (UR) based synchronous stateful caching strategy that reduces the query latency, improves the cache hit ratio, minimizes the client disconnection and failure overheads, makes better utilization of wireless channel, supports client mobility from one cell to another, and conserves the client energy. Mobile client resources arc exploited by maintaining the cache in nonvolatile memory such as flash disk, thereby reducing the need to obtain data from the server. The strategy ensures that cached item at a mobile client has same value as on the original server so that no obsolete data would be used to serve the queries. It utilizes the knowledge ofdata access frequency for scheduling and periodically broadcasts the invalidation messages which results in minimization ofuplink requests and downlink broadcasts. To reduce the query latency, the recently requested data items are broadcasted after the invalidation message. Minimization ofquery latency leads to communication cost savings and hence better bandwidth usage and energy saving. By exploiting the feature of stateful caching approach, the strategy filters out non-cached items from the invalidation message thus reducing the message size which results in reduction of overhead over the wireless channel, query latency and client tuning time. Selective tuning is used to further conserve the client ballcry energy. Simulation results show that UR strategy yields better performance than existing cache invalidation strategies. It is shown by our results that client disconnections impede the caching performance, and the proposed disconnection handling algorithm significantly outperforms over other schemes and is particularly effective in handling long disconnections. The unpredictable mobility of the client adds a great deal ofcomplexity to the cache invalidation problem. Our strategy is also capable to maintain consistent local cache for data accessed from remote server while a client is on the move. The second part of the thesis presents a cache replacement strategy, called Rule based Least Profit Value (R-LPV). R-LPV makes eviction decision sensitive to various performance factors ofan item including update frequency, retrieval delay from the server, cache invalidation delay and data size. In addition, it considers relation of an item to be replaced to the cache set. It has been observed that data items queried during aperiod of time are related to each other and therefore replacement ofadata item which is strongly associated to the cache set may lead to series ofmisses during client's subsequent requests. Association rule based data mining is applied to find the relationship among data items. To further boost the caching performance, we devise an innovative algorithm, called Prefetching based on Prefetch Set (PPS), where the generated association rules are used to prefetch the data items that are most likely to be accessed in the near future. Moreover, unlike existing works, we also present an integrated technique that exploits R-LPV for cache replacement, and PPS during prefetching under UR based cache invalidation. Simulation experiments show a considerable improvement in various performance metrics by our algorithms as compared to their existing counterparts. The third and fourth parts of the thesis consider the cooperative caching problem in multi hop based mobile environment. We propose two caching schemes, namely Zone Cooperative (ZC) and Cluster Cooperative (CC) for multi hop mobile environment. When there is no pre-installed mobile support station, mobile clients may form a multi hop based Mobile Ad hoc NETwork (MANET) and forward packets for each other. As mobile clients in MANETs may have similar tasks and share common iiiterest, the proposed strategies enhance 111 the data access performance because they allow sharing and coordination of cached data among multiple clients. These schemes are able to improve data availability and reduce query latency without incurring high overhead. In ZC scheme, one hop neighbors of a mobile client form a cooperative cache zone since the cost for communication with them is low both in terms of energy consumption and message exchange. As a part of cache management, cache admission control and utility based replacement policy are developed to improve the data accessibility and reduce the local cache miss ratio. An analytical study of ZC based on data popularity, client density and transmission range is also performed. CC scheme exploits clustering for efficient cooperative caching in MANETs where the network topology is partitioned into non-overlapping clusters based on the physical network proximity. To enhance the system performance, within a cluster, individual caches interact with each other such that combined result is a larger cumulative cache. To further improve the access efficiency in CC, a cache replacement policy, called Least Utility Value with Migration (LUV-Mi) is also developed. The performance of the proposed caching strategies is evaluated through simulation experiments. The results show that ZC and CC caching mechanisms achieve significant improvements in comparison with existing strategies. Fifth part of the thesis introduces the concept of caching in emerging heterogeneous mobile environment. Present wireless technology is now enabling mobile clients not only to have multi hop communication among clients themselves, but also to have direct connection with an Access Point (AP) as well as, thus bringing the heterogeneous technologies to reality. We call such an environment as Cooperation based Access Point MANET (CAPMANET). A Hop Oriented Cooperative Caching (HOCC) scheme for CAPMANET has been proposed which helps in reducing the communication overhead and the query latency. HOCC employs a hybrid Pull with Push (PwP) mechanism to maintain data consistency. The caching scheme considers data popularity, size, consistency and distance during replacement to optimize cache content at clients. Simulation results demonstrate that HOCC outperforms the pure push and pure pull based strategies. Lastly, the contribution made in the dissertation is summarized and scope for future work is outlined.