A Distributed Newton's Method for Joint Multi-Hop Routing and Flow Control: Theory and Algorithm
The fast growing scale and heterogeneity of current communication networks necessitate the design of distributed cross-layer optimization algorithms. So far, the standard approach of distributed cross-layer design is based on dual decomposition and the sub-gradient algorithm, which is a first-order method that has a slow convergence rate. In this paper, the authors focus on solving a joint Multi-path Routing and Flow Control (MRFC) problem by designing a new distributed Newton's method, which is a second-order method and enjoys a quadratic rate of convergence. The major challenges in developing a distributed Newton's method lie in decentralizing the computation of the Hessian matrix and its inverse for both the primal Newton direction and dual variable updates.