Efficient Network Coding for Different Network Topologies

Thumbnail Image
Li, Ye
Network Coding
Network coding is known to be able to improve a network's throughput and resilience to packet losses. However, in practice high decoding complexity has been a major obstacle that prevents network coding from being widely employed. This thesis considers efficient network coding methods that have low complexity for different types of scenarios. Simple network topologies are first considered. We propose a systematic network coding approach for networks that consist of one or two two-hop lossy paths. It is proved that, compared to the random linear network coding approach, the proposed scheme requires much less computation in encoding and decoding and also achieves a higher end-to-end rate. It is demonstrated that a judicious use of uncoded packets in these networks may provide considerable gain over random coding. For networks with complex or changing topologies, we investigate the generation-based strategy to design network codes, in which source packets are grouped into subsets called generations and coding is only performed among packets belonging to the same generation. We design generation-based network codes for two different decoders that may be used in different scenarios to meet specific performance/complexity constraints. The first approach, which is generation-by-generation decoding, decodes within generations and therefore its complexity can be made linear by properly choosing the generation size. We analyze the decoding process and propose 1) a method to estimate the optimal amount of overlap among generations, which is a key parameter of generation-based network codes and 2) a new code based on unequal-size generations. The proposed code is shown to outperform existing codes in terms of both computational cost and reception overhead. The second approach considers overhead-optimized decoding, which decodes generations jointly and has lower overhead than the generation-by-generation decoder but requires more computation. We provide an overhead-optimized decoder design with low computational cost and then design codes that are sparser than existing codes. The proposed code is shown to have lower overhead and decoding cost.
External DOI