Strategic network coding - How much and where to code to obtain most of the benefits

We consider the problem of introducing network coding in a network in a manner that balances the benefits obtained from coding with the costs of providing coding, where such costs depend both on the number of nodes performing coding and the volume of traffic that is coded. Previous work has envisaged either the minimization of the number of nodes performing coding, which is a NP-hard problem, or the trade-off between the volume of the coded traffic and the throughput gains obtained from coding. We provide an optimization framework that considers both parameters jointly and also considers the use of duplication versus coding at nodes. Traffic is multicast in a hybrid way that combines a tree with a coded multicast graph. Our results indicate that the gains of coding, which increase markedly with graph density, can be obtained with very few nodes' performing coding, but that most, though by no means all, traffic in a multicast session should be coded for the bulk of the throughput gains to be achieved for that session. Moreover, our results indicate that an optimized hybrid approach based on trees and network coded graphs may differ considerably from a mere combination of the result of optimizing for multicast trees only or for a coded solution alone.