Network Coding Theory, Algorithms and Applications

We are interested in several fundamental questions that span from achievable rate bounds to algorithms and coding techniques for network information flow. Our research program is especially focused on new fundamental questions and approaches that arise from and feed to application areas.

Traditionally network coding is employed for information dissemination (multicats), but new applications give rise to different traffic demands which are non-uniform. We have shown that using ideas from network coding one can develop algorithms for satisfying non-uniform demands that give significant rate advantage over traditional methods when groups of users have different graph min-cuts. We are investigating the use of network coding techniques for a variety of traffic demand scenatios. These form fundamental questions that will also impact application areas like multimedia delivery.

Delay and processing complexity are important considerations in network information delivery. We have examined communication through a cascade of L identical discrete memoryless channels, where the source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate (relay) nodes are restricted by delay considerations to process only blocks of a fixed length. We showed that the intermediate nodes need only process blocks of length greater than log(L) to achieve the min-cut capacity even asymptotically in L. At the other extreme, if the intermediate nodes can only process constant block-lengths, we can show that the only rate that can be sent is the zero-error capacity of the DMC. This result immediately opens up questions on the role of finite processing for other networks, and on whether the throughput-delay trade off has a similar characterization. We have also developed rateless codes for packet erasure networks with finite intermediate node processing and memory capabilities. These are sparse, linear codes specifically tailored to line networks (or single paths), but give intrigying suggestions for generalization to arbitrary networks.

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N>1 receivers can also be achieved using packets of length log N bits, if the operations the intermediate nodes perform are deterministally known at the receivers. In a recent work, we calculated the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.

Finally, there are natural connections between network coding and combinatorics that we are exploring. Our studies in network information flow revealed structural properties of the graph through a method we developed termed subtree decomposition. This decomposition allowed us to show that very different networks are equivalent from the coding point of view, facilitating code design and providing for several cases sharp bounds on the alphabet size needed for achieving the min-cur bound in network coding. These ideas also revealed a connection between graph coloring and alphabet size in network coding. In our examination of average throughput benefits of network coding, we demonstrated that the throughput gains over routing can be the average throughput gap between plain routing and network coding can be quantified in terms of the integrality gap of a standard formulation of the Steiner tree problem. We believe several more intricate connects between combinatorics and network coding are still to be discovered which will have an important influence on fundamental questions of network information flow.

Selected Publications

A PHP Error was encountered

Severity: Warning

Message: Creating default object from empty value

Filename: gettext/gettext.inc

Line Number: 195

  1. J. Ebrahimi and C. Fragouli, Combinatorial algorithms for wireless information flow, ACM Transactions on Algorithms, 2011
    Download:  
    Citation: BibTeX RIS
    A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
  2. M. Jafari Siavoshani, L. Keller, K. Argyraki and C. Fragouli, Compressed network coding vectors, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009
    Download:  
    Citation: BibTeX RIS
    In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.
  3. U. Niesen, C. Fragouli and D. Tuninetti, On the capacity of line networks, IEEE Transactions on Information Theory, 53, 2007
    Download:  
    Citation: BibTeX RIS
    We consider communication through a cascade of discrete memoryless channels (DMCs). The source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of a fixed length. We investigate how the processing at the relays must be chosen in order to maximize the capacity of the cascade, that is, the maximum achievable end-to-end rate between the source and the destination. For infinite cascades with fixed intermediate processing length at the relays, we prove that this intermediate processing can be chosen to be identical without loss of optimality, and that the capacity of the cascade coincides with the rate of the best zero-error code of length equal to the block length of the intermediate processing. We further show that for fixed and identical intermediate processing at all relays, convergence of capacity as the length of the cascade goes to infinity is exponentially fast. Finally, we characterize how the block length of the intermediate processing must scale with the length of the cascade to guarantee a constant end-to-end rate. We prove that it is sufficient that the block length scales logarithmically with the network length in order to achieve any rate above the zero-error capacity. We show that in many cases of interest logarithmic growth is also necessary
  4. C. Fragouli and E. Soljanin, Information Flow Decomposition for Network Coding, IEEE Trans. Inform. Theory, 2006
    Download:  
    Citation: BibTeX RIS
    The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.
  5. C. Fragouli, J. Widmer and J.-Y. Le Boudec, Network coding: an instant primer, ACM SIGCOM Computer Communication Review, 2006
    Download:  
    Citation: BibTeX RIS
    Network coding is a new research area that may have interesting applications in practical networking systems. With network coding, intermediate nodes may send out packets that are linear combinations of previously received information. There are two main benefits of this approach: potential throughput improvements and a high degree of robustness. Robustness translates into loss resilience and facilitates the design of simple distributed algorithms that perform well, even if decisions are based only on partial information. This paper is an instant primer on network coding: we explain what network coding does and how it does it. We also discuss the implications of theoretical results on network coding for realistic settings and show how network coding can be used in practice.
  6. C. Chekuri, C. Fragouli and E. Soljanin, On Average Throughput Benefits and Alphabet Size in Network Coding, IEEE Trans. Inform. Theory, 2006
    Download:  
    Citation: BibTeX RIS
    We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard LP formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with $N$ receivers where network coding offers benefits proportional to $\sqrt{N}$. We also discuss other throughput measures in networks, and show how in certain classes of networks, the average throughput can be achieved uniformly by all receivers by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.
  7. P. Pakzad, C. Fragouli and A. Shokrollahi, Coding schemes for line networks, ISIT, 2005
    Download:  
    Citation: BibTeX RIS
    We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks.

Complete List of Publications in Network Coding

research/network_coding.txt · Last modified: 2011/04/24 11:23 by lokeller
© ARNI/EPFL, 1015 Lausanne
webmaster