Optimization Online


Survivable Network Coding

Cédric Bentz (cedric.bentz***at***cnam.fr)
Sourour Elloumi (sourour.elloumi***at***ensiie.fr)
Eric Gourdin (eric.gourdin***at***orange.com)
Thibaut Lefebvre (thibaut.lefebvre***at***orange.com)

Abstract: Given a telecommunication network, modeled by a graph with capacities, we are interested in comparing the behavior and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to single 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. We model such a failure by removing this arc from our graph thus losing a part of the information flow of our static routing. Our aim is to design models and algorithms to compute the survivable maximum throughput in multicast network and compare results obtained with and without network coding. The survivable coding advantage is defined as the quotient of the optimal throughput obtained using survivable network coding over the survivable multicast optimal throughput. We provide theoretical and experimental results on this last quantity.

Keywords: Network optimization ; Multicast ; Network Coding

Category 1: Network Optimization

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: roadef2014:29121

Download: [PDF]

Entry Submitted: 11/22/2013
Entry Accepted: 12/01/2013
Entry Last Modified: 12/02/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society