Chang, Christopher SungWook (2012) Applications of coding in network communications. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:05312012-173613536
This thesis uses the tool of network coding to investigate fast peer-to-peer file distribution, anonymous communication, robust network construction under uncertainty, and prioritized transmission.
In a peer-to-peer file distribution system, we use a linear optimization approach to show that the network coding framework significantly simplifies analysis even in scenarios where the optimal solution does not require coding. We also study the effect of requiring reciprocity and the impact of dynamically changing network scenarios.
Second, we investigate anonymous routing in peer-to-peer networks. The goal is to design and analyze a peer-to-peer system that hides the identities of source and sink pairs against adversarial nodes. We first propose a protocol for subgraph construction signaling. The protocol uses path diversity rather than cryptographic keys. We prove information theoretic security of the proposed protocol. We investigate a variety of deterministic and randomized subgraph designs. We also give a reverse path construction mechanism, with which a sink can reply to the source without knowing the source identity. We next investigate anonymous data transmission using network coding. Again, path diversity (with network coding) is used to hide the identities of source and sink pairs. We investigate the effect of subgraph shape on anonymity and congestion arising from traffic shaping constraints, demonstrating the tradeoff between the two through simulations.
Third, we study the problem of network construction under uncertainty about link-loss rates. We prove that both maximizing throughput and minimizing cost are coNP-hard problems. We find polynomial time-solvable solutions that outperform other deterministic approaches.
Lastly, we investigate strategies for communication under a system that prioritizes data based on the worth of data and the probability of successful transmission. Only the highest priority data is transmitted when communication is very limited.
|Item Type:||Thesis (Dissertation (Ph.D.))|
|Subject Keywords:||Peer-to-peer file distribution, Anonymous networking, Network coding, Robust optimization, and Prioritized communication|
|Degree Grantor:||California Institute of Technology|
|Division:||Engineering and Applied Science|
|Major Option:||Electrical Engineering|
|Thesis Availability:||Public (worldwide access)|
|Defense Date:||29 May 2012|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Christopher Chang|
|Deposited On:||01 Jun 2012 20:39|
|Last Modified:||26 Dec 2012 04:44|
- Final Version
See Usage Policy.
Repository Staff Only: item control page