Evolutionary Minimization of Network Coding Resources

A method to identify feasible minimal network coding configurations between a source and a set of receivers without altering or modifying the established network infrastructure is proposed. The approach minimizes the resources used for multicast coding while achieving the desired throughput in the multicast scenario. Because the problem of identifying minimal configurations of a graph is known to be NP-hard, our method first identifies candidate minimal configurations and then searches for the optimal ones using a genetic algorithm (GA). Because the optimization process considers the number of coding nodes, the mean number of coding node input links and the sharing of resources by sinks, the problem is thus a multiobjective problem. Two multiobjective algorithms, MOGA and VEGA, are chosen to solve the problem because they are simple enough not to place heavy demands on source nodes when the minimal configuration is sought. The optimization process is investigated by the simulation of a range of randomly g...