Broadcast-based group invalidation: An energy-efficient cache invalidation strategy

In a wireless environment, mobile clients may cache frequently accessed data to reduce the contention on the narrow bandwidth of the wireless channel. However, to minimize energy consumption, mobile clients may also often operate in a disconnected mode. As a result, the clients may miss some cache invalidation reports broadcast by a server. Thus, upon reconnection, a cache invalidation scheme must be employed to ensure the validity of the cached data. Existing techniques either require the clients to discard the cached data entirely, or require the clients to transmit uplink messages to a server. While the former eliminates the benefits of caching, the latter may lead to high energy consumption, poor channel utilization, and costs. In this paper, we present a new cache invalidation scheme, called Broadcast-Based Group Invalidation (BGI), that retains the benefits of caching while avoiding unnecessary transmissions (which translates to energy saving, better channel utilization, and lower costs). Under BGI, a pair of invalidation reports is broadcast periodically. While the object invalidation report enables the clients to salvage as many recently cached objects as possible, the group invalidation report cuts down on false invalidation. We conduct extensive studies based on a simulation model. The simulation results show that BGI consumes less energy and is superior over existing techniques.     

在移动计算环境中基于移动代理的缓存失效方案

1 引言缓存技术是分布式计算环境中的重要技术,它可以改善系统的整体性能(如查询响应时间、吞吐量等),而移动计算的网络环境是一种特殊的分布式环境,与传统的分布式系统相比,它具有鲜明的特点:移动性、断接性、带宽多样性、可伸缩性、弱可靠性、网络通信的非对称性、电源能力局限性等等。这些特点使得缓存技术在移动计算环境中尤为重要。因为缓存能有效减少带宽需求,并能节省移动计算机的能耗。     

An evaluation of cache invalidation strategies in wirelessenvironments

Caching can reduce the bandwidth requirement in a wireless computing environment as well as minimize the energy consumption of wireless portable computers. To facilitate mobile clients in ascertaining the validity of their cache content, servers periodically broadcast cache invalidation reports that contain information of data that has been updated. However, as mobile clients may operate in a doze or even totally disconnected mode (to conserve energy), it is possible that some reports may be missed and the clients are forced to discard the entire cache content. In this paper, we reexamine the issue of designing cache invalidation strategies. We identify the basic issues in designing cache invalidation strategies. From the solutions to these issues, a large set of cache invalidation schemes can be constructed. We evaluate the performance of four representative algorithms-two of which are known algorithms (i.e., Dual-Report Cache Invalidation and Bit-Sequences) while the other two are their counterparts that exploit selective tuning (namely, Selective Dual-Report Cache Invalidation and Bit-Sequences with Bit Count). Our study shows that the two proposed schemes are not only effective in salvaging the cache content but consume significantly less energy than their counterparts. While the Selective Dual-Report Cache Invalidation scheme performs best in most cases, it is inferior to the Bit-Sequences with the Bit-Count scheme under high update rates     

A cache invalidation strategy for mobile networks

The diversity of services delivered over wireless channels has increased people's desire in ubiquitously accessing these services from their mobile devices. However, a ubiquitous mobile computing environment faces several challenges such as scarce bandwidth, limited energy resources, and frequent disconnection of the server and mobile devices. Caching frequently accessed data is an effective technique to improve the network performance because it reduces the network congestion, the query delay, and the power consumption. When caching is used, maintaining cache consistency becomes a major challenge since data items that are updated on the server should be also updated in the cache of the mobile devices. In this paper we propose a new cache invalidation scheme called Selective Adaptive Sorted (SAS) cache invalidation strategy that overcomes the false invalidation problem that exists in most of the invalidation strategies found in the literature. The performance of the proposed strategy is evaluated and compared with the selective cache invalidation strategy and the updated invalidation report startegy found in the literature. Results showed that a significant cost reduction can be obtained with the proposed strategy when measuring performance metrics such as delay, bandwidth, and energy.     

基于深度强化学习的边缘网络内容协作缓存与传输方案研究

为了应对第五代无线通信网络中数据吞吐量急剧增加的问题,移动边缘缓存成为了一种有效的解决方案。它通过在边缘设备上存储网络内容,减轻回程链路和核心网络的负担,缩短服务时延。到目前为止,大多数边缘缓存研究主要在协作内容缓存的优化方面,忽略了内容传输的效率。研究超密集网络的内容协作边缘缓存与无线带宽资源的分配问题,通过余弦相似度和高斯相似度求解基站之间总的相似度,将网络中的小基站根据总相似度进行分组,把缓存和无线带宽分配问题建模成一个长期混合整数的非线性规划问题（LT-MINLP）,进而将协作边缘缓存与带宽分配问题转变为一个带约束的马尔可夫决策过程,并利用深度确定性策略梯度DDPG模型,提出了一种基于深度强化学习的内容协作边缘缓存与带宽分配算法CBDDPG。提出的基站分组方案增加了基站之间文件共享的机会,提出的CBDDPG算法的缓存方案利用DDPG双网络机制能更好地捕捉用户的请求规律,优化缓存部署。将CBDDPG算法与三种基线算法（RBDDPG、LCCS和CB-TS）进行了对比实验,实验结果表明所提方案能够有效地提高内容缓存命中率,降低内容传递的时延,提升用户体验。     

Web caching in broadcast mobile wireless environments

Effectively exploiting available communication bandwidth and client resources is vital in wireless mobile environments. One technique for doing so is client-side data caching, which helps reduce latency and conserve network resources. The SliCache generic self-tunable cache-replacement policy addresses these issues by using intelligent slicing of the cache space and novel methods for selecting which objects to purge. Performance evaluations show that SliCache improves mobile clients' access to Web objects compared to other common policies.     

移动环境下缓存弱一致性的研究

在移动环境下，客户缓存为提高客户一服务器数据库系统的整体性能提供了有效途径。缓存与服务方数据的同步策略是缓存研究的重要内容。移动环境下，考虑到网络的带宽、开销和可靠性等因素，客户有可能允许缓存维护弱一致性，即允许缓存与服务方数据存在偏差。本文针对基于语义的缓存，给出客户限定偏差范围的方法，并且提出基于有效期的缓存同步算法。     

A mobility-aware dynamic database caching scheme for wireless mobile computing and communications

This paper describes a mobility-aware dynamic database caching scheme for wireless mobile computing and communications. A mobile-floating agent scheme is proposed, in which caching techniques are cognizant of the mobile nature of mobile users and the location-sensitive nature of mobile systems. The mobile-floating agent maintains a second class cache in the fixed network and employs Barbara's invalidation reports broadcasting cache consistency strategies to maintain a dynamic cache consistent with the first class cache in the mobile client. The invalidation reports broadcasting scheme is combined with knowledge of the mobility behavior of each individual mobile user and broadcasts of invalidation reports only occur within the user's mobility area. The evaluation results show that, for a large system (200 cells), this scheme can reduce the system cost by more than 87%, for even highly mobile users, compared with a fully replicated database system.Recommended by: Daniel Barbara, Ravi Jain and Narayanan Krishnakumar     

Improved group-based cooperative caching scheme for mobile ad hoc networks

Data caching is a popular technique that improves data accessibility in wired or wireless networks. However, in mobile ad hoc networks, improvement in access latency and cache hit ratio may diminish because of the mobility and limited cache space of mobile hosts (MHs). In this paper, an improved cooperative caching scheme called group-based cooperative caching (GCC) is proposed to generalize and enhance the performance of most group-based caching schemes. GCC allows MHs and their neighbors to form a group, and exchange a bitmap data directory periodically used for proposed algorithms, such as the process of data discovery, and cache placement and replacement. The goal is to reduce the access latency of data requests and efficiently use available caching space among MH groups. Two optimization techniques are also developed for GCC to reduce computation and communication overheads. The first technique compresses the directories using an aggregate bitmap. The second employs multi-point relays to develop a forwarding node selection scheme to reduce the number of broadcast messages inside the group. Our simulation results show that the optimized GCC yields better results than existing cooperative caching schemes in terms of cache hit ratio, access latency, and average hop count.     

基于GPRS网络的强一致性两级缓存系统框架

无线移动环境中缓存的主要目的是减少对无线带宽资源的占用和节省电池能量,然而移动无线终端的漫游与经常断开连接又给缓存内容的一致性带来了一系列新的问题。本文针对目前运行的GPRS网络,提出了在用户端（移动终端）和GPRS骨干网中添加验证服务器VS（Validation Server）对数据进行两级缓存的系统框架和缓存强一致性策略。该框架简化了无线移动环境下维护缓存一致性的复杂性,有效地降低了对无线带宽的占用和数据库服务器的负载,支持移动终端断开连接的时间任意和在一个公众陆地移动通信网PLMN网内的漫游,具有很强的实用性。     

A scalable low-latency cache invalidation strategy for mobile environments

Caching frequently accessed data items on the client side is an effective technique for improving performance in a mobile environment. Classical cache invalidation strategies are not suitable for mobile environments due to frequent disconnections and mobility of the clients. One attractive cache invalidation technique is based on invalidation reports (IRs). However, the IR-based cache invalidation solution has two major drawbacks, which have not been addressed in previous research. First, there is a long query latency associated with this solution since a client cannot answer the query until the next IR interval. Second, when the server updates a hot data item, all clients have to query the server and get the data from the server separately, which wastes a large amount of bandwidth. In this paper, we propose an IR-based cache invalidation algorithm, which can significantly reduce the query latency and efficiently utilize the broadcast bandwidth. Detailed analytical analysis and simulation experiments are carried out to evaluate the proposed methodology. Compared to previous IR-based schemes, our scheme can significantly improve the throughput and reduce the query latency, the number of uplink request, and the broadcast bandwidth requirements.     

移动计算环境中缓存失效策略的归类研究法

缓存失效报告法是在移动计算环境中普遍采用的缓存方案，即服务器定期广播缓存失效报告，该报告中包含了最近被更新的对象，根据报告内容，客户可使缓存中被更新对象失效，以保证缓存的有效性。缓存失效报告技术可采用多种策略，本文在研究多种缓存策略的基础上，提出了一种针对缓存失效方案的归类研究法，可对具体策略加以分析和评估，在此基础上对其性能进行改良，以形成更适应特定移动计算环境要求的缓存方案。     

A cache invalidation scheme for continuous partial match queries in mobile computing environments

The continuous partial match query is a partial match query whose result remains consistently in the client’s memory. Conventional cache invalidation methods for mobile clients are record ID-based. However, since the partial match query uses content-based retrieval, the conventional ID-based approaches cannot efficiently manage the cache consistency of mobile clients. In this paper, we propose a predicate-based cache invalidation scheme for continuous partial match queries in mobile computing environments. We represent the cache state of a mobile client as a predicate, and also construct a cache invalidation report (CIR), which the server broadcasts to clients for cache management, with predicates. In order to reduce the amount of information that is needed for cache management, we propose a set of methods for CIR construction (in the server) and identification of invalidated data (in the client). Through experiments, we show that the predicate-based approach is very effective for the cache management of mobile clients.     

Efficient cache invalidation schemes for mobile data accesses

This paper presents two cache invalidation schemes to maintain data consistency between the server and clients in a mobile environment. Designed according to real situations like MANET, the Adaptive Data Dividing (ADD) scheme divides data into groups of different utilization ratios and varies group broadcast intervals to reduce data access time and bandwidth consumption. The Data Validity Defining (DVD) scheme aims to solve the validity problem of cached data items, which usually happens after clients disconnect from the server. Experimental evaluations and performance analyses exhibit that the two schemes outperform most existing cache invalidation schemes in terms of data access time, cache miss ratios, query uplink ratios and bandwidth consumption.     

Adaptive caching and refreshing in mobile databases

The mobile computing environment is receiving increasing attention recently. We consider a mobile environment in which a collection of mobile clients accesses a stationary database server via a wireless channel. Due to the limited bandwidth of a wireless channel and the instability of the wireless network, caching of frequently accessed data items in a client's local storage becomes especially important for improving the performance and data availability of data access queries. In this paper, we discuss the limitations of existing caching mechanisms in a mobile environment and investigate issues that need to be addressed. We propose an adaptive caching model that could cope with the nature of a mobile environment and the low-bandwidth wireless media, supporting fast data access. We describe the adaptive cache replacement and refresh mechanisms; explain the implementation in the context of object-oriented databases; and illustrate the results of some exploratory experiments to demonstrate the feasibility of the mechanisms.     

Performance analysis of location-dependent cache invalidation schemes for mobile environments

Mobile location-dependent information services are gaining increasing interest in both academic and industrial communities. In these services, data values depend on their locations. Caching frequently accessed data on mobile clients can help save wireless bandwidth and improve system performance. However, since client location changes constantly, location-dependent data may become obsolete not only due to updates performed on data items but also because of client movements across the network. To the best of the authors' knowledge, previous work on cache invalidation issues focused on data updates only. This paper considers data inconsistency caused by client movements and proposes three location-dependent cache invalidation schemes. The performance for the proposed schemes is investigated by both analytical study and simulation experiments in a scenario where temporal- and location-dependent updates coexist. Both analytical and experimental results show that, in most cases, the proposed methods substantially outperform the NSI scheme, which drops the entire cache contents when hand-off is performed.     

命名数据网络中基于内容类型的隔跳概率缓存机制

网络化缓存是命名数据网络实现对信息的高效获取,有效降低互联网骨干网络流量的关键技术.网络化缓存将缓存作为普适的功能添加到每个网络节点.用户需要获取信息时,缓存有该内容的任意网络节点(例如路由器)接收到用户请求后都可直接向用户返回相应内容,提升用户请求响应效率.然而,命名数据网络采用泛在缓存使得内容发布者到用户的传输路径上的各节点对内容进行重复并无差别缓存,造成数据冗余、内容缓存无差别对待问题.为此,提出一种基于内容类型的隔跳概率缓存机制.首先根据业务特征(例如时延要求、带宽占用)将内容划分为4种类型:动态类、实时类、大数据类、以及小数据类;其次构造隔跳待定缓存策略,将数据存储在非连续的传输节点上,从空间上减少冗余缓存;最后针对不同内容提供差异化缓存服务:无缓存、网络边缘概率缓存、网络次边缘概率缓存、以及网络核心概率缓存策略,从而进一步降低冗余数据,同时提高用户获取内容的效率.实验结果表明,该机制能够减少冗余缓存,降低用户请求内容时延.     

A Framework for Cache Management for Mobile Databases: Design and Evaluation

In a mobile computing environment, database servers disseminate information to multiple mobile clients via wireless channels. Due to the low bandwidth and low reliability of wireless channels, it is important for a mobile client to cache its frequently accessed database items into its local storage. This improves performance of database queries and improves availability of database items for query processing during disconnection. In this paper, we investigate issues on caching granularity, coherence strategy, and replacement policy of caching mechanisms for a mobile environment utilizing point-to-point communication paradigm.We first illustrate that page-based caching is not suitable in the mobile context due to the lack of locality among database items. We propose three different levels of caching granularity: attribute caching, object caching, and hybrid caching, a hybrid approach of attribute and object caching. Next, we show that existing coherence strategies are inappropriate due to frequent disconnection in a mobile environment, and propose a cache coherence strategy, based on the update patterns of database items. Via a detail simulation model, we examine the performance of various levels of caching granularity with our cache coherence strategy. We observe, in general, that hybrid caching could achieve a better performance. Finally, we propose several cache replacement policies that can adapt to the access patterns of database items. For each given caching granularity, we discover that our replacement policies outperform conventional ones in most situations.     

Sleepers and workaholics: Caching strategies in mobile environments (Extended version)

In the mobile wireless computing environment of the future, a large number of users, equipped with low-powered palmtop machines, will query databases over wireless communication channels. Palmtop-based units will often be disconnected for prolonged periods of time, due to battery power saving measures; palmtops also will frequently relocate between different cells, and will connect to different data servers at different times. Caching of frequently accessed data items will be an important technique that will reduce contention on the narrow-bandwidth, wireless channel. However, cache individualization strategies will be severely affected by the disconnection and mobility of the clients. The server may no longer know which clients are currently residing under its cell, and which of them are currently on. We propose a taxonomy of different cache invalidation strategies, and study the impact of clients' disconnection times on their performance. We study ways to improve further the efficiency of the invalidation techniques described. We also describe how our techniques can be implemented over different network environments.