A Fresh Look at an Old Problem: Network Utility Maximization—Convergence, Delay, and Complexity

Absract:  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.

Bio: 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 and director of a university wide center on wireless systems and applications (CWSA) in 2004. 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 chair of the ACM Mobihoc steering committee, 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.