We consider the problem of throughput-optimal packet dissemination, in the presence of an arbitrary mix of unicast, broadcast, multicast and any cast traffic, in a wireless network. We propose an efficient online dynamic policy, called Universal Max-Weight (UMW), which is provably optimal. To the best of our knowledge, UMW is the first known throughput-optimal policy of such versatility in the context of generalized network-flow. 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. When specialized to the unicast setting, the UMW policy yields a throughput-optimal cycle-free routing and scheduling policy. This is in contrast with the well-known Back-Pressure (BP) policy which allows for packet cycling, which, in turn, causes excessive delay. Time permitting, an extension of the UMW policy to the Network Utility Maximization (NUM) problem and the optimal wireless broadcasting problem with point-to-multipoint links will also be discussed. Extensive simulation results show that the proposed policy incurs a substantially smaller delay as compared to the BP policy and its enhanced variants. The proof of throughput-optimality of the UMW policy combines ideas from the stochastic Lyapunov theory with a sample path argument from the adversarial queueing theory and may be of independent theoretical interest.
Abhishek Sinha received his Ph.D. degree from the Massachusetts Institute of Technology in 2017, where he worked in the Laboratory for Information and Decision Systems (LIDS). Prior to joining MIT, he obtained his M.E. degree in Telecommunication Engg. from the Indian Institute of Science, Bangalore and B.E. degree in Electronics and Telecommunication Engg. from Jadavpur University, Kolkata, India, in 2012 and 2010, respectively. He is currently working as a senior engineer at Qualcomm Research, San Diego, USA. He is a recipient of several awards including the Best Paper Award in ACM MobiHoc 2016, Prof. Jnansaran Chatterjee memorial gold medal and T.P. Saha Memorial gold centered silver medal from Jadavpur University, and Jagadis Bose National Science Talent Search (JBNSTS) scholarship, Kolkata, India. His areas of interests include network control, information theory, optimization, and applied probability.