On The Integral Coding Advantage In Unit Combination Networks

Abstract

Network coding is a networking paradigm which allows network nodes to combine different pieces of data at various steps in the transmission rather than simply copying and forwarding the data. Network coding has various applications, and can be used to increase throughput, routing efficiency, robustness, and security. The original benefit that was demonstrated was improving the allowable transmission rate for a multicast session, and this application has been the focus of much research. One important parameter, the coding advantage, is the ratio of throughput with network coding to that without. The multicast networks that have a non-trivial coding advantage (i.e., coding advantage greater than 1) all seem to contain a substructure called the combination network which has a source, n relay nodes, and ð€€€n k receivers in which each receiver is adjacent to a unique subset of k relay nodes. The coding advantage in combination networks has previously been determined for networks with fractional routing. In this paper, we address integral routing, which is more appropriate for networks (like optical wavelength-division-multiplexing networks) which allow only coarse-grained subdivision of the available bandwidth on any given channel. We give exact formulas for the integral coding advantage in both directed and undirected networks. For directed networks, we show that the coding advantage is k=n nð€€€k+1. For undirected networks, we show that the coding advantage is k=(kð€€€1). The latter result ts with conjectures that the integral coding advantage in any undirected network is bounded above by 2.