Capacity assurance in hostile networks

Linear network coding provides a new communication diagram to significantly increase the network capacity by allowing the relay nodes to encode the incoming messages. However, this communication diagram is fragile to communication errors and pollution attacks. How to combat errors while maintaining the network efficiency is a challenging research problem. In this dissertation, we study how to combat the attacks in both fixed network coding and random network coding.;For fixed network coding, we provide a novel methodology to characterize linear network coding through error control coding. We propose to map each linear network coding to an error control coding. Under this mapping, these two codes are essentially identical in algebraic aspects. Meanwhile, we propose a novel methodology to characterize a linear network coding through a series of cascaded linear error control codes, and to develop network coding schemes that can combat node compromising attacks.;For random network coding, we propose a new error-detection and error-correction (EDEC) scheme to detect and remove malicious attacks. The proposed EDEC scheme can maintain throughput unchanged when moderate network pollution exists with only a slight increase in computational overhead. Then we propose an improved LEDEC scheme by integrating the low-density parity check (LDPC) decoding. Our theoretical analysis, performance evaluation and simulation results using ns-2 simulator demonstrate that the LEDEC scheme can guarantee a high throughput even for heavily polluted network environment.;Distributed storage is a natural application of network coding. It plays a crucial role in the current cloud computing framework in that it can provide a design trade-off between security management and storage. Regenerating code based approach attracted unique attention because it can achieve the minimum storage regeneration (MSR) point and minimum bandwidth regeneration (MBR) point for distributed storage. Since then, Reed-Solomon code based regenerating codes (RS-MSR code and RS-MBR code) were developed. They can also maintain the MDS (maximum distance separable) property in code reconstruction. However, in the hostile network where the storage nodes can be compromised and the packets can be tampered with, the storage capacity of the network can be significantly affected.In this dissertation, we propose a Hermitian code based minimum storage regenerating (H-MSR) code and a Hermitian code based minimum bandwidth regenerating (H-MBR) code. We first prove that they can achieve the theoretical MSR bound and MBR bound respectively. We then propose data regeneration and reconstruction algorithms for the H-MSR code and the H-MBR code in both error-free networks and hostile networks. Theoretical evaluation shows that our proposed schemes can detect the erroneous decodings and correct more errors in the hostile network than the RS-MSR/RS-MBR code with the same code rate respectively.;Inspired by the novel construction of Hermitian code based regenerating codes, a natural question is how to construct optimal regenerating codes based on the layered structure like Hermitian code in distributed storage. Compared to the Hermitian based code, these codes have simpler structures and are easier to understand and implement. We propose two optimal constructions of MSR codes through rate-matching in hostile networks: 2-layer rate-matched MSR code and m-layer rate-matched MSR code. For the 2-layer code, we can achieve the optimal storage efficiency for given system requirements. Our comprehensive analysis shows that our code can detect and correct malicious nodes with higher storage efficiency compared to the RS-MSR code. Then we propose the m-layer code by extending the 2-layer code and achieve the optimal error correction efficiency by matching the code rate of each layer's MSR code. We also demonstrate that the optimized parameter can achieve the maximum storage capacity under the same constraint. Compared to the RS-MSR code, our code can achieve much higher error correction efficiency. The optimized m-layer code also has better error correction capability than the H-MSR code.