Computer Science – Networking and Internet Architecture
Scientific paper
2011-08-09
Computer Science
Networking and Internet Architecture
A short version of this work has been submitted to IEEE INFOCOM 2012
Scientific paper
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 subgradient algorithm, which is a first-order method that has a slow convergence rate. In this paper, we 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. By appropriately reformulating, rearranging, and exploiting the special problem structures, we show that it is possible to decompose such computations into source nodes and links in the network, thus eliminating the need for global information. Furthermore, we derive closed-form expressions for both the primal Newton direction and dual variable updates, thus significantly reducing the computational complexity. The most attractive feature of our proposed distributed Newton's method is that it requires almost the same scale of information exchange as in first-order methods, while achieving a quadratic rate of convergence as in centralized Newton methods. We provide extensive numerical results to demonstrate the efficacy of our proposed algorithm. Our work contributes to the advanced paradigm shift in cross-layer network design that is evolving from first-order to second-order methods.
Liu Jia
Sherali Hanif D.
No associations
LandOfFree
A Distributed Newton Approach for Joint Multi-Hop Routing and Flow Control: Theory and Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Distributed Newton Approach for Joint Multi-Hop Routing and Flow Control: Theory and Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Distributed Newton Approach for Joint Multi-Hop Routing and Flow Control: Theory and Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-70635