Optimization and Systems Theory Seminar
Friday, May 24, 2002, 11.00-12.00, Room 3721, Lindstedtsvägen 25

Luigi Iannelli
Dipartimento di Informatica e Sistemistica
Universitā degli Studi di Napoli Federico II
Napoli, Italy
E-mail: luiannel@unina.it

Pricing techniques for network congestion control

Communications networks are systems becoming more and more complex to analyse and to control. While in the past "good" design rules have been used to avoid or at least to reduce problems due to the finite bandwidth allocation to an increasing number of users, recently some researchers from different fields have begun to investigate such problems by using mathematical modeling and to solve them by some "ad hoc" tools that could be easily implemented.

A promising technique to control the congestion in communications networks is the pricing: the idea is that users pay a price in order to obtain some bandwidth. The congestion can be controlled by opportunely acting on the price and the allocated bandwidth. Controlling the congestion means to maximize an overall utility function. The decentralized constraint of the solution (networks are intrinsically decentralized systems) makes the problem very interesting since it involves different disciplines such as optimization, algorithm theory and control theory. In fact the optimization problem needs a decentralized solution and, at the same time, the algorithm that implements the solution must converge (we want a stable system).

In this talk a review of different approaches to the problem will be given. Firstly we discuss the work by Kelly et al. [1] in which the algorithm for solving the optimization problem by pricing is modeled as a continuous-time dynamical system (a couple of nonlinear differential equations) and its stability is proved by Lyapunov techniques. Then we review the work by Low and Lapsley [2], where they propose a decentralized algorithm modeled as a discrete-time dynamical system. Finally our work in di Bernardo et al. [3] will be presented as a particular case of resource allocation interpreted as a competitive model. A comparison of the different approaches and common points among the solutions will be highlighted.

[1] F.P. Kelly, A.K. Maulloo, D.K.H. Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, Journal of the Operational Research Society 49 (1998), 237-252.
[2] S.H. Low, D.E. Lapsley, Optimization flow control - I: Basic algorithm and convergence, IEEE/ACM Transactions on Networking, vol. 7, no. 6, Dec. 1999.
[3] M. di Bernardo, F. Garofalo, L. Iannelli, D. Manfredi, F. Vasca, A competitive model of user behaviour for resource allocation in congested networks, submitted to the CDC 2002.

Calendar of seminars
Last update: May 13, 2002 by Anders Forsgren, anders.forsgren@math.kth.se.