Network Utility Maximization has been studied for resource allocation problems in communication networks for nearly two decades. Nonetheless, a major challenge that continues to remain open is how to develop a distributed congestion control and routing algorithm that can simultaneously provide utility optimality, fast convergence speed, and low delay. To address this challenge we take a fresh perspective on this old problem and develop a new algorithm that offers the fastest known convergence speed, vanishing utility optimality gap with finite queue length, and low routing complexity.
Our key contributions in this work are: i) the design of a new joint congestion control and routing algorithm based on a type of inexact Uzawa method in the Alternating Directional Method of Multiplier; ii) a new theoretical path to prove global and linear convergence rate without requiring the full rank assumption of the constraint matrix; and iii) a clear path for implementing the proposed method in a fully distributed fashion.
Ness B. Shroff received his Ph.D. degree from Columbia University, NY in 1994 and joined Purdue university immediately thereafter as an Assistant Professor. At Purdue, he became Professor of the school of Electrical and Computer Engineering in 2003 and director of CWSA in 2004, a university-wide center on wireless systems and applications. In July 2007, he joined the ECE and CSE departments at The Ohio State University, where he holds the Ohio Eminent Scholar Chaired Professorship of Networking and Communications. From 2009-2012, he also served as a Guest Chaired professor of Wireless Communications at Tsinghua University, Beijing, China, and currently holds an honorary Guest professor at Shanghai Jiaotong University in China and visiting position at the Indian Institute of Technology, Bombay.
Dr. Shroff's research interests span the areas of communication, networking, storage, cloud, recommender, social, and cyberphysical systems. He is especially interested in fundamental problems in learning, design, control, performance, pricing, and security of these complex systems. He currently serves as editor-at-large in the IEEE/ACM Trans. on Networking, and as senior editor of the IEEE Transactions on Control of Networked Systems. He also serves on the editorial boards of the IEEE Network Magazine, and the Network Science journal. He has served on the technical and executive committees of several major conferences and workshops. For example, he was the technical program co-chair of IEEE INFOCOM'03, the premier conference in communication networking, the technical program co-chair of ACM Mobihoc 2008, the General co-chair of WICON'08, and the conference chair of IEEE CCW'99. He has served as a keynote speaker and panelist on several major conferences in these fields. Dr. Shroff was also a co-organizer of the NSF workshop on Fundamental Research in Networking in 2003, and the NSF workshop on the Future of Wireless Networks in 2009.
Dr. Shroff is a Fellow of the IEEE, and a National Science Foundation CAREER awardee. His papers have received numerous awards at top-tier venues. For example, he received the best paper award at IEEE INFOCOM 2006, IEEE INFOCOM 2008, and IEEE INFOCOM 2016, the best paper of the year in the journal of Communication and Networking (2005) and in Computer Networks (2003). He also also received runner-up awards at IEEE INFOCOM 2005 and IEEE INFOCOM 2013. In addition, his papers have received the best student paper award (from all papers whose first author is a student) at IEEE WIOPT 2013, IEEE WiOPT 2012, and IEEE IWQoS 2006. Dr. Shroff is on the list of highly cited researchers from Thomson Reuters ISI (previously ISI web of Science) in 2014 and 2015, and in Thomson Reuters Book on The World's Most Influential Scientific Minds in 2014. He received the IEEE INFOCOM achievement award for seminal contributions to scheduling and resource allocation in wireless networks, in 2014.
Inspired by the success of cloud-based machine learning, there is a strong current interest in extending these techniques to real-time inference and learning on Internet of Things (IoT) data. Since this data is created by edge devices, it is beneficial to move the information processing from distant data centers to devices close to the network edge: less data has to be communicated back to the cloud, and the latency from sensing to decisions can be decreased.
However, the development of distributed machine-learning algorithms for resource-constrained devices involves many design decisions for which we have very limited theoretical support. For example, what information needs to be shared among devices, how often, and at what accuracy? How should one best process delayed and compressed data to guarantee real-time performance with limited information exchange?
This talk describes our recent efforts in developing theory and algorithms for resource-constrained machine learning. Special attention is given to asynchronous and communication-efficient optimization algorithms for training with distributed data.
We first describe a framework for analyzing asynchronous iterations, which allows to guarantee convergence under total and partial asynchronism and to provide explicit bounds on how the amount of asynchrony impacts the convergence times. We use this framework to design a proximal incremental aggregate gradient method, and demonstrate how our theoretical tools are easy to apply and offer strong performance guarantees. We then turn our attention to gradient compression techniques for reducing the communication overhead in distributed learning. We show how several compression heuristics can be analyzed in a uniform manner and provide theoretical bounds on convergence rates and information exchange for convex optimization using compressed gradients. Simulations and real-world implementations illustrate our theoretical findings.
Mikael Johansson earned the M.Sc. and Ph.D. in Electrical Engineering from Lund University, Sweden, in 1994 and 1999, respectively. He held postdoctoral research positions at Stanford University and UC Berkeley before joining KTH in 2002, where he now serves as a full professor.
His research interests are in distributed optimization, wireless networking, and control. He has published several ISI-highly cited papers, has served on the editorial board of Automatica and the IEEE Transaction on Control of Network Systems, as well as on the program committee for conferences such as IEEE CDC, IEEE Infocom, ACM SenSys.
A purpose of studying human movement patterns is to use its understanding in simulating and predicting the performance of mobile networks where devices are being carried by people. In particular, a special attention has been given to a new mobile networking paradigm called store-carry-forward data transfer where mobile devices store and carry incoming packets by their mobility until they meet relays or the destination. While the concept of store-carry-forward data transfer is attractive, a fundamental question is whether or not actual human movements in our daily life would provide sufficient amount of such opportunistic data transfer chances to keep end-to-end packet delays within an acceptable range. In this talk, we address what have been found on human movement patterns and what the root causes of these findings. One remarkable finding is that actual human movement patterns are very different from those simulated by widely-used mobility models, exhibiting power-law characteristics. We take a closer look at how these power-law characteristics impact on mobile network performance and suggest some new engineering guidelines.
Song Chong is the KAIST ICT Endowed Chair Professor of Electrical Engineering at Korea Advanced Institute of Science and Technology (KAIST) where he has led Network Systems Laboratory since 2000. He is the Head of Computing, Networking and Security Division and the Founding Director of KAIST 5G Mobile Communications & Networking Research Center. Prior to joining KAIST, he was with AT&T Bell Laboratories, Holmdel, New Jersey, USA, as a Member of Technical Staff. His current research interests include wireless networks, mobile systems, distributed algorithms, optimization, performance evaluation and machine learning. He is on the editorial boards of IEEE/ACM Transactions on Networking, IEEE Transactions on Mobile Computing and IEEE Transactions on Wireless Communications. He is the Program Committee Co-Chair of IEEE SECON 2015 and IEEE WCNC 2020, and has served on the Program Committee of a number of leading international conferences including IEEE INFOCOM, ACM MobiCom, ACM CoNEXT, ACM MobiHoc, IEEE ICNP and ITC. He is the Steering Committee Chair of WiOpt and was the General Chair of WiOpt 2009. He received the 2013 and 2016 IEEE William R. Bennett Prize Paper Awards, given to the best original paper published in IEEE/ACM Transactions on Networking in the previous three calendar years, the 2013 IEEE SECON Best Paper Award, the 2016 KAIST Grand Prize Technology Innovation Award, and the 2016 Haedong Grand Prize Research Award, given to the Korean scholar who has made the most significant contribution to the advancement of communications research over the last 10 years. His team at KAIST has won 3 gold, 6 silver and 3 bronze prizes at the Samsung Electronics HumanTech paper competitions. He received the B.S. and M.S. degrees from Seoul National University and the Ph.D. degree from the University of Texas at Austin, all in electrical and computer engineering.
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 (d-cn) unicast capacity problem. When only routing is allowed, [Ying, et al. 2011] showed that the aforementioned d-cn unicast routing capacity can be characterized and computed efficiently. However, the d-cn capacity problem changes completely when network coding (NC) is allowed. We construct the first example showing that NC can achieve strictly higher d-cn throughput than routing even for the single unicast setting. This is in sharp contrast to the delay-unconstrained (D → ∞) 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 NC 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.
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. He is currently serving on the Steering Committee of ACM e-Energy. He serves as an Associate Editor of IEEE/ACM Transactions on Networking in 2014 - 2018. He serves as TPC Co-Chair of ACM e-Energy 2016 and General Chair of ACM e-Energy 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.