Optimization of Computer Networks

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.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

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