Decomposition Techniques
Pablo Pavón‐Mariño · 2016
This chapter presents a framework for applying decomposition techniques to network problems, producing independent smaller subproblems coordinated by a master program. We first describe the primal and dual decomposition approaches and some problem reformulation techniques. Then, we provide three cases studies where decomposition is the theoretical support for cross-layer algorithms that make protocols at different network layers cooperate in a common goal: cross-layer congestion control and capacity allocation flows with different QoS requirements, cross-layer congestion control and backpressure routing, and cross-layer congestion control and power allocation in wireless networks. Afterwards, primal decomposition is applied to asynchronously coordinate multiple network carriers that cooperate to globally optimize the routing, for example, in the Internet, without disclosing topology and traffic sensitive information. Finally, we use a dual decomposition to design an approximation algorithm for a 𝒩𝒫-hard capacity and routing design problem to be solved offline. Illustrative numerical tests are included for all the examples.