Research Abstracts - 2007

What and Why?

Network coding is a novel technique that generalizes routing. In traditional routing, each interior network node simply forwards the received data or sends out multiple copies of it. In contrast, network coding allows interior network nodes to perform arbitrary mathematical operations, e.g., summation or subtraction, to combine the data received from different links. While most network coding solutions employ coding at all possible nodes, it is often possible to achieve the network coding advantage by coding only at a subset of nodes.

If network coding is handled at the application layer, we can minimize the cost of network coding by identifying the nodes where access up to the application layer is not necessary. If network coding is integrated in the buffer management of a router, it is important to understand where and how many such special routers must be deployed to satisfy the communication demands.

Determining a minimal set of nodes where coding is required is difficult. The optimization problem to find the minimal number of required coding nodes, or even its crude approximation, is NP-hard. The structure of the problem is very little known for the application of traditional optimization methods, and no further methods have been proposed thus far beyond centralized greedy algorithms or LP formulations with an exponential number of variables/constraints.

For the multicast scenario with a single source and a set of receiver nodes, with the constraint of the target multicast throughput to achieve, we seek to find a method to yield sufficiently good solutions, i.e., at least as good as those obtained by the existing centralized algorithms, in an efficient and practicable manner.

How?

We propose an evolutionary approach, based on a genetic algorithm, with a number of novel mechanisms which greatly improve the algorithm's performance and practicability. We first develop a block-wise genotype encoding with the associated genetic operators which, by preserving the inherent modularity between the variables given by the network topology, is shown to often lead to far superior solutions than those obtained by existing algorithms [1]. Despite its stochastic nature, our proposed algorithm provides the worst-case performance bound at least as good as the existing algorithms [2].

Our proposed algorithm operates in a distributed fashion, offering a significantly lower complexity compared with the existing centralized algorithms [2]. Combined with a decentralized network coding framework, our algorithm enables a distributed network coding protocol where the resources used for coding are optimized on the fly in a setup phase. In addition, we develop a novel framework of the temporally distributed genetic algorithm, which in our experiments leads to a substantial gain in terms of the time to convergence [3], as well as the benefit of robustness operation against delays, failures, or topological changes in the network.

Ongoing research topics include extending the proposed algorithm to investigate the tradeoff between the coding and link costs for multicast network coding and applying evolutionary algorithms to the more generalized scenario of non-multicast network coding.

References:

[1] M. Kim, V. Aggarwal, U.-M. O'Reilly, and M. Médard. Genetic Representations for Evolutionary Minimization of Network Coding Resources. In Proceedings of the 4th European Workshop on the Application of Nature-Inspired Techniques to Telecommunication Networks and Other Connected Systems (EvoCOMNET 2007), Valencia, Spain, April 2007.

[2] M. Kim, M. Médard, V. Aggarwal, U.-M. O'Reilly, W. Kim, C. W. Ahn, and M. Effros. Evolutionary Approaches to Minimizing Network Coding Resources. In Proceedings of the 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, AK, May 2007.

[3] M. Kim, V. Aggarwal, U.-M. O'Reilly, and M. Médard. A Doubly Distributed Genetic Algorithm for Network Coding. In Proceedings of the ACM Genetic and Evolutionary Computation Conference (GECCO 2007), London, UK, July 2007.