  


Survivable Network Coding
Cédric Bentz (cedric.bentzcnam.fr) 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  