Monday, August 06, 2007

Network Coding, Open Problems

I'm spending a couple of days at the DIMACS Tutorial on Algorithms for Next Generation Networks. Tracey Ho and Alex Sprintson and giving a talk on Network Coding, and since in the past I've promised a post on open questions in network coding, I'm interviewing them. I apologize that the questions might be vague; the problem with a new area is that it's still a little unclear what the right open problems are, and we all use different lingo. But here are a few...
  1. For 3 source-receiver pairs and unicast, in an undirected network, with arbitrary coding, is there an advantage from coding over routing?(I think the reference paper is Li and Li, Network Coding: The Case of Multiple Unicast Sessions)?
  2. General multiple unicast in directed networks: is there an algorithm that, given a network, computes the capacity? For acyclic networks, there's an implicit characterization, but not an explicit characterization; for cyclic networks, there's not even that.
  3. What is the complexity of finding the optimal (in terms of capacity) non-linear code for various network coding problems? Specific problems include determining the truth/falsehood of the following statements:
    1. Given an instance of the general network coding
      problem in a directed graph G and a real number
      r, there is a polynomial-time algorithm which
      computes a solution achieving rate r if one exists,
      and otherwise reports that this is impossible.
    2. Given an instance of the k-pairs communication
      problem in an undirected graph G and a real number
      r, it is recursively undecidable to determine
      whether the network coding rate is less than r.
  4. For multicast networks, what is the minimum number of nodes that need to do encoding to make network encoding work? That is, can we minimize the coding complexity in terms of the number of nodes doing coding (or some other reasonable metric).
  5. There must be open questions in the recent work by Koetter/Kschischang on coding for errors/erasures in random network coding. For example, they seem to give general (network-oblivious) bounds. Are there ways to improve their bounds by using knowledge of the network topology?
  6. Is there an algorithm to find the minimum cost subnetwork that guarantees delivery using network coding subject to certain classes of adversarial (or non-adversarial) link failures.
  7. A good place to look for CS-style open problems is probably also the Adler/Harvey/Jain/Kleinberg/Lehman paper On the Capacity of Information Networks, which has a nice section on open problems at the end.
Maybe I'll have more after the talk...


Anonymous said...

Your first link is broken (typo)

Michael Mitzenmacher said...

Fixed, thanks.

Anonymous said...

I might be wrong but Number 6 in the list seems to be NP-hard because, if we can determine the minimum number of nodes that need to code, it would also answer the weaker question "is network coding necessary at all in this network". To answer the latter, one probably needs to solve a min Steiner tree or Steiner tree packing problem as part of the work, and that is NP-hard.

Anonymous said...

sorry, in the post above, by "number 6" I actually mean "number 4"

Meisam Navaki Arefi HomePage said...

are this problems open problems yet?
can you give me some current open problem in network coding?