Introduction

Sending data through a network is a task that pervades much of our modern lives. The question of how to send data efficiently remains a central question in several fields of research, from information theory to computer networking. Despite the considerable amount of research that has focused on this question, many aspects of it remain poorly understood. Recently, a pragmatic approach to studying data transmission through a network has lead to the field of network coding [1].

An instance of a general network coding problem can involve an arbitrary graph and an arbitrary number of data streams, each with arbitrary sets of sources and sinks. Such general problems are quite difficult to analyze and remain poorly understood. Much of the existing network coding literature has focused on special classes of network coding problems, most notably multicast problems on directed acyclic graphs. A multicast problem is an instance with a single data stream, a single source node, and an arbitrary set of sink nodes. The objective is to transmit all the data available at the source to all of the sinks.

Given an instance of a multicast problem, a natural question is: How can one transmit data from the sources to the sinks at the maximum possible rate? Koetter and Medard [2] showed that multicast problems can be recast in an algebraic framework involving matrices of indeterminates. This framework leads to a natural randomized algorithm for computing solutions to multicast problem [3]. We use this framework to obtain a deterministic, polynomial time algorithm for computing solutions to multicast problems that transmit data at the maximum possible rate.

Approach

Using the framework of Koetter and Medard, we can recast the multicast network coding question as a matrix completion problem. What is a matrix completion? Suppose one is given a matrix whose entries are a mixture of numbers and distinct variables. Sometimes it is inconvenient to deal with a matrix containing variables and so one might want to plug in particular values for the variables. An assignment of values to the indeterminates that maximizes the rank of the resulting matrix is called a max-rank completion. The multicast network coding problem reduces to finding a max-rank completion for several matrices simultaneously.

We develop an algorithm for simultaneous max-rank matrix completions using the theory of mixed matrices developed by Murota [4]. We use Murota's algorithm for computing the rank of a mixed matrix to identify the variables that play an important role in the rank of the matrix. After identifying these important variables, we are able to efficiently chose values for them so that all matrices have large rank.

Results

We obtain a deterministic algorithm for finding a max-rank completion of a single matrix over in O(n^3 log n) time. This algorithm can operate over smaller fields than previous algorithms [5,6] and is faster than previous deterministic algorithms [6,7]. We also extend this algorithm so that it can find simultaneous max-rank completions for several matrices. As a consequence, we obtain a new deterministic algorithm for computing solutions to multicast network coding problems. This algorithm is somewhat slower than existing deterministic algorithms for multicast problems [8], but it is more flexible since it easily generalizes to several interesting variants of the multicast problem.

This work was presented at SODA 2005 [9].

Future Work

We would like to extend this work beyond multicast problems to more general instances of the network coding problem.

References

[1] Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li and Raymond W. Yeung. Network Information Flow. In IEEE Transactions on Information Theory, 46(4), pp. 1204-1216, 2000.

[2] Ralf Koetter and Muriel Medard. An Algebraic Approach to Network Coding. To appear in IEEE/ACM Transactions on Networking.

[3] Tracey Ho, David R. Karger, Muriel Medard and Ralf Koetter. Network Coding from a Network Flow Perspective. In Proceedings of the IEEE International Symposium on Information Theory, 2003.

[4] Kazuo Murota. Matrices and Matroids for Systems Analysis. Springer-Verlag, 2000.

[5] Laszlo Lovasz. On determinants, matchings and random algorithms. In Fundamentals of Computation Theory, FCT '79, pp. 565-574, Akademie-Verlag, Berlin, 1979.

[6] James F. Geelen. Maximum rank matrix completion. In Linear Algebra and its Applications, 288, pp. 211-217, 1999.

[7] Mark Berdan. A Matrix Rank Problem. Master's Thesis, University of Waterloo, 2003.

[8] Sidharth Jaggi, Peter Sanders, Philip A. Chou, Michelle Effros, Sebastian Egner, Kamal Jain and Ludo Tolhuizen. Polynomial Time Algorithms for Multicast Network Code Construction. Submitted to IEEE Transactions on Information Theory, July 2003.

[9] Nicholas J. A. Harvey, David R. Karger and Kazuo Murota. Deterministic Network Coding by Matrix Completion. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 05), pp. 489-498, 2005.