Network Alignment: Treating Network as Wireless Interference Channel

Mr. Chun MENG
University of California, Irvine
Thursday, 9 August, 2012
2:30 - 3:30 pm
Room 833, Ho Sin Hang Engineering Building The Chinese University of Hong Kong

We consider the problem of network coding across multiple unicast sessions over a directed acyclic graph. Under linear network coding, the network behaves like a linear system, and can be treated as a mimic wireless interference channel. This similarity enables us to apply interference alignment, originally proposed by Cadambe and Jafar for the wireless channel, to the network setting. We refer to this approach as network alignment. Basically, we introduce two approaches to network alignment, i.e., precoding-based network alignment (PBNA for short) and ergodic network alignment, with emphasis on PBNA. Similar to wireless channel, it guarantees that each unicast session achieves a transmission rate close to one half of its minimum cut; different from the wireless setting, its feasibility depends on network topology. We restrict ourselves to the simplest non-trivial case of three unicast sessions, each with min-cut one. In the context of PBNA, we show that the class of networks for which PBNA is feasible can be fully characterized by three constraints, each of which turns out to have a unique interpretation in terms of network topology. The enabling technique involves special properties of transfer functions, which are closely related to network topology. The interpretation also provides a polynomial-time algorithm to verify the feasibility of PBNA. 


Chun Meng got his BS and MS degree from Peking University and Beijing University of Posts and Telecommunications respectively. He is currently a Ph.D. student of Electronic Engineering and Computer Science Department at University of California, Irvine. His research interests include: network coding, interference alignment, peer-to-peer networks and distributed storage.