TY - GEN

T1 - The encoding complexity of network coding

AU - Langberg, Michael

AU - Sprintson, Alexander

AU - Bruck, Jehoshua

PY - 2005

Y1 - 2005

N2 - In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying network G. The nodes of the coding network can be broadly categorized into two groups. The first group incudes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in an acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h3k2. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h3k2. We show that the number of encoding nodes may depend both on h and k as we present acyclic instances of the multicast network coding problem in which Ω(h2k) encoding nodes are required. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. Specifically, we prove that the number of encoding nodes is bounded by (2B + 1)h3k2, where B is the minimum size of the feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of encoding nodes required to achieve the capacity for a given instance of the network coding problem is NP-hard.

AB - In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying network G. The nodes of the coding network can be broadly categorized into two groups. The first group incudes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in an acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h3k2. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h3k2. We show that the number of encoding nodes may depend both on h and k as we present acyclic instances of the multicast network coding problem in which Ω(h2k) encoding nodes are required. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. Specifically, we prove that the number of encoding nodes is bounded by (2B + 1)h3k2, where B is the minimum size of the feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of encoding nodes required to achieve the capacity for a given instance of the network coding problem is NP-hard.

UR - http://www.scopus.com/inward/record.url?scp=33749437733&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2005.1523693

DO - 10.1109/ISIT.2005.1523693

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:33749437733

SN - 0780391519

SN - 9780780391512

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1987

EP - 1991

BT - Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05

T2 - 2005 IEEE International Symposium on Information Theory, ISIT 05

Y2 - 4 September 2005 through 9 September 2005

ER -