Many modern communication networks suffer significantly from the unreliable characteristic of their nodes and links. To deal with failures, traditionally, centralized erasure codes have been extensively used to improve reliability by introducing data redundancy. In this thesis, we address several issues in implementing erasure codes in a decentralized way such that coding operations are spread to multiple nodes. Our solutions are based on fountain codes and randomized network coding, because of their capability of being amenable to decentralized implementation originated from their simplicity and randomization properties.
Our contributions consist of four parts. First, we propose a novel decentralized implementation of fountain codes utilizing random walks. Our solution does not require node location information and enjoys a small local routing table with a size in proportion to the number of neighbors. Second, we introduce priority random linear codes to achieve partial data recovery by partition and encoding data into non-overlapping or overlapping subsets. Third, we present geometric random linear codes to decrease communication costs in decoding significantly, by introducing modest data redundancy in a hierarchical fashion. Finally, we study the application of network coding in disruption tolerant networks. We show that network coding achieves shorter data transmission time than replication, especially when data buffers are limited. We also propose an efficient variant of network coding based protocol, which attains similar transmission delay, but with much lower transmission costs, as compared to a protocol based on epidemic routing.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/24816 |
| Date | 30 August 2010 |
| Creators | Lin, Yunfeng |
| Contributors | Li, Baochun, Liang, Ben |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0021 seconds