Sending Perishable Information: Delay-Constrained Network Information Flow

Add to your list(s) Download to your calendar using vCal

• Dr. Minghua Chen, the Chinese University of Hong Kong
• Thursday 23 August 2018, 11:00-12:00
• EEE Department, Control Seminar Room, Level 11, Room 1109A.

If you have a question about this talk, please contact Kin K Leung.

Please let the host, Kin Leung, know if you are interested in discussing with the speaker.

We consider a delay-constrained communication scenario, where a source node streams perishable information to a set of destination nodes over a directed acyclic graph, subject to a delay constraint. Transmission along any edge incurs unit delay, and we require that every information bit generated at the source in the beginning of time t to be received and recovered by the destination in the beginning of t + D where D > 0 is the maximum allowed communication delay. We first study the corresponding delay-constrained unicast capacity problem. When only routing is allowed, [Ying, et al. 2011] showed that the aforementioned delay-constrained unicast routing capacity can be characterized and computed efficiently. However, the delay-constrained capacity problem changes completely when network coding is allowed. We construct the first example showing that NC can achieve strictly higher delay-constrained throughput than routing even for the single unicast setting. This is in sharp contrast to the delay-unconstrained (D \rightarrow \infty) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. We then generalize the algebraic approach by Li-Yeung-Cai and Koetter-Medard for delay-unconstrained network coding to the delay-constrained setting. The generalized approach allows us to model deadline-induced interference, which is the unique challenge in studying network coding for delay-constrained communication. Using this algebraic approach, we characterize the coding capacity for single-source unicast and multicast, as the rank difference between an information space and a deadline-induced interference space. The results in principle allow us to numerically compute the (linear) coding capacity for any given graph, serving as a benchmark for existing and future solutions on improving delay-constrained throughput. The result reveals that the landscape of delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and calls for investigation participation.

This is a joint work with Chih-Chun Wang from Purdue University and Ye Tian from Nanjing University.

Bio: Minghua Chen received his B.Eng. and M.S. degrees from the Department of Electronic Engineering at Tsinghua University in 1999 and 2001, respectively. He received his Ph.D. degree from the Department of Electrical Engineering and Computer Sciences at University of California at Berkeley in 2006. He spent one year visiting Microsoft Research Redmond as a Postdoc Researcher. He joined the Department of Information Engineering, the Chinese University of Hong Kong, in 2007, where he is now an Associate Professor. He is also currently an Adjunct Associate Professor in Tsinghua University, Institute of Interdisciplinary Information Sciences. He received the Eli Jury award from UC Berkeley in 2007 (presented to a graduate student or recent alumnus for outstanding achievement in the area of Systems, Communications, Control, or Signal Processing) and The Chinese University of Hong Kong Young Researcher Award in 2013. He also received several best paper awards, including the IEEE ICME Best Paper Award in 2009, the IEEE Transactions on Multimedia Prize Paper Award in 2009, and the ACM Multimedia Best Paper Award in 2012. His five recent co-authored papers were nominated for best papers in flagship conferences on energy systems and networked communication. He is currently the Steering Committee Chair of ACM e-Energy. He serves as an Associate Editor of IEEE /ACM Transactions on Networking in 2014 – 2018, TPC Co-Chair of ACM e-Energy in 2016, and General Chair of ACM e-Energy in 2017. He receives the ACM Recognition of Service Award in 2017 for service contribution to the research community. His recent research interests include energy systems (e.g., smart power grids and energy-efficient data centers), intelligent transportation systems, distributed optimization, multimedia networking, wireless networking, delay-constrained network coding, and characterizing the benefit of data-driven prediction in algorithm/system design.

This talk is part of the Featured talks series.

This talk is included in these lists:

• Andrea Picciau's list
• COMMSP & CP list
• COMMSP Seminar
• EEE Department, Control Seminar Room, Level 11, Room 1109A
• Featured talks
• SAP Talks

Note that ex-directory lists are not shown.