Mining block correlations to improve storage performance
Block correlations are common semantic patterns in storage systems. They can be exploited for improving the effectiveness of storage caching, prefetching, data layout, and disk scheduling. Unfortunately, information about block correlations is unavailable at the storage system level. Previous approaches for discovering file correlations in file systems do not scale well enough for discovering block correlations in storage systems.In this article, we propose two algorithms, C-Miner and C-Miner*, that use a data mining technique called frequent sequence mining to discover block correlations in storage systems. Both algorithms run reasonably fast with feasible space requirement, indicating that they are practical for dynamically inferring correlations in a storage system. C-Miner is a direct application of a frequent-sequence mining algorithm with a few modifications; compared with C-Miner, C-Miner* is redesigned for mining block correlations by making concessions for the specific problem of long sequences in storage system traces. Therefore, C-Miner* can discover 7--109% more correlation rules within 2--15 times shorter time than C-Miner. Moreover, we have also evaluated the benefits of block correlation-directed prefetching and data layout through experiments. Our results using real system workloads show that correlation-directed prefetching and data layout can reduce average I/O response time by 12--30% compared to the base case, and 7--25% compared to the commonly used sequential prefetching scheme for most workloads.

title: Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management
abstract: Reducing energy consumption is an important issue for data centers. Among the various components of a data center, storage is one of the biggest consumers of energy. Previous studies have shown that the average idle period for a server disk in a data center is very small compared to the time taken to spin down and spin up. This significantly limits the effectiveness of disk power management schemes. This paper proposes several power-aware storage cache management algorithms that provide more opportunities for the underlying disk power management schemes to save energy. More specifically, we present an off-line power-aware greedy algorithm that is more energy-efficient than Belady’s off-line algorithm (which minimizes cache misses only). We also propose an online power-aware cache replacement algorithm. Our trace-driven simulations show that, compared to LRU, our algorithm saves 16% more disk energy and provides 50% better average response time for OLTP I/O workloads. We have also investigated the effects of four storage cache write policies on disk energy consumption.

title: Performance-directed energy management for storage systems
abstract: Energy consumption has become an important issue in the design of battery-operated mobile devices and sophisticated data centers. The storage hierarchy, which includes memory and disks, is a major energy consumer in such systems; especially for high-end servers at data centers. Much work has focused on energy control algorithms for storage systems that transition a device into a low power mode when a certain usage function exceeds a specified threshold. These algorithms are difficult to use in real systems, however, because designers must painstakingly and manually tune threshold values, and even then a performance guarantee is difficult. To address these limitations, we develop three algorithms: 1) a performance guarantee technique that designers can use with any underlying energy-control algorithm 2) a performance-directed control algorithm that periodically assigns a static configuration to different devices by solving an optimization problem 3) another performance-directed control algorithm that dynamically self-tunes according to an optimal set of thresholds

title: The impact of topology on overlay routing service
abstract: A moderate amount of recent work has been dedicated to using overlay network to support value-added network service, such as overlay multicast, OverQoS, etc. Overlay service network is a generic service framework which is designed to provide a variety of services to overlay service customers. To design an overlay service network, the first step is to choose an overlay topology connecting all the overlay service nodes. For example, RON [Anderson, DG et al., 2001] has used full mesh topology connecting all the nodes. In this paper, we did a study on the impact of topology on the overlay routing service. We found that the overlay topology has significant impact on the overlay routing in terms of routing performance and routing overhead. For example, the full mesh topology does not always give us the best performance. Moreover, the physical topology information can benefit us a lot to construct an efficient overlay topology. In addition, some alternative topologies can provide us with better performance when considering both the routing performance and overhead.

title: Efficient and distributed computation of maximum multicast rates
abstract: The transmission of information within a data network is constrained by network topology and link capacities. In this paper, we study the fundamental upper bound of information multicast rates with these constraints, given the unique replicable and encodable property of information flows. Based on recent information theory advances in coded multicast rates, we are able to formulate the maximum multicast rate problem as a linear network optimization problem, assuming the general undirected network model. We then proceed to apply Lagrangian relaxation techniques to obtain (1) a necessary and sufficient condition for multicast rate feasibility, and (2) a subgradient solution for computing the maximum rate and the optimal routing strategy to achieve it. The condition we give is a generalization of the well-known conditions for the unicast and broadcast cases. Our subgradient solution takes advantage of the underlying network flow structure of the problem, and therefore outperforms general linear programming solving techniques. It also admits a natural intuitive interpretation, and is amenable to fully distributed implementations.

title: WICCAP: from semi-structured data to structured data
abstract: Web data extraction is a technique for extracting and integrating data from Web based semistructured data. Wrappers function like the kernel of Web data extraction systems providing information mediator between users and a large number of heterogeneous data sources. Typically, they process semistructured documents generated from structured databases based on rules that are usually hidden to users. Much research has been done to use various methods to represent the knowledge of hidden rules and exploit techniques such as grammar induction, inductive logic programming, etc., to discover these rules that can be used by wrappers to extract data. An important property of semistructured data is its hierarchical structure. Intuitively, we can devise a method that can use this structure information to generate wrappers. We describe a Web data extraction system - WICCAP and its internal Web Data Extraction Language (WDEL) that provides unified view of Web data resources and extracted data. We describe some rule generation features of WICCAP and provide detailed description of the internal language and its implementation. We have conducted experiments to show the ease on generating wrappers with this approach.

title: Impact of data compression on energy consumption of wireless-networked handheld devices
abstract: We investigate the use of data compression to reduce the battery consumed by handheld devices when downloading data from proxy servers over a wireless LAN. To make a careful trade-off between the communication energy and the overhead to perform decompression, we experiment with three universal lossless compression schemes, using a popular handheld device in a wireless LAN environment and we find interesting facts. The results show that, from the battery-saving perspective, the gzip compression software (based on LZ77) to be far superior to bzip2 (based on BWT) and compress (based on LZW). We then present an energy model to estimate the energy consumption for the compressed downloading. With this model, we further reduce the energy cost of gzip by interleaving communication with computation and by using a block-by-block selective scheme based on the compression factor of each block. We also use a threshold file size below which the file is not to be compressed before transferring.

title: Applying array contraction to a sequence of DOALL loops
abstract: Efficient program execution on multiprocessor computers requires both sufficient parallelism and good data locality. Recent research found that, using a combination of loop shifting, loop fusion, and array contraction, one can reduce the memory required to execute a sequence of serial loops, thereby to improve the cache locality. This paper studies how to extend such a memory-reduction scheme to a sequence of DOALL loops, which are executed in parallel on multiprocessors. Two methods are proposed to overcome difficulties caused by loop-carried dependences. Data copy-in is performed to remove anti-dependences between different parallel threads, and computation duplication is performed to remove flow dependences. Experiments performed on a number of benchmark programs show that the proposed technique improves both cache locality and parallel execution speed for the DOALL loops. The scheme achieves an average speedup of 1.41 for 17 programs on a 4-processor SUN machine.