On the Coding-Link Cost Tradeoff in Multicast Network Coding

We investigate the issue of the tradeoff between network coding and link usage in multicast network coding. Network coding makes minimum-cost multicast, an NP-complete problem with traditional routing alone, polynomially solvable, but if we consider the network coding capability as a resource, the link cost is actually minimized at the expense of the coding cost. We show that identifying such a tradeoff is NP-hard. For this problem, we propose an evolutionary approach that generalizes our previously proposed algorithms for coding resource optimization. Based on an existing multi-objective genetic algorithm, we develop a novel selection mechanism that utilizes some specific characteristics of the problem. We then show that the algorithm can be implemented in a distributed manner and evaluate the algorithm´s performance by performing experiments on several topologies.