Network-Channel Separation in Adversarial Networks

Dr. Mayank BAKSHI
Institute of Network Coding, The Chinese University of Hong Kong
Thursday, 22 March, 2012
2:30 - 3:30pm
Room 833, Ho Sin Hang Engineering Building, CUHK

A common approach for communicating in networks of noisy channels is to separate network coding and channel coding. Previous works have shown this approach to be capacity-wise optimal when the noise values on the distinct channels of the network are independent of each other. It is also known that when channels corresponding to different links are not independent, operating the channel code for each link independently may be strictly suboptimal as the dependence between the noise values on different channels may be exploited by creating an appropriate dependence between the transmitted codewords on these channels.

In this talk, we consider a network of independent point-to-point channels with the presence of an adversary that observes all transmissions, messages, and channel noise values, and can corrupt some of the transmissions by replacing a constrained subset of the received channel outputs. It is tempting to believe that separation of network coding and channel coding is suboptimal in the case of our adversarial model due to the potential for statistical dependence between the ”noise” observed on edges controlled by the adversary. We show, however, that the capacity of this network equals the adversarial capacity of another network in which each channel is replaced by a noise-free capacitated link of the same capacity. We do not assume any special structure on the topology of the network, e.g., we allow unequal link capacities and networks with cycles. We also allow arbitrary model of adversarial attack, e.g. edge-based or node-based attack. This result immediately extends previous adversarial network coding capacity results from noise-free networks to that of networks of independent point-to-point channels.


Mayank Bakshi is a postdoctoral fellow at the Institute of Network Coding, CUHK. He finished his PhD in Electrical Engineering from California Institute of Technology, USA in 2011. Prior to that, he did his Masters and Bachelors in Electrical Engineering at Indian Institute of Technology, Kanpur, India in 2005 and 2003 respectively. His research focuses on Network Information Theory, with emphasis on Network Coding and Data Compression.