The growing adoption of prediction serving systems (PSSes) has made cost-saving deployment on preemptible spot instances crucial, yet frequent preemptions severely harm availability. While coded computation (CC) can keep availability cost-effectively by encoding original jobs into parity ones, its direct application to spot instances incurs prohibitive decoding overhead and tail latency under frequent preemptions. We identify two findings for optimization: (i) decoding asymmetry (only original job failures require decoding); (ii) preemption unevenness (variation in preemption rates across cloud regions). Leveraging these findings, we propose SpotCC, a new CC framework that strategically dispatches parity jobs to high-preemption (volatile) regions and original jobs to low-preemption (stable) regions. SpotCC designs locality-based and fine-grained volatility identification to reduce decoding operations and mitigate job congestion, respectively, and adaptively tunes configurations for decoding minimization. Experiments show that SpotCC improves P99 latency by 83.9% over state-of-the-arts, while maintaining ultra-low monetary costs.

Minimum-storage regenerating (MSR) codes are provably optimal erasure codes that minimize the repair bandwidth (i.e., the amount of traffic being transferred during a repair operation), while minimizing storage redundancy, in distributed storage systems. However, the practical repair performance of MSR codes still has significant room for improvements, as their mathematical structure makes repair operations difficult to parallelize. In this article, we present HyperParaRC, a parallel repair framework for MSR codes. HyperParaRC leverages the sub-packetization nature of MSR codes to parallelize the repair of sub-blocks and balance repair load (i.e., the amount of traffic sent or received by a node) across available nodes. We first demonstrate that there exists a trade-off between repair bandwidth and maximum repair load. We then propose an affinity-based heuristic for HyperParaRC, which approximately minimizes the maximum repair load by examining the bandwidth incurred during sub-block computations and significantly reduces the search time for large coding parameters compared with our earlier work, ParaRC. Based on our affinity-based heuristic, we further design a full-node recovery mechanism for HyperParaRC that combines both intra-stripe and inter-stripe parallel repair scheduling to repair multiple lost blocks in a failed node. We prototype HyperParaRC on Hadoop HDFS and evaluate it on Alibaba Cloud. Our evaluation results show that HyperParaRC reduces both single-block repair and full-node recovery times compared with state-of-the-art repair approaches.

To improve storage efficiency in large-scale clustered storage systems, deduplication that removes duplicate chunks has been widely deployed in distributed ways. Many distributed deduplication-related studies focus on backup storage, and some recent studies focus on deploying deduplication in clustered primary storage systems which store active data. While fragmentation is one of the traditional challenges in backup deduplication, we observe that a new fragmentation problem arises when performing deduplication in the clustered primary storage system due to the system's concurrent file writes. However, we find that existing state-of-the-art methods that address traditional fragmentation in backup deduplication fail to work effectively for the new fragmentation problem, as they significantly incur additional redundancy or lower the deduplication ratio. In this paper, we revisit fragmentation-solving methods in memory management and our main idea is inspired by the classic garbage collection methods in memory management: relocating fragments consecutively. Based on the idea, we propose an effective deduplication mechanism for clustered primary storage systems, ReoDedup, which applies: i) a cosine-similarity based chunk relocating algorithm that aims to minimize the fragmentation; ii) an adjacency-table based relocating heuristic that reduces the relocating's time complexity by placing two chunks residing in the same file consecutively; and iii) an indexremapping update scheme that alleviates the extra fragmentation caused by updates. We implement ReoDedup atop Ceph and our cloud experiments show that the average read throughput of ReoDedup can be increased by up to$1.72 \times$over state-of-thearts, without any deduplication ratio loss.

11This work was supported by the Young Scientists Fund of the National Natural Science Foundation of China under Grant 62302182.Persistent memory (PM) leveraging memory-mapped I/O(MMIO) delivers superior I/O performance, leading to the development of user-space PM file systems based on MMIO. While effective in single-process scenarios, these systems encounter challenges in multi-process environments, such as performance degradation due to repeated page faults and cross-process synchronizations, as well as a large memory footprint from duplicated paging structures. To address these problems, we propose a Multi-process PM File System (MPFS). MPFS builds a shareable page table and shares it among processes, avoiding building duplicate paging structures for distinct processes, thereby significantly reducing the software overhead and memory footprint caused by repeated page faults. MPFS further proposes a PGD-aligned (512GB) mapping method to accelerate page table sharing. Furthermore, MPFS provides a cross-process memory protection mechanism based on the PGD-aligned mapping, ensuring multi-process data reliability with negligible overheads. The experimental results show that MPFS outperforms existing user-space PM file systems by 1560% in multi-process scenarios.

A hashing index provides rapid search performance by swiftly locating key-value items. Non-volatile memory (NVM) technologies have driven research into hashing indexes for NVM, combining hard disk persistence with DRAM-level performance. Nevertheless, current NVM-based hashing indexes must tackle data inconsistency challenges caused by NVM write reordering or partial writes, and mitigate rapid local wear due to frequent updates, considering NVM's limited endurance. The temporary allocation of buckets in NVM-based chained hashing to resolve hash collisions prolongs the critical path for writing, thus hampering write performance. This paper presents WOPHI, a write-optimized persistent hash index scheme for NVM. By utilizing log-free failure-atomic writes, WOPHI minimizes data consistency overhead and addresses hash conflicts with bucket pre-allocation. Experimental results underscore WOPHI's significant performance enhancements, with insertion latency slashed by up to 88.2% and deletion latency boosted by up to 82.6% compared to existing state-of-the-art schemes. Moreover, WOPHI substantially mitigates data consistency overhead, reducing cache line flushes by 59.3%, while maintaining robust write throughput for insert and delete operations.

Distributed deep neural networks (DNN) training systems deployed across workers have been widely used in various domains, while the communication overhead among workers for synchronizing gradient tensors often becomes the performance bottleneck. To optimize communication efficiency, state-of-the-art studies often apply both two techniques: i) gradient sparsification compression, which truncates the gradient to its largest elements to reduce the communication traffic, and ii) tensor fusion, which merges multiple gradient tensors within a fusion buffer to transmit them together to reduce the communication startup overhead. However, we find that existing studies often apply gradient sparsification after tensor fusion (we call sparsification-behind tensor fusion), which leads to a fact that a lot of fused gradient tensors are missed after the sparsification, thus impairing the convergence performance.

Data center storage systems commonly use erasure codes instead of replication to ensure data reliability at a lower cost, striping data into blocks and placing them randomly across nodes. Studies on replication have shown that random block placement can lead to data loss during multi-node failures, and grouping nodes and placing replicas within these groups is used to enhance data reliability. However, random grouping block placement in erasure-coded storage systems often falls short of the required repair parallelism across nodes. Additionally, creating a globally optimal grouping scheme that meets the requirements incurs prohibitively high time complexity. In this paper, we analyze the data reliability of erasure-coded storage systems using node-grouping-based data placement, revealing a trade-off between fault tolerance and repair parallelism. Based on the above analysis, we propose GroupRS, a node-grouping-based data placement strategy that utilizes a greedy heuristic to group nodes for greater node repair parallelism while maintaining the fault tolerance, thereby enhancing the reliability of the data. In addition, for rack failures, we propose GroupRSR atop GroupRS, a simulated annealing-based optimization strategy to reduce the probability of data loss caused by rack failures. Simulation results show that GroupRS improves system reliability by 18% over Copyset with the same fault tolerance, and by 1 × with the same repair parallelism. Cloud tests reveal that GroupRS reduces the average repair time by 47% with the same fault tolerance and increases MTTDL by 2.5 times. In racklevel fault scenarios, GroupRS-R further reduces the repair time by 10%.

Compared to DRAM, persistent memory (PM) offers higher density and persistence but encounters more severe reliability challenges. Erasure coding is widely adopted to enhance reliability with minimal space overhead. Unfortunately, applying erasure coding to PM introduces significant additional latency. Previous work to mitigate coding latency has primarily focused on optimizing computational efficiency. Instead, we reveal that the main performance bottleneck is high memory latency due to inefficient hardware prefetchers, rather than computation. We further observe that the prefetching inefficiency mainly results from: (i) too wide or narrow coding stripes, (ii) small block sizes, and (iii) high concurrency.

Distributed training of large deep-learning models often leads to failures, so checkpointing is commonly employed for recovery. State-of-the-art studies focus on frequent checkpointing for fast recovery from failures. However, it generates numerous checkpoints, incurring substantial costs and thus degrading training performance. Recently, differential checkpointing has been proposed to reduce costs, but it is limited to recommendation systems, so its application to general distributed training systems remains unexplored.

Erasure codes(EC) have been widely adopted to provide high data reliability with low storage costs in clusters. Due to the deletion and out-of-place update operations, some data blocks are invalid, which unfortunately arouses the tediousgarbage collection(GC) problem. Several limitations still plague existing designs: substantial network traffic, unbalanced traffic load, and low read/write performance after GC. This paper proposes FastGC, a fast garbage collection method that merges the old stripes into a new stripe and reclaims invalid blocks. FastGC quickly generates an efficient merge solution by stripe grouping and bit sequences operations to minimize network traffic and maintains data block distributions of the same stripe to ensure read performance. It carefully allocates the storage space for new stripes during merging to eliminate the discontinuous free spaces that affect write performance. Furthermore, to accelerate the parity updates after merging, FastGC greedily schedules the transmission links for multi-stripe updates to balance the traffic load across nodes and adopts a maximum flow algorithm to saturate the bandwidth utilization. Comprehensive evaluation results show via simulations and Alibaba ECS experiments that FastGC can significantly reduce 10.36%-81.22% of the network traffic and 34.25%-72.36% of the GC time while maintaining read/write performance after GC.

Emerging persistent memory (PM) can provide large persistent capacity with performance comparable to DRAM in modern memory systems. Persistent transactional memory (PTM) needs to ensure data consistency after unexpected power loss or crashes. Therefore, crash consistency strategies, such as persistent logging, are still required. However, the additional overhead introduced by these strategies, such as significant extra writes on PM, can lead to system performance degradation. In this article, we propose CodePM, a fault-tolerant PM transactional library that utilizes parity-based crash consistency to remove logging overhead while guaranteeing the correct state of data. CodePM reuses the decoding capability of parity to detect and recover inconsistent objects. To ensure consistency without logs when updating, CodePM employs fine-grained memory fences to carefully align potential inconsistency with the repairability of parity. To detect inconsistency without logs when recovering, CodePM utilizes optimistic speculative scanning recovery by reusing checksum and parity, which supports instant recovery with transient degraded reliability. Moreover, we study the memory fence blocking effects and further augment CodePM with pipelined encoding and persistent writing to hide update latency. We implemented CodePM on Pangolin, the state-of-the-art parity-based PTM for fault-tolerance. Evaluation results with real-world workloads on Intel Optane DCPMM show that CodePM can achieve up to$3.4\times $higher throughput than Pangolin.

Erasure coding is a known redundancy technique that has been popularly deployed in modern storage systems to protect against failures. By introducing a small portion of coded redundancy into data storage, erasure coding is shown to provide higher reliability guarantees than replication under the same storage overhead. Despite its storage efficiency, erasure coding incurs high-performance overhead in repair and updates, and its reliability also depends on the amount of redundancy. How to resolve the tensions among storage efficiency, performance, and reliability has been the major research direction in the literature for decades. In this article, we present an in-depth survey of the past, present, and future of erasure coding in storage systems. We conduct our survey from a systems perspective, with an emphasis on how erasure coding is deployed in practical storage systems. Specifically, we first review the use of erasure coding in storage systems from both academia and industry and state the challenges of deploying erasure coding in practice. We then review the topics of erasure coding in three aspects: (i) new erasure code constructions, (ii) algorithmic techniques for efficient erasure coding operations, and (iii) erasure coding for emerging architectures. Finally, we provide future research directions for erasure coding.

Redundancy transitioning enables erasure-coded storage to adapt to varying performance and reliability requirements by re-encoding data with new coding parameters on-the-fly. Existing studies focus on bandwidth-driven redundancy transitioning that reduces the transitioning bandwidth across storage nodes, yet the actual redundancy transitioning performance remains bottlenecked by the most loaded node. We present BART, a load-balanced redundancy transitioning scheme that aims to reduce the redundancy transitioning time via carefully scheduled parallelization. We show that finding an optimal load-balanced solution is difficult due to the large solution space. Given this challenge, BART decomposes the redundancy transitioning problem into multiple sub-problems and solves the sub-problems via efficient heuristics. We evaluate BART using both simulations for large-scale storage and HDFS prototype experiments on Alibaba Cloud. We show that BART significantly reduces the redundancy transitioning time compared with the bandwidth-driven approach.

In the edge computing environment, app vendors can distribute popular data from the cloud to edge servers to provide low-latency data retrieval. A key problem is how to distribute these data from the cloud to edge servers cost-effectively. Under current schemes, a file is divided into some data blocks for parallel transmissions from the cloud to target edge servers. Edge servers can then combine received data blocks to reconstruct the file. While this method expedites the data distribution process, it presents potential drawbacks. It is sensitive to transmission delays and transmission failures caused by runtime exceptions like network fluctuations and server failures. This paper presents EdgeHydra, the first edge data distribution scheme that tackles this challenge through fault tolerance based on erasure coding. Under EdgeHydra, a file is encoded into data blocks and parity blocks for parallel transmission from the cloud to target edge servers. An edge server can reconstruct the file upon the receipt of a sufficient number of these blocks without having to wait for all the blocks in transmission. It also innovatively employs a leaderless block supplement mechanism to ensure the receipt of sufficient blocks for individual target edge servers. These improve the robustness of the data distribution process significantly. Extensive experiments show that EdgeHydra can tolerate delays and failures in individual transmission links effectively, outperforming the state-of-the-art scheme by up to 50.54% in distribution time.

Emerging resistive RAM (ReRAM) devices can in-situ execute vector-matrix-multiplication (VMM) and is able to achieve energy-efficient in-memory scientific computing. However, the peripheral separated S&Hs and ADCs for row buffering and sensing in conventional designs are the system bottleneck. We propose an ADC-less all-in-one processing-in-ReRAM design that enables the precharge once, readout multiple-bits (PORM) functionality for overlapping the tRCD latencies of different-significance result bits sensed out on the same bitline. Specifically, to support PORM sensing, we propose a cascaded-feedback bitline sensing architecture for VMM and a buffering-and-sensing-collocated sense amplifier elemental design with the bitline and the storage node fully decoupled for enabling conflict-free column accesses. We further propose cross-level inter-leaving mechanism for successive column VMM accesses to reduce the overall latency through improving the hardware spatiotemporal utilization. Experimental results show that our proposed design achieves 297% overall performance improvement and 85.8% energy reduction, compared with an aggressive baseline.

Data-parallel deep neural networks (DNN) training systems deployed across nodes have been widely used in various domains, while the system performance is often bottlenecked by the communication overhead among workers for synchronizing gradients. Top-k sparsification compression is the de facto approach to alleviate the communication bottleneck, which truncates the gradient to its largest k elements before sending it to other nodes.

Hash indexes are widely used in key-value storage systems due to their ability to perform rapid single-point queries. The persistent memory (PM) technology has received significant attention in both academia and industry due to its high performance, non-volatility, and large capacity characteristics. Currently, hash indexes tailored for persistent memories have been extensively researched. However, through an in-depth experimental study, we have discovered that existing persistent hash indexes suffer from low query performance. This is primarily due to persistent memory's higher read latency than DRAM's, which reduces the performance of both positive and negative queries in persistent hash indexes. Additionally, the former's higher read lock overhead further diminishes query performance. To address the above problems, we propose in this paper a Read-Optimized Persistent Hash Index, referred to as ROPHI, based on fingerprint filtering and lock-free prefetching. By employing a fingerprint filtering method, ROPHI introduces a DRAM-based Cuckoo filter to store fingerprints of keys on top of the PM-based hash table, effectively mitigating the time-consuming access overhead of persistent memory hash tables by accessing only the DRAM-based filter. Additionally, ROPHI employs lock-free prefetching for positive query acceleration, utilizing lock-free optimistic concurrent read techniques to avoid read lock overhead and high-speed cache prefetching techniques to reduce access overhead to persistent memory. Experimental results on the Intel Optane DC Persistent Memory Module (DCPMM) platform demonstrate that ROPHI significantly improves query performance over existing persistent hash index schemes. Specifically, ROPHI achieves an improvement of 2.67×-13.59× in negative query performance and 1.72x-7.86x in positive query performance. ROPHI outperforms the state-of-the-art SmartHT in positive query throughput by 34.5%, and in insertion and deletion throughput by 9.20% and 19.87% respectively, while sacrificing only 1.93% of negative query throughput. Additionally, it achieves a 5.07x improvement in recovery efficiency.

A significant drawback of erasure-coding is suffering from the expensive update traffic. The analysis of real-world-production traces shows that partial updates, including partial-block-updates and partial-stripe-updates, are both common. Existing schemes cannot work adequately for partial updates. Raid-based scheme coordinates multiple updated entire blocks to update parity, yet it incurs significant network traffic for partial-block-updates. Delta-based scheme transmits the updated parts and independently updates parity, yet it cannot share computed-delta parts for partial-stripe-updates. We propose CoRD, which optimally combines Raid-based and Delta-based schemes to minimize the update traffic. It exploits the offset address intersections between multiple updated blocks and only transmits the updated parts to coordinate in parity updates. CoRD further address cross-block update scenarios by flipping some dedicated blocks to improve the performance. Comprehensive evaluations verify the effectiveness of CoRD for the latest traces, with the update traffic reduction of 37.02%-87.19% and the performance improvement of 36.54%-231.92% compared to state-of-the-art.

This paper explores the design of an architecture that replaces Disk with Persistent Memory (PM) to achieve the highest I/O throughput in Log-Structured Merge Tree (LSM-Tree) based key-value stores (KVS). Most existing LSM-Tree based KVSs use PM as an intermediate or smoothing layer, which fails to fully exploit PM’s unique advantages to maximize I/O throughput. However, due to PM’s distinct characteristics, such as byte addressability and short erasure time, simply replacing existing storage with PM does not yield optimal I/O performance. Furthermore, LSM-Tree based KVSs often face slow read performance. To tackle these challenges, this paper presents HPDK, a hybrid PM-DRAM KVS that combines level compression for LSM-Trees in PM with a B+-tree based in-memory search index in DRAM, resulting in high write and read throughput. HPDK also employs a key-value separation design and a live-item rate-based dynamic merge method to reduce the volume of PM writes. We implement and evaluate HPDK using a real PM drive, and our extensive experiments show that HPDK provides 1.25-11.8 and 1.47-36.4 times higher read and write throughput, respectively, compared to other state-of-the-art LSM-Tree based approaches.

Clustered storage systems often deploy erasure coding that encodes data into coded chunks and distributes them across nodes to tolerate node failures. It is a storage-efficient redundancy scheme but incurs high repair penalty; thus some state-of-the-arts aim to pipeline the above repair process to improve the repair performance. However, we observe that all existing repair pipelining methods only use a single pipeline, making network bandwidth resources of storage nodes underutilized.In this paper, we propose FullRepair, a new repair pipelining mechanism based on multiple pipelines with the aim of fully exploiting all available bandwidth resources during repair. We construct four constraints to model the repair pipelining problem such that we can obtain the optimal pipelined repair throughput under full bandwidth utilization. We design a multi-pipeline scheduling scheme for FullRepair so as to achieve the above optimality. Experiments on the Amazon EC2 show that compared with the state-of-the-art repair pipelining methods RP and PivotRepair, FullRepair reduces the repair time of single chunk by up to 45.40% and 33.19%, respectively.

Modern clustered storage systems have commonly used erasure coding to maintain data durability against failures, yet it introduces significant update overhead for partial updates (e.g., only part of a block is updated). Recent studies propose the append-commit and buffer-logging techniques, which append multiple updated data to buffer-log and cache the corresponding old data from disk into memory, to reduce the update costs when committing the updates to parity. However, caching the entire old data block will introduce additional disk reads and memory overhead because caching the old part that not be updated, caching the partial old data block will incur the significant disk seeks for frequent partial updates. Our real-cloud experiments show that the unbalanced disk I/O may cause the bottleneck for updating, which is unfortunately overlooked by existing studies.This paper proposes LASC, a locality-aware speculative cache scheme for partial updates. LASC perceives the update locality of a data block from an update request stream within a period and speculatively caches the old data from the disk. It caches the entire old data block with high update locality to reduce the disk seeks. For a series of update requests to the same data block, LASC only performs one disk seek. Otherwise, it caches the old partial data to migrate the disk reads and memory overhead. We evaluate LASC via trace-driven simulations and Alibaba ECS experiments for two of the largest and latest public block-level I/O traces and show that LASC can effectively balance the disk I/O and improve the update performance while keeping memory overhead low.

Outsourcing storage to the cloud can relieve pressure on storage capacity, wherein encrypted deduplication is often used to perform deduplication on encrypted data, for ensuring both storage efficiency and security. However, encrypted deduplication only removes duplicate encrypted data without considering non-duplicate but very similar ones. In this paper, we propose EDelta, which is the first to enable encrypted delta compression so as to further reduce redundancy of similar encrypted data atop encrypted deduplication, by means of preserving similarity after encryption. We also propose two methods to speed up the encryption process of encrypted delta compression. We prototype EDelta in cloud environments and our experimental results based on real-world datasets show that EDelta can achieve an additional data reduction ratio by up to 45.0% on top of encrypted deduplication.

Hashing is a widely used and efficient indexing mechanism for key-value storage. Persistent memory (PM) has attracted extensive attention in research due to its non-volatility and DRAM-like performance. Intel DCPMM, as a PM, can provide large capacity and low total cost of ownership, further promoting the research of PM-based hash index. However, based on real-world workloads, we found that negative searches of existing PM-based hash indexes significantly degrade system performance. A direct method to solve this problem is to use a PM-based Bloom filter to reduce negative searches, but at the cost of the decreased lifespan of PM due to extra PM writes. An alternative method is to use a DRAM-based Bloom filter, but it still faces increased multi-threaded insertion/deletion/positive-search scalability overhead as well as increased data consistency and recovery overhead.In this paper, we propose SmartHT, a small-size DRAM-based Bloom filter to accelerate hash table operations for PM while solving the aforementioned problems. SmartHT uses efficient merge write optimization with head insertion, lazy deletion, and shortened average chained length of head-bucket to provide high insertion/deletion/positive-search scalability, respectively. On the other hand, it utilizes a merged-flush mechanism based on an 8-byte failure-atomic write method to reduce flush instructions and extra PM writes to achieve low data consistency overhead. Experimental results on Intel Optane DCPMM show that, compared with the state-of-the-art persistent hash indexes, SmartHT improves multi-threaded negative queries under uniform and skewed distributions by 4.61x-13.86x and 2.76x-12.99x respectively, achieves high multi-threaded scalability and low data consistency overhead, at the modest cost of recovery time overhead.

Cloud storage systems have commonly used erasure coding that encodes data in stripes of blocks as a low-cost redundancy method for data reliability. Relative to traditional erasure coding, wide-stripe erasure coding that increases the stripe size has been recently proposed and explored to achieve lower redundancy. We observe that wide-stripe erasure coding makes multi-block failures occur much more frequently than traditional erasure coding in cloud storage systems.However, how to efficiently repair multiple blocks in wide-stripe erasure-coded storage systems remains unexplored. The conventional multi-block repair method sends available blocks from surviving nodes to one single new node to repair all failed blocks in a centralized way, which may cause the new node to be the bottleneck; recent multi-block repair methods follow pipelined single-block repair methods and the former are simply built on the latter in an independent way, which may cause the surviving nodes with limited bandwidth to be bottlenecks.In this paper, we first analyze the effects of both centralized and independent ways on the multi-block repair and then propose HMBR, a hybrid multi-block repair mechanism that combines centralized and independent multi-block repairs to tradeoff the bandwidth bottlenecks caused by the new and surviving nodes, thus optimizing the multi-block repair performance. We further extend HMBR for hierarchical network topology and multi-node failures. We prototype HMBR and show via Amazon EC2 that the repair time of a multi-block failure can be reduced by up to 64.8% over state-of-the-art schemes.

A significant drawback of erasure codes is suffering from the expensive update overhead, and all parity blocks are regenerated once any update of one data block for consistency. Existing update techniques either neglect the multi-block updates scenario under update-intensive workloads or do not consider how to minimize the update cost in heterogeneous clusters. This paper presents the first systematic study on multi-block updates in heterogeneous clusters. We formulate the problem as a cost-based routing optimization model and propose a novelMulti-block Double Tree Update(MDTUpdate) technique. The key idea is to construct a double tree structure for multiple updated data blocks and all parity blocks, which avoids the congested link bottleneck. To reduce the update costs effectively, we exploit a hybrid update scheme that combines the data-delta and parity-delta schemes under the double tree structure. To accelerate the tree construction, we design a time-efficient greedy algorithm that timely determines the transmission route via perceiving the cost discrepancy among nodes while avoiding exhaustive enumeration. We further prove that our algorithm is optimal in minimizing the update costs. The experiments show that MDTUpdate can improve the update performance by up to 83.23% over the existing techniques while incurring extremely lightweight running overhead.

As an increasingly popular task in multimedia information retrieval, video moment retrieval (VMR) aims to localize the target moment from an untrimmed video according to a given language query. Most previous methods depend heavily on numerous manual annotations (i.e., moment boundaries), which are extremely expensive to acquire in practice. In addition, due to the domain gap between different datasets, directly applying these pre-trained models to an unseen domain leads to a significant performance drop. In this paper, we focus on a novel task: cross-domain VMR, where fully-annotated datasets are available in one domain (“source domain”), but the domain of interest (“target domain”) only contains unannotated datasets. As far as we know, we present the first study on cross-domain VMR. To address this new task, we propose a novelMulti-ModalCross-DomainAlignment (MMCDA) network to transfer the annotation knowledge from the source domain to the target domain. However, due to the domain discrepancy between the source and target domains and the semantic gap between videos and queries, directly applying trained models to the target domain generally leads to a performance drop. To solve this problem, we develop three novel modules: (i) a domain alignment module is designed to align the feature distributions between different domains of each modality; (ii) a cross-modal alignment module aims to map both video and query features into a joint embedding space and to align the feature distributions between different modalities in the target domain; and (iii) a specific alignment module tries to obtain the fine-grained similarity between a specific frame and the given query for optimal localization. By jointly training these three modules, our MMCDA can learn domain-invariant and semantic-aligned cross-modal representations. Extensive experiments on three challenging benchmarks (ActivityNet Captions, Charades-STA and TACoS) illustrate that our cross-domain method MMCDA outperforms all state-of-the-art single-domain methods. Impressively, MMCDA raises the performance by more than 7% in representative cases, which demonstrates its effectiveness.

More and more commodity storage systems use erasure code to tolerate faults. When reconsidering the recovery problem in a multi-stripe level and heterogeneous network for the erasure-coded cluster, efficiently generating an optimal multi-stripe recovery solution that reduces recovery time remains a challenging and time-consuming task. Previous works either use a greedy algorithm that may fall into the local-optimal and has low performance or use a meta-heuristic algorithm with a long search time and low efficiency.In this paper, we propose a Stripe-schedule Aware Repair (SARepair) technique for multi-stripe recovery in heterogeneous erasure-coded clusters. By carefully examining the metadata of blocks, SARepair intelligently adjusts the recovery solution for each stripe and obtains another multi-stripe solution with less recovery time in a computationally efficient manner. It then tolerates worse solutions to overcome the local-optimal and uses a rollback mechanism to adjust search regions to further reduce recovery time. Moreover, instead of reading blocks sequentially from each node, SARepair also selectively schedules the reading order for each block to reduce the memory overhead. We prototype SARepair and show via both simulations and Amazon EC2 experiments that the recovery time can be reduced by up to 68% over a state-of-the-art recovery approach while keeping time complexity and memory overhead low.

Erasure coding is commonly used as a storage-efficient redundancy method for fault tolerance in cold storage. Recent studies have begun to explore the use of erasure coding in hot storage, which requires fast online recovery to preserve read performance. However, existing erasure-coded repair strategies cannot effectively handle frequent and rapidly-changing network congestions in hot storage clusters. In this paper, we present the notion of pivots, which refer to the storage nodes with sufficient available downlink and uplink bandwidths in a congested hot storage network. We propose PivotRepair, a pivot-based pipelined single-chunk repair technique that leverages pivots for enabling the fast construction of a pipelined repair tree that bypasses congested links. We further propose an adaptive scheduling strategy to improve full-node repair performance. We prototype PivotRepair and show that the repair time of a single-chunk repair and a full-node repair can be reduced by up to 71.27% and 16.50%, respectively, over state-of-the-art repair schemes.

High-density storage servers (HDSSes), which pack many disks into single servers, are currently used in data centers to save costs (power, cooling, etc). Erasure coding, which stripes data and provides high availability guarantees, is also commonly deployed in data centers at lower cost than replication. However, when applying erasure coding to a single HDSS, we find that erasure coding’s state-of-the-art studies that improve repair performance in parallel mainly use multiple servers’ sufficient footprint, which is yet quite limited in the single HDSS, thus leading to a memory-competition issue for disk failure recovery.

Abstract Data deduplication is a widely used technique to remove duplicate data to reduce the storage overhead. However, deduplication typically cannot eliminate the redundancy among nonidentical but similar data chunks. To reduce the storage overhead further, delta compression is often applied to compress the post‐deduplication data. While the two techniques are effective in saving storage space, they introduce complex references among data chunks, which inevitably undermines the system reliability and introduces fragmentation that may degrade the restore performance. In this paper, we observe that the delta compressed chunks (DCCs) are much smaller than regular chunks (non‐DCCs). Also, most fragmentation caused by the base chunk of DCCs remain fragmented in consecutive backups. Based on these observations, we introduce a framework called , which combines replication and erasure coding and uses History‐aware Delta Selection to ensure high reliability and restore performance. Specifically, uses a delta‐utilization‐aware filter and a cooperative cache scheme (CCS) to maintain cache locality and avoid unnecessary container reads, respectively. Moreover, the system selectively performs delta compression by historical information to avoid cyclic fragmentation in consecutive backups. Experimental results based on four real‐world datasets demonstrate that significantly improves the restore performance by 58.3%–76.7% with a low storage overhead.

Abstract Flash‐based key‐value (KV) caching has received increasing attention in recent years with the advantages of flash‐based solid state drives (SSDs) in capacity and cost. By caching most data in SSD, the caching system can eliminate lots of time‐consuming requests to back‐end data stores to provide low‐latency services. To adapt to the unique technical constraints of flash memory, flash‐based KV caching adopts a slab‐based log‐structured management scheme in which the slab is the basic storage unit, and uses a small memory space as a write buffer to eliminate small random writes to SSD for consistent performance and increased lifetime of SSD. However, we have observed that under update‐intensive workloads with strong temporal locality, the slab‐based management in flash‐based KV caching introduces substantial SSD write traffic because of indistinguishable SSD flushing of hot items in slabs, which shortens the SSD lifetime and degrades the performance with increased erase operations. In this article, we first analyze the SSD write traffic in the flash‐based KV caching, and then propose a novel slab popularity‐based storage management scheme‐SPOPB, to extend SSD lifetime and improve performance. Our scheme identifies hot items using a self‐adaptive threshold to reorganize and classify slabs with both the hotness and size of items. Then SPOPB filters and retains the popular slabs containing hot items in the write buffer with redesigned replacement policy to reduce the SSD write traffic. Our experiments show that our design can effectively reduce the SSD write traffic by 63.6%, the erase counts by 55.6%, and improve the performance by 42%.

To adapt to the increasing storage demands and varying storage redundancy requirements, practical distributed storage systems need to supportstorage scalingby relocating currently stored data to different storage nodes. However, the scaling process inevitably transfers substantial data traffic over the network. Thus, minimizing the bandwidth cost of the scaling process is critical in distributed settings. In this paper, we show that optimal storage scaling is achievable in erasure-coded distributed storage based on network coding, by allowing storage nodes to send encoded data during scaling. We formally prove the information-theoretically minimum scaling bandwidth for both scale-out and scale-in cases. Based on our theoretical findings, we also build a distributed storage system prototype NCScale based on Hadoop Distributed File System, so as to realize network-coding-based scaling while preserving the necessary properties for practical deployment. Experiments on Amazon EC2 show that the scaling time can be reduced by up to 50% over the state-of-the-art.

Erasure codes offer a storage-efficient redundancy mechanism for maintaining data availability guarantees in storage clusters, yet also incur high network traffic consumption and recovery time in failure repair. Extensive research has been carried out to reduce the recovery time. However, previous works either target specific erasure code constructions which are not commonly used in today’s distributed storage clusters or neglect the heterogeneous bandwidth property in real network environments. Since erasure-coded clusters are typically composed of multi-node with heterogeneous bandwidth and accessed in parallel, the whole recovery time is mainly restricted by the low-bandwidth links. In this article, we propose SMFRepair, a single-node multi-level forwarding repair technique that is designed to improve the performance in heterogeneous networks based on Reed-Solomon codes for general fault tolerance. SMFRepair carefully selects the helper nodes and uses idle nodes to bypass low-bandwidth links. Idle nodes have sufficient and unused network bandwidth. It also pipelines the repair links that are optimized by idle nodes. Furthermore, a multi-node scheduling repair technique, called MSRepair, is proposed. MSRepair carefully schedules the multi-node repair link to saturate the most unoccupied bandwidth and transfers data from as large-bandwidth links as possible, with the primary objective of minimizing the recovery time. Large-scale simulation and Amazon EC2 real experiments show that compared to state-of-the-art repair techniques, SMFRepair can accelerate the single-node recovery by up to 47.69%, and MSRepair can reduce the multi-node recovery time by 33.78%$\sim$67.53%.

Erasure coding has been widely deployed in modern large-scale storage systems for storage-efficient fault tolerance by storing stripes of data and parity chunks. Recently, enterprises explore the notion of wide stripes to suppress the fraction of parity chunks in each stripe to achieve extreme storage savings. However, how to efficiently generate wide stripes remains a non-trivial issue. In particular, re-encoding the currently stored stripes (termed narrow stripes) into wide stripes triggers substantial bandwidth overhead in relocating and regenerating the chunks for wide stripes. We propose StripeMerge, a wide-stripe generation mechanism that selects and merges narrow stripes into wide stripes, with the primary objective of minimizing the wide-stripe generation bandwidth. We prove the existence of an optimal scheme that does not incur any data transfer for wide-stripe generation, yet the optimal scheme is computationally expensive. To this end, we propose two heuristics that can be efficiently executed with only limited wide-stripe generation bandwidth overhead. We prototype StripeMerge and show via both simulations and Amazon EC2 experiments that the wide-stripe generation time can be reduced by up to 87.8% over a state-of-the-art storage scaling approach.

Modern cloud-scale cold storage data centers have begun to support right-provisioning of a rack’s resources (power, cooling, etc.), which allows only a small fraction of all hard disks to be active (spinning) concurrently at any given time to reduce the cost of ownership. Data deduplication is a traditional approach to split files into chunks and eliminate duplicate chunks, which can also cut costs for cold storage systems. However, when combined with right-provisioning, classical deduplication may make a file deduplicated and stored across the disks some of which are not active currently, thus leading to unacceptable access performance caused by spinning up and down of the disks.

Erasure codes offer a storage-efficient redundancy mechanism for maintaining data availability guarantees in storage clusters, yet also incur high network traffic consumption and recovery time in failure repair. Exiting studies aim to reduce the recovery time in the heterogeneous network. However, the recovery time is always limited by the link with the low bandwidth between nodes, due to bandwidth heterogeneity. Recently, Bai et al. proposed a parallel pipeline tree technique, called PPT, to reduce recovery time by utilizing a special bandwidth gap to bypass the low-bandwidth link. But we find that PPT’s gap-based bypassing method will cause network congestion and competition. In this paper, we propose SMFRepair, a single-node multi-level forwarding repair technique that uses idle nodes to bypass low-bandwidth links without incurring network congestion and competition. Furthermore, a multi-node scheduling repair technique, called MSRepair, is proposed. MSRepair finds a recovery solution that schedules the parallel repair of multi-node and transfers data from as large-bandwidth links as possible, with the primary objective of minimizing the recovery time. Large-scale Mininet simulation and Amazon EC2 real experiments show that compared to state-of-the-art repair techniques, the single-node recovery time can be reduced by up to 36.65%, and the multi-node recovery time can be reduced by up to 55.10%.

In-memory key-value stores are often used to speed up Big Data workloads on modern HPC clusters. To maintain their high availability, erasure coding has been recently adopted as a low-cost redundancy scheme instead of replication. Existing erasure-coded update schemes, however, have either low performance or high memory overhead. In this paper, we propose a novel parity logging-based architecture, HybridPL, which creates a hybrid of in-place update (for data and XOR parity chunks) and log-based update (for the remaining parity chunks), so as to balance the update performance and memory cost, while maintaining efficient single-failure repairs. We realize HybridPL as an in-memory key-value store called LogECMem, and further design efficient repair schemes for multiple failures. We prototype LogECMem and conduct experiments on different workloads. We show that LogECMem achieves better update performance over existing erasure-coded update schemes with low memory overhead, while maintaining high basic I/O and repair performance.

The consistency of a response to a given post at the semantic level and emotional level is essential for a dialogue system to deliver humanlike interactions. However, this challenge is not well addressed in the literature, since most of the approaches neglect the emotional information conveyed by a post while generating responses. This article addresses this problem and proposes a unified end-to-end neural architecture, which is capable of simultaneously encoding the semantics and the emotions in a post and leveraging target information to generate more intelligent responses with appropriately expressed emotions. Extensive experiments on real-world data demonstrate that the proposed method outperforms the state-of-the-art methods in terms of both content coherence and emotion appropriateness.

We propose repair pipelining , a technique that speeds up the repair performance in general erasure-coded storage. By carefully scheduling the repair of failed data in small-size units across storage nodes in a pipelined manner, repair pipelining reduces the single-block repair time to approximately the same as the normal read time for a single block in homogeneous environments. We further design different extensions of repair pipelining algorithms for heterogeneous environments and multi-block repair operations. We implement a repair pipelining prototype, called ECPipe , and integrate it as a middleware system into two versions of Hadoop Distributed File System (HDFS) (namely, HDFS-RAID and HDFS-3) as well as Quantcast File System. Experiments on a local testbed and Amazon EC2 show that repair pipelining significantly improves the performance of degraded reads and full-node recovery over existing repair techniques.

Efficient intrusion detection and analysis of the security landscape in big data environments present challenge for today's users. Intrusion behavior can be described by provenance graphs that record the dependency relationships between intrusion processes and the infected files. Existing intrusion detection methods typically analyze and identify the anomaly either in a single provenance path or the whole provenance graph, neither of which can achieve the benefit on both detection accuracy and detection time. We propose Pagoda, a hybrid approach that takes into account the anomaly degree of both a single provenance path and the whole provenance graph. It can identify intrusion quickly if a serious compromise has been found on one path, and can further improve the detection rate by considering the behavior representation in the whole provenance graph. Pagoda uses a persistent memory database to store provenance and aggregates multiple similar items into one provenance record to maximumly reduce unnecessary I/O during the detection analysis. In addition, it encodes duplicate items in the rule database and filters noise that does not contain intrusion information. The experimental results on a wide variety of real-world applications demonstrate its performance and efficiency.

Erasure codes are being extensively deployed in practical storage systems to prevent data loss with low redundancy. However, these codes require excessive disk I/Os and network traffic for recovering unavailable data. Among all erasure codes, Minimum Storage Regenerating (MSR) codes can achieve optimal repair bandwidth under the minimum storage during recovery, but some open issues remain to be addressed before applying them in real systems. Facing with the huge burden during recovery, erasure-coded storage systems need to be developed with high repair efficiency. Aiming at this goal, a new class of coding scheme is introduced—Hybrid Regenerating Codes (Hybrid-RC). The codes utilize the superiority of MSR codes to compute a subset of data blocks while some other parity blocks are used for reliability maintenance. As a result, our design is near-optimal with respect to storage and network traffic and shows great improvements in recovery performance.

Content-Defined Chunking (CDC) has been playing a key role in data deduplication systems recently due to its high redundancy detection ability. However, existing CDC-based approaches introduce heavy CPU overhead because they declare the chunk cut-points by computing and judging the rolling hashes of the data stream byte by byte. In this article, we propose FastCDC, a Fast and efficient Content-Defined Chunking approach, for data deduplication-based storage systems. The key idea behind FastCDC is the combined use of five key techniques, namely, gear based fast rolling hash, simplifying and enhancing the Gear hash judgment, skipping sub-minimum chunk cut-points, normalizing the chunk-size distribution in a small specified region to address the problem of the decreased deduplication ratio stemming from the cut-point skipping, and last but not least, rolling two bytes each time to further speed up CDC. Our evaluation results show that, by using a combination of the five techniques, FastCDC is 3-12X faster than the state-of-the-art CDC approaches, while achieving nearly the same and even higher deduplication ratio as the classic Rabin-based CDC. In addition, our study on the deduplication throughput of FastCDC-based Destor (an open source deduplication project) indicates that FastCDC helps achieve 1.2-3.0X higher throughput than Destor based on state-of-the-art chunkers.

The consistency of a response to a given post at semantic-level and emotional-level is essential for a dialogue system to deliver human-like interactions. However, this challenge is not well addressed in the literature, since most of the approaches neglect the emotional information conveyed by a post while generating responses. This article addresses this problem by proposing a unified end-to-end neural architecture, which is capable of simultaneously encoding the semantics and the emotions in a post for generating more intelligent responses with appropriately expressed emotions. Extensive experiments on real-world data demonstrate that the proposed method outperforms the state-of-the-art methods in terms of both content coherence and emotion appropriateness.

Modern decentralized key-value stores often replicate and distribute data via consistent hashing for availability and scalability. Compared to replication, erasure coding is a promising redundancy approach that provides availability guarantees at much lower cost. However, when combined with consistent hashing, erasure coding incurs a lot of parity updates during scaling (i.e., adding or removing nodes) and cannot efficiently handle degraded reads caused by scaling. In this paper, we propose a novel erasure coding model called FragEC, which incurs no parity updates during scaling. We further extend consistent hashing with multiple hash rings to enable erasure coding to seamlessly address degraded reads during scaling. We realize our design as an in-memory key-value store called ECHash, and conduct testbed experiments on different scaling workloads in both local and cloud environments. We show that ECHash achieves better scaling performance (in terms of scaling throughput and degraded read latency during scaling) over the baseline erasure coding implementation, while maintaining high basic I/O and node repair performance.

Data deduplication is a widely deployed technique to remove duplicate content to save storage space, which is however incapable of eliminating the redundancy between nonidentical but similar data blocks. To achieve further space savings in deduplicated storage systems, delta compression is employed to compress post-deduplication data. Both deduplication and delta compression introduce content references among blocks, which inevitably undermines the reliability of deduplicated and delta compressed storage systems. To ensure better reliability, existing approaches utilize either replication or erasure codes to redundantly distribute data across multiple nodes. In deduplicated and delta compressed storage systems, we observe that delta compressed chunks (DCCs) are far smaller than regular chunks called non-DCCs. Motivated by this observation, we suggest a straightforward approach in which replication is used to protect DCCs and erasure code is deployed to protect non-DCCs. However, we need to address two critical challenges to ensure this solution effective. First, the random placement of DCCs replicas destroys cache locality. Second, the separate and individual recovery and restore cache could cause storage containers to be accessed repeatedly. To address these two challenges, in this paper, we propose RepEC-Duet which employs both replication and erasure codes to ensure high reliability and performance for deduplicated and delta-compressed storage systems. RepEC-Duet introduces a delta-utilization-aware filter to select and replicate containers based on the percentage of DCCs in the containers to maintain cache locality. Moreover, to avoid unnecessary container reads, we design a cooperative cache scheme that is aware of both failure recovery and regular restore cache. Our experimental results based on three real-world datasets demonstrate that RepEC-Duet significantly improves the restore performance by 26%-59%, and reduces the storage overhead by 54%-98% than the existing approaches.

Deduplication, as a space-saving technology, is widely deployed in the flash-based storage systems to address the capacity and endurance limitations of flash devices. In this paper, we find that deduplication changes the physical data layout, which raises the chances of the uneven read distribution. This uneven read distribution not only increases the access contention but also deteriorates the read parallelism, thus leading to the read performance degradation. To solve this issue, we propose an efficient read-leveling data distribution scheme (RLDDS), which scatters the highly-duplicated data into different parallel units, to improve the read performance for SSDs with deduplication for access-intensive workloads. RLDDS writes data into a parallel unit with lower potential read-hotness to balance the read distribution among all the parallel units. Extensive experimental results show that RLDDS effectively improves the read performance by up to 21.61% compared to deduplication with the conventional dynamic data allocation scheme. Additional benefits of RLDDS include the promoted write performance (up to 23.69%) in access-intensive workloads and the overall system performance improvement (up to 18.22%) with the same write traffic reduction.

Minimum-Storage Regenerating (MSR) codes have become superior alternatives to traditional erasure codes as they can provide optimal repair bandwidth while the reliability and the storage overhead are still optimal. So far, the state-of-the-art MSR codes mainly focus on connecting to all the remaining nodes to repair a single failure. Since the recovery latency may be bottlenecked by the time taken to retrieve the slowest or straggling block, it is however impractical to have the highest connectivity in MSR codes. In this paper, we introduce a generic construction for all parameters in MSR codes, which allows for bandwidth-efficient repair of a single data node failure with an arbitrary (but fixed) number of accessed nodes d. Our method provides explicit and generic encoding and repairing processes, and such codes were not previously known to exist. When d = n - 1, we show that our codes are not inferior to the other MSR codes and retain the same recovery optimality. Furthermore, the arbitrary number of d allows our codes to adapt to the late binding strategy to avoid stragglers (overloaded sites) for efficient recovery performance. As a result, our codes outperform both traditional erasure codes and the state-of-the-art MSR codes on the aspect of the response time when the system is subjected to an imbalanced load.

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provides fault tolerance with minimum storage redundancy but also achieves low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. Specifically, if a single column fails, then our goal is to minimize the repair bandwidth by downloading the least amount of bits from d healthy columns, where k <; d <; k + r - 1. If one column of an MDS code is failed, it is known that we need to download at least 1/(d - k + 1) fraction of the data stored in each of the d healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary d healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by d specific healthy columns, then we say the MDS code has weak-optimal repair. In this paper, we propose two explicit constructions of binary MDS array codes with more parity columns (i.e., r ≥ 3) that achieve asymptotically weak-optimal repair, where k + 1 <; d <; k + L(r - 1)/2J, and “asymptotic" means that the repair bandwidth achieves the minimum value asymptotically in d. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for anyone information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.

Erasure coding is widely used for massive storage in data centers to achieve high fault tolerance and low storage redundancy. Since the cross-rack communication cost is often high, it is critical to design erasure codes that minimize the cross-rack repair bandwidth during failure repair. In this paper, we analyze the optimal trade-off between storage redundancy and cross-rack repair bandwidth specifically for data centers, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. We characterize the optimal trade-off curve under functional repair, and propose a general family of erasure codes called rack-aware regenerating codes (RRC), which achieve the optimal trade-off. We further propose exact repair constructions of RRC that have minimum storage redundancy and minimum cross-rack repair bandwidth, respectively. We show that (i) the minimum storage redundancy constructions support a wide range of parameters and have cross-rack repair bandwidth that is strictly less than that of the classical minimum storage regenerating codes in most cases, and (ii) the minimum cross-rack repair bandwidth constructions support all the parameters and have less cross-rack repair bandwidth than that of the minimum bandwidth regenerating codes for almost all of the parameters.

We consider the online shortest path routing (SPR) of a network with stochastically time varying link states under potential adversarial attacks. Due to the denial of service (DoS) attacks, the distributions of link states could be stochastic (benign) or adversarial at different temporal and spatial locations. Without any a priori, designing an adaptive and optimal DoS-proof SPR protocol to thwart all possible adversarial attacks is a very challenging issue. In this paper, we present the first such integral solution based on the multi-armed bandit (MAB) theory, where jamming is the adversarial strategy. By introducing a novel control parameter into the exploration phase for each link, a martingale inequality is applied in our formulated combinatorial adversarial MAB framework. The proposed algorithm could automatically detect the specific jammed and un-jammed links within a unified framework. As a result, the adaptive online SPR strategies with near-optimal learning performance in all possible regimes are obtained. Moreover, we propose the accelerated algorithms by multi-path route probing and cooperative learning among multiple sources, and study their implementation issues. Comparing to existing works, our algorithm has the respective 30.3% and 87.1% improvements of network delay for oblivious jamming and adaptive jamming given a typical learning period and a 81.5% improvement of learning duration under a specified network delay on average, while it enjoys almost the same performance without jamming. Lastly, the accelerated algorithms can achieve a maximal of 150.2% improvement in network delay and a 431.3% improvement in learning duration.

Data deduplication, a lossless data compression technique, has been widely deployed in backup systems to save storage space. However, data fragmentation introduced by data deduplication seriously degrades restore performance. To alleviate the fragmentation problem, rewriting algorithms such as CBR, CAP, and HAR have been proposed. In certain backup datasets containing packed files like UNIX tar files, we have observed that a large amount of rewritten fragmented chunks tend to remain fragmented in following backups and thus get rewritten repeatedly in consecutive backups. Such repeatedly rewritten chunks are referred to as persistent fragmented chunks (PFCs), and they severely impact the efficiency of rewriting algorithms and restore performance. In this paper, we propose PFCG, an efficient scheme to enhance the efficiency of rewriting algorithms and restore performance. The central idea of PFCG is to identify and differentiate PFCs from regular fragmented chunks, i.e., non-PFCs, and store these two types of fragmented chunks into separate containers during backups to prevent the proliferation of PFCs in following backups. Our experimental results based on six real-world datasets demonstrate that PFCG significantly improves the restore performance by 21% to 47% over the state-of-the-art rewriting algorithms, without sacrificing deduplication efficiency.

To adapt to the increasing storage demands and varying storage redundancy requirements, practical distributed storage systems need to support storage scaling by relocating currently stored data to different storage nodes. However, the scaling process inevitably transfers substantial data traffic over the network. Thus, minimizing the bandwidth cost of the scaling process is critical in distributed settings. In this paper, we show that optimal storage scaling is achievable in erasure-coded distributed storage based on network coding, by allowing storage nodes to send encoded data during scaling. We formally prove the information-theoretically minimum scaling bandwidth. Based on our theoretical findings, we also build a distributed storage system prototype NCScale, which realizes network-coding-based scaling while preserving the necessary properties for practical deployment. Experiments on Amazon EC2 show that the scaling time can be reduced by up to 50% over the state-of-the-art.

It is critical to support efficient scaling in distributed storage systems so as to meet increasing storage demands with new storage nodes. However, the scaling process incurs substantial scaling bandwidth due to reorganizing currently stored data to new storage nodes. Recent work has applied network coding to minimize scaling bandwidth for a special case where (n, k) MDS codes are scaled to (n', k') MDS codes for n'-k'=n-k. In this paper, we extend the results and prove the minimum scaling bandwidth for a more general setting where (n, k) MDS codes are scaled to (n', k') MDS codes for and k'≥ k. Furthermore, we present a family of MDS code construction that achieves optimal scaling from (n, k) to (n', k') where k=k'.

Distributed storage systems can store data with erasure coding to maintain data availability with low storage redundancy. One class of erasure coding is based on regenerating codes, which provably minimize the amount of data transferred for failure repair and realize the optimal tradeoff between the storage redundancy and the amount of traffic transferred for repair. Typical regenerating codes often require surviving storage nodes to encode their stored data for repair. In this paper, we study a framework called proxy-assisted regeneration, which offloads the repair process to a centralized proxy. We extend the previous applied work on proxy-assisted regeneration by providing theoretical validation. Specifically, we study a special class of regenerating codes called proxy-assisted minimum storage regenerating (PMSR) codes, which enable uncoded repair without the need of encoding in surviving nodes, while preserving the minimum storage redundancy and minimum amount of traffic transferred for repair. We formally prove the existence of PMSR codes for two configurations: 1) repairing single-node failures under double fault tolerance and 2) repairing double-node failures under triple fault tolerance. We also provide a semideterministic PMSR code construction for repairing single-node failures under double fault tolerance.

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy, but also achieve low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance. Specifically, if a single column fails, our goal is to minimize the repair bandwidth by downloading the least amount of bits from d non-failed columns, where k ≤ d ≤ k + r − 1. However, existing binary MDS codes that achieve high data rates (i.e., k/(k + r) > 1/2) and minimum repair bandwidth only support double fault tolerance (i.e., r = 2), which is insufficient for failure-prone distributed storage environments in practice. This paper fills the void by proposing an explicit construction of triple-fault-tolerant (i.e., r = 3) binary MDS array codes that achieve asymptotically minimum repair bandwidth for d = k + 1.

Cloud datacenters use limited network resources to host complex and diverse applications that requires us to treat upper applications as a black box and provide low latency for latency-sensitive short flows. Many good performance schemes need to preliminarily obtain flow information (flow size, deadline or traffic distribution) or modify hardware or software, which leads to difficult use and inefficient in practice.

Chunk-level deduplication, while robust in removing duplicate chunks, introduces chunk fragmentation which decreases restore performance. Rewriting algorithms are proposed to reduce the chunk fragmentation and accelerate the restore speed. Delta compression can remove redundant data between non-duplicate but similar chunks which cannot be eliminated by chunk-level deduplication. Some applications use delta compression as a complement for chunk-level deduplication to attain extra space and bandwidth savings. However, we observe that delta compression introduces a new type of chunk fragmentation stemming from delta compressed chunks whose base chunks are fragmented. We refer to such delta compressed chunks as base-fragmented chunks. We found that this new type of chunk fragmentation has a more severely impact on the restore performance than the chunk fragmentation introduced by chunk-level deduplication and cannot be reduced by existing rewriting algorithms. In order to address the problem due to the base-fragmented chunks, we propose SDC, a scheme that selectively performs delta compression after chunk-level deduplication. The main idea behind SDC is to simulate a restore cache to identify the non-base-fragmented chunks and only perform delta compression for these chunks, thus avoiding the new type of chunk fragmentation. Due to the locality among the backup streams, most of the non-base-fragmented chunks can be detected by the simulated restore cache. Experimental results based on real-world datasets show that SDC improves the restore performance of the delta compressed and deduplicated backup system by 1.93X-7.48X, and achieves 95.5%-97.4% of its compression, while imposing negligible impact on the backup throughput.

Erasure codes are widely used in practical storage systems to prevent disk failure and data loss. However, these codes require excessive disk I/Os and network traffic for recovering unavailable data. As a result, the recovery performance of erasure codes is suboptimal. Among all erasure codes, Minimum Storage Regenerating (MSR) codes can achieve optimal repair bandwidth under the minimum storage during recovery, but some open issues remain to be addressed before applying them in real systems. In this paper, we present Hybrid Regenerating Codes (Hybrid-RC), a new set of erasure codes with optimized recovery performance and low storage overhead. The codes utilize the superiority of MSR codes to compute a subset of data blocks while some other parity blocks are used for reliability maintenance. As a result, our design is near-optimal with respect to storage and network traffic. We show that Hybrid-RC reduces the reconstruction cost by up to 21% compared to the Local Reconstruction Codes (LRC) with the same storage overhead. Most importantly, in Hybrid-RC, each block contributes only half the amount of data when processing a single block failure. Therefore, the number of I/Os consumed per block is reduced by 50%, which is of great help to balance the network load and reduce the latency.

Thanks to the rapid development of information technology, the size of a wireless network is becoming larger and larger, which makes spectrum resources more precious than ever before. To improve the efficiency of spectrum utilization, game theory has been applied to study efficient spectrum sharing for a long time. However, the scale of wireless networks in existing studies is relatively small. In this paper, we introduce a novel game called aggregative game and use it to model spectrum sharing in large-scale, heterogeneous, and dynamic networks. Meanwhile, the massive usage of the spectrum leads to easier divulgence of privacy of spectrum users, which calls for privacy and truthfulness guarantees. In a large decentralized scenario, each user has no priori about other users’ channel access decisions, which forms an incomplete information game. A “weak mediator,” e.g., the base station or licensed spectrum regulator, is introduced and it turns the incomplete spectrum sharing game into a complete one. This is essential in reaching a Nash equilibrium (NE). By utilizing past channel access experience, we propose an online learning algorithm to improve the utility of each user. We show that the learning algorithm achieves an NE over time and provides no regret guarantee for each user. Specifically, our mechanism admits an approximateex-postNE, and is joint differentially private and incentive-compatible. Efficiency of the approximate NE is evaluated, and innovative scaling law results are disclosed. We also provide simulation results to verify our analysis.

This paper studies the problem of jamming-resistant spectrum aggregation and access (SAA) for energy-efficiency (EE) cognitive radio communications. We consider various jamming behaviors, where jammers may attack all available channels with arbitrarily changing strategies over time, attack a subset of the channels at certain time slots, or have different intelligence, i.e., oblivious or adaptive adversary, and so on. Without any priori knowledge about the channels and jammers, it is very challenging to design an efficient and practical jamming-resistant SAA algorithm to reach the optimal EE goal. In this paper, we utilize the advanced martingale concentration inequalities in an multi-armed bandits-based online learning framework to facilitate the optimal detection of various jamming behaviors. We first define a novel EE model for discontiguous orthogonal frequency division multiplexing to facilitate scalable SAA over distributed spectrum pools in practice. Then, the jamming-resistant dynamic channel access problem is formulated as a regret minimization problem. Meanwhile, an online stochastic gradient descent with bandit feedback procedure is adopted to allocate the transmit power. The proposed algorithm can autonomously detect the environmental features and find a near-optimal solution in each attacking scenario. Our algorithm is implemented with low complexity and with multiple users under some practical jamming scenarios. Extensive numerical studies show that under some practical jamming scenarios, our algorithm has an EE improvement of 45.3% over a fixed learning period, and an improvement of 82.5% in terms of learning duration compared with existing approaches.

Repair performance in hierarchical data centers is often bottlenecked by cross-rack network transfer. Recent theoretical results show that the cross-rack repair traffic can be minimized through repair layering, whose idea is to partition a repair operation into inner-rack and cross-rack layers. However, how repair layering should be implemented and deployed in practice remains an open issue. In this article, we address this issue by proposing a practical repair layering framework called DoubleR . We design two families of practical double regenerating codes (DRC), which not only minimize the cross-rack repair traffic but also have several practical properties that improve state-of-the-art regenerating codes. We implement and deploy DoubleR atop the Hadoop Distributed File System (HDFS) and show that DoubleR maintains the theoretical guarantees of DRC and improves the repair performance of regenerating codes in both node recovery and degraded read operations.

Erasure codes are widely used in modern distributed storage systems to prevent data loss and server failures. Regenerating codes are a class of erasure codes that trade storage efficiency and computation for repair bandwidth reduction. However, their nonunified coding parameters and huge computational overhead prohibit their applications. Hence, we first propose a family of General Functional Regenerating (GFR) codes with uncoded repair, balancing storage efficiency and repair bandwidth with general parameters. The GFR codes take advantage of a heuristic repair algorithm, which makes efforts to employ as little repair bandwidth as possible to repair a single failure. Second, we also present a scheduled shift multiplication (SSM) algorithm, which accelerates the matrix product over the Galois field by scheduling the order of coding operations, so encoding and repairing of GFR codes can be executed by fast bitwise shifting and exclusive-OR. Compared to the traditional table-lookup multiplication algorithm, our SSM algorithm gains 1.2 to 2 X speedup in our experimental evaluations, with little effect on the repair success rate.

Erasure codes are widely used in distributed storage systems to prevent data loss. Traditional codes suffer from a typical repair-bandwidth problem in which the amount of data required to reconstruct the lost data, referred to as the repair bandwidth, is often far more than the theoretical minimum. While many novel codes have been proposed in recent years to reduce the repair bandwidth, these codes either require extra storage and computation overhead or are only applicable to some special cases. To address the weaknesses of the existing solutions to the repair-bandwidth problem, we propose Z Codes, a general family of codes capable of achieving the theoretical lower bound of repair bandwidth versus storage. To the best of our knowledge, the Z codes are the first general systematic erasure codes that jointly achieve optimal repair bandwidth and storage. Further, we generalize the Z codes to the GZ codes to gain the Maximum Distance Separable (MDS) property. Our evaluations of a real system indicate that Z/GZ and Reed-Solomon (RS) codes show approximately close encoding and repairing speeds, while GZ codes achieve over 37.5% response time reduction for repairing the same size of data, compared to the RS and Cauchy Reed-Solomon (CRS) codes.

To balance performance and storage efficiency, modern clustered file systems often first store data with replication, followed by encoding the replicated data with erasure coding. We argue that the commonly used random replication does not take into account erasure coding in its design, thereby raising both performance and availability issues in the subsequent encoding operation. We propose encoding-aware replication, which carefully places the replicas so as to (i) eliminate cross-rack downloads of data blocks during the encoding operation, (ii) preserve availability without data relocation after the encoding operation, and (iii) maintain load balancing across replicas as in random replication before the encoding operation. We conduct extensive HDFS-based testbed experiments and discrete-event simulations, and demonstrate the performance gains of encoding-aware replication over random replication.

Due to the high complexity in software hierarchy and the shared queue & lock mechanism for synchronized access, existing I/O stack for accessing the FCoE based SAN storage becomes a performance bottleneck, thus leading to a high I/O overhead and limited scalability in multi-core servers. In order to address this performance bottleneck, we propose a synergetic and efficient solution that consists of three optimization strategies for accessing the FCoE based SAN storage: (1) We use private per-CPU structures and disabling kernel preemption method to process I/Os, which significantly improves the performance of parallel I/O in multi-core servers; (2) We directly map the requests from the block-layer to the FCoE frames, which efficiently translates I/O requests into network messages; (3) We adopt a low latency I/O completion scheme, which substantially reduces the I/O completion latency. We have implemented a prototype (called FastFCoE, a protocol stack for accessing the FCoE based SAN storage). Experimental results demonstrate that FastFCoE achieves efficient and scalable I/O throughput, obtaining 1132.1K/836K IOPS (6.6/5.4 times as much as original Linux Open-FCoE stack) for read/write requests.

Data compression is widely used in storage systems to reduce redundant data and thus save storage space. One challenge facing the traditional compression approaches is the limitation of compression windows size, which fails to reduce redundancy globally. In this paper, we present DEC, a Deduplication-Enhanced Compression approach that effectively combines deduplication and traditional compressors to increase compression ratio and efficiency. Specifically, we make full use of deduplication to (1) accelerate data reduction by fast but global deduplication and (2) exploit data locality to compress similar chunks by clustering the data chunks which are adjacent to the same duplicate chunks. Our experimental results of a DEC prototype based on real-world datasets show that DEC increases the compression ratio by 20% to 71% and speeds up the compression throughput by 17%~183% compared to traditional compressors, without sacrificing the decompression throughput by leveraging deduplication in traditional compression approaches.

Data centers increasingly adopt erasure coding to ensure fault-tolerant storage with low redundancy, yet the hierarchical nature of data centers incurs substantial oversubscribed cross-rack bandwidth in failure repair. We present Double Regenerating Codes (DRC), whose idea is to perform two-stage regeneration, so as to minimize the cross-rack repair bandwidth for a single-node repair with the minimum storage redundancy. We prove the existence of a DRC construction, and show via quantitative comparisons that DRC significantly reduces the cross-rack repair bandwidth of state-of-the-art minimum storage regenerating codes.

To balance performance and storage efficiency, modern clustered file systems (CFSes) often first store data with random replication (i.e., distributing replicas across randomly selected nodes), followed by encoding the replicated data with erasure coding. We argue that random replication, while being commonly used, does not take into account erasure coding and hence will raise both performance and availability issues to the subsequent encoding operation. We propose encoding-aware replication, which carefully places the replicas so as to (i) avoid cross-rack downloads of data blocks during encoding, (ii) preserve availability without data relocation after encoding, and (iii) maintain load balancing as in random replication. We implement encoding-aware replication on HDFS, and show via tested experiments that it achieves significant encoding throughput gains over random replication. We also show via discrete-event simulations that encoding-aware replication remains effective under various parameter choices in a large-scale setting. We further show that encoding-aware replication evenly distributes replicas as in random replication.

Due to the high complexity in software hierarchy and the shared queue & lock mechanism for synchronized access, existing I/O stack for remote target access in FCoE-based SAN storage becomes a performance bottleneck, thus leading to a high I/O overhead and limited I/O scalability in multi-core servers. For scalable performance, existing works focus on improving the efficiency of lock algorithm or reducing the number of synchronization points to decrease the synchronization overhead. However, the synchronization problem still exists and leads to a limited I/O scalability. In this paper, we propose Fast FCoE, a protocol stack framework for remote storage access in FCoE based SAN storage. Fast FCoE uses private per-CPU structures and disables the kernel preemption to process I/Os. This method avoids the synchronization overhead. For further I/O efficiency, Fast FCoE directly maps the requests from the block-layer to the FCoE frames. A salient feature of Fast FCoE is using the standard interfaces, thus supporting all upper softwares (such as existing file systems and applications) and offering flexible use in existing infrastructure (e.g., Adaptors, switches, storage devices). Our results demonstrate that Fast FCoE achieves efficient and scalable I/O throughput, obtaining 1107.3K/831.3K IOPS (5.43/4.88 times as much as Open-FCoE stack) for read/write requests.

Erasure codes are widely used in distributed storage systems to prevent data loss. Traditional erasure codes suffer from a typical repair-bandwidth problem in which the amount of data required to reconstruct the lost data, referred to as the repair bandwidth, is often far more than the theoretical minimum. While many novel erasure codes have been proposed in recent years to reduce the repair bandwidth, these codes either require extra storage capacity and computation overhead or are only applicable to some special cases. To address the weaknesses of the existing solutions to the repair-bandwidth problem, we propose Z Codes, a general family of codes capable of achieving the theoretical lower bound of repair bandwidth for a single data node failure. To the best of our knowledge, the Z codes are the first general systematic erasure codes that achieve optimal repair bandwidth under the minimum storage. Our in-memory performance evaluations of a 1-GB file indicate that Z codes have encoding and repairing speeds that are approximately equal to those of the Reed-Solomon (RS) codes, and their speed on the order of GB/s practically removes computation as a performance bottleneck.

We have witnessed an increasing adoption of erasure coding in modern clustered storage systems to reduce the storage overhead of traditional 3-way replication. However, it remains an open issue of how to customize the data analytics paradigm for erasure-coded storage, especially when the storage system operates in failure mode. We propose degraded-first scheduling, a new MapReduce scheduling scheme that improves MapReduce performance in erasure-coded clustered storage systems in failure mode. Its main idea is to launch degraded tasks earlier so as to leverage the unused network resources. We conduct mathematical analysis and discrete event simulation to show the performance gain of degraded-first scheduling over Hadoop's default locality-first scheduling. We further implement degraded-first scheduling on Hadoop and conduct test bed experiments in a 13-node cluster. We show that degraded-first scheduling reduces the MapReduce runtime of locality-first scheduling.

To provide fault tolerance for cloud storage, recent studies propose to stripe data across multiple cloud vendors. However, if a cloud suffers from a permanent failure and loses all its data, we need to repair the lost data with the help of the other surviving clouds to preserve data redundancy. We present a proxy-based storage system for fault-tolerant multiple-cloud storage called NCCloud, which achieves cost-effective repair for a permanent single-cloud failure. NCCloud is built on top of a network-coding-based storage scheme called the functional minimum-storage regenerating (FMSR) codes, which maintain the same fault tolerance and data redundancy as in traditional erasure codes (e.g., RAID-6), but use less repair traffic and, hence, incur less monetary cost due to data transfer. One key design feature of our FMSR codes is that we relax the encoding requirement of storage nodes during repair, while preserving the benefits of network coding in repair. We implement a proof-of-concept prototype of NCCloud and deploy it atop both local and commercial clouds. We validate that FMSR codes provide significant monetary cost savings in repair over RAID-6 codes, while having comparable response time performance in normal cloud storage operations such as upload/download.

Modern storage systems stripe redundant data across multiple nodes to provide availability guarantees against node failures. One form of data redundancy is based on XOR-based erasure codes, which use only XOR operations for encoding and decoding. In addition to tolerating failures, a storage system must also provide fast failure recovery to reduce the window of vulnerability. This work addresses the problem of speeding up the recovery of a single-node failure for general XOR-based erasure codes. We propose a replace recovery algorithm, which uses a hill-climbing technique to search for a fast recovery solution, such that the solution search can be completed within a short time period. We further extend the algorithm to adapt to the scenario where nodes have heterogeneous capabilities (e.g., processing power and transmission bandwidth). We implement our replace recovery algorithm atop a parallelized architecture to demonstrate its feasibility. We conduct experiments on a networked storage system testbed, and show that our replace recovery algorithm uses less recovery time than the conventional recovery approach.

Modern distributed storage systems apply redundancy coding techniques to stored data. One form of redundancy is based on regenerating codes, which can minimize the repair bandwidth, i.e., the amount of data transferred when repairing a failed storage node. Existing regenerating codes mainly require surviving storage nodes encode data during repair. In this paper, we study functional minimum storage regenerating (FMSR) codes, which enable uncoded repair without the encoding requirement in surviving nodes, while preserving the minimum repair bandwidth guarantees and also minimizing disk reads. Under double-fault tolerance settings, we formally prove the existence of FMSR codes, and provide a deterministic FMSR code construction that can significantly speed up the repair process. We further implement and evaluate our deterministic FMSR codes to show the benefits. Our work is built atop a practical cloud storage system that implements FMSR codes, and we provide theoretical validation to justify the practicality of FMSR codes.

One of the design objectives in distributed storage system is the minimization of the data traffic during the repair of failed storage nodes. By repairing multiple failures simultaneously and cooperatively rather than successively and independently, further reduction of repair traffic is made possible. A closed-form expression of the optimal tradeoff between the repair traffic and the amount of storage in each node for cooperative repair is given. We show that the points on the tradeoff curve can be achieved by linear cooperative regenerating codes, with an explicit bound on the required finite-field size. The proof relies on a max-flow-min-cut-type theorem from combinatorial optimization for submodular flows. Two families of explicit constructions are given.

In a distributed storage system, a data file is distributed to several storage nodes, such that the original file can be decoded from any subset of the storage nodes of size larger than or equal to a certain threshold. Upon the failure of a storage node, we would like to regenerate it with minimal amount of data transmissions from the surviving nodes to the new node. This performance metric is called the repair-bandwidth. Another performance metric is the disk input/output (I/O) cost, which measures the number of bits a storage node needs to read out from its memory in order to repair the failed node. In this paper, we give examples of linear regenerating codes with minimal disk I/O cost and repair-bandwidth, without any linear mixing in the helping storage nodes.

Modern storage systems stripe redundant data across multiple disks to provide availability guarantees against disk failures. One form of data redundancy is based on XOR-based erasure codes, which use only XOR operations for encoding and decoding. In addition to providing failure tolerance, a storage system must also provide fast failure recovery to avoid data unavailability. We consider the problem of speeding up the recovery of a single-disk failure for arbitrary XOR-based erasure codes. We address this problem from both theoretical and practical perspectives. We propose a replace recovery algorithm, which uses a hill-climbing technique to search for a fast recovery solution, such that the solution search can be completed within a short time period. We further implement our replace recovery algorithm atop a parallelized architecture to justify its practicality. We experiment our replace recovery algorithm and its parallelized implementation on a networked storage system testbed, and demonstrate that our replace recovery algorithm uses less recovery time than the conventional approach.

In order to provide high data reliability, distributed storage systems disperse data with redundancy to multiple storage nodes. Regenerating codes is a new class of erasure codes to introduce redundancy for the purpose of improving the data repair performance in distributed storage. Most of the studies on regenerating codes focus on the single-failure recovery, but it is not uncommon to see two or more node failures at the same time in large storage networks. To exploit the opportunity of repairing multiple failed nodes simultaneously, a cooperative repair mechanism, in the sense that the nodes to be repaired can exchange data among themselves, is investigated. A lower bound on the repair-bandwidth for cooperative repair is derived and a construction of a family of exact cooperative regenerating codes matching this lower bound is presented.

Distributed storage systems provide reliable access to data through redundancy spread in network system. A key goal is to minimize bandwidth overhead to maintain the redundancy. This paper studies the flexible recovery from multiple node failures in distributed storage systems. Via a cut-based analysis of information flow graph, we obtain a lower bound of maintenance bandwidth for multi-loss flexible recovery (MFR). We also design a coding scheme based on MFR with maintenance bandwidth matching the lower bound. So the lower bound of maintenance bandwidth for multi-loss recovery is tight and the proposed recovery scheme is optimal.

This paper studies the recovery from multiple node failures in distributed storage systems. We design a mutually cooperative recovery (MCR) mechanism for multiple node failures. Via a cut-based analysis of the information flow graph, we obtain a lower bound of maintenance bandwidth based on MCR. For MCR, we also propose a transmission scheme and design a linear network coding scheme based on (η, κ) strong-MDS code, which is a generalization of (η, κ) MDS code. We prove that the maintenance bandwidth based on our transmission and coding schemes matches the lower bound, so the lower bound is tight and the transmission scheme and coding scheme for MCR are optimal. We also give numerical comparisons of MCR with other redundancy recovery mechanisms in storage cost and maintenance bandwidth to show the advantage of MCR.

Power control can help to reduce energy consumption in wireless networks, while the selfish power control of a link may affect the performance of the neighbors. This paper studies the impact of selfish power control on the stability in wireless networks where each link is under a throughput requirement. Employing the modulation scheme non-coherent frequency shift keying (NFSK), we prove that there is an optimal reception rate and a corresponding optimal transmission strategy to minimize the energy consumption for a link with fixed channel condition, and further present a transmission strategy selection algorithm for links with varying channel condition. A round-based repeated non-cooperative game is proposed, assuming that there is only one link which can adjust its transmission strategy in each unit time and the link always adopts the self-optimal strategy myopically. It is observed that this game cannot converge in some cases, since links are motivated to move transmission power from high interference durations to low interference ones. To bring the game into a steady state, a penalty function is introduced and the performance of various penalty functions is investigated. Simulation results show that heavier penalty leads to faster convergence, but has no effect on the energy consumption of the steady state.