Research On Consistency Maintenance In Cooperative Caching In MANETs

With the development of Internet technologies, isolated personal computers are connected. Users throughout the world can now easily communicate with each other, and it becomes quite convenient to publish and access information via Internet. The Internet has deeply changed our daily life, which makes it an urgent task to provide pervasive Internet access, i.e., to enable the users to access useful Internet resources anytime anywhere. As wireless communication and mobile embedded devices manufactory technologies mature, Mobile Ad hoc Networks (MANETs) can provide essential support for pervasive Internet access. The key issue in supporting pervasive Internet access is to enable efficient data dissemination and sharing among mobile users in MANETs. Cooperative caching has emerged as a primary technique to support efficient data dissemination and sharing. In order to ensure valid data access, the cache consistency must be maintained properly. Although there have been many existing works on cache consistency maintenance in wired networks and infrastructure-based mobile networks, it has not been sufficiently studied how to efficiently maintain cache consistency in MANETs. The resource (e.g., bandwidth, battery power etc.) and mobility constraints have made it a challenging task to maintain cache consistency in MANETs.In this paper, we work on the issues of cache consistency maintenance in cooperative caching in MANETs. We first propose a new consistency model called Probabilistic Delta Consistency (PDC). In the PDC model, users can specify their consistency requirements in two orthogonal dimensions, namely the deviation (in time, value and etc.) and the ratio of queries gaining the specified consistency. The PDC model enables the users to specify their consistency requirements with great flexibility. Thus, the users can efficiently make tradeoffs between cache consistency and the cost incurred. The PDC model also has great generality. It coves all widely-studied consistency models as its special cases.Then, we propose a three-dimensional framework for designing cache consistency maintenance algorithms. In each dimension of the framework, we address one key issue in design of cache consistency maintenance algorithms. We first work on the issue of consistency control initiation. As we know, basic consistency maintenance schemes include push and pull. The scheduling of push and pull not only decides whether users' consistency requirements can be satisfied, but also decides whether the consistency maintenance cost incurred is appropriate. However, in a MANET environment, the issue of consistency control initiation has not been sufficiently studied. Thus, we propose the Predictive Cache Consistency algorithm and the Flexible Combination of Push and Pull algorithm to efficiently decide the initiation of cache consistency maintenance in MANETs. After the initiation of consistency control has been decided, it becomes a critical issue how to efficiently propagate the data updates. The multi-hop communication, the mobility and the resource constraints make this issue even more challenging in MANETs. To this end, we propose the Hierarchical Data Update Propagation (HDUP) algorithm. The HDUP algorithm constructs a hierarchical overlay network among the data source node and the caching nodes in MANETs. Data updates are efficiently propagated in the overlay based on the cooperation among the data source node and the caching nodes.In the literature, the consistency maintenance algorithms can be divided into two main categories: stateful and stateless. Stateless algorithms impose great traffic overhead since it mainly relies on flooding to propagate the data updates. Stateful algorithms are comparatively more cost-effective since it selectively propagates the data updates to the caching nodes which are in great need of the updates. Most existing works designed for the infrastructure-based mobile networks employ stateless cache consistency maintenance algorithms. However, the stateless consistency maintenance algorithms are not efficient in MANETs, since the flooding of data updates will impose inhibitive overhead. Hence, we propose the stateful Greedy Walk-based Selective Push (GWSP) algorithm. In GWSP, the data source node efficiently chooses the cache copies which should receive the data updates, based on the status of each cache copy it maintains.In order to evaluate the cache consistency maintenance algorithms proposed, we developed the prototype system P2PSim. The design and implementation of P2PSim are discussed in detail. In P2PSim, the cache consistency maintenance algorithms we propose are all implemented. We also implement some existing works for the sake of performance comparison. P2PSim is implemented in standard C++ and the Standard Template Library.