Beyond routing: An algebraic approach to network coding

Abstract—In this paper we consider the issue of network ca-pacity. The recent work by Li and Yeung examined the network capacity of multicast networks and related capacity to cutsets. Ca-pacity is achieved by coding over a network. We present a new framework for studying networks and their capacity. Our frame-work, based on algebraic methods, is surprisingly simple and ef-fective. For networks which are restricted to using linear codes (we make precise later the meaning of linear codes, since the codes are not bit-wise linear), we find necessary and sufficient conditions for any given set of connections to be achievable over a given net-work. For multicast connections, linear codes are not a restrictive assumption, since all achievable connections can be achieved using linear codes. Moreover, coding can be used to maintain connec-tions after permanent failures such as the removal of an edge from the network. We show necessary and sufficient conditions for a set of connections to be robust to a set of permanent failures. For multicast connections, we show the rather surprising result that, if a multicast connection is achievable under different failure sce-narios, a single static code can ensure robustness of the connection under all of those failure scenarios. Index Terms—Network routing, coding. I