A Caltech Library Service

Applications of Coding in Network Communications


Chang, Christopher SungWook (2012) Applications of Coding in Network Communications. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/3N60-MB49.


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)
Research Advisor(s):
  • Ho, Tracey C. (advisor)
  • Effros, Michelle (advisor)
Thesis Committee:
  • Ho, Tracey C. (chair)
  • Effros, Michelle (co-chair)
  • McEliece, Robert J.
  • Hassibi, Babak
  • Ligett, Katrina A.
Defense Date:29 May 2012
Funding AgencyGrant Number
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Jet Propulsion Laboratory, NASAUNSPECIFIED
Lincoln LaboratoryUNSPECIFIED
Record Number:CaltechTHESIS:05312012-173613536
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7114
Deposited By: Christopher Chang
Deposited On:01 Jun 2012 20:39
Last Modified:07 Jun 2023 17:17

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page