A Caltech Library Service

Network Coding and Distributed Compression over Large Networks: Some Basic Principles


Bakshi, Mayank (2012) Network Coding and Distributed Compression over Large Networks: Some Basic Principles. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/GWDW-5H78.


The fields of Network Coding and Distributed Compression have focused primarily on finding the capacity for families of problems defined by either a broad class of networks topologies (e.g., directed, acyclic networks) under a narrow class of demands (e.g., multicast), or a specific network topology (e.g. three-node networks) under different types of demands (e.g. Slepian-Wolf, Ahlswede-Körner). Given the difficulty of the general problem, it is not surprising that the collection of networks that have been fully solved to date is still very small. This work investigates several new approaches to bounding the achievable rate region for general network source coding problems - reducing a network to an equivalent network or collection of networks, investigating the effect of feedback on achievable rates, and characterizing the role of side information.

We describe two approaches aimed at simplifying the capacity calculations in a large network. First, we prove the optimality of separation between network coding and channel coding for networks of point-to-point channels with a Byzantine adversary. Next, we give a strategy for calculating the capacity of an error-free network by decomposing that network into smaller networks. We show that this strategy is optimal for a large class of networks and give a bound for other cases.

To date, the role of feedback in network source coding has received very little attention. We present several examples of networks that demonstrate that feedback can increases the set of achievable rates in both lossy and lossless network source coding settings. We derive general upper and lower bounds on the rate regions for networks with limited feedback that demonstrate a fundamental tradeoff between the forward rate and the feedback rate. For zero error source coding with limited feedback and decoder side information, we derive the exact tradeoff between the forward rate and the feedback rate for several classes of sources. A surprising result is that even zero rate feedback can reduce the optimal forward rate by an arbitrary factor.

Side information can be used to reduce the rates required for reliable information. We precisely characterize the exact achievable region for multicast networks with side information at the sinks and find upper and lower bounds on the achievable rate region for other demand types.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:network coding; data compression; information theory;
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Effros, Michelle
Thesis Committee:
  • Effros, Michelle (chair)
  • Bruck, Jehoshua
  • Ho, Tracey C.
  • Chandy, K. Mani
  • Wierman, Adam C.
Defense Date:16 August 2011
Non-Caltech Author Email:mayank.bakshi (AT)
Funding AgencyGrant Number
NSFCCR- 0325324
Lee Center for Advanced Networking at CaltechUNSPECIFIED
Record Number:CaltechTHESIS:06082012-122324439
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7148
Deposited By: Mayank Bakshi
Deposited On:11 Jun 2012 16:24
Last Modified:07 Jun 2023 17:25

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page