A Caltech Library Service

Evolutionary Approaches To Minimizing Network Coding Resources

Kim, Minkyu and Médard, Muriel and Aggarwal, Varun and O'Reilly, Una-May and Kim, Wonsik and Ahn, Chang Wook and Effros, Michelle (2007) Evolutionary Approaches To Minimizing Network Coding Resources. In: IEEE INFOCOM 2007, IEEE International Conference on Computer Communications, 26th, Anchorage, AK, 6-12 May 2007. IEEE , Piscataway, NJ, pp. 1991-1999. ISBN 1-4244-1047-9.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We wish to minimize the resources used for network coding while achieving the desired throughput in a multicast scenario. We employ evolutionary approaches, based on a genetic algorithm, that avoid the computational complexity that makes the problem NP-hard. Our experiments show great improvements over the sub-optimal solutions of prior methods. Our new algorithms improve over our previously proposed algorithm in three ways. First, whereas the previous algorithm can be applied only to acyclic networks, our new method works also with networks with cycles. Second, we enrich the set of components used in the genetic algorithm, which improves the performance. Third, we develop a novel distributed framework. Combining distributed random network coding with our distributed optimization yields a network coding protocol where the resources used for coding are optimized in the setup phase by running our evolutionary algorithm at each node of the network. We demonstrate the effectiveness of our approach by carrying out simulations on a number of different sets of network topologies.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2007 IEEE. Reprinted with permission. Current Version Published: 2007-05-29. The first author would like to thank Fang Zhao for her help on the experiments.
Subject Keywords:computational complexity; encoding; genetic algorithms; telecommunication network topology
Record Number:CaltechAUTHORS:KIMinfocomm07
Persistent URL:
Official Citation:M. Kim et al., "Evolutionary Approaches To Minimizing Network Coding Resources," IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, Barcelona, 2007, pp. 1991-1999. doi: 10.1109/INFCOM.2007.231
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11952
Deposited By: Archive Administrator
Deposited On:13 Oct 2008 22:22
Last Modified:08 Nov 2021 22:23

Repository Staff Only: item control page