Jia (Kevin) Liu,

Major Activities

1. Heavy-Ball-Based Joint Congestion Control and Routing (Partial SOHI)

   In our first research thrust, we propose a heavy-ball-based joint congestion control and routing scheme that requires only simple eigen-spectrum information of the Hessian matrix to dramatically reduce queueing delay, increase convergence speed, and achieve network utility-optimality. Our approach is based on the key idea of separating the queue-lengths from the weights in the back-pressure-based approach, and then uses a weight updating scheme that utilizes only one more time-slot of memory of the weight change history. Surprisingly, we show that this simple scheme offers two control degrees of freedom to achieve utility-optimality, low-delay, and fast-convergence. More importantly, we show that our heavy-ball-based approach leads to an important and elegant three-way performance trade-off relationship, which has not been discovered so far in the literature.

2. Primal-Dual Second-Order Congestion Control and Routing (Full SOHI)

   To further increase convergence speed and reduce delay, in our second research thrust, we propose a full-SOHI-based joint congestion control and routing framework based on a primal-dual second-order approach. In our preliminary studies, we have established the utility-optimality and queue-stability of the proposed second-order framework. Our theoretical analysis confirms the fast-convergence and low-delay of the proposed algorithm. Our analytical results also suggest an elegant utility-optimality and queueing-delay trade-off relationship governed by a barrier parameter. This key insight unifies techniques and concepts that originated independently from control theory and optimization theory. We compare this trade-off relationship to those in the back-pressure-based methods and contrast their similarities and differences, further advancing our understanding of both first- and second-order methods in network optimization theory.

3. SOHI-Based Distributed Control and Optimization Algorithm Design

   In our third research thrust, we focus on decentralizing the SOHI-based network control and optimization schemes proposed in the previous two thrusts. For the heavy-ball-based approach, we show that it possesses a decomposition structure and only requires one-hop information exchange, which lead to the same distributed design as in the back-pressure-based approaches. This also implies that all distributed schemes developed for the back-pressure-based framework (e.g., adaptive CSMA) can be directly adapted into our heavy-ball-based framework to achieve fast-convergence and low-delay. For the primal-dual second-order approach, we exploit the special problem structure to develop a new decentralization scheme based on Sherman-Morrison-Woodbury (SMW) matrix inversion. Our preliminary workshows that our SMW-based approach is far more efficient than the existing approaches in the literature.

Products

1. J. Liu, A. Eryilmaz, N. B. Shroff, and E. S. Bentley, "Heavy-Ball: A New Approach for Taming Delay and Convergence in Wireless Network Optimization," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2016 (Best Paper Award, acceptance rate: 17%).


2. J. Liu, "Achieving Low-Delay and Fast-Convergence in Stochastic Network Optimization: A Nesterovian Approach," in Proc. ACM Sigmetrics, Antibes Juan-les-Pins, Jun. 2016 (acceptance rate: 13%).


3. J. Liu, N. B. Shroff, C. H. Xia, H. D. Sherali, "Joint Congestion Control and Routing Optimization: An Efficient Second-Order Distributed Approach,'' IEEE/ACM Transactions on Networking, vol. 24, no. 3, pp. 1404-1420, Jun. 2016.