Network Coding Capacity With a Constrained Number of Coding Nodes

Abstract — We study network coding capacity under a con-straint on the total number of network nodes that can perform coding. That is, only a certain number of network nodes can produce coded outputs, whereas the remaining nodes are limited to performing routing. We prove that every non-negative, monotonically non-decreasing, eventually constant, rational-valued function on the non-negative integers is equal to the capacity as a function of the number of allowable coding nodes of some directed acyclic network. I