Optimal Stochastic Control for Generalized Network Flow Problems

ABSTRACT: We will describe a new online dynamic policy, called Universal Max-Weight (UMW), for throughput-optimal routing and scheduling in wireless networks with an arbitrary mix of unicast, broadcast, multicast and anycast traffic.  To the best of our knowledge, UMW is the first throughput-optimal algorithm for solving the generalized network-flow problem.  Building upon UMW, we also design an admission control, routing and scheduling policy that maximizes network utility, while simultaneously keeping the physical queues in the network stable.  

When specialized to the unicast setting, the UMW policy yields a throughput-optimal, loop-free, routing and link-scheduling policy. This is in contrast to the Back-Pressure (BP) policy which allows for packet cycling, resulting in excessive latency.  Extensive simulation results show that the proposed UMW policy incurs substantially smaller delays as compared to backpressure.  Conceptually, the UMW policy is derived by relaxing the precedence constraints associated with multi-hop routing and then solving a min-cost routing and max-weight scheduling problem on a virtual network of queues.  The proof of optimality combines ideas from stochastic Lyapunov theory with a sample path argument from adversarial queueing theory.

BIO: Eytan Modiano received his B.S. degree in Electrical Engineering and Computer Science from the University of Connecticut at Storrs in 1986 and his M.S. and PhD degrees, both in Electrical Engineering, from the University of Maryland, College Park, MD, in 1989 and 1992 respectively.  He was a Naval Research Laboratory Fellow between 1987 and 1992 and a National Research Council Post Doctoral Fellow during 1992-1993.  Between 1993 and 1999 he was with MIT Lincoln Laboratory.  Since 1999 he has been on the faculty at MIT, where he is a Professor and Associate Department Head in the Department of Aeronautics and Astronautics, and Associate Director of the Laboratory for Information and Decision Systems (LIDS).  

His research is on communication networks and protocols with emphasis on satellite, wireless, and optical networks.   He is the co-recipient of the MobiHoc 2016 best paper award, the Wiopt 2013 best paper award, and the Sigmetrics 2006 Best paper award.  He is the Editor-in-Chief for IEEE/ACM Transactions on Networking, and served as Associate Editor for IEEE Transactions on Information Theory and IEEE/ACM Transactions on Networking.  He was the Technical Program co-chair for  IEEE Wiopt 2006, IEEE Infocom 2007, ACM MobiHoc 2007, and DRCN 2015.  He is a Fellow of the IEEE and an Associate Fellow of the AIAA, and served on the IEEE Fellows committee.

Hosted by: Paul Bogdan