List of Personnel

Principal Investigator: Jia (Kevin) Liu

Intellectual Merits

The proposed SOHI-based stochastic network control and optimization technologies will not only advance the knowledge in the design of data communication networks but will also allow the general communications and signal processing research communities to explore a fundamental understanding of stochastic network control and optimization through a comprehensive study that include developing accurate theoretical models, investigating theoretical performance bounds and capacity limits, and the designing distributed algorithms. The proposed research aims to fill the void and contribute to an exciting second-order network control and optimization paradigm. The proposed research will support the communications, networking, and signal processing communities and the general public by facilitating the development of SOHI-based network protocols with substantially increased network performance.

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.