Chapter 11Decomposition Techniques

11.1 Introduction

In this chapter, we focus on the application of decomposition techniques to network optimization problems. A problem decomposition is a transformation of a problem into a set of, potentially, many independent and simpler problems, coordinated by a so-called master program, such that the optimum solution of this overall scheme also solves the original problem.

A key idea is that there can be many alternative decompositions to the same network problem and that different decompositions yield to different schemes, network engineering decisions, and protocols. Section 11.2 is devoted to reviewing the most relevant baseline techniques called primal and dual decomposition, together with other mixed approaches that can exist. Then, Sections 11.311.7 include a set of case studies to illustrate the richness and strength of decomposition techniques in network design. Table 11.1 summarizes the case studies addressed.

Table 11.1 Case studies in Chapter 11

Problem type Decomposition technique Section
Cross-layer congestion control and QoS capacity alloc. Primal Section 11.3
Cross-layer congestion control and backpressure routing Dual Section 11.4
Cross-layer congestion control and power allocation Dual Section 11.5
Multidomain routing design Primal Section 11.6
Joint capacity and routing offline planning Dual Section 11.7

First, in Sections 11.311.5 we put the emphasis on problem decomposition as a theoretical support ...

Get Optimization of Computer Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.