Back to search

Michigan State University

Capacity assurance in hostile networks

Abstract

dc:description

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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Jian
Contributors dc:contributor
  • Ren, Jian
  • Biswas, Subir
  • Enbody, Richard
  • Salem, Fathi

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:3648
isbn:9781339205144
isbn:1339205149
oclc:945890784
umi:3732587
local:Li_grad.msu_0128D_14124

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Li, Jian. Capacity assurance in hostile networks. 2015. https://doi.org/doi:10.25335/vv44-vq76