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.3–11.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|