A concurrency control scheme for mobile transactions in broadcast disk environments

Broadcast disk technique has been often used to disseminate frequently requested data efficiently to a large volume of mobile clients over wireless channels. In broadcast disk environments, a server often broadcasts different data items with differing frequencies to reflect the skewed data access patterns of mobile clients. Previously proposed concurrency control methods for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. These protocols perform poorly in broadcast disk environments where the data access patterns of mobile transactions are skewed. In broadcast disk environments, the time length of a broadcast cycle usually becomes large to reflect the skewed data access patterns. This will often cause read-only transactions to access old data items rather than the latest data items. Furthermore, updating mobile transactions will be frequently aborted and restarted in the final validation stage due to the update conflict of the same data items with high access frequencies. This problem will increase the average response time of the update mobile transactions and waste the uplink communication bandwidth. In this paper, we extend the existing FBOCC concurrency control method to efficiently handle mobile transactions with skewed data access patterns in broadcast disk environments. Our method allows read-only transactions to access the more updated data, and reduces the average response time of updating transactions through early aborts and restarts. Our method also reduces the amount of uplink communication bandwidth for the final validation of the update transactions. We present an in-depth experimental analysis of our method by comparing with existing concurrency control protocols. Our performance analysis shows that it significantly decreases the average response time and the amount of uplink bandwidths over existing methods.     

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.     

Performance evaluation of an optimal cache replacement policy for wireless data dissemination

Data caching at mobile clients is an important technique for improving the performance of wireless data dissemination systems. However, variable data sizes, data updates, limited client resources, and frequent client disconnections make cache management a challenge. We propose a gain-based cache replacement policy, Min-SAUD, for wireless data dissemination when cache consistency must be enforced before a cached item is used. Min-SAUD considers several factors that affect cache performance, namely, access probability, update frequency, data size, retrieval delay, and cache validation cost. The paper employs stretch as the major performance metric since it accounts for the data service time and, thus, is fair when items have different sizes. We prove that Min-SAUD achieves optimal stretch under some standard assumptions. Moreover, a series of simulation experiments have been conducted to thoroughly evaluate the performance of Min-SAUD under various system configurations. The simulation results show that, in most cases, the Min-SAUD replacement policy substantially outperforms two existing policies, namely, LRU and SAIU.     

Tree-based data retrieval algorithm for multi-item request with deadline in wireless networks

The data retrieval problem in wireless communication has attracted increasing attentions in many applications such as electronic information sharing and e-business. However, most existing studies do not consider how to retrieve the requested data items in their deadlines. In this paper, we discuss the so-called deadline-based multi-item data retrieval problem, which aims at finding an access pattern for retrieving requested data items in certain deadlines such that the access latency and data miss rate are minimized. We propose two algorithms, named EDFS and UR, to deal with the above problem. The EDFS algorithm gives priority to retrieve the requested data item with the least deadline, while the UR algorithm introduces the urgent rate that is computed by the broadcast time and deadline of requested data item for further reducing the access latency and data miss ratio. Moreover, we design a tree-based data retrieval algorithm that finds the longest downloading sequence of data items in one broadcast cycle and is applied to EDFS and UR for finding data retrieval sequence of requested data items. The efficiency of our proposed schemes has been validated by the extensive experiments.     

An energy-efficient mobile transaction processing method using random back-off in wireless broadcast environments

Broadcast is widely accepted as an efficient technique for disseminating data to a large number of mobile clients over a single or multiple channels. Due to the limited uplink bandwidth from mobile clients to server, conventional concurrency control methods cannot be directly applied. There has been many researches on concurrency control methods for wireless broadcast environments. However, they are mostly for read-only transactions or do not consider exploiting cache. They also suffer from the repetitive aborts and restarts of mobile transactions when the access patterns of mobile transactions are skewed. In this paper, we propose a new optimistic concurrency control method suitable for mobile broadcast environments. To prevent the repetitive aborts and restarts of mobile transactions, we propose a random back-off technique. To exploit the cache on mobile clients, our method keeps the read data set of mobile transactions and prefetches those data items when the mobile transactions are restarted. As other existing optimistic concurrency control methods for mobile broadcast environments does, it works for both read-only and update transactions. Read-only transactions are validated and locally committed without using any uplink bandwidth. Update transactions are validated with forward and backward validation, and committed after final validation consuming a small amount of uplink bandwidth. Our performance analysis shows that it significantly decreases uplink and downlink bandwidth usage compared to other existing methods.     

A bandwidth and effective hit optimal cache scheme for wireless data access networks with client injected updates

In this paper, we propose an optimal cache replacement policy for data access applications in wireless networks where data updates are injected from all the clients. The goal of the policy is to increase effective hits in the client caches and in turn, make efficient use of the network bandwidth in wireless environment. To serve the applications with the most updated data, we also propose two enhanced cache access policies making copies of data objects strongly consistent. We analytically prove that a cache system, with a combination of our cache access and replacement policy, guarantees the optimal number of effective cache hits and optimal cost (in terms of network bandwidth) per data object access. Results from both analysis and extensive simulations demonstrate that the proposed policies outperform the popular Least Frequently Used (LFU) scheme in terms of both effective hits and bandwidth consumption. Our flexible system model makes the proposed policies equally applicable to applications for the existing 3G, as well as upcoming LTE, LTE Advanced and WiMAX wireless data access networks.     

Exploiting the performance gains of modern disk drives by enhancing data locality

Due to the widening performance gap between RAM and disk drives, a large number of I/O optimization methods have been proposed and designed to alleviate the impact of this gap. One of the most effective approaches of improving disk access performance is enhancing data locality. This is because the method could increase the hit ratio of disk cache and reduce the seek time and rotational latency. Disk drives have experienced dramatic development since the first disk drive was announced in 1956. This paper investigates some important characteristics of modern disk drives. Based on the characteristics and the observation that data access on disk drives is highly skewed, the frequently accessed data blocks and the correlated data blocks are clustered into objects and moved to the outer zones of a modern disk drive. The idea attempts to enhance spatial locality, improve the efficiency of aggressive sequential prefetch, and take advantage of Zoned Bit Recording (ZBR). An experimental simulation is employed to investigate the performance gains generated by the enhanced data locality. The performance gains are analyzed by breaking down the disk access time into seek time, rotational latency, data transfer time, and hit ratio of the disk cache. Experimental results provide useful insights into the performance behaviours of a modern disk drive with enhanced data locality.     

An energy-efficient and access latency optimized indexing scheme for wireless data broadcast

Data broadcast is an attractive data dissemination method in mobile environments. To improve energy efficiency, existing air indexing schemes for data broadcast have focused on reducing tuning time only, i.e., the duration that a mobile client stays active in data accesses. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. This paper proposes an energy-efficient indexing scheme called MHash that optimizes tuning time and access latency in an integrated fashion. MHash reduces tuning time by means of hash-based indexing and enables nonflat data broadcast to reduce access latency. The design of hash function and the optimization of bandwidth allocation are investigated in depth to refine MHash. Experimental results show that, under skewed access distribution, MHash outperforms state-of-the-art air indexing schemes and achieves access latency close to optimal broadcast scheduling.     

Scalable cache invalidation algorithms for mobile data access

In this paper, we address the problem of cache invalidation in mobile and wireless client/server environments. We present cache invalidation techniques that can scale not only to a large number of mobile clients, but also to a large number of data items that can be cached in the mobile clients. We propose two scalable algorithms: the Multidimensional Bit-Sequence (MD-BS) algorithm and the Multilevel Bit-Sequence (ML-BS) algorithm. Both algorithms are based on our prior work on the Basic Bit-Sequences (BS) algorithm. Our study shows that the proposed algorithms are effective for a large number of cached data items with low update rates. The study also illustrates that the algorithms ran be used with other complementary techniques to address the problem of cache invalidation for data items with varied update and access rates.     

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.     

Exploiting skewed access and energy-efficient algorithm to improve the performance of wireless data broadcasting

As wireless networks become an integral component of the current communication infrastructure, energy efficiency is a crucial design consideration because of the limited battery life of mobile terminals. Data broadcast is an effective data dissemination method in mobile environments. The current air indexing schemes for data broadcast focused on energy efficiency (reducing tuning time) only, and current broadcast scheduling schemes reduce access latency through nonflat data broadcast to improve only responsiveness. Few studies have addressed energy efficiency and responsiveness issues concurrently. This study proposes a fast data access scheme that concurrently supports the energy saving protocol, which constructs broadcast channels according to the access frequency of each type of message to improve energy efficiency in mobile devices. The windmill scheduling algorithm that is presented in this paper was used to organize all types of messages in the broadcast channel in the most symmetrical distribution, to reduce tuning and access time. The performance of the proposed mechanism was analyzed, and the efficiency improvement over existing methods was demonstrated numerically. Results indicate that the proposed mechanism is capable of improving both tuning and access time because of the presence of skewness in the access distribution among disseminated messages.     

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.     

Power-aware data retrieval protocols for indexed broadcast parallel channels

In pervasive and mobile computing environments, “timely and reliable” access to public data requires methods that allow quick, efficient, and low-power access to information to overcome technological limitations of wireless communication and access devices. The literature suggests broadcasting (one-way communication) as an effective way to disseminate the public data to mobile devices. Within the scope of broadcasting, the response time and energy consumption of retrieval methods have been used as the performance metrics for measuring the effectiveness of different access methods. The hardware and architecture of the mobile units offer different operational modes that consume different energy levels. Along with these architectural and hardware enhancements, techniques such as indexing, broadcasting along parallel channels, and efficient allocation and retrieval protocols can be used to minimize power consumption and access latency.In general, the retrieval methods attempt to determine the optimal access pattern for retrieving the requested data objects on parallel broadcast channels. The employment of heuristics provides a methodology for such ideal path planning solutions. Using informative heuristics and intelligent searches of an access forest can provide a prioritized cost evaluation of access patterns for requested data objects and, hence, an optimal path for the access of requested data on broadcast air channels.This paper examines two scheduling methods that along with a set of heuristics generate and facilitate the access patterns for retrieving data objects in the presence of conflicts in an indexed parallel broadcast channel environment. A simulation of the proposed schemes is presented for analyzing the relationship between response time and power consumption.     

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.     

非对称网络环境中数据广播的启发式多盘调度算法

在以无线网络为代表的非对称网络环境中,数据广播是一种有效的数据访问方式。针对非均匀的访问概率分布,我们分析了数据广播访问时间的最优值,并提出了一种启发式多盘调度算法（ＨＭＤ）,该算法能够根据给定的数据项访问概率分布,自动生成广播调度。 欠的理论分析和实验结果表明,ＨＭＤ算法是一种高效的数据广播调度算法,具有接近于理论最优值的性能,并且具有良好的可操作性。     

An update-based step-wise optimal cache replacement for wireless data access

Many network applications requires access to most up-to-date information. An update event makes the corresponding cached data item obsolete, and cache hits due to obsolete data items become simply useless to those applications. Frequently accessed but infrequently updated data items should get higher preference while caching, and infrequently accessed but frequently updated items should have lower preference. Such items may not be cached at all or should be evicted from the cache to accommodate items with higher preference. In wireless networks, remote data access is typically more expensive than in wired networks. Hence, an efficient caching scheme considers both data access and update patterns can better reduce data transmissions in wireless networks. In this paper, we propose a step-wise optimal update-based replacement policy, called the Update-based Step-wise Optimal (USO) policy, for wireless data networks to optimize transmission cost by increasing effective hit ratio. Our cache replacement policy is based on the idea of giving preference to frequently accessed but infrequently updated data, and is supported by an analytical model with quantitative analysis. We also present results from our extensive simulations. We demonstrate that (1) the analytical model is validated by the simulation results and (2) the proposed scheme outperforms the Least Frequently Used (LFU) scheme in terms of effective hit ratio and communication cost.     

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.     

Disseminating dependent data in wireless broadcast environments

In wireless mobile environments, data broadcasting is an effective approach to disseminate information to mobile clients. In some applications, the access pattern of all the data can be represented by a weighted DAG. In this paper, we explore how to efficiently generate the broadcast schedule in a wireless environment for the data set having a weighted DAG access pattern. Such a broadcast schedule not only minimizes the access latency but also is a topological ordering of the DAG. Minimized access latency ensures the quality of service (QoS). We prove that it is NP-hard to find an optimal broadcast schedule and provide some heuristics. After giving an analysis for these heuristics on the latency and complexity, we implement all the proposed heuristics to compare their performance. Recommended by: Sunil Prabhakar     

An efficient nonuniform index in the wireless broadcast environments

Data broadcast is an efficient dissemination method to deliver information to mobile clients through the wireless channel. It allows a huge number of the mobile clients simultaneously access data in the wireless environments. In real-life applications, more popular data may be frequently accessed by clients than less popular ones. Under such scenarios, Acharya et al.’s Broadcast Disks algorithm (BD) allocates more popular data appeared more times in a broadcast period than less popular ones, i.e., the nonuniform broadcast, and provides a good performance on reducing client waiting time. However, mobile devices should constantly tune in to the wireless broadcast channel to examine data, consuming a lot of energy. Using index technologies on the broadcast file can reduce a lot of energy consumption of the mobile devices without significantly increasing client waiting time. In this paper, we propose an efficient nonuniform index called the skewed index, SI, over BD. The proposed algorithm builds an index tree according to skewed access patterns of clients, and allocates index nodes for the popular data more times than those for the less popular ones in a broadcast cycle. From our experimental study, we have shown that our proposed algorithm outperforms the flexible index and the flexible distributed index.     

断接下查询的缓存处理

移动环境下，由于无线网络可靠性低、费用高，移动主机本身受电源、资源等方面的限制，移动主机经常会主动或被动地处于断接，即没有网络连接的状态．为了提高断接时移动客户对数据的访问能力，有效利用移动缓存，该文提出断接下基于语义缓存的查询处理QPID算法．该算法的主要思路是先找出缓存中与当前查询相关的缓存项，再通过对相关项数据的进一步处理获得缓存中满足查询的结果．试验表明，基于QPID算法的查询处理可以更好地满足断接下客户的查询请求．