Network coding allows intermediate nodes to encode data packets to improve network throughput and robustness. However, it increases the propagation speed of polluted data packets if a malicious node injects fake data packets into the network, which degrades the bandwidth efficiency greatly and leads to incorrect decoding at sinks. In this paper, insights on new mathematical relations in linear network coding are presented and a key predistribution-based tag encoding scheme KEPTE is proposed, which enables all intermediate nodes and sinks to detect the correctness of the received data packets. Furthermore, the security of KEPTE with regard to pollution attack and tag pollution attack is quantitatively analyzed. The performance of KEPTE is competitive in terms of: low computational complexity; the ability that all intermediate nodes and sinks detect pollution attack; the ability that all intermediate nodes and sinks detect tag pollution attack; and high fault-tolerance ability. To the best of our knowledge, the existing key predistribution-based schemes aiming at pollution detection can only achieve at most three points as described above. Finally, discussions on the application of KEPTE to practical network coding are also presented.
12 November 2013 in IEEE Transactions on Vehicular Technology
In this paper, we dynamically select the transmission rate and design wireless network coding to improve the quality of services, such as delay for time-critical applications. In a network coded system, with a low transmission rate and, hence, a longer transmission range, more packets may be encoded, which increases the coding opportunity. However, a low transmission rate may incur extra transmission delay, which is intolerable for time-critical applications. We design a novel joint rate selection and wireless network coding (RSNC) scheme with a delay constraint to maximize the total benefit (where we can define the benefit based on the priority or importance of a packet for example) of the packets that are successfully received at the destinations without missing their deadlines. We prove that the proposed problem is NP-hard and propose a novel graph model to mathematically formulate the problem. For the general case, we propose a transmission metric and design an efficient algorithm to determine the transmission rate and coding strategy for each transmission. For a special case when all delay constraints are the same, we study pairwise coding and present a polynomial-time pairwise coding algorithm that achieves an approximation ratio of 1 - (1/e) to the optimal pairwise coding solution, where e is the base of the natural logarithm. Finally, simulation results demonstrate the superiority of the proposed RSNC scheme.
Caching is crucial for accelerating data access, employed as a ubiquitous design in modern systems at many parts of computer systems. With increasing core count, and shrinking latency gap between cache and modern storage devices, hit-path scalability becomes increasingly critical. However, existing production in-memory caches often use list-based management with promotion on each cache hit, which requires extensive locking and poses a significant overhead for scaling beyond a few cores. Moreover, existing techniques for improving scalability either (1) only focus on the indexing structure and do not improve cache management scalability, or (2) sacrifice efficiency or miss-path scalability. Inspired by highly skewed data popularity and short-term hotspot stability in cache workloads, we propose Frozen-Hot, a generic approach to improve the scalability of list-based caches. FrozenHot partitions the cache space into two parts: a frozen cache and a dynamic cache. The frozen cache serves requests for hot objects with minimal latency by eliminating promotion and locking, while the latter leverages the existing cache design to achieve workload adaptivity. We built FrozenHot as a library that can be easily integrated into existing systems. We demonstrate its performance by enabling FrozenHot in two production systems: HHVM and RocksDB using under 100 lines of code. Evaluated using production traces from MSR and Twitter, FrozenHot improves the throughput of three baseline cache algorithms by up to 551%. Compared to stock RocksDB, FrozenHot-enhanced RocksDB shows a higher throughput on all YCSB workloads with up to 90% increase, as well as reduced tail latency.
5 September 2012 in Distributed and Parallel Databases
Due to individual unreliable commodity components, failures are common in large-scale distributed storage systems. Erasure codes are widely deployed in practical storage systems to provide fault tolerance with low storage overhead. However, random data distribution (RDD), commonly used in erasure-coded storage systems, induces heavy cross-rack traffic, load imbalance, and random access, which adversely affects failure recovery. In this paper, with orthogonal arrays, we define a Deterministic Data Distribution (D3) to uniformly distribute data/parity blocks among nodes, and propose an efficient failure recovery approach based on D3, which minimizes the cross-rack repair traffic against a single node failure. Thanks to the uniformity of D3, the proposed recovery approach balances the repair traffic not only among nodes within a rack but also among racks. We implement D3 over Reed-Solomon codes and Locally Repairable Codes in Hadoop Distributed File System (HDFS) with a cluster of 28 machines. Compared with RDD, our experiments show that D3 significantly speeds up the failure recovery up to 2.49 times for RS codes and 1.38 times for LRCs. Moreover, D3 supports front-end applications better than RDD in both of normal and recovery states.