CaltechAUTHORS
  A Caltech Library Service

Network Coding: A Computational Perspective

Langberg, Michael and Sprintson, Alexander and Bruck, Jehoshua (2006) Network Coding: A Computational Perspective. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2006.ETR074

[img]
Preview
PDF
See Usage Policy.

181Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2006.ETR074

Abstract

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by combining the packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V,E) in time O(|E|kh + |V |k2h2 + h4k3(k + h)), where k is the number of destinations and h is the number of packets. Our result improves the best known running time of O(|E|kh+ |V |k2h2(k + h)) of the algorithm due to Jaggi et al. [1] in the typical case of large communication graphs. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is bounded by O(h3k2). Next, we address the problem of finding a network code with the minimum number of encoding nodes in both integer and fractional coding networks. We prove that in the majority of settings this problem is NP-hard. However, we show that if h = O(1), k = O(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time.


Item Type:Report or Paper (Technical Report)
Additional Information:Research supported in part by by the Caltech Lee Center for Advanced Networking and by NSF grants ANI-0322475 and CCF-0346991. Also available from http://www.paradise.caltech.edu/papers/etr072.pdf
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2006.ETR074
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2006.ETR074
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26105
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:04 Apr 2006
Last Modified:26 Dec 2012 13:53

Repository Staff Only: item control page