[EGL13] Network coding with single arc failures

Conférence Internationale avec comité de lecture : ECCO, European Chapter on Combinatorial Optimization, May 2013, pp.2,
Résumé: Given a telecommunication network, modelled by a capacitated digraph, we are interested in comparing the behaviour and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to simple arc failure. We consider the case with a single source node and a set of terminal nodes. The problem of studying the maximum quantity of information that can be routed from the source to each terminal, using either multicast replication alone or combined with network coding, has been extensively studied. Multicast protocols allow an intermediate node to replicate its input data towards several output interfaces, and network coding refers to the ability for an intermediary node to perform coding operations on its inputs, for example linear combinations, releasing a coded information flow on its outputs. We consider the survivability extension of the throughput maximization problem where any single arc can fail. Our aim is to design models and algorithms to compute the survivable maximum throughput in multicast network and compare the results obtained with and without network coding. The coding advantage is defined as the quotient of the optimal throughput obtained using network coding over the multicast optimal throughput. When no arc can fail, it has been shown that the coding advantage can be strictly greater than one, but this holds only on some particular network topologies (the so-called "butterfly network"). However, when instances are randomly generated, the coding advantage almost always vanishes. We investigated the network's evolution when we remove a single arc to model the failure. We define an analoguous quantity to the coding advantage which takes into account single arc failures. Our first experiments seem to show that, even when considering the possibility of a single arc failure, the throughput gain offered by network coding remains relatively moderate.

Equipe: oc


@inproceedings {
title="{Network coding with single arc failures}",
author=" S. Elloumi and E. Gourdin and T. Lefebvre ",
booktitle="{ECCO, European Chapter on Combinatorial Optimization}",