Network coding with single arc failures
Sourour Elloumi, Éric Gourdin, Thibaut Lefebvre · HAL (Le Centre pour la Communication Scientifique Directe) · 2013
Given a telecommunication network, modelled by a capacitated digraph,we are interested in comparing the behaviour and usefulness of twoinformation 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 terminalnodes. The problem of studying the maximum quantity of informationthat can be routed from the source to each terminal, using eithermulticast replication alone or combined with network coding, has beenextensively studied. Multicast protocols allow an intermediatenode to replicate its input data towards several output interfaces,and network coding refers to the ability for an intermediary nodeto 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 arccan fail. Our aim is to design models and algorithms to compute thesurvivable maximum throughput in multicast network and compare theresults obtained with and without network coding. Thecoding advantage is defined as the quotient of the optimal throughputobtained using network coding over the multicast optimal throughput. When no arc can fail, it has been shown that thecoding advantage can be strictly greater than one, but this holdsonly on some particular network topologies (the so-called "butterflynetwork"). However, when instances are randomly generated,the coding advantage almost always vanishes. We investigatedthe network's evolution when we remove a single arc to model the failure.We define an analoguous quantity to the coding advantage which takes intoaccount 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 remainsrelatively moderate.