Optimization of Computer Networks

Chapter 8Gradient Algorithms in Network Design

8.1 Introduction

In this chapter, we introduce the application of gradient methods to network design problems. Most of these problems, like congestion control or fast capacity allocation in wireless networks, involve a potentially large amount of loosely coupled elements that operate more or less independently. Then, there is no possibility of having a central decision unit that receives all the problem inputs, implements a sophisticated algorithm and returns the outputs to the network nodes that have to apply them. For these important cases, we pursue algorithms where each element can proceed to make decisions on its own, coordinated by a small amount of signaling information. As we will see, gradient algorithms are a strong theoretical tool that permits creating such schemes, with convergence guarantees.

We concentrate on constrained convex problems of the form:

8.1

where is a vector in , is convex in , and is an arbitrary closed convex ...