DOC PREVIEW
UConn CSE 3300 - A Tutorial on Decomposition Methods

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 24, NO. 8, AUGUST 2006 1439A Tutorial on Decomposition Methods forNetwork Utility MaximizationDaniel P. Palomar, Member, IEEE, and Mung Chiang, Member, IEEETutorial PaperAbstract—A systematic understanding of the decomposabilitystructures in network utility maximization is key to both resourceallocation and functionality allocation. It helps us obtain the mostappropriate distributed algorithm for a given network resource al-location problem, and quantifies the comparison across architec-tural alternatives of modularized network design. Decompositiontheory naturally provides the mathematical language to build ananalytic foundation for the design of modularized and distributedcontrol of networks.In this tutorial paper, we first review the basics of convexity,Lagrange duality, distributed subgradient method, Jacobi andGauss–Seidel iterations, and implication of different time scalesof variable updates. Then, we introduce primal, dual, indirect,partial, and hierarchical decompositions, focusing on networkutility maximization problem formulations and the meanings ofprimal and dual decompositions in terms of network architec-tures. Finally, we present recent examples on: systematic searchfor alternative decompositions; decoupling techniques for cou-pled objective functions; and decoupling techniques for coupledconstraint sets that are not readily decomposable.Index Terms—Congestion control, cross-layer design, decompo-sition, distributed algorithm, network architecture, network con-trol by pricing, network utility maximization, optimization, powercontrol, resource allocation.I. INTRODUCTIONMANY NETWORK resource allocation problems can beformulated as a constrained maximization of some utilityfunction. There are at least three levels of understanding as towhat it means to “efficiently solve” a network utility maximiza-tion problem. The first is on theoretical properties such as globaloptimality and duality gap. It is well known that for a convexoptimization (minimizing a convex function over a convex con-straint set), a local optimum is also a global optimum and theduality gap is zero under mild conditions. The second is oncomputational properties. There are provably polynomial-timeand practically fast and scalable (but centralized) algorithms,such as interior-point methods, to solve convex optimization.Manuscript received April 20, 2006; revised May 8, 2006. This work was sup-ported in part by the National Science Foundation under Grant CCF-0448012,Grant CNS-0417607, Grant CNS-0427677, and Grant CNS-0519880.D. P. Palomar is with the Department of Electrical Engineering, PrincetonUniversity, Princeton, NJ 08544 USA (e-mail: [email protected]).M. Chiang is with the Department of Electrical Engineering, PrincetonUniversity, Princeton, NJ 08544 USA. He is also affiliated with Applied andComputational Mathematics, Princeton University, Princeton, NJ 08544 USA(e-mail: [email protected]).Digital Object Identifier 10.1109/JSAC.2006.879350The third is on decomposability structures, which may lead todistributed (and often iterative) algorithms that converge to theglobal optimum. Distributed solutions are particularly attractivein large-scale networks where a centralized solution is infea-sible, nonscalable, too costly, or too fragile. It is the third levelthat we concern ourselves with in this tutorial paper.The importance of “decomposability” to distributed solu-tions is similar to that of “convexity” to efficient computationof global optimum.1Similar to transformations that may turnan apparently nonconvex optimization into a convex one,there are alternative problem representations that may revealhidden decomposability structures, even though representingthe problem in a different way does not change the optimalsolution. For a given problem representation, there are oftenmany choices of distributed algorithms, each with possiblydifferent characteristics of the following attributes: rate androbustness of convergence, tradeoff between local computationand global communication, and quantity and symmetry ofmessage passing. Which alternative is the best depends on thespecifics of the application.A systematic understanding of the decomposability structuresin network utility maximization is key to both resource alloca-tion and functionality allocation. It obviously helps us obtain themost appropriate distributed algorithm for a given network re-source allocation problem, ranging from distributed routing andscheduling to power control and congestion control. Perhapseven more importantly, it quantifies the comparison across ar-chitectural alternatives of modularized network design. A para-mount issue in the design of network architecture is where toplace functionalities and how to connect them, an issue that isoften more critical than the detailed design of how to carry out acertain functionality. Decomposition theory naturally providesthe mathematical language to build an analytic foundation forthe design of modularized and distributed control of networks.In particular, the framework of network utility maximization(NUM) has recently been substantially extended from an ana-lytic tool of reverse-engineering transmission control protocol(TCP) congestion control to a mathematical theory of layerednetwork architectures. This framework of “Layering as Opti-mization Decomposition” (surveyed in [1], see also discussionsin [2] and another tutorial in this special issue [3]) rigorously in-tegrates the various protocol layers into a single coherent theory,1However, unlike the notion of convexity, the notion of decomposabilitydoes not have a precise definition. It is often quantified by the least amountof global communications needed among decomposed modules to solve areference problem.0733-8716/$20.00 © 2006 IEEE1440 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 24, NO. 8, AUGUST 2006by regarding them as carrying out an asynchronous distributedcomputation over the network to implicitly solve a global NUMproblem. Different layers iterate on different subsets of the de-cision variables at different time scales using local informationto achieve individual optimality. These local algorithms collec-tively achieve a global objective. This approach provides a uni-fying view and holistic methodology to study performance andarchitectural issues in protocol layering.Most of the papers in the vast, recent literature on NUM usea


View Full Document

UConn CSE 3300 - A Tutorial on Decomposition Methods

Download A Tutorial on Decomposition Methods
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Tutorial on Decomposition Methods and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Tutorial on Decomposition Methods 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?