Login [Center] Logout Join Us Guidelines  I  CQI

 Delay-Constrained Network Information Flow and Timely Wireless Flow with General Traffic Patterns

Speaker: Minghua Chen Chinese University of Hong Kong
Time: 2018-09-14 10:30-2018-09-14 11:30
Venue: FIT 1-222


We discuss two of our recent results on delay-constrained wireline and wireless networking. In the first part of the talk, we focus on the scenario where a source node streams perishable information to a set of destination nodes over a wireline network, subject to an end-to-end 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 construct the first example showing that network coding can achieve strictly higher delay-constrained throughput than routing even for the single unicast. This is in sharp contrast to the delay-unconstrained 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. 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. In the second part of the talk, we focus on the scenario of supporting timely flows over lossy wireless links.  Recently, Hou and Kumar provided a novel framework for analyzing and designing delay-guaranteed wireless networking solutions. While inspiring, their idle-time-based analysis applies only to flows with a special traffic pattern called the frame-synchronized setting. The problem remains largely open for general traffic patterns. We show that the timely wireless flow problem is fundamentally an infinite-horizon Markov Decision Process (MDP). Then we judiciously combine different simplification methods to show for the first time that the timely capacity region can be characterized by a finite-size convex polygon. We then design scheduling policies to optimize network utility and/or support feasible timely throughput vectors for general traffic patterns. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives. 

This is a joint work with Chih-Chun Wang and Shizhen Zhao from Purdue University, Lei Deng from CUHK, and Ye Tian from Nanjing University.


Short 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.