O'Reilly logo

Optimization of Computer Networks by Pablo Pavón Mariño

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required